図面 (/)

技術 セル生産方式における適応型ロットサイズ決定のためのシステムおよび方法

出願人 ゼロックスコーポレイションパロ・アルト・リサーチ・センター・インコーポレーテッド
発明者 ロン・チョウサドヘンデュ・ライミン・ビン・ドゥ
出願日 2011年10月14日 (8年0ヶ月経過) 出願番号 2011-227451
公開日 2012年5月17日 (7年5ヶ月経過) 公開番号 2012-094136
状態 特許登録済
技術分野 総合的工場管理
主要キーワード セル作業 論理的分類 機能シーケンス ループプロセス 簡略版 最小成分 設定コスト 小型店舗
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2012年5月17日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (13)

課題

セル生産方式環境内の複数のセル全体にわたって作業負荷バランスをとるシステムおよび方法セル生産方式を提供する。

解決手段

複数のジョブは複数のセルの少なくとも一部により生産され、前記セルのそれぞれは少なくとも1つの生産装置を含むセル生産方法は、コンピュータ操作可能プロセッサを用いて複数のジョブおよびセルのリストを作成することを含み、必要以上にきめ細かくないロットセル作業負荷適合させるために、分割後統合作業を用いて前記ジョブをより小さいサイズのロットに自動分割することを含み、セル生産方式環境内の複数のセル全体にわたって作業負荷のバランスをとる。

概要

背景

従来の印刷所は、印刷ジョブ、印刷ジョブミックス、およびシステムを通る印刷ジョブの総量から機能的に独立した形で構成されている。

したがって、通常、印刷所は、すべてのプリンタを「プリンタ専用」領域内に集めて一団にする、またはすべてのインサータを「インサータ専用」領域内に集めて一団にするなどして印刷所の設備を配置するであろう。これは、プリンタの近くにあるのは他のプリンタだけであり、インサータの近くにあるのは他のインサータだけであり、単一の生産ジョブ仕上げるために密接に関与する必要のある異なる種類の機械間の分離を事実上引き起こすことを意味する。結果として、従来の印刷所の仕掛品(WIP)が非常に高額である可能性があると同時に、平均ジョブ納期が長くなる。LDP解決方法文書生産プロセス内のこの「摩擦」を認識しており、これらの効率の悪さの大部分を取り除く「セル」と呼ばれるプロセスに適した小型店舗を作るように印刷所レイアウトを再編する。

概要

セル生産方式環境内の複数のセル全体にわたって作業負荷バランスをとるシステムおよび方法セル生産方式を提供する。複数のジョブは複数のセルの少なくとも一部により生産され、前記セルのそれぞれは少なくとも1つの生産装置を含むセル生産方法は、コンピュータ操作可能プロセッサを用いて複数のジョブおよびセルのリストを作成することを含み、必要以上にきめ細かくないロットセル作業負荷適合させるために、分割後統合作業を用いて前記ジョブをより小さいサイズのロットに自動分割することを含み、セル生産方式環境内の複数のセル全体にわたって作業負荷のバランスをとる。

目的

最後に、セルにより処理される予定のバッチを割り当てるためにセル割当モジュール120を提供する

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

コンピュータ操作可能プロセッサを用いて複数のジョブおよびセルリストを作成することを含み、前記複数のジョブは前記複数のセルの少なくとも一部により生産される予定であり、前記セルのそれぞれは少なくとも1つの生産装置を含み、必要以上にきめ細かくないロットサイズを戻しながら前記ロットセル作業負荷適合させるために、分割後統合作業を用いて前記ジョブをより小さいサイズのロットに自動分割することを含む、セル生産方式環境内の複数のセル全体にわたって作業負荷バランスをとる方法。

請求項2

前記自動分割することが、最適ロットサイズを決定するための固定した式を用いずに機能する、請求項1に記載の方法。

請求項3

前記自動分割することが、前記ジョブをより小さいサイズのロットに分割することと、前記より小さいサイズのロットを一度に一つずつ割り振ることと、すべての前記より小さいサイズのロットが割り振られると、より大きなロットを形成するために、前記より小さいサイズのロットのうちのどれを他のロットと組み合わすことができるかを判断することと、組み合わせ可能と判断された前記より小さいサイズのロットをいっしょに統合することと、を含む、請求項1に記載の方法。

請求項4

先行するロットおよび新しく割り振られたロットが連続しているときには、前記新しく割り振られたロットに対する準備時間を準備時間から差し引く、請求項3に記載の方法。

請求項5

2つのロットが連続して割り振られており、かつ同じジョブに属している場合、およびその場合のみ、2つのロットは連続している、請求項4に記載の方法。

請求項6

2つの連続したロットを統合するとき、前記統合されたロットのサイズは統合中の前記2つのロットのサイズの合計であり、前記統合されたロットの開始時刻は、より早く開始するように割り振られているロットの開始時刻であり、前記統合されたロットの終了時刻は、より遅く終了するように割り振られているロットの終了時刻である、請求項5に記載の方法。

