(57)【要約】【課題】  システムの機能のいくらかをより高い優先度のジョブに再割当てすることをも可能とする。【解決手段】  作業ユニットを処理するための複数の選択的機能を伴う、複数のモジュールを有する再構成可能な生産システムにおける、コンフィギュレーション特有の、ジョブの再優先度付けのためのコンピュータ制御されたシステムであって、システム・コントローラ、一つ以上の作業ユニットを持つジョブの生産における、選択されたモジュール機能のプラニング利用のための、少なくとも一つのプラニング・ファンクションであって、モジュール機能が、モジュール機能の相対コストを含む、プラニングファンクション、および、一つ以上の作業ユニットを持つジョブの生産における選択されたモジュール機能の利用をスケジューリングするための、少なくとも一つのスケジューリング・ファンクション、を備えるシステム。【選択図】          図１
2004326788.tif 000002
【特許請求の範囲】
【請求項１】
作業ユニットを処理するための複数の選択的機能(alternative capabilities)を伴う、複数のモジュールを有する再構成可能な生産システムにおける、コンフィギュレーション特有の(configuration-specific)、ジョブの再優先度付け(reprioritization)のためのコンピュータ制御されたシステムであって、
システム・コントローラ、
一つ以上の作業ユニット（work unit）を持つジョブの生産における、選択されたモジュール機能の利用をプラニングするための、少なくとも一つのプラニング・ファンクション（planning function）であって、当該モジュール機能が、当該モジュール機能の相対コストを含む、プラニングファンクション、および、
一つ以上の作業ユニットを持つ前記ジョブの生産における前記選択されたモジュール機能の利用をスケジューリングするための、少なくとも一つのスケジューリング・ファンクション、
を備えるシステム。
【請求項２】
請求項１に記載の、再構成可能な生産システムにおける、コンフィギュレーション特有の、ジョブの再優先度付けのためのシステムであって、
選択されたモジュール機能の利用をプラニングするための前記ファンクションが、
計画される(planned)べき一つ以上の作業ユニットを選択するための手段、および、
計画されるべき前記一つ以上の作業ユニットと対応付けられた機能を決定するための手段、
を備えるシステム。
【請求項３】
請求項１に記載の、再構成可能な生産システムにおける、コンフィギュレーション特有の、ジョブの再優先度付けのためのシステムであって、前記プラニング・ファンクションが、
再構成可能な生産システムで利用可能なモジュール機能を決定するための少なくとも一つのファンクション、
選択変数(selection variables)によって修正されたタイミング制約(constraints)を通知する(posting)ための、少なくとも一つのファンクション、
選択変数および共通モジュールについての制約を通知するための、少なくとも一つのファンクション、
リアル・タイムの制約およびオーダ制約(order constraints)を通知するための、少なくとも一つのファンクション、
全ての選択された機能に対するコスト値(cost value)を通知するための、少なくとも一つのファンクション、および、
同じジョブの後続の作業ユニットを、考慮の対象(consideration)から一時的に除去するための、少なくとも一つのファンクション、
を更に備えるシステム。
【請求項４】
作業ユニットを処理するための複数の選択的機能(alternative capabilities)を伴う複数のモジュールを有する、再構成可能な生産システムにおける、コンフィギュレーション特有の、ジョブの再優先度付けのための方法であって、
少なくとも一つのジョブの生産において計画されるべき一つ以上の作業ユニットを選択するステップであって、当該ジョブが、一つ以上の作業ユニットおよび一つ以上の優先度(priority)を含むステップ、
前記作業ユニットを実行するために必要な機能を決定(determining)するステップ、
前記作業ユニットを実行するために、十分なモジュール機能が利用可能か否かを判断するステップ、
計画されるべき一つ以上の作業ユニットを選択すること、前記作業ユニットを実行するために必要な機能を決定すること、および、前記作業ユニットを実行するために十分なモジュール機能が利用可能か否かを判断すること、を、全ての作業ユニットが計画され尽くされるまで反復するステップ、および、
或るジョブに対して、当該ジョブを実行するための十分なモジュール機能が利用不可能な、当該ジョブの、いかなる作業ユニットをも考慮の対象から一時的に除去するステップ、
を含む方法。
【請求項５】
請求項４に記載の、複数のモジュールを有する、再構成可能なコンピュータ制御された生産システムにおける、コンフィギュレーション特有の、ジョブの再優先度付けのための方法であって、
スケジューリングされるべき機能(capabilities)を選択し、
同じジョブを伴う計画された機能のための出口リソース(exit resources)を予約(reserving)し、そして、
計画された機能のタイミングおよび選択変数(selection variables)を解決する(solving)、
ステップを更に含む方法。
【請求項６】
請求項４に記載の、複数のモジュールを有する、再構成可能なコンピュータ制御された生産システムにおける、コンフィギュレーション特有の、ジョブの再優先度付けのための方法であって、
選択変数によって修正されたタイミング制約を通知し(posting)、
選択変数および共通モジュールについての制約を通知し、
実時間の制約およびオーダ制約(order constraints)を通知し、そして、
全ての選択された機能に対するコスト値を通知する、
ステップを更に含む方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は全体として、自動化された製造システムの制御および管理に関連し、より詳細には、異なった優先度を持つジョブの中でのリソースの再優先度付け(reprioritization)および再割当てへの、モデルベースのプラニングおよびスケジューリングの適用に関連する。
【背景技術】
【０００２】
生産システムのための、現在のシステム制御ソフトウェアは、実行されているジョブが、他のジョブが実行され得る前に、完全に完了していることを要求する。これは、ジョブがしばしば長い大量生産システム、特に新しいジョブが、現在生産されているジョブに較べてより高い優先度を持つような場合の大量生産システムにとって、不満足なことである。そして、長い低優先度のジョブの終了を待つ替わりに、それらの新しいジョブを並行して生産すること、または、低優先度のジョブの替わりにそれらの新しいジョブを生産することが望まれる。従来の、イン・ライン(in-line)・システムのために、または、再構成可能なシステムのために提案されたシステムのために、実行されたスケジューリングおよびシステム制御は、新しいジョブが、実行されているジョブと衝突(conflict)しない場合に限り、新しいジョブの追加を可能とするだけである。例えば、印刷システムにおいて、もしシステムが、十分なキャパシティーを持ち、必要なリソースが利用可能ならば、ジョブ・キューの先頭において、新しいジョブが挿入され得、これによって、残りの未終了のジョブを遅らせる。しかし、現在のジョブは、全ての仕上げ器(finishers)を予約してしまっているかもしれず、この場合には、新しいジョブは、少なくとも現在のジョブの一つが完了するまで、スケジューリングされ得ず、実行され得ない。そのような場合には、もし高優先度のジョブがジョブ・キューに入るならば、長くて低優先度のジョブを、中断または更に中止することが望ましいであろう。再構成可能な生産システム、特に並行機能(parallel capabilities)を持つシステムは、操作者が、システムの機能のいくらかを、より高い優先度のジョブに再割当てすることをも可能とすべきである。これによって、生産性および顧客の満足度を増加させることになろう。
【０００３】
この目的を達成するために、システム制御ソフトウェアが、プラナ(planner)およびスケジューラ(scheduler)からの助力によって、システムの種々のモジュールおよび、しばしば、広い機能(extensive capabilities)を利用して、処理中のジョブを再ルーティング(reroute)し、作業を新しいより高い優先度のジョブに移し、或いは、ジョブの一部分をインテリジェントにパージして、それを後に再スタートすることを可能とすることが有用となろう。
【発明の開示】
【課題を解決するための手段】
【０００４】
簡潔に述べると、そして、本発明の一つの特徴に従って、コンピュータ制御されたシステムは、膨大な選択肢の機能を伴ったいくつかのモジュールを持つ、自動化された製造システムに対する、ジョブの、構成に特有の再優先度付けを提供する。コンピュータ制御されたシステムは、一つ上の作業ユニット(work unit)を有する、ジョブの生産における、選択されたモジュール機能(capabilities)の利用のプラニングおよびスケジューリングのための、少なくとも一つのシステム・コントローラを含む。モジュール機能には、モジュール機能の相対的コスト(relative cost)が含まれる。
【０００５】
本発明の他の特徴によって、作業ユニットを処理するための複数の選択的(alternative)機能を伴う、複数のモジュールを有する再構成可能な生産システムにおける、構成に特有の(configuration-specific)ジョブの再優先度付けための方法が開示される。本方法は、生産のためにプラニングされるべき、少なくとも一つの作業ユニット、および、少なくとも一つの優先度、を有するジョブから、少なくとも一つの作業ユニットを選択することを含む。作業ユニットを実行するために必要な機能(capabilities)、および、作業ユニットを実行するための、それら(必要な機能)の利用可能性、が決定される。本工程は、全ての作業ユニットがプラニングされ終えるまで反復される。ジョブのそれらの作業ユニット(これらに対して十分なモジュール機能が利用不可能なもの)は、考慮の対象から一時的に除去される。
【発明を実施するための最良の形態】
【０００６】
ここに開示されるものは、モデル・ベースのプラニングおよびスケジューリングを適用して、システム・コントローラ内で、異なった優先度の、到着したジョブの中でのリソースの再優先度付け、および、再割当てを行う方法およびシステムであり、コントローラが全ての利用可能なシステム機能の連続する使用を提供し、各機能が実行された後の必要に応じて、システム状態および更新されたモジュール・モデルをレポートする、方法およびシステムである。これを実現するために、本方法は、新しいジョブを、挿入し、プラニングし、スケジューリングする一方、同時に、未終了のジョブ要素を、それらの制約(例えば、共有されたリソース)を考慮しつつ、正確に完了させる。未終了のジョブが中断され得ないような(後に再スタートできないような）場合には、未終了のジョブを中止するか、或いは、挿入されたジョブを遅らせるか、が更に判断される。制約ベースのフォーマットでのシステム状態とすれば、本方法は、システムの機能およびオリジナルのジョブ制約(constraints)を用いて、新しい(一つあるいはそれ以上の)挿入されたジョブとともに、未終了のジョブ要素および現在のジョブの残りを生産(produce)するために、新しいプランおよびスケジュールを生成することを試みる。スケジューリングのための現存するアプローチとは対照的に、ここに記載される本システムは、現在のシステム状態からのプラニングおよびスケジューリング、新しいジョブの挿入、および、必要に応じての作業の中止および再試行(redoing)、によって可能とされる。
【０００７】
本システムおよび方法は、製造、印刷、または組立、のような、マルチ・ステップ生産工程(multi-step production process)のために用いられる制御ソフトウェアに適用され、柔軟なルーティング、最適な生産性、および、最適な負荷バランシング、を提供するための、パス(paths)に亘った複雑なオペレーションの取扱いを提供する。以下の説明において、本発明の完全な理解を提供するために、膨大な特定の詳細が記載される。しかし当業者にとって、そのような特定の詳細無しに、本発明が実施できることは明白であろう。他の場合には、本発明が不必要に不明瞭化されることを避けるために、特定の実施の詳細は詳しく示されていない。
【０００８】
図面の説明に進む。ここでの目的は、本システムおよび方法の実施例の説明目的であり、それを限定するためではない。図１は、本システムの実施例に適合する、異なったジョブ優先度に対する、プラニングおよびスケジューリングのためのコントローラを示す。システム100において、システム・コントローラ110は、何らかの既知のタイプのジョブ入力リソースから生産されるべき作業(work)ユニットの記述(descriptions)を受け取る。これらの記述は、所望の出力製品(products)、または、達成されるべき他のゴールの記述に対応する。それらは、製品の属性(または特性)、これらの属性に対する値または範囲または一般的制約、および、可能性あるものとして、生産のタイミング(例えば締め切り)についての制約、を指定し得るが、一般的に、如何にして製品が生産されるかが指定されることは無い。作業ユニットの記述は一般的に、複数のジョブにグループ化され、インクリメンタルに受け取られる。プラニングおよびスケジューリングを含むシステム制御、および実行は、インクリメンタリに発生するので、これらのオペレーションは全て、同時に発生する。それ故、プランを生成し、次にそれを修正無しに実行することは、常に可能ではなく、または望ましくないかもしれない。システム・コントローラ110は、システム内の各モジュール120から、パス130に沿って、機能モデルおよびパフォーマンス・ログ情報をも受信する。機能モデルは、いかにして、モジュールが異同し、作業ユニットを移動させるかの記述であり、作業ユニットの属性およびタイミングについての情報通常を伴う。モデルは、生産システムが起動されたときに一回だけ、システム・コントローラに送られ得る。或いは、モデルは、定期的に、または、変化が起こったときに更新され得る。モジュール内でのそのような変化は(そして、それによるモデルでの変化は)、例えば、モジュールの再構成、タイミング値の変化、および、リソースの利用不可能性(及び、いくらかの機能)、であり得る。機能モデルには、例えば、タイミング制約(例えば、機能の実行の期間、リソースが占有される期間、または、リソースの予約)、特性(feature)の制約(例えば、処理されている作業ユニットのサイズについての制限、パーツ(parts)のオリエンテーション(orientation)の変更や、２つのパーツを一緒に付加すること、のような作業ユニットの変換)、およびコマンド(例えば、時間および、可能なものとしての(possibly)他の情報を伴う、機能に対応するオペレーションの名称またはＩＤ(identification))、が含まれる。タイミングおよび特性(feature)の制約は、いつ、そして、如何にして、機能が作業ユニットに適用され得るか、を記述する。コマンドは、対応するオペレーションを起動するためにモジュールに送られるコマンドである。
【０００９】
モジュール120は、例えば、フィーダー・モジュール、マーク・エンジン・モジュール、仕上げ器(finisher)モジュール、または、輸送モジュール、のような印刷エンジンの機器モジュールのような、多くの異なったタイプの生産システムを包含し(encompass)得る。或いは、モジュール120は、バイオテクノロジーのスクリーニング・システムの分析モジュール(これは、準備モジュール、加熱モジュール、混合モジュール、分析モジュール、または、輸送ロボット、を備え得る)を含み得る。製造ラインモジュールは、機械工作(machining)モジュール、組立(assembling)モジュール、試験モジュール、輸送ロボット、または梱包モジュール、を含み得る。梱包ラインは、ボトル充填モジュール、または、ラベリング・モジュールを含み得る。所望の作業ユニットのためのスケジュールをサーチする時に、システム・コントローラ110は、全てのあり得るシステム機能を考慮する。
【００１０】
一つあるいはそれ以上のジョブの、所望の作業ユニットの、いくつかを、或いは全てを、プラニングおよびスケジューリングすることは、選択された、および、スケジューリングされた、機能の組を結果としてもたらす。これらが利用可能となるので、システム・コントローラ110は、スケジューリングされた機能に対応する命令コマンドを、パス140に亘るモジュール120に送る。モジュールの各々は次に、指定されたジョブを完了させるための、そのタスク・シーケンスを実行する。処理されている作業ユニットのパスを示す、パス150に見られるように、作業(work)は、次のモジュールに連続して移動する前に、特定のモジュール120内で、反復して繰り返し得るか、または、第３のモジュールに渡す前に、複数のモジュールの中を反復して繰り返し得る。ここでの目的のために、３つのモジュール120だけが示されるが、ジョブ要求の複雑さにより、システムは膨大なモジュールを含むことが理解出来るであろう。モジュールは、再構成可能なシステム内に、種々の構成を持ち得る。更に、何時の時点においても、モジュールおよびシステムの状態について作業がスケジューリングされるに際しての、オペレータ・フィードバックのための機能も存在する。
【００１１】
システム制御ソフトウェアは、ジョブ優先度を識別し、機能を選択し、これらの機能のタイミング変数(timing variables)を決定し、スケジューリングされた機能を実行することによって、ジョブをプラニングし、スケジューリングする。図２は、システム・コントローラによる、モニタリング、レポーティングのファンクション、および、予測的(predictive)およびプリエンプティブなプラニングへのアプローチ、および、異なったジョブ優先度付けのためのスケジューリング、を説明する。この図面において、本方法のステップは、受信され、工程内の各後続のステップに提供された、データに関して説明される。この工程内のステップ220、230および240の各々は、次々と(一つの後に次の一つが)、または、同時に実行され得る。いずれの場合でも、各ステップは、データ225、235を消費する(consumes)か、または、スケジュールと、前のステップまたはシステム内の他のアクションによって提供された実行の間の不一致(discrepancies)を消費し、後続のステップまたは他のシステム・オペレーションのために、データ235、245、そして究極的に270、を生成する。このデータの消費および生産は一般的にインクリメンタリに為される。つまり、ステップは、一つのデータ・アイテムを、次から次に処理するが、実時間ソフトウェアの当業者にとって明白なように、バッチによっても為され得る 。最初は、作業ユニット225の記述は、或いは、実行されるべきジョブが、コントローラに提供される。そのような作業ユニットおよびジョブ記述は一般的に、インクリメンタリ(incrementally)に提供される。マルチプルの(multiple)ジョブのための作業ユニットの記述は、シリーズに(series)、または、パラレルに(parallel)提出され得る。新しいジョブは、前のジョブが完了する前に、或いは、完全に提出される前にさえ、提出され(submitted)得る。
【００１２】
コントローラは、現在のシステムの状態および、スケジュールと実行260(例えば、どのオペレーションがモジュールによって現在実行されているか、そして、それが、以前にプラニングし、スケジューリングしたかもしれない、何らかの機能)の間の不一致(discrepancies)についての情報とともに、利用可能なシステム・モジュールのモデルをも持つ。提出された作業ユニット記述の組から、どれが次に、プラニングされ、スケジューリングされるべきかが決定される。この選択は一般的に、作業ユニットとジョブが提出されたのと同じオーダー(order)で為されるが、例えば、以前に未知であった新しいジョブの優先度を考慮して、以前のジョブが完全にスケジューリングされる前に、新しいジョブのプラニングを開始することもまた可能である。選択された作業ユニット225は次に、ステップ220に渡され、各モジュールのための機能モデルを考慮して、選択された作業ユニットのための機能をプラニングし、スケジューリングする。このステップは、前のステップで選択された各作業ユニットおよび診断ユニットについて反復され、スケジューリングされた機能235の組が生成される。230において、故障が識別され、260からのスケジュールおよび実行の不一致(discrepancy)データに基づいて、復旧モデルが識別される。具体的に、何らかの(重要な)、スケジュールと実行との間の不一致は、潜在的な故障を示す。(故障は、介入(intervention)を必要とする現在の故障か、未だ回避し得る差し迫った故障かのいずれかで有り得る。)
【００１３】
従って、ソフトウェアは、レポートされた実行が、依然として、ジョブおよびモデルによって与えられた制約を満足させるか否かを識別しなければならない。例えば、もし作業ユニットが、モジュールに、予定されたより長く滞在する(stays)ならば、それは、他のスケジューリングされた作業ユニットとオーバーラップ(即ち衝突(collide))するであろうか？もし、作業ユニットが遅延されるならば、それは、依然として、他の作業ユニットとの関係で順位の(precedence)制約を満足させるであろうか？もし作業ユニット変換(例えば、オリエンテーション(orientation)での変化)が、実行されていなかったなら、それはクリティカルか？この理由付けは、モジュール・レポートに基づいて、スケジュールを修正し、次にそれを、制約との関係でチェックすることによって為され得る。もし制約が、相変わらず満足されるならば、更なるアクションは不必要である。(これは、モジュールが、ローカルな問題を解決することについての自律性(autonomy)を持ち、それによって更にロバストネスを改善することをも可能とする。)
【００１４】
モジュール・レポートによって、スケジュールを更新すること、または、更新を試みることによって、実行の差異(execution differences)のために、生産が不整合になってきているか否かを検知するために、正しいスケジュールを生成するためのスケジューラのファシリティ(例えば、制約解決器(constraint solver))が使用され得る。例えば、もし、作業ユニットについてのオペレーションが遅延しているならば、同じジョブの作業ユニットは、不適切に生成され得る(そして、順位制約(precedence constraints)は違反されることになる)、または、作業ユニットは、衝突(collide)し得る(そして、それによってリソース制約に違反することになる)。そのような実行差(execution differences)を比較し、そのスケジュールに統合(integrating)することによって、スケジューラは、即座に、そのような不整合(inconsistencies)を検知出来る。
【００１５】
もし、制約がもはや満足されないならば、詳細なシステム状態は、システムが故障から復旧出来るか否か、および、どのように復旧できるか、を決定するための基盤を提供する。例えば、故障(failure)の一般的な結果は、ジョブのその部分が、それらの順位制約(precedence constraints)に違反する(即ち、いくつかの作業ユニットの遅延によって、所望のものとは異なったオーダー(order)となること)、または、(それらを生成するためにスケジューリングされたモジュールが、オフラインとなってしまったために)全く生産されないということである。システム制御ソフトウェアが、恐らく、これらのジョブを再プラニング、または再ルーティングすることによって復旧出来るという意味で、その状態は、それらの部分(parts)を識別するために役立つ。ダイナミックなシステム・スケジュールに取りこむために、プラニングおよびスケジューリング・ステップ220に、システム故障識別および故障復旧モードが提供される。
【００１６】
スケジューリングされた機能235は次に、ステップ240に提供される。このステップにおいて、コントローラは、スケジューリングされた機能に対応するコマンド245を、個々のモジュールに送る。このステップは、各スケジューリングされた機能に対して反復される。モジュールはインクリメンタリに、それらのモデルで定義されたのと同じレベルの詳細度で、機能の実行をレポートする。例えば、輸送モジュール(transport module)は、入力時間、出力時間、入力作業ユニット(および、その属性)、出力作業ユニット(および、その属性)、および、それらの間のいくつかの制約(例えば、時間変数の間の時間制約、作業ユニット変数の間の属性変換、等)、を伴って「移動」機能を定義し得る。そして、もしシステム制御ソフトウェアが、その機能を選択し、スケジュールする(時間と属性変数のための値を決定する)ならば、コマンドが、モジュールに送られて、所定の時間に、この機能を実行し、モデル変数(時間、属性、リソース)のために、モジュールは、実際の値(または、予測された値への差異)を、折り返しレポートする。これらのモジュール・レポート255は、250でロギングされ、詳細化された、そのスケジュールの実行のログを構築するために統合される。ログは、明示的に、或いは黙示的に、システムのビヘイビヤのヒストリを含み得る。例えば、タイミング値に対する単一の値の替わりに、ログは、発生の頻度および見込みを含む、値の分散(distribution)を維持し得る。この情報は次に、システム状態260を更新し、システム・レポート270を生成するために利用される。
【００１７】
図３に進む。ここで、フローチャートは、異なったジョブ優先度の存在下での、予測可能(predictive)で、プリエンプティブな、プラニングを実現するために利用された例示のオペレーションを示す。この模範的実施例において、プラナ／スケジューラは、新しいジョブをも含み、それらと関連する種々の優先度を考慮する。種々の優先度は、例えば、ジョブの優先度のみでなく、ジョブの再製、及び／又は、遅延のコストをも考慮するコスト・モデルで表現され得る。高優先度のジョブを挿入することは単に、低優先度のジョブを、遅延すること、または、中止すること、を意味しない。システムの現在の状態および機能に依存して、恐らく、現在のジョブに対するいくらかの僅かな再プラニングを伴って、単純に、現在のジョブと並行して新しいジョブが生産され得る。他の場合には、現在のジョブは、殆ど(そのまま)遂行されて、より高い優先度のジョブが、短期間だけ遅延させられ得ることが、現在のジョブを再生成することに較べて、より、コスト的に有利であり得る。もし、より高い優先度のジョブを遅延するコストが、他のジョブを中止して再生成するコストより高いだけならば、そのオプションが採用されるべきである。スケジューラは、ジョブよりも木目細かに(at a finger granularity)さえ、つまり、個々の作業ユニットで、それらの決定を為し得る。制約ベースのスケジューラを用いると、何を遅延させるか、棚上げする(shelve)(例えば、バッファ・トレイに)か、または、パージさせるて再生成させるか、の判断は、システムの機能、システムの状態、システムについてのジョブの要求、および、ユーザの所望の目的ファンクション(objective function)(例えば、最も高い優先度のジョブの完了時間を最小化する)、についての詳細の情報に起因して為され得る。このアプローチは更に、ユーザが、決断に対する人間の介入を利用すること(例えば、アクションの経過(course of action)にコミットする(commit)前に、スケジューラの情報に基づいて、オペレータに、いくつかのオプションを提示することによって)を可能とする。
【００１８】
310においてコントローラは、新しい、処理中の(in-process)、または、完了したジョブを考慮して、プラニングされるべき作業ユニットを選択する。コントローラは次に、320において、作業ユニットを生産、修復、またはパージし、そして再生産するために必要な機能を判断する。作業ユニットのためのスケジュールを修復するための機能には、作業ユニットの再ルーティング、または、前に決定された(previously determined)ルートの作業ユニットの遅延が含まれる。復旧の機能、パージングおよび再生成の機能は、全て、割り当てられたコストである。スケジュールのトータルのコストは、全ての選択された機能のコストの合計である。従って、殆ど完了したジョブを終了することは、それをパージングして再生成するよりかなり少ないコストしか掛からないはずである一方、より高い優先度のジョブを、短期間だけ遅延することのインクリメンタルなコストは、小さいはずである。より高い優先度のジョブを遅延するコストが、他のジョブを中止して再生成するコストより高い場合に、明白に、その逆は真であり、よって、より低い優先度のジョブを中止することが選択されることとなろう。現在のプランを維持し、単に、新しいジョブを追加することは、もしそれがオプションであるならば、それが可能なときは何時でも、最も低いコスト(遅延無しで、実行するための余計なオペレーション無し)をもたらすはずである。
【００１９】
新しいジョブが受け取られるにつれて、プラナは絶えず、スケジューリングに関する、以前の判断に再訪問(revisit)して質問する。例えば、非常に高い優先度のジョブが提出された(submitted)場合にのみ、現在のジョブはパージされ得る。もし全てのジョブが同じ優先度を持つ、または、優先度が少ししか違わない、または、全ての可能なシナリオを考慮すること無しに決定が為され得る (即ち、現在のジョブが殆ど完了している) ならば、新しいジョブが到着した時に、現在のジョブをパージして再生成するオプションは、考慮する必要さえ無い。従って、320は代替的に、プラナが明白に、全ての可能な機能を詳細に比較することを避けることを援助する、(直近に述べたことのような)ジョブについての一定のヒューリスティックを知悉する判断要素を含み得る。
【００２０】
コントローラは次に、330において、どんな機能が利用可能かを判断する。もしジョブを完了するために十分な機能が利用不可能ならば、同じジョブの後続の作業ユニットが、340において、慮の対象から一時的に除去され、コントローラは310に戻って、プラニングされるべき作業ユニットを選択する。もし、十分な機能が利用可能ならば、選択変数(selection variables)によって修正されたタイミング制約が、350において通知(posted)される。コントローラは、360において、選択変数および共通モジュール(common modules)についての制約をも通知する。実時間制約およびオーダ制約(order constraints)は、370において通知され、全ての選択された機能に対するコスト値は、380で通知される。コントローラは次に、310に戻り、プラニングされるべき他の作業ユニットを選択する。
【００２１】
ここに提示される、異なったジョブ優先度に対する、プラニングおよびスケジューリングのための擬似コードの一つの例は、全体の(分離(disjunctive))問題を、制約記憶(constraint store)に提示し(posts)、同時にプラニングしてスケジューリングするために、ブーレアン変数(Boolean variables)を使用して、機能の中から選択する。当業者が理解するであろうように、例えば、サーチ手順が、必要に応じて代替的機能の選択および通知(posting)に亘って後戻り(backtracking)しつつ、異なった代替的機能が次から次へと(one after another)通知(posted)され得る、というような他のアプローチが利用され得る。そのような代替的アプローチは、本出願の明細書および特許請求の範囲の視野によって完全に考慮される。
【００２２】
initialize schedule S and constraint store C; 
repeat forever do 
given the current schedule S, determine set Up of in-process work units u and set Uf of 
all other (future, including new) work units in S; 
for all work units u in Up do 
determine set Su,c of "create" capabilities S such that u = output work unit of s 
and exit port of s is in Pu 
and s does not use off-line resources; 
determine the exit port pu of the module currently containing u; 
determine set Su,p of "purge" capabilities s such that the entry port of s = pu 
and exit port of s is a purge module 
and s does not use off-line resources; 
determine set Su,r of "repair" capabilities s such that u = output work unit of s 
and exit port of s is in Pu 
and s does not use off-line resources; 
let Su = union of Su,c, Su,p, and Su,r;
add Su to S; 
post to C: timing constraints of si in Su,c, with selection variables bi added; 
post to C: timing constraints of si,p in Su,p, with selection variables bi,p, added ;
post to C: timing constraints of si,r, in Su,r, with selection variables bi, added; 
post to C : bc = sum (si in Su,c) bi; 
post to C : bp = sum (si in Su,p) bi,p; 
post to C : br = sum (si in Su,r) bi,r, 
post to C : b = bp; 
post to C : 1 = bp + br, 
post to C : real-time constraints for si in Su ; 
for all si in Su,c and Su,r, post to C: exit port of si = exit port of job of u; end for 
post to C : to = sum (si in Su,c and Su,r) bi times output time of si;
post to C : order constraint for to, 
end if 
end for 
for all work units u in Uf do 
(determine capabilities and post constraints as in regular scheduling;) 
end for 
for all schedules i in Su,r for work units in Up of jobs j do 
post objective ci that combines the priority pj of job j and the quality 
(e.g., end time) ei of schedule i (e.g., ci = bi pj ei with schedule selection variable bi); 
end for 
for all schedule pairs i in Su,p and Su,c, for work units in Up of jobs j do 
post objective ci that combines the priority pj of job j and the quality 
(e.g., end time) ei of schedule i (e.g., ci = bi pj ei with schedule selection variable bi); 
end for 
for all schedules i for work units in Uf of jobs j do 
post objective ci that combines the priority pj of job j and the quality 
(e.g., end time) ei of schedule i (e.g., ci = bi pj ei with schedule selection variable bi); 
end for 
for all jobs j and all possibly capabilities si,j in Su,c and Su,r scheduled above do
ri,j = resource for exit port of si,j; 
if all work units in j are being scheduled then 
post to C: reserve ri,j for the duration of job j; 
else 
post to C: reserve ri,j for open-ended future for job j; 
end if 
end for 
solve for the undetermined time variables and selection variables in C, 
preferring schedules (and capabilities) i that optimize objectives ci, 
send commands to modules based on selected capabilities (bi = 1) in S and 
determined time variables in C; 
clean up completed parts of S and C; 
end repeat
【００２３】
上記目的(objectives)は、個々の作業ユニットからの目的(例えば、全ての個々の作業ユニットに対する、優先度およびスケジュール長の合計)、および、それまでにプラニングされ、スケジューリングされた全体のジョブのための目的(例えば、ジョブ内の、先週の作業ユニットに対する優先度およびスケジュール長)を含む、異なったやり方によって計算され得ることが理解されるべきである。
【００２４】
図４を参照する。ここで、フローチャートは、コントローラのスケジューリング・ファンクションを示す。最初は、ステップ410において、コントローラは、スケジューリングされるべきそれらの機能(これらは、プラニング・ステップによって提供された機能の全てまたはサブセットであり得る)を選択する。コントローラは次に、ステップ420において、同じジョブ内のプラニングされた機能に対する出口リソースをリザーブする。同じジョブの全ての作業ユニットは、同じ最終出口ポートに配送されるように制約されるので、その同じ最終出口ポート(例えば、印刷エンジンの仕上げ器(finisher)のスタックに対応するもの)に接続されたリソースは、ジョブが終了するまでは、他のジョブによって使用され得ない。ステップ430において、コントローラは次に、プラニングされた機能の、タイミングおよび選択変数を解決する。これは、いくつかの制約解決または制約された最適化技術(これらは、当業者に既知である)を用いて実現され得る。
【００２５】
本発明は、特定の実施例を参照して説明され、記述されてきた一方、更なる修正および改善が当業者に想起されるであろう。例えば、このアプローチの種々の単純化と事前編集(pre-compilations)が可能であり得る。例えば単に、ジョブ中の、完了した、および、未完了の作業ユニットの数に基づいて、ヒューリスティックの近似が、現在のジョブを中止するか、終了させるか否かを決定し得る。更に、ここで用いられる「コード」、またはここで用いられる「プログラム」は、コンピュータまたはタスクを遂行するために実行可能な装置によって使用され得る、何らかの、複数のバイナリの値、または、何らかの実行可能な、解釈された(interpreted)または、コンパイルされた、コードである。このコードまたはプログラムは、幾つかの既知のコンピュータ言語の何らかの一つで書き込まれ得る。ここで用いられる「コンピュータ」は、データを記憶し、処理し、ルーティングし、操作し、または、これらに類似するオペレーションを実行する、何らかの装置を意味し得る。
【図面の簡単な説明】
【００２６】
【図１】本発明(subject invention)の一つの実施例による、ジョブ優先度に対する、予測可能でプリエンプティブなプラニングおよびスケジューリングのためのシステムを説明する。
【図２】本発明の一つの実施例による、異なったジョブ優先度のための、予測可能なプラニングおよびスケジューリングを実現するための、オペレーションのフローを詳述するフロー図を提供する。
【図３】本発明の一つの実施例による、異なったジョブ優先度のための、予測可能(predictive)で、プリエンプティブなプラニングを実現するための、オペレーションのオーダリング(ordering)を詳説するフロー・チャートを提供する。
【図４】本発明の一つの実施例による、異なったジョブ優先度のための、予測可能でプリエンプティブなプラニングが存在する状態でのスケジューリングを実現するための、オペレーションのオーダリングを詳説するフロー・チャートを提供する。
【図１】
2004326788.tif 000003
【図２】
2004326788.tif 000004
【図３】
2004326788.tif 000005
【図４】
2004326788.tif 000006