(57)【要約】【課題】本発明は、受信されたジョブを実行するためのジョブ計画を迅速に検索する、及び、予め定められた時間の範囲において最適で高品質な計画の更なる探索を実行する、ことを容易にするシステム及び方法を提供することを目的とする。【解決手段】計画が作成されるジョブを受信し、実行可能である第１の計画を特定するために、予め計算された計画のセットを解析し、第１の計画を初期値の計画としてスケジューリングし、第２の計画を特定するために、最長計画作成期間を設定し、使用可能であれば、第２の計画を特定し、第２の計画が第１の計画より良好かどうかを判断する。【選択図】図１
2008299846.tif 000002
【特許請求の範囲】
【請求項１】
機器環境においてジョブの計画を作成する方法であって、
計画が作成されるジョブを受信し、
実行可能である第１の計画を特定するために、予め計算された計画のセットを解析し、
前記第１の計画を初期値の計画としてスケジューリングし、
第２の計画を特定するために、最長計画作成期間を設定し、
使用可能であれば、前記第２の計画を特定し、
前記第２の計画が前記第１の計画より良好かどうかを判断する、
ことを含む方法。
【請求項２】
前記第２の計画が使用可能でない場合、又は、前記第２の計画が前記第１の計画よりも良好でない場合、前記第１の計画を実行する、
ことを更に含む請求項１に記載の方法。
【請求項３】
システムモデルを受信し、
前記システムモデルに関連付けられた少なくとも一つの制約条件を緩和し、
一つ以上の前記予め計算された計画を生成するために、緩和された前記システムモデルを解決する、
ことを更に含む請求項１に記載の方法。
【請求項４】
前記少なくとも一つの制約条件が、予め定められた最長ジョブ実行時間、前記ジョブを完了するために用いられる予め定められた最大コンポーネント数、スケジューリングされるオブジェクトの分散性、異なるオブジェクトの異なる実施の間の相互関係、又はジョブ実行中に生じるイベントの順序付け、の内の少なくとも一つに関連付けられる、
ことを含む請求項３に記載の方法。
【請求項５】
機器のジョブのためのオフライン及びオンラインジョブの計画作成を実行するためのシステムであって、
与えられたジョブの計画がジョブリクエストに適合していることを確実とするために適用される、少なくとも一つの制約条件を記憶する制約ライブラリと、
予め定められた計画作成期間の第１の期間中に、予め計算された計画データベースを解析し、前記ジョブリクエストを満たす第１の計画を特定し、前記予め定められた計画作成期間の第２の期間中に、第２の計画を特定しようと試みる、計画手段と、
どちらの計画が、前記ジョブリクエストを実行するためにより良好であるかを判断するために、前記第１の計画と前記第２の計画とを比較する最適化手段と、
を備えるシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書中に記載されている様々な特徴を有する本発明は、一般に、強固に統合された並列プリントアーキテクチュアに係り、より詳細には、プリントジョブ計画の最適化に関する。
【背景技術】
【０００２】
プリント機と関連するコンポーネントが複雑化していることから、数多くのコマンドと、多量の情報量の処理と、を容易にする、システム及び方法に対するニーズが高まっている。一方、プロセッサの処理速度が上昇し、メモリの容量が拡大するにつれて、現代のコンピュータシステムの処理能力を十分に活用するために、プリントプラットフォームも益々複雑になってきている。システムに対する要求に応えるため、処理能力を上昇させる傾向と、使用可能な処理能力の利用率を最大化するためにシステムの機能性を高める傾向と、がプリントシステムをより複雑化している。
【０００３】
従来の計画作成アルゴリズムは、プリンタ側で受信されたプリントジョブを処理するための計画された順序付け、又は、一連のイベントを生成することを試みる。プリントジョブに多数のプリントオプションが含まれる場合、プリンタによって印字される一連のページを注意深く経路選択することが重要となる。例えば、プリントジョブ計画の作成は、トナー及び紙などの資源の節約、及び、プリントプラットフォームの効率を向上させる。
【０００４】
モデルベースの計画作成において、特にプリンタなど製造システムのためのオンライン計画作成にとって、計画手段の速度が重要である。新しいジョブリクエストが受信された場合、従来のオンライン計画手段は、初期状態から増加可能（インクリメント）に計画を構成する。これによって、全ての可能性の探索が可能となり、良質な計画、ひいては、最適な計画が見つけ出される。しかしながら、このような方法は、システムが複雑な場合、計画作成が長期化してしまうという欠点がある。
【特許文献１】米国特許出願公開第２００５／０２７８３０３号明細書
【特許文献２】米国特許第４，５７９，４４６号明細書
【特許文献３】米国特許第４，５８７，５３２号明細書
【特許文献４】米国特許第４，８３６，１１９号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従って、本発明は、受信されたジョブを実行するためのジョブ計画を迅速に検索すること、予め定められた時間の範囲において最適で高品質な計画の更なる探索を実行すること、を容易にするシステム及び方法を提供することを目的としている。
【課題を解決するための手段】
【０００６】
機器（ｍａｃｈｉｎｅ）環境においてジョブを計画作成する方法は、計画作成されるジョブを受信し、実行可能である第１の計画を特定するために、予め計算された計画の１セットを解析し、第１の計画を初期値の計画としてスケジューリングし、第２の計画を特定するために、最長計画作成期間を設定し、使用可能であれば、第２の計画を特定し、第２の計画の方が第１の計画より良好かどうかを判断する、ことを含む。
【０００７】
機器のジョブのためのオフライン及びオンラインジョブの計画作成を実行するためのシステムが、与えられたジョブ計画がジョブリクエストに適合していることを確実とするために用いられる、少なくとも一つの制約条件を記憶する制約条件ライブラリと、予め定められた計画作成期間の第１の期間中にジョブリクエストに応じるために、予め計算された計画データベースを解析し、第１の計画を特定して、予め定められた計画作成期間の第２の期間中に第２の計画を特定しようと試みる計画手段と、ジョブリクエストを実行するための計画のどちらがより良好であるかを判断するために、第１の計画と第２の計画を比較する最適化手段と、を備える。
【０００８】
本発明の第１の態様は、機器環境においてジョブの計画を作成する方法であって、計画が作成されるジョブを受信し、実行可能である第１の計画を特定するために、予め計算された計画のセットを解析し、第１の計画を初期値の計画としてスケジューリングし、第２の計画を特定するために、最長計画作成期間を設定し、使用可能であれば、第２の計画を特定し、第２の計画が第１の計画より良好かどうかを判断する、ことを含む。
【０００９】
本発明の別の態様は、第１の態様の方法であって、第２の計画が使用可能でない場合、又は、第２の計画が第１の計画よりも良好でない場合、第１の計画を実行する、ことを更に含む。
【００１０】
本発明の別の態様は、第１の態様の方法であって、システムモデルを受信し、システムモデルに関連付けられた少なくとも一つの制約条件を緩和し、一つ以上の予め計算された計画を生成するために、緩和されたシステムモデルを解決する、ことを更に含む。
【００１１】
本発明の別の態様は、上記の態様の方法であって、少なくとも一つの制約条件が、予め定められた最長ジョブ実行時間、ジョブを完了するために用いられる予め定められた最大コンポーネント数、スケジューリングされるオブジェクトの分散性、異なるオブジェクトの異なる実施の間の相互関係、又はジョブ実行中に生じるイベントの順序付け、の内の少なくとも一つに関連付けられる、ことを含む。
【００１２】
本発明の第２の態様は、機器のジョブのためのオフライン及びオンラインジョブの計画作成を実行するためのシステムであって、与えられたジョブ計画がジョブリクエストに適合していることを確実とするために適用される、少なくとも一つの制約条件を記憶する制約ライブラリと、予め定められた計画作成期間の第１の期間中に、予め計算された計画データベースを解析し、ジョブリクエストを満たす第１の計画を特定し、予め定められた計画作成期間の第２の期間中に、第２の計画を特定しようと試みる、計画手段と、どちらの計画が、ジョブリクエストを実行するためにより良好であるかを判断するために、第１の計画と第２の計画とを比較する最適化手段と、を備える。
【発明を実施するための最良の形態】
【００１３】
本発明の明細書に記載されている様々な特徴は、与えられたジョブに対する解を迅速に選択するために、予め計算された計画のセットを用いることによって、計画作成時間を削減するための方法に関する。また、計画手段は、最初に選択された解を改良するために、割当てられた計画作成時間の残り時間を利用しても差し支えない。既存の方法に比べると、この方法の利点は、有効な計画をきわめて迅速に見つけ出せることである。従って、多数のＩＭＥ（Ｉｎｐｕｔ Ｍｅｔｈｏｄ Ｅｄｉｔｏｒ）プリンタなどの高速な計画作成を要求するシステムにおいて、この方法は、リアルタイムであるための制約条件によって、従来の計画手段が適正な期間内で、システムの生産性が最大のとなる最適計画を見つけ出すことが困難な場面においても、性能を保証できる。
【００１４】
図１に関して参照すると、システム１００は、機器１０４に動作可能に連結され、この機器１０４のためのジョブの計画を作成する計画手段１０２を含む。例えば、機器は、製造環境において、経路選択装置（ルータ）となり得て、一つの製造装置から他の製造装置へオブジェクトを経路選択（ルーチング）することもできる。このような場面において、計画手段１０２は、製造環境において、様々な装置へ送信され様々な装置から送受信される、オブジェクトの動作に対して、最適な計画又は最適スケジュールを決定し得る。他の例によれば、機器１０４は、プリンタであってもよい。そして、計画手段１０２は、一つのコンポーネントから他のコンポーネントへ、紙の経路を選択するための最適な方法を見つけ出すことによって、プリントジョブなどの実行を最適化することを容易にすることができる。
【００１５】
計画手段１０２は、受信されたタスク又はジョブに対する計画を、構成及び／又は選択した場合に適用されてもよい１つ以上の制約条件に関する情報を記憶する、制約条件ライブラリ１０６を更に含む。例えば、時間の制約条件は、ジョブが終了するまでの所定の最長期間、又は、ジョブ解を特定又は選択するための所定の最長期間などであり、これらがジョブ解に関連付けられてもよい。他の例において、制約条件は、例えば、ジョブを完了させるために必要な最小コンポーネント数を使用するジョブ解が、優先権をもつこと示す制約条件など、最適解が選択されることを確実にすることに関する。他の例においては、制約条件ライブラリ１０６は、スケジューリングされるオブジェクトの分散性（ディスクリートネス）及び／又は異なるオブジェクトの異なる実施（ａｃｔｉｖｉｔｉｅｓ）の間の相互関係（ｉｎｔｅｒａｃｔｉｏｎ）に関連付けられた制約条件を含む。また他の実施例においては、ライブラリは、システムの異なる作用素（ｏｐｅｒａｔｏｒｓ）間の干渉及び／又はシステム内を移動する異なるオブジェクトの干渉に関連する制約条件を含む。制約条件ライブラリ１０６は、上述したような制約条件、及び、当業者によって理解されるような他の制約条件を含み得る。
【００１６】
計画手段１０２は、与えられたジョブのために生成又は特定される計画の数を増やすことによって、迅速に計画を見つけ出すことを容易にするために、ジョブ解又は計画を生成及び／又は選択する時に適用される１つ以上の制約条件の選択的緩和及び／又は選択的除去を行う制約条件緩和手段（リラクサ）１０８を更に含む。例えば、ジョブ計画の規準について１つ以上の制約を緩和することによって、制約条件緩和手段１０８は、ジョブの実行に受容可能であると識別されるジョブ計画の数を増やすことができ、これによって、使用可能なジョブ計画のオプション数も増やすことができる。この結果、良好な又は最適な計画の発見が一層容易になる（ただし、緩和された制約条件のセット有り）。例えば、時間の制約条件は、好ましいとされるジョブ計画の実行時間が１０秒以下であることを指図し、順序付け制約条件は、イベントａ、ｂ、ｃが、この順に実行されることを指図する。６個の使用可能なジョブ解が１０秒以下で実行され得るが、一つの解のみがイベントａ、ｂ、ｃを所望の順序で実行する場合、制約条件緩和手段１０８は、最初にイベントａが発生することを前提に、例えば、イベントｂ、ｃを任意順に発生可能とするように、順序付け制約条件を緩和する。これによって、より多くの良好なジョブ解が得られる。関連する例として、制約条件緩和手段１０８は、６個のジョブ計画の全てを選択及び／又は実行可能とするために、順序付け制約条件を完全に除去してもよい。
【００１７】
計画データベース１１０は、ジョブもしくはタスクの受信時に、予め計算又は生成される１つ以上のジョブ計画又は解を記憶することができる。計画データベース１１０は、与えられたジョブに関する全ての規準及び／又は制約条件に一致する１つ以上の選択された計画に関する情報と、ジョブ計画作成及び／又は実行に関する任意の他の情報と、の内の少なくとも一方を記憶することができる。更に、計画手段１０２は、与えられた制約条件を満たす１つ以上の計画を含む計画のセットの内から、最適な計画を特定する最適化手段（最適化装置）１１２を含む。機器１０４がプリンタ又は他の電子写真装置である例によれば、最適化手段１１２は、実行に時間が掛かる計画に対しては最短実行時間を有する計画が望ましいが、（例えば、ジョブキューが満杯、又は、ほぼ満杯である等）特定セットの制約条件がある場合、紙もしくはトナーなどの特定の資源の保存がそれほど重要ではないと判断する。このような場合、最適化手段１１２は、最小量のトナー使用を要求する制約条件を緩和又は除去するように、制約条件緩和手段１０８に命令することができ、これが更に、最短実行時間を有するジョブ計画がより短時間で特定、解析、選択されることを可能とする。
【００１８】
他の例によれば、例えば、機器１０４（例えば、製造設備）のモデルが計画手段１０２に与えられると、計画手段１０２は、このモデルを使用して、（例えば、製造設備、機器、プリンタなどによるオブジェクトの）使用可能な経路（ルート）又はジョブ計画を計算することができ、製造設備又は機器１０４の全体的な処理能力を最適化する。そうしている間、計画手段１０２は、制約条件緩和手段１０８を介して、いくつかの制約条件を緩和して、ジョブ解の選択時間を削減することができる。例えば、計画手段１０２は、ネットワークフローベースの最適化手段１１２を使用することができる。次いで、計画手段１０２は、計画データベース１１０内の緩和された条件下で計算されたジョブ計画を記憶し、新しいジョブのために計画を探索する時、記憶されたジョブ計画を最初に試用することができる。このように、計画作成探索又はスケジューリング探索の必要性が緩和されるので、良好な計画を迅速に見つけ出すことができる。次いで、この良好な計画は、与えられた計画作成時間内に、より良好な計画を探索する後の計画探索のための上限として、使用され得る。従って、システム１００は、計画手段１０２によって用いられる分枝限定探索アルゴリズム、最良優先探索アルゴリズム、又は任意の随時探索アルゴリズムと一緒に使用され得るフレキシブルなフレームワークを提供する。
【００１９】
図２は、本明細書中に記載されている様々な特徴が用いられる環境を表す、カラープリントシートバッファ又は密統合された並列プリンタ（ＴＩＰＰ）システムを有する汎用製造プリンタにおいて用いられるような、複数のコンポーネントを含むシステム２００を示す。システム２００は、一枚以上の紙を含み、カラープリントエンジン２０４及び差込手段（インサータ）２０８に動作可能に関連付けられる紙供給部２０２を含む。紙供給部２０２からの紙は、二つの経路の内の一つを選択する。例えば、紙は、差込手段２０８に入る前に、紙供給部２０２から、カラープリントエンジン２０４、そして、カラープリントバッファ２０６まで経路選択される。更にもしくは代替的に、紙は、紙供給部２０２から差込手段２０８へ直接、経路選択されてもよい（例えば、高速経路２１６を用いてカラーエンジン２０４とカラープリントバッファ２０６を迂回する）。同様に、紙は、高速経路２１８を用いて、白黒エンジン２１０を迂回してもよい。
【００２０】
紙供給部２０２から差込手段２０８まで直接経路選択された紙は、ユーザへ提供されるドキュメントの仕上げをする仕上手段（フィニッシャ）２１４へ進む前に、白黒ページ及びカラーページを組み合わせる融合手段（マージャ）２１２を介して、白黒プリントエンジン２１０へ受け渡されてもよい。他の例によれば、紙は、システム２００の全てのコンポーネントを通過し、カラー部分と白黒部分の両方を有してもよい。システム２００によって実行されるジョブに関連付けられる機能は、このジョブに対して、１つ以上の解、又は、「複数の計画」を定義する一連のイベントとなるように編成される。
【００２１】
図３は、ＴＩＰＰプラットフォームなどの機器における媒体経路選択ジョブのための、ネットワークフローモデルの解３００を示す。モデルがあれば、ネットワークフローモデルの解は、製造設備内の材料（例えば、ＴＩＰＰプリンタにおける（複数の）紙）が分散した状態である場合の制約条件を緩和し、この緩和された条件下で、システムにおいて製造設備の処理能力を最大にする、実行可能な経路を見つけ出す。モデルは一度「解」を与えられており、プリントジョブのリクエストの際にプリンタ内の異なる場所において配置された複数の紙が存在する場合、リアルタイムであるための制約条件を考慮に入れる必要がない。解３００は、システムに対して所望される処理能力を達成することができる、１セットの有効な経路３０２を示す。
【００２２】
図４は、ＴＩＰＰプラットフォームなどの機器における媒体経路選択ジョブのためのモデルベースのオンライン計画手段の解４００を示す。モデルベースのオンライン計画手段は、図中に示された経路４０２などの所与のプリントジョブのために具体的な経路を組み立てることができる。経路４０２は、増加可能に組み立てられることができ、リアルタイムであるための制約条件を考慮に入れる。全ての実行可能な経路は、最終解が正確かつ最適であることを確実とするために検討され得る。例えば、プリンタなどにおいて、空経路から開始して、必要なモジュールを横切る入力（フィーダ）から出力（仕上手段）までの完了経路が終了するまで、各ステップにおいて与えられた機器の能力が追加されてもよい。計画又は経路が毎回初期状態から組み立てられ、制約条件が緩和されない場合、解を見つけ出すために必要な時間を把握することはむずかしい。しかしながら、先に使用された探索アルゴリズム（例えば、Ａ＊）が最適性を保証する場合、解の品質は良好となる。
【００２３】
図５は、受信されたジョブを実行するために、予め計算されたジョブ計画を迅速に検索する、及び、予め定められた時間内で最適な品質の計画の探索を実行する、ことを容易にする計画作成フレームワーク５００を示す。計画作成フレームワーク５００は、製造設備、組み立てライン、プリントプラットフォームなどのシステムモデルに関する情報を受け取る、問題緩和手段５０２を含む。問題緩和手段５０２は、モデリングされたシステムによって実行されるジョブに関連付けられた情報も受信できる。このような情報が受信されると、問題緩和手段は、ジョブの性能に関連付けられた１つ以上の制約条件（例えば、ジョブ期間制限、特定の実行規準、イベント順序付けなど）を緩和することができ、簡単化された、即ち、「緩和された」計画を作成するための問題を出力することができる。緩和された問題を解決する解決手段５０４は、簡単化された計画を作成するための問題を受け取り、受け取ったジョブ記述を実行するための、各々の計画を示す１つ以上の解を生成することができる。この解（複数を含む）は、計画手段−スケジュール作成手段５０８によって、引き続きアクセスできるように、計画データベース５０６内に記憶されてもよい。
【００２４】
例によれば、計画手段−スケジュール作成手段５０８は、ジョブ計画が所望されるプリンタなどの現在のシステム状態に関する情報を受信できる。現在のシステム状態の情報は、これらに限定されないが、使用可能な資源のレベル、システム資源の使用レベル、このシステムが他のジョブを実行しているためにビジー状態であるかどうか、このシステムが現在計画作成されているジョブを実行する用意ができているか、及び／又は、それが何時なのか等であっても良い。計画手段−スケジュール作成手段５０８が、予め計算された計画データベース５０６にアクセスし、最適化規準に従って予め計算された計画データベース５０６内に記憶された計画の中から最良の計画を選択し、実行可能システムへこの計画を、最終的な計画として出力する。所与の計画が最良な計画であるかどうかを判断する際に、計画手段−スケジュール作成手段は、多種多様の規準を検討する。規準は、これらに限定されないが、一つ以上の定義された制約条件を準拠する、緩和された制約条件を準拠する、実行時間を最短にする、資源消費を最低にする等を含む。関連する例によれば、現在システム状態の情報が、ネットワークフローのモデル化手段によって受信され、オンラインシステム情報を提供する。この情報は、ネットワークフローのモデル化手段によってこのシステムのモデルを連続的及び／又は周期的に更新可能とさせる。
【００２５】
このように、機器モデル及び／又はジョブ記述が受信された時、計画作成フレームワーク５００は、計画作成問題を簡単化するためにいくつかの制約条件を緩和する。緩和は、タイプ次第であり、計画作成フレームワーク５００は、簡単化された問題に解を与えるために適切な解決手段５０４を呼び出し、特定された解を予め計算された計画データベース５０６内に記憶する。リアルタイムにおいて、ジョブリクエストが受信された時、計画手段−スケジュール作成手段５０８は、予め計算された計画データベース５０６から解を選択し、少なくとも一つの有効な計画を、実行する計画として使用可能とすることを確実にするために、この解を迅速にスケジューリングする。次に、計画手段５０８は、初期の解よりも良好な解（例えば、より速く、又は、より低価格な解）を発見しようと、計画作成時間の残り時間を使う。
【００２６】
図６は、割当てられた計画作成期間の第１の期間中に少なくとも一つの有効なジョブ計画を見つけ出し、最適なジョブ計画の生成及び／又は特定のための計画作成期間の残りの期間を保存するために、制約緩和プロトコルに連携している欲張り探索アルゴリズムを用いて、ジョブ計画をオンラインで計算する、計画作成フレームワーク６００を示す。計画作成フレームワーク６００は、システムモデル及び／又はジョブ記述情報を受信する問題緩和手段６０２を含む。問題緩和手段６０２は、実行されるジョブ、使用可能な資源、システムの使用率などの現在のシステムの状態に関連付けられた情報を、更に受信し得る。受信された情報に基づいて、問題緩和手段６０２は、ジョブを終了させるに足る１セットのイベントを特定するために、ジョブ性能に対する一つ以上の制約条件を緩和及び／又は無視するために欲張りアルゴリズムを用いることができ、これによって、有効なジョブ解の数が増加する。（例えば、削減された制約条件を有する）簡単化されたジョブ計画作成するための問題は、解決手段６０４へ出力され、この解決手段６０４は、残った制約条件を満たす一つ以上の計画を特定することができる。解決手段６０４によって戻された最良な計画は、計画手段−スケジュール作成手段６０６によって選択され、最終的な計画として出力され得る。従って、解決手段６０４は、一つ以上の制約条件に必ずしも従わずにジョブを終了することを可能とする、初期ジョブ解を戻すことができる。緩和された問題を解決する解決手段６０４が問題の解決をより簡単にするために、いくつかの制約条件を無視することを前提にした場合、その解は、元の制約条件の全てに照合して最適とはなり得ない。予め定められた計画作成期間の残りの期間中に、より良好な計画（例えば、元の制約条件のより多くの条件又は全ての条件に一致した計画）が探索及び／又は生成されてもよい。
【００２７】
図７は、ジョブ計画作成に対して他の方法を用いる場合の計画作成フレームワーク７００を示す。他の方法とは、１セットの予め計算されたジョブ計画と、リアルタイムでオンライン特定され、前もって実行されたジョブ計画との両方から、ジョブ解が選択され、次に、これらのジョブ解は予め計算された計画と一緒にキャッシュ記憶される方法であっても良い。例えば、計画作成フレームワーク７００は、ジョブが計画作成されるシステムの状態に関連付けられた現在のシステム状態の情報を受信する計画手段−スケジュール作成手段７０２を含むことができる。計画手段−スケジュール作成手段７０２は、予め計算された計画データベース７０４（オフライン期間に予め計算されていたジョブリクエストのための一つ以上の計画が記憶され得る）から最良の計画を更に検索することができる。計画手段−スケジュール作成手段７０２によって選択される予め計算された計画は、予め計算された計画データベース内の他の計画と比較すると、リクエストされたジョブを（例えば、資源、時間などについて）最低コストで終了することができる計画である。予め計算された計画が一旦選択されると、計画手段−スケジュール作成手段７０２は、最終計画を生成することができる。この最終的な計画は、検索された予め計算された計画の変更内容を含んでいてもよいし、実行のために出力されてもよい。計画手段は、この予め計算された計画を、最終的な計画の品質の上限として使用し、割当てられた計画作成時間の残りの期間において、より良好な計画を発見しようと試みる。このような良好な計画が発見されれば、それが最終的な計画として出力される。次に、この最終的な計画が、（この計画の評価を行う）制約条件緩和手段７０６によって受信され、この計画が予め定義された規準のセットを満たしていれば、この最終的な計画は、これ以降の計画手段−スケジュール作成手段７０２による評価及び／又は選択のために予め計算された計画データベース７０４に記憶され得る。このように、計画手段−スケジュール作成手段７０２によってオンラインで作成された最終的な計画は、引き続いてジョブ計画作成を求めるための予め計算された計画となり得る。同様に、予め計算された計画データベース７０４内に記憶された予め計算された計画の内の一つ以上の計画は、先行する計画作成期間中に、計画手段−スケジュール作成手段７０２によって作成されたものであってもよい。
【００２８】
図８は、一つ以上のジョブ計画を予め計算するためのネットワークフローモデルと、混合整数プログラミング（ＭＩＰ）技術と、を一つ以上の特性に応じて用いることによって、ジョブ計画手順の簡単化を容易にする計画作成フレームワーク８００を示す。計画作成フレームワーク８００は、ジョブが計画作成されるシステムのモデルに関連する情報のみならず、計画作成されるジョブの記述に関連する情報を受信するネットワークフローモデル化手段８０２を含む。ネットワークフローモデル化手段８０２は、ＭＩＰ符号化技術を用いて、システムのモデルを生成してもよいし、ジョブ期間中に処理されるオブジェクトの分散された状態を緩和することによって、そして、このジョブの異なる製造上の必要条件に関連する作用素間の相互関係を無視することによって、解決すべきジョブ計画作成のための問題を簡単化してもよい。（例えば、市販のＭＩＰ解決手段、無料の解決手段などであってもよい）ＭＩＰ解決手段８０４は、計画作成のための問題を解決することができ、有効なジョブ解をもたらすことができる。ネットワークフローモデルのための最終解に含まれた複数の経路及び／又は計画は、予め計算された計画データベース８０６に記憶され得る。次に、計画手段−スケジュール作成手段８０８は、良好な予め計算された計画に関連する情報と現在システム状態の情報とを受信して最終計画を生成することができる。
【００２９】
図９は、さまざまな態様に従って、接続グラフを用いたジョブ計画解の生成及び／又は選択を容易にする計画作成フレームワーク９００を示す。接続グラフ構築手段９０２は、システムモデルと、システムによって実行されるジョブを記述する情報と、を受信することができる。接続グラフ構築手段９０２は、移動する異なるオブジェクトに関連付けられる異なる作用素間の相互関係を無視しながら、オブジェクトを経路選択するために用いられるシステムの異なるコンポーネント間の接続を表す、接続グラフを生成することができる。例えば、プリントプラットフォームにおいて、オブジェクトは処理又はプリントを必要とする紙面であってもよいし、作用素はこれらのページを処理するための機能を実行するコンポーネントなどを含んでいてもよい。最短経路解決手段９０４は、接続グラフを受信し、全てのペアの最短経路探索アルゴリズムを用いて、セット解を生成する。セット解の各解は、リクエストされたジョブを実行するための計画を代表しており、このような計画が予め計算された計画データベース９０６に記憶され得る。次に、良好な予め計算された計画は、計画手段−スケジュール作成手段９０８によって選択又は検索され、この計画手段−スケジュール作成手段９０８が、実行される最終的な計画を生成するために、現在システム状態の情報に従って選択された計画を更に最適化することもある。次に、最終的な計画は、実行のために出力され得る。システムモデルにおける作用素間の相互関係のみは無視するが、オブジェクトの分散性を重視することによって、フレームワーク９００は、本明細書中に記載された他のフレームワークよりも少ない制約条件を緩和することができ、これによって、より高品質の予め計算された計画が得られる。接続グラフは、この技術に限定されないが、ＭＩＰ（混合整数プログラミング）技術を用いて符号化されてもよいし、１セットのＭＩＰの符号化された解を出力することもできる。
【００３０】
図１０は、予め定められた期間中にジョブを計画作成するために、予め計算された計画を利用するための方法１０００を示す図である。この方法１０００において、計画作成期間の第１の期間中に十分なジョブ計画が特定され、計画作成期間の第２の期間中により良好なジョブ計画が探索される。１セットの予め計算された計画は、計画作成期間の第１の期間中に、評価され、そうでなければ、受信され、ステップ１００２において、予め計算された計画の中から、計画Ｐ１が、実行されるジョブに関連付けられる一つ以上の規準を満たす計画として特定され、実行のためにスケジューリングされる。例えば、製造ジョブが受信された時、計画手段は、予め計算された計画データベースから計画を選択し、この計画を実行するためにスケジューリングしてもよい。このように、ステップ１００２は、リアルタイムな資源の制約条件と製造ジョブの実行中に処理される材料の分散性とを考慮に入れながら、ジョブ計画作成を容易にすることができる。例えば、製造ジョブはプリンタにおけるプリントジョブであってもよいし、材料は、紙であってもよい。競合を解決するために資源の割当てをスケジューリングする場合、同一資源の他の全ての割当てを行った後に、新しい割当てをスケジューリングすることによって、探索なしで有効な計画を導くことができる。次に、選択された、又は、得られた計画Ｐ１は、計画作成期間中に計画手段によって探索又は発見される最終的な計画の品質の上限として使用されてもよい。
【００３１】
ステップ１００４において、計画作成最長期間Ｔは、計画作成期間の第２の期間の最長許容期間として設定される。ステップ１００６において、予め定義されたジョブ規準を満たす第２の計画Ｐ２の探索が行われてもよいし、この探索は、期間Ｔ（例えば、計画作成期間の第２の期間）の期限満了まで続行されてもよい。ステップ１００８において、第２の計画Ｐ２が特定されたかどうかについての判断が行われてもよい。第２の計画Ｐ２が特定されなければ、ステップ１０１４において、計画Ｐ１が、これまで実行のために特定された計画のうちの最高の品質の計画として、計画手段又は他のシステムプロセッサへ戻される。
【００３２】
ステップ１００８において第２の良好な計画が特定された場合、次に、ステップ１０１０において、計画Ｐ２の方が計画Ｐ１よりも良好かどうかについて判断される。計画の最適性は、計画の実行及び／又は性能に関連する１つ以上のパラメータの関数として求められてもよい。例えば、計画の最適性に影響を与えるパラメータは、これらに限定されないが、計画実行速度、資源消費、出力品質などを含んでいてもよい。プリンタ又は電子写真装置に関連する具体的な例において、計画最適性は、プリントジョブ速度、一つ以上の資源（紙、トナーなど）に関連するコスト削減、機器を介した経路選択効率などの関数であってもよい。Ｐ１の方がＰ２より良好であると判断された場合、次のステップ１０１４へ進み、Ｐ１が実行可能なプロセッサ及び／又は計画手段コンポーネントへ出力される、又は、戻される。Ｐ２の方がＰ１より良好であると判断された場合、次に、ステップ１０１２において、Ｐ２は、ジョブ又はタスクの実行可能な「今までで最高の解」として戻されてもよい。計画Ｐ１のコストが、分枝限定探索における上限として用いられる場合、計画Ｐ２の発見によって、Ｐ２の方がＰ１よりも良好であることが示唆されていることが理解されよう。従って、Ｐ１とＰ２のコストを更に比較する必要性がなくなる。
【００３３】
計画作成期間は、継続時間が、秒、ミリ秒、マイクロ秒などであってよく、計画作成期間の第１及び第２の期間は、等しい長さである必要はない。例えば、計画作成期間は、約１００ミリ秒〜約２秒の範囲内であってもよく、計画作成期間の第１及び第２の期間の長さ比率を約１：２としてもよい。他の例によれば、計画作成期間の全体の継続時間が３００ミリ秒である場合、（例えば、ステップ１００２に対応する）計画作成期間の第１の期間は、約１１０ミリ秒の継続時間を有していてもよく、残りの約１９０ミリ秒の継続時間が、（例えば、ステップ１００４から１０１４に対応する）計画作成期間の第２の期間に割当てられてもよい。更に他の例によれば、この方法は、二つより多い計画を評価し、実行するための最良の計画を選択するために、計画作成期間内で、多数回、繰り返される。以上の述べた例は、本来、例として挙げたにすぎず、計画作成期間、計画作成期間の各期間中、又は計画作成期間の第１の期間と計画作成期間の第２の期間との比率を限定することを意図するのもではないことが理解されよう。
【００３４】
図１１は、プリントプラットフォームによって実行される予定のプリントジョブを評価し、少なくとも一つの計画が使用可能であることを確実にするために、このジョブを実行するための少なくとも最低規準を満たす第１のジョブ計画を選択し、さまざまな態様に従って、ジョブの実行とジョブ性能を改良するために、このジョブを実行するための最適な計画を特定するための方法１１００を示す。方法１１００は、これまでに図面に関して説明された計画手段などの計画作成コンポーネントによって実行される。プリントプラットフォーム又は他の電子写真装置もしくは画像形成装置の場合、ジョブ計画は、テキストが用紙に適正にプリントされることが確実となるように処理される１つ以上の紙面が、この経路に沿って移動する（例えば、プリンタを横切る）一つ以上の経路の決定を含んでいてもよい。他の自動化された製造領域についても同様である。ステップ１１０２において、機器モデルが評価され、このモデルのためにネットワークフローモデルが生成され、解が与えられ、このネットワークフローモデルの最終的な解に含まれる実行可能な経路が、記憶される。ステップ１１０２は、ネットワークフローモデルが、分散性と、ジョブ実行に関するリアルタイムの制約条件と、を緩和するので、迅速に実行され得る。ステップ１１０４において、入ってくるプリントジョブが検出され、計画手段によって解析され、次いで、計画手段は、ネットワークフローモデルによって予め計算された経路の一つを選択し、ステップ１１０６において、選択された経路をスケジューリングしようと試みる。選択された計画は、計画手段によって発見される最終的な計画の上限として用いられる。ステップ１１０８においては、限定された時間内で、ステップ１１０４においてネットワークフローの解から選択された最初の解より良好な解を求める探索が行われる。最初の解より良好な解がなければ、ステップ１１１０において、より良好な解に関連する計画が出力され得る。ステップ１１１２において、ネットワークフローモデルに変更があったかどうかが判断される。オフ／オンラインで進行するモデルにおいて、モジュールなどのモデル変更があった時は必ず、ステップ１１０２へ戻り、新しいネットワークフローモデルが組み立てられ、再び解が与えられ、データベースへ新しい有効な経路が記憶される。
【００３５】
ステップ１１０４において、最終的な解がスケジューリングプロセスを受けられることに注目されたい。このスケジューリングプロセスは、ネットワークフローによって予め計算された経路から選択された時の計画が有効な計画ではなくても、リアルタイムの資源の制約条件と材料（例えば、紙）の分散性を考慮に入れる。上述された通りに、「ネットワークフロー」（ステップ１１０２において解決手段として用いられる）は、オンライン計画作成のために一つの解を迅速に返却するために、１セットの緩和された解が探索され得るいくつかの方法の一つである。ネットワークフローモデルは、材料の分散性とシステムのオンラインの態様とを考慮に入れる必要がない（例えば、設備を移動する他の部品の材料との有効な相互関係を無視する）。他のバリエーションを有する方式は、限定された「オンライン」情報を考慮に入れ、新しいジョブが入ってくる各段階においてネットワークフローモデルを設定するだけでなく、ネットワークフローモデルに解を与えるときに材料の分散性を近似することができる。ネットワークフローモデルが本明細書中に記載されたさまざまな態様と連携して用いられているが、理論的な計画作成リサーチにおいての「緩和された計画（ｒｅｌａｘｅｄ−ｐｌａｎ）」などの他の方式が、１セットの候補となる計画を予め計算するための更なる又は他の方法として用いられることができる。例えば、「緩和された計画」方式は、機能と性能との間の論理的な相互関係を緩和することによって作動するが、ネットワークフローモデルにおけるような材料の分散性に対する制約条件を緩和することによっては、作用しない。更に、大小のセットの制約条件は、上記に説明されたネットワークフローモデルを適用した場合、緩和され得る。他の方式は、前もって全ての実行可能な経路を得るために、全ての最短経路を算出するアルゴリズムを用いることである。この方式は、異なる個々のオブジェクト又は個々の紙面の間の相互関係を緩和しながらも、オブジェクトの分散性を考慮に入れる。
【００３６】
上記に開示された発明、他の特徴、作用、又はその代替が、望ましくは、多くの他の異なるシステム又は用途に組み込まれてもよいことが理解されよう。本発明において、今の時点で予想できない代替案、変更、変形、又は改良が、請求の範囲を逸脱することなく、今後、当業者によって作成され得ることも理解されよう。
【図面の簡単な説明】
【００３７】
【図１】本発明の機器に動作可能に連結され、この機器のためのジョブを計画作成する計画手段を含むシステムを示す図である。
【図２】本明細書中に記載された様々な特徴が用いられ得る環境を表すカラープリントシートバッファ又は強固に統合された並列プリンタ（ＴＩＰＰ）システムを有する汎用製造プリンタにおいて用いられるような複数のコンポーネントを含むシステムを示す図である。
【図３】ＴＩＰＰプラットフォームなどの機器における記憶媒体経路選択ジョブのためのネットワークフローモデルの解を示す図である。
【図４】ＴＩＰＰプラットフォームなどの機器における記憶媒体経路選択ジョブのためのモデルベースのオンライン計画手段の解を示す図である。
【図５】受信されたジョブを実行するためにジョブ計画を迅速に検索することと、予め定められた時間の範囲内で、最適な品質計画の探索を実行することを容易にする計画作成フレームワークを示す図である。
【図６】割当てられた計画作成期間の第１の期間中に少なくとも一つの有効なジョブ計画を見つけ出す、及び、最適ジョブ計画の生成及び／又は特定のための計画作成期間の残りの期間を保存する、ことを容易にするために、制約緩和プロトコルに連携している欲張り探索アルゴリズムを用いる計画作成フレームワークを示す図である。
【図７】予め計算されたジョブ計画の１セットと、リアルタイムでオンライン特定された前もって実行されたジョブ計画と、の両方からジョブ解が選択されるジョブ計画作成に用いられる計画作成フレームワークを示す図である。
【図８】一つ以上の特徴に応じて、整数線形プログラミング（ＩＬＰ）技術を用いることによってジョブ計画手順の簡単化を容易にする計画作成フレームワークを示す図である。
【図９】さまざまな態様に応じて、接続グラフを用いて、ジョブ計画解の生成及び／又は選択を容易にする計画作成フレームワークを示す図である。
【図１０】予め定められた期間中にジョブを計画作成するために、予め計算された計画を利用するための方法であって、計画作成期間の第１の期間中に十分なジョブ計画が特定され、計画作成期間の第２の期間中により良好なジョブ計画が探索される方法を示す図である。
【図１１】プリントプラットフォームによって実行される予定のプリントジョブを評価し、少なくとも一つの計画が使用可能であることを確実にするためにこのジョブを実行するための少なくとも最低規準を満たす第１のジョブ計画を選択し、計画を探索するための全体時間の限定などのさまざまな態様に従って、ジョブの実行とジョブ性能を改良するためにこのジョブを実行するための最適な計画を特定するための方法を示す図である。
【符号の説明】
【００３８】
１０２  計画手段
１０４  機器
１０６  制約条件ライブラリ
１０８  制約条件緩和手段
１１０  計画データベース
１１２  最適化手段
【図１】
2008299846.tif 000003
【図２】
2008299846.tif 000004
【図３】
2008299846.tif 000005
【図４】
2008299846.tif 000006
【図５】
2008299846.tif 000007
【図６】
2008299846.tif 000008
【図７】
2008299846.tif 000009
【図８】
2008299846.tif 000010
【図９】
2008299846.tif 000011
【図１０】
2008299846.tif 000012
【図１１】
2008299846.tif 000013