請求項7

生産環境内の複数のセル全体にわたって作業負荷のバランスをとる方法であって、前記方法は、コンピュータ操作可能プロセッサを用いて複数のジョブおよびセルのリストを作成することであって、前記複数のジョブは前記複数のセルの少なくとも一部により生産される予定であり、前記セルのそれぞれは少なくとも1つの生産装置を含む、作成することと、より少ないセル間跳躍を有する経路優先しながら前記生産環境内の実行可能な経路を列挙することと、最早完了経路アルゴリズムを用いて前記ジョブを前記セルに割り当てることであって、個別のジョブは前記個別のジョブに対する最早完了時間を提供する個別のセルに割り当てられる、割り当てることと、前記最早完了経路アルゴリズムの前記結果に基づきジョブ生産のためのジョブスケジュールを生成することと、を含む方法。

請求項8

同じワークフロー内の離れたセルおよび/または隣接するセルを接続する経路に対する不利益または恩恵をさらに含む、請求項7に記載の方法。

請求項9

ロットサイズ決定の有無にかかわらず前記セル生産方式に対する改良されたスケジューリング性能を実現する、請求項8に記載の方法。

請求項10

自動分割作業および最早完了経路作業を並行して実行することによりジョブスケジュールをさらに取得する、請求項9に記載の方法。

技術分野

0001

本発明は、セル生産方式概念を使用する改良型リーン文書生産(LDP)の新規で改善されたシステムおよび方法に関する。特に、セル生産方式環境内の複数のセル全体にわたって作業負荷バランスをとるシステムおよび方法に関する。

背景技術

0002

従来の印刷所は、印刷ジョブ、印刷ジョブミックス、およびシステムを通る印刷ジョブの総量から機能的に独立した形で構成されている。

0003

したがって、通常、印刷所は、すべてのプリンタを「プリンタ専用」領域内に集めて一団にする、またはすべてのインサータを「インサータ専用」領域内に集めて一団にするなどして印刷所の設備を配置するであろう。これは、プリンタの近くにあるのは他のプリンタだけであり、インサータの近くにあるのは他のインサータだけであり、単一の生産ジョブ仕上げるために密接に関与する必要のある異なる種類の機械間の分離を事実上引き起こすことを意味する。結果として、従来の印刷所の仕掛品(WIP)が非常に高額である可能性があると同時に、平均ジョブ納期が長くなる。LDP解決方法は文書生産プロセス内のこの「摩擦」を認識しており、これらの効率の悪さの大部分を取り除く「セル」と呼ばれるプロセスに適した小型店舗を作るように印刷所レイアウトを再編する。

発明が解決しようとする課題

0004

LDP解決方法は文書生産を「リーン」プロセスにする数々の革新を含んでいるが、この技術の中心には依然としてセル生産方式の概念があり、これは多くのやりがいのある技術的課題を作り出しており、それらの技術的課題のうち最も注目に値するものは、セルの概念の周囲に構成されている生産環境においてどのようにして効率的にジョブを割り振るかということである。新しいスケジューリングエンティティとしてのセルの出現以外にも、LDPシステム内で使用されるスケジューラに対して付加的な課題を提起する他の多くの問題がある。

0005

1つの問題は大きくテールを引くジョブサイズ分布であり、この分布は印刷ジョブ(特に、大きな印刷所で見られる印刷ジョブ)のサイズが大幅にばらつくという事実を示しており、有限分散を有するいかなる「教科書的な」分布(正規分布または指数分布など)によっても、もはやそれらの印刷ジョブ分布を十分に特徴付けることはできない。多くのスケジューリングアルゴリズムおよびシステムがまったく正反対前提としている(すなわち、大きくテールを引かない分布を取り扱うだけである)ことを考えれば、この課題に対処するには新しいスケジューラが必要である。

0006

既存のスケジューラは店舗ベルのスケジューラによりジョブをセル(または必要に応じてセルのシーケンス)に最初に割り当てる2層構造スケジューリング方法の形を取り、各セルはそれ自身のジョブキューを有しているため、ひとたびあるセルにジョブが割り当てられると、セルの中のジョブステップが終わるまで、そのジョブは恒久的にそのセルに結び付けられる。この戦略は、店舗レベルのスケジューラが各セルの作業負荷をいつでも正確に予測でき、かつ各セルの利用レベルをできるだけ高く(または均等に分布した状態に)保持するようにジョブからセルへの写像を計算できる場合にはうまくいく。しかしながら、現在のスケジューラを用いる場合、この戦略を実現するのは困難な可能性がある状況がある。1つの理由は、店舗レベルのスケジューラが、その決定を行う間に各セルの中の詳細なスケジューリング制約条件を考慮しないことである。ジョブの具体的な到着日および納入日、シーケンス依存の設定コスト、および単一セルに割り振られた類似の納入日のジョブの個数などの要因は、店舗レベルのスケジューラには扱われない。扱われないこれらすべての要因は、常にセルの作業負荷に寄与する可能性がある(および、通常、寄与する)ことは明らかである。したがって、ジョブからセルへのこのような任意の固定した写像は、いくつかのセルを過負荷にさせる一方で、他のセルはときどきジョブのない状態のままにしておく傾向がある。

0007

既存のLDPシステムを改善することが有利であろう他の領域は「バッチ分割」の領域にあり、これはLDPシステムにおいて大きなジョブを取り扱うためのスループット改善戦略である。バッチ分割は、長いジョブを「バッチ」と呼ばれる多数の、より小さいユニットに分ける。また、ときには、バッチをサブジョブと呼んでもよい。狙いは、長いジョブの一部分がシステムの中を通って流れる準備ができるとすぐにダウンストリーム待ち時間を無くすことである。

0008

既存のLDP解決方法では、ワークフローの種類(すなわち、シリアルまたはアセンブリ)に応じて2つの異なる方法でロットサイズを計算する。したがって、これらの状況でのバッチ分割の効率を改善することは有利であろう。本願は、これらおよび他の問題に対処する。

課題を解決するための手段

0009

本願は、セル生産方式概念を使用する改良型リーン文書生産(LDP)の新規で改善されたシステムおよび方法を提示する。LDPプロセスは、作業工程表を生成するために自動分割アルゴリズムおよび/または最早完了経路アルゴリズムを内蔵している。

図面の簡単な説明

0010

セルおよびセルに対応する装置を組み合わせた印刷ワークフローシステムを示すブロック図である。
図1の印刷ワークフローシステム内で使用されるソフトウェアコンポーネントを含むブロック図である。
図1の印刷ワークフローシステムを使用するサーバのブロック図である。
文書処理ジョブのサブジョブへの分割に適合するために印刷ワークフローシステムをどのようにして使用するかを示すブロック図である。
対応する一連キューを経由してジョブをセルにルーティングするための方法を示すブロック図である。
n個の作業を含むシリアルワークフローを示す図である。
6個の作業を含むアセンブリワークフローを示す図である。
ロットサイズに対するクリティカルパス変化を示すグラフを示す図である。
ロット統合するためのフローチャートである。
統合が行われると何が起こるかについてさらに詳述する図である。
最早完了スケジューリングシステムおよび方法である。
経路列挙フローチャートである。

実施例

0011

開示される実施形態は、文書工場(印刷所などの)内の文書処理ジョブの生産を調整するためのスケジューラとして働くリーン生産プロセスサーバ(LPPS)または適切なソフトウェアを実行する他の電子プロセッサの使用を想定している。サーバは文書処理ジョブを制御するためにリーン生産技術活用し、UNIXおよびWindows(「UNIX」はオープンソースグループ登録商標であり、他方、「Windows」はマイクロソフト社の登録商標である)に基づくプラットフォームを含む多くの異なるプラットフォーム上で実行できるが、これらのUNIXおよびWindowsに基づくプラットフォームに限らない。サーバはワークフロー優先順位を決定し、それに応じてワークフローを管理する。間もなく開示される実施形態は、また、他のさまざまなオペレーティングシステムを実行するプラットフォームとともに実施してもよいことを当業者は理解するであろう。さらに、サーバは専用コンピュータシステム上で実行される必要はなく、むしろプリンタ、コピー機などの他のさまざまな電子装置上で実行されてもよい。文書処理ジョブのワークフロー優先順位は、さまざまなジョブ処理ユニットを観察することにより決定できる。

0012

本明細書に開示される少なくとも1つの説明に役立つ実施形態は、文書工場が自立したセルに区分されていると見なす。各セルは、少なくとも1種類の文書処理ジョブを完了するのに十分な文書工場内の資源論理的分類である。したがって、第1のセルはプリンタおよびバインダを含んでいてもよく、他方、第2のセルはコピー機および照合機を含んでいてもよい。LPPSは、このようなセルの中で文書処理ジョブを効果的に分配するのに関与する。

0013

図1を参照すると、印刷所(すなわち、文書工場)内の印刷ワークフローシステム100を示している。ソフトウェアを作動させるように構成された電子プロセッサなどの少なくとも1つのプロセッサを含む印刷ワークフローシステム100は、多数のセル102〜106を制御するとともに、通信リンク108を介してセル102〜106へ情報を送信し、セル102〜106から情報を受信する。セル102〜106は、所与生産物タイプの文書処理ジョブを完了するのを支援するための少なくとも1つの装置を含んでいる。例えば、印刷装置110が600dpi白黒プリンタである可能性があり、他方、印刷装置112が1200dpiカラープリンタである可能性がある。もちろん、これらはあくまで例に過ぎず、他の多くの処理装置がセルの中にあってもよい。

0014

図2を参照すると、印刷ワークフローシステム100で使用してもよいモジュールの種類のうちのいくつかを示している。これらのモジュールは、選択された文書処理ジョブに対するワークフローを決定するワークフロー写像モジュール114を含んでいる。特に、ワークフローモジュールは、文書処理ジョブを完了するのに必要な運用テップと、その中でこれらの運用ステップを実行すべきシーケンスと、を特定する。文書処理ジョブをバッチ(本明細書ではロットとも呼ばれる)またはサブジョブに分割するために、およびバッチをセルに送って完了するためにジョブ分解モジュール116を含んでいる。セル内の装置により処理される予定の少なくとも1つのバッチを受け取るために所与のセルに生産物セルコントローラ(PCC)118を提供してもよい。最後に、セルにより処理される予定のバッチを割り当てるためにセル割当モジュール120を提供する。

0015

一般に、印刷ジョブを受け取り、ワークフロー写像モジュール114により印刷ジョブに対するワークフローを開発する。ジョブ分解モジュール116はジョブをバッチに分割してもよく、その後、セル割当モジュール120により完了するために、バッチまたはジョブをセル(例えば、102〜106)に割り当てる。割り当てられたセルの生産物セルコントローラ118にバッチを送ってもよく、この生産物セルコントローラ118で各バッチをさらに細分してもよい。

0016

図3を参照すると、印刷ワークフローシステム100での使用に適したサーバ300(すなわち、LPPS)の一実施例を示している。サーバ300は、プロセッサ302、記憶装置304、通信リンク306、および入力モジュール308を含んでいる。通信リンク306を介してさまざまな装置から入力を受信するために入力モジュール308を使用する。入力モジュール308はサーバ300を代表して文書処理ジョブを受信する。プロセッサ302はサーバ300上でプログラム命令を実行して、文書処理ジョブを管理する。サーバ300は記憶装置304内に命令を保存する。例えば、モジュール114、116、および118(図2の)のデータ、ならびに他のデータを記憶装置304内に保存してもよい。サーバ300上で、またはセルに特有の別のサーバ上でモジュール120のデータを実行してもよい。

0017

図4を参照すると、生産システムのセル(例えば、図1の104および106など)と情報をやりとりする印刷ワークフローシステム(図1の印刷ワークフローシステム100のような)のサーバ300を含む配置を示している。セルに対する生産物セルコントローラ118は、セル104、106によりさらに処理される予定の、サーバ300からのバッチ400、402を受け取る。サーバ300は、異なる生産物タイプを生産するために印刷所内の各セルの最大生産量および機能を記憶装置304内に保存している。例えば、ネットワーク内のセル104は3つの異なるタイプの文書を生産してもよく、セル106は2つのタイプの文書を生産してもよい。2つの異なるセルが類似の文書タイプ、または同じ文書タイプでさえも生産できることが十分起こり得ることに言及する(すなわち、文書タイプは文書を完全に仕上げるための処理ステップのシーケンスにより一意的に特徴付けられる)。サーバ300はこの情報を保存して、どのセルが文書ジョブを処理する機能を有しているかを判断する。また、各セルの最大生産量を保存して、セルが生産できる特定の生産物タイプの生産量を判断する。

0018

上述のように、さまざまな自立したセルに送って処理するためにジョブ分解モジュール116は文書処理ジョブをバッチに分割してもよい。ネットワーク内のセルが自立している限りは、セルはジョブを完全に処理できる。図4に示す実施例では、文書処理ジョブはバッチ400および402に分割され、それぞれセル104および106に送られる。生産物セルコントローラ118および118’は、バッチ400、402をそれぞれ装置集合404A〜404Cおよび装置集合406A〜406Cに送って処理する。

0019

図5を参照すると、本実施形態とともに使用するためのジョブルーティングシステム500の簡略版を示している。ひとそろいの保存されたジョブ504と通信するルータ502が、セル割当モジュール120(図2)およびLPPS300(図3)に関連するジョブ管理機能の少なくとも一部を含んでいてもよい。ルータは一連の印刷処理関連キュー506(506−1、506−2、...506−nとして指定される)とさらに通信し、これらのキューはセル102〜106にそれぞれ動作可能に関連している。

0020

上述のように、この領域での特定のスループット改善戦略はロットサイズ決定通称バッチ分割)であり、このロットサイズ決定は、大きいジョブを「ロット」と呼ばれる(またある時には、本明細書でバッチまたはサブジョブと呼ばれる)多数の、より小さいユニットに分ける。狙いは、長いジョブの一部分がさらに処理する準備ができるとすぐにダウンストリーム待ち時間を無くすことである。既存のLDP解決方法では、ワークフローの種類(シリアルまたはアセンブリ)に応じて2つの異なる方法でロットサイズを計算する。

0021

ワークフローの概念に注意して、図6は、対応するステーション(ステーション1〜ステーションn)で連続して実行されなければならないn個の作業(すなわち、作業1〜作業n)を含むシリアルワークフロー600を示しており、各ステーションはジョブまたはジョブの一部分を完了するのに必要な上述の資源(例えば、プリンタ、バインダ、コピー機、照合機など)を含んでいる。各作業は、1生産品目あたりriタイムユニットの処理時間を有している。処理の間に1つのロットから次のロットへ切り換えるためには、フロー600は1生産品目あたりsiユニットの準備時間を必要とする。

0022

ジョブの全体のサイズはN項目と定義され、ロットサイズはb項目である。次の式で全体のメイクスパンを与える。



Tがロットサイズbの関数であるため、最適ロットサイズはTを最小にするロットサイズである。この最小値は次のように見つけることができる。
1.Nを正確に分割する整数bの集合を計算する。
2.この集合内のすべてのbに対するT(b)を評価し、これらの値をベクトルに保存する。
3.このベクトルの最小成分を選択する。この成分に対応するbが最適ロットサイズである。

0023

アセンブリワークフローでは、最適ロットサイズの計算はさらに複雑である。図7は、6個の作業(作業1〜作業6)を含むアセンブリワークフロー700により処理されているジョブの実施例を示しており、これらの6個の作業の一部は並行して同時に実行され(例えば、作業1および2など)、これらの6個の作業の一部は連続的に実行される(例えば、作業5および6など)。6個の作業を示しているが、この6個という個数はあくまで例として提供したに過ぎず、本概念は他の個数のステーションおよび作業を有するワークフローにも同様に適用できることを理解すべきである。

0024

シリアルケースとは異なり、全メイクスパンが、ロットサイズごとに変化する可能性があるクリティカルパス(すなわち、最大生産時間を有する経路)に依存するため、アセンブリワークフローに対する最適ロットサイズを計算するための閉形式の式がない。このことを理解するために、準備時間s1、s2、およびユニット処理時間r1、r2をそれぞれ有する2つのステーションがあると仮定する。サイズbを有するロットに対するそれらの処理時間は、それぞれs1+br1およびs2+br2である。図8の線図800に示すように、b<=b*のとき、s1+br1<=s2+br2であり、これはステーション2がクリティカルパス上にあることを意味しており、b>b*のとき、s1+br1>s2+br2であり、これはステーション2ではなく、ステーション1がクリティカルパス上にあることを意味している。

0025

現在のLDPスケジューラは、クリティカルパスを動的に決定するために下記の戦略を使用している。仮に、ti=si+bri、i∈{1,2,..,m}∈がステーションi上のサイズbを有するロットの全処理時間を示すとする。さらに、

であるとし、ここで、Piはステーションiの上流のステーションの集合である。そのとき、

は、ステーションiを通じてロットを処理するための経過時間である。したがって、ライン内の最後のステーションを通じてロット(またはバッチ)を処理する経過時間である

は、クリティカルパスにより決定されるサイズbを有するロット(またはバッチ)の全納期である。さらに、各ステーションは、これまでのところ最大処理時間を与える上流のブランチの経過を追い、この上流のブランチがクリティカルパスを決定する。その後、bのあらゆる可能な値に対して、既存のLDPスケジューラは、上述のプロセスを通して特定されるクリティカルパス内のステーションを用いて上述の式(1)により決定されるT(b)を計算する。そのとき、最適ロットサイズはT(b)を最小にするロットサイズである。T(b)はロットサイズbの変化がクリティカルパスの変化を引き起こすときに再評価される必要があるだけであるため、bが変化するたびにT(b)を計算する必要はないことに留意されたい。

0026

上述のように、それを用いて既存のLDPスケジューラ内の最適ロットサイズを決定するためのプロセスは、特に、最も一般的なタイプであるアセンブリワークフローに対して、かなり複雑である。しかしながら、さらに重要なことは、実際の最適ロットサイズは上述のプロセスで計算される値から大きく異なる可能性があることである。これは、第1のロットを処理するまでは、これまでに使用されたすべてのステーションは使用されていない状態でなければならない、という暗黙の前提に起因している。残念ながら、これは、店舗がほとんど使用されていないときに提示されるほんのわずかなジョブに対して正しいだけである。忙しい店舗では、後で提示されたジョブは、まだ依然として処理中の先に提示されたジョブと競争しなければならない。最悪の場合、すべての機械が既に完全に占有されているときには、ロットサイズ決定がメイクスパンの低減に少しもつながらない可能性がある。それどころか、複数の準備時間が同じジョブに属する異なるロットに対して必要となるため、ロットサイズ決定がメイクスパンを増加させる可能性がある。

0027

現在のロットサイズ決定式の他の制限は、単一ジョブステップを処理するのに複数の機械が利用できるケースを取り扱うのに、処理速度の寄せ集めに依存していることである。LDPでは、所望のスループットを実現するために複数のプリンタおよび/またはインサータを備えた単一のセルを有することが一般的である。これは、各プロセス段階iは単一の準備時間siおよび処理速度riだけを有することができる、という式(1)の前提に違反している。この問題を解決するために、既存のLDPスケジューラは、同じ機能(または機能シーケンス)を実行できる同じセル内のすべての機械の処理速度を合計する。これは複数の並列機械を有するセルに対して同じ式が引き続き適用できることを確保するが、また同様に、これは、複数の、より遅い機械は多くの状況で単一の高速度の機械と同じではないという事実を無視している。

0028

任意のこのような静的に計算されたロットサイズは現実の印刷所ほど動的なスケジューリング環境には適合できないため、上述の制限がない、後述のシステムおよび方法は、「最適」ロットサイズを決定するのに、いかなる固定した式も使用しない。その代わり、図9のフローチャート900に示すように、本システムおよび方法は大きなジョブを多数の小ロット(バッチまたはサブジョブ)に分割し、一度に一つずつ、それらを割り振る。すべてのロットが割り振られると、統合段階を使用して、より大きなロットを形成するために、どのロットを他のロットと組み合わすことができるかを判断する。したがって、最終的なスケジュールは、あまりに多くの小さいロットを有することに苦しむことはない。実際に、ジョブを単一のロットよりも多いロットにさらに分割すべきではない(まれな)事象では、本システムおよび方法は最適ロットサイズを見つけるであろうということを示すことができる。図9は上記を達成するためのステップ(さらに詳述されるであろう)を規定する高レベルフロー900である。したがって、プロセスフロー900は下記の通りである。
1.ジョブを十分多くのロット(またはシステムで事前に定義されてもよい最大許容ロット数)に分割する(902)。
2.すべてのロットに、まだ割り振られていないとの印を付ける(904)。
3.まだ割り振られていないロット数>0の間はループ入り(906)、ループプロセスは下記の通りである。
a.次のロットを割り振る(908)。
b.新しい/現在のロットに、割り振り済みとの印を付ける(910)。
c.同じ機械上の先行するロットおよび新しい(または次の)ロットが同じジョブに属しており、かつ現在のロットと連続して割り振られているかどうかを判断する(「いいえ」のとき、プロセスはステップ906に戻る)。「はい」のとき、プロセスは続く(912)。
d.新しく割り振られたロットの準備時間を差し引く(914)。
4.ループが終わると(すなわち、ステップ906が「いいえ」であるとき)、同じ機械上に割り振られた連続したロットを統合する(916)。

0029

少なくとも1つの実施形態では、「十分大きな」の使用は、自然に課された制約により決定されたロットサイズを意味すると理解されることが分かる。また、2つのロットが連続して割り振られており、かつ同じジョブに属している場合、およびその場合のみ、2つのロットは連続している。

0030

図10のフローチャート1000で示すように、2つの連続したロットを統合するとき、統合されたロットを定義するために下記のステップを実行する。
1.統合されたロットのサイズは統合中の2つのロットのサイズの合計である(1002)。
2.統合されたロットの開始時刻は、より早く開始するように割り振られているロットの開始時刻である(1004)。
3.統合されたロットの終了時刻は、より遅く終了するように割り振られているロットの終了時刻である(1006)。

0031

もちろん、統合されたロットは、他の統合済みロット、またはまだ統合されていないロットと、さらに統合できる。すべてのi∈{1,2,..,m}に対して、機械i上に割り振られている連続したロットを見つけることができない場合、およびその場合のみ、スケジュールを極限まで統合する。このアルゴリズムは極限まで統合されたスケジュールだけを戻すため、このことは、極限まで統合されたスケジュールはジョブを完了するために必要な最少のロットしか含んでいないことから、アルゴリズムに必要以上に多くのロットを作らせない。例えば、1台を除き、すべての機械が稼働中の場合には、アルゴリズムは、稼働していない同じ機械上にすべてのロットを連続して割り振ることを統合段階において発見するため、それらのロットのすべてを単一ロットに統合することで、複数の準備の代わりに1回の準備だけが必要になる。このようなケースは特に一般的というわけではないが、ときどき起こる。単一ロットスケジュールは極限まで統合されたスケジュールのうちの、すべてのロットを統合できる単なる特別なケースであるため、新しいアルゴリズムはその特別なケースを難なく取り扱う。記載のアルゴリズムは、セルの変化する作業負荷に合わせてロットサイズを自動的に変化させるため、自動分割アルゴリズムと呼んでもよい。

0032

複数のセルを関与させる必要があるワークフローを有するジョブに対しては、上述の自動分割アルゴリズムは、セル境界を超えたスケジューリングができるスケジューラ内で使用される。したがって、本明細書ではLDPにおいてセル間のスケジューリングを行うための計算効率の良い方法についても同様に説明している。また、しかしながら、本教示はセル生産方式の他の実施形態にも適用できることを理解すべきである。

0033

効率的な複数セルスケジューリングの際立った態様は、ジョブを仕上げるために協働しなければならない異なるセルを接続するための「最短経路」を特定することである。このような経路を見つけることは困難だがやりがいがある可能性があり、その理由は、関与するセルの個数を最少にすることだけが目的ではなく、これらのセルで費やされる時間を最小にすることの方がさらに重要であるためである。この目的を達成するために、本開示は、最も効率的な経路を特定するための最早完了スケジューリング戦略1100(図11)を開発した。アルゴリズムは下記のように働く。
1.最初に、アルゴリズムは最少回数セル間跳躍を有するすべての経路を列挙する(1102)。
2.その後、この集合内の各経路に対して、アルゴリズムは、経路により特定されるそれらのセルを使用することだけにより最良スケジュールを見つけようと試みる(1104)。
3.その後、アルゴリズムは経路を選択し、ジョブを最も早く終える対応するスケジュールを選択する(1106)。

0034

上記について詳述すると、経路列挙アルゴリズムについて最初に説明するが、このアルゴリズムは最少回数のセル間跳躍を要求するジョブを完了するための経路の集合を戻すため、本明細書ではこのアルゴリズムを最少跳躍経路列挙アルゴリズムと呼ぶ。この議論では、「steps」はジョブのステップの総数であり、「h」はジョブが要求するセル間跳躍回数である。hはワークフローに含まれるセル数から1を引いた数値以上であるが、しかし、単一セルを2回以上訪れ、これらの訪問の間に、途中でさらに他のセルを訪れる(例えば、最初にセルAを訪れ、その後セルBを訪れ、その後再びセルAを訪れる)場合、hは、さらに大きくなる可能性があることに注目すること。訪問されたセルの集合の基数ではなく、セル間跳躍回数を使用する理由は、セル境界を超えた仕掛品(WIP)転送のようなセル間ワークフロー連携コストを、より正確に明らかにするためである。図11計数器ステップ1102および1104に対する最少跳躍経路列挙アルゴリズム1200のステップを図12に示している。この配置では、システムは下記のように働くであろう。
1.hmax(セル間跳躍の仮想上限)を0に設定する(1202)。
2.hmax<Stepsの間はループに入る(1206)。
a.Rmin−hopが、ジョブを完了できるhmax以下のセル間跳躍を有するすべての経路の集合であるとする(1206)。
b.Rmin−hop<>Φのとき、ループを出る(1208)。
c.Rmin−hop<>Φではないとき、hmax=hmax+1(1210)。
3.Rmin−hop<>Φのとき、最少跳躍経路の集合としてRmin−hopを戻す(1212)。
4.Rmin−hop<>Φではないとき、エラー報告する(すなわち、現在のジョブは店舗内には無い1つ以上の機能を要求する)(1214)。

0035

上述の列挙アルゴリズム1200は、反復拡大戦略を使用して経路列挙基準を徐々に緩和する。セル間跳躍の最大回数はSteps(ジョブステップの総数)から1を引いた数値に上方から境界されているため、ジョブが要求するすべての機能が店舗内のどこか(必ずしも単一セル内とは限らない)に存在しているとき、アルゴリズムは少なくとも1つの経路を見つけるように設計されている。一方、アルゴリズムは、より少ないセル間跳躍を有する経路を最初に試してみるため、少なくとも1つの実行可能な経路が存在しているとき、アルゴリズムはまた、Rmin−hop、すなわち、最少跳躍経路の集合を見つけるように設計されている。

0036

最少跳躍経路の集合を見つけると、セル間スケジューリングアルゴリズムは、それぞれのr∈Rmin−hopに対する可能な最良のスケジュールを見つけようと試みて、ジョブを最も早く完了する経路r*を選択する(すなわち、図11のステップ1106)。したがって、このアルゴリズムを最早完了経路スケジューリングと呼んでもよい。

0037

既存の、式に基づく静的なアルゴリズムと比較して、この実施形態の自動分割アルゴリズムは完全に動的であり、リアルタイムセル作業負荷適応できる。特に、自動分割アルゴリズムは、
1.静的な式を使用せず、
2.シリアルワークフローとアセンブリワークフローの両方に適用でき(すなわち、異なる種類のワークフローに対して別々に取り扱う必要がなく)、これによりコードの簡略化をもたらし、
3.最初は使用されていない機械についての前提を要求せず、
4.不十分なスケジューリング品質につながる可能性がある擬似的な処理速度を生成する速度の寄せ集め(個々の機械の処理速度の合計として)の必要性がない。

0038

実験では、店舗A(中型店)、店舗B(中型店)、および店舗C(大型店)を含む多くの異なる大きさの印刷所について、記載の自動分割アルゴリズムの性能を評価した。店舗A(中型店)では、納期遅れジョブ数(637から560に減少)、平均遅れ(773から738に減少)、および平均納期(934から899に短縮)を含むすべての主要なスケジューリング評価指標から見て、自動分割は静的方法よりも良いことが分かった。店舗B(中型店)では、自動分割は納期遅れのジョブ数を1から0に、平均遅れを−137から−150に(小さいほど良い)、および平均納期を20.46から7.62に減少させた。大型店舗である店舗C(大型店)では、両方の方法ともに、納期遅れのないスケジュールを見つけることができたが、自動分割は平均納期を1.79から0.84に、および平均処理時間を1.07から0.61に短縮する。

0039

ここでの際立った革新は動的ロットサイズ決定であるため、異なる作業負荷と、納入日などのさまざまなスケジューリング制約条件との下でロットサイズが変化するかどうかを観察することにより、静的ロットサイズ決定との違いを見つけることができる。静的方法では、このような変化はロットサイズにいかなる実質的変化も引き起こさないであろうが、印刷所の生産性はさまざまな条件の下で変動するであろう。しかしながら、自動分割を用いる動的ロットサイズ決定では、これらのすべての要因がロットサイズに影響を与える可能性があり、通常、影響を与えることになり、このことはスケジューラのソースコードを必要とせずに観察できる。

0040

最早完了経路スケジューリングでは、類似の方法を使用して、動的径路選択アルゴリズムが使用されているかどうかを判断でき、その理由は、最早完了経路スケジューリングでは、どの経路が「最短なのか」が、すべてのセルの作業負荷と、他のスケジューリング制約条件とに依存するためであるが、他方、先行する静的方法は、セルがどんなに忙しくても、常に同じ経路を選択する。この場合も先と同様に、このスケジューリング挙動を見つけるのにソースコードにアクセスする必要はない。

0041

記載の経路列挙アルゴリズムの変形は、すべての最少跳躍経路を見つけた後も、実行可能な経路を列挙し続けることであり、その理由は、ジョブを完了するための全体の処理時間から見ると、最少のセル間跳躍回数を有する経路が必ずしも「最短」であるとは限らないためである。さらに、経路列挙アルゴリズムは、本明細書に示すように、セルの近所については考慮しない(例えば、セルAはセルBとは近いが、セルCとは離れている)。経路列挙アルゴリズムの他の実施形態では、特定の経路が同じワークフロー内の2つの離れた(または隣接する)セルを接続する場合には、その経路に対して不利益(または恩恵)を付加する。

0042

本願は、少量の計算の複雑性を有するが、それにもかかわらず、他の品質評価指標の中で納期遅れのジョブ数と、平均納期の両方を減少させるのに有効な、既存のLDPスケジューリングアルゴリズムの多くの改善について説明している。使用されるスケジューリングフレームワークの一般性を考えると、本概念は、特に、自動車製造、供給チェーン管理を含む他の分野に適用できる。

0043

また、本願は、上述の方法を利用して、バッチ分割を備えたセル生産方式のための改良されたスケジューリング性能を実現するシステムを含んでいる。また、システムは、最早完了経路アルゴリズムおよび/または動的ロット/バッチ(改良されたシステム性能のための自動分割スケジューリングアルゴリズム)の並列実現を含んでいてもよい。並列であることにより、最適なスケジュールを戻すために自動分割作業および最早完了経路作業は2つのコアプロセッサにより並列処理してもよいことが分かる。

0044

上述の、および他の、特徴および機能、またはそれらの代替の変形が、他の多くの異なるシステムまたは応用において組み合わされてもよいことを理解されたい。これらの特徴および機能、またはそれらの代替の、現在のところ予見できない、または思いがけないさまざまな代替手段、変更、変形、または改良が、その後に当業者により行われる可能性があるが、これらの代替手段、変更、変形、または改良もまた下記クレームにより含まれるものとする。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

該当するデータがありません

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

  • 日本電産株式会社の「 生産ラインシステム、及びベースユニット」が 公開されました。( 2019/09/19)

    【課題】生産ラインを容易に変更することができる生産ラインシステムを提供する。【解決手段】生産ラインシステム1は、複数のベースユニット2を備える。複数のベースユニット2は、作業対象のワークWを搬送する方... 詳細

  • ロンザ リミテッドの「 カスタマイズ可能施設」が 公開されました。( 2019/09/12)

    【課題・解決手段】少なくとも1つの医薬製品を製作するキャンパスは、少なくとも1つの医薬製品を製造するようにそれぞれ構成される1つ若しくは複数のカスタマイズ可能施設と、培地/緩衝プラントと、ユーティリテ... 詳細

  • フラッシーリミテッドの「 通信システム及び通信方法」が 公開されました。( 2019/09/12)

    【課題・解決手段】本発明は、通信システム及び通信方法を提供する。本通信システムは、アイテムに関連する送信器から信号を受信する受信器と、前記受信した信号のパラメータに基づいて、関連するアイテムに対するユ... 詳細

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

該当するデータがありません

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