(57)【特許請求の範囲】
【請求項１】
印刷された複数のシートを一時的に蓄積するマルチ容量プリントシートバッファのアロケーションの順序付けリストのモデルを評価し、
前記マルチ容量プリントシートバッファのアロケーションの順序付けリストへの新しいアロケーションの挿入位置を選択し、
アロケーションの実行の順序を決定する少なくとも１つの時間的制約条件を掲示し、
前記選択された挿入位置における新しいアロケーションの挿入の後でモデルの実行が少なくとも１つの前記時間的制約条件に基づいて実現可能であるかどうか決定し、
実現可能である場合、比較及び実行の少なくとも一方のためにモデルを格納し、
実現不可能である場合、モデルが実現不可能であることを記録し、
前記アロケーションの順序付けリストがマルチ容量プリントシートバッファ内を通過することになるページの順序を含むリストであり、
新しいアロケーションが順序付けリストに挿入される新しいページであり、
少なくとも１つの前記時間的制約条件は、ｉ＋１番目のページがマルチ容量プリントシートバッファに入る前にｉ番目のページがマルチ容量プリントシートバッファに入り、ｉ＋１番目のページがマルチ容量プリントシートバッファから出る前にｉ番目のページがマルチ容量プリントシートバッファから出て、ｉ＋Ｎ番目のページがマルチ容量プリントシートバッファに入る前にｉ番目のページがマルチ容量プリントシートバッファから出ることを保証する制約条件を含み、
ｉは整数であり、ＮはＣ以下の整数であり、Ｃはマルチ容量プリントシートバッファに蓄積可能な最大シート数である、
機械制御のためにマルチ容量プリントシートバッファのモデル・ベース・プランニングを使用する方法。
【請求項２】
印刷された複数のシートを一時的に蓄積するマルチ容量プリントシートバッファの既存のアロケーションのオーダリングへの新しいアロケーションの挿入位置を選択するプランナと、
マルチ容量プリントシートバッファのアロケーション上の少なくとも１つの時間的制約条件を特定するプランナ生成器と、
選択された挿入位置に新しいアロケーションを含む新しいアロケーションのオーダリングが特定された少なくとも１つの前記時間的制約条件を考慮して実現可能であるかどうかを決定するプラン・テスタと、
を含み、
実現可能である場合、比較及び実行の少なくとも一方のためにオーダリングをメモリに格納し、
実現不可能である場合、オーダリングが実現不可能であることをメモリに記録し、
前記アロケーションのオーダリングがマルチ容量プリントシートバッファ内を通過することになるページのオーダリングであり、
新しいアロケーションがページのオーダリングに挿入される新しいページであり、
少なくとも１つの時間的制約条件は、ｉ＋１番目のページがシートバッファに入る前にｉ番目のページがシートバッファに入り、ｉ＋１番目のページがシートバッファから出る前にｉ番目のページがシートバッファから出て、ｉ＋Ｎ番目のページがシートバッファに入る前にｉ番目のページがシートバッファから出ることを保証する制約条件を含み、
ｉは整数であり、ＮはＣ以下の整数であり、Ｃはマルチ容量プリントシートバッファに蓄積可能な最大シート数である、
マルチ容量プリントシートバッファのためのモデル・ベース・プランニングを支援するシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチ容量資源を使用して資源配分のモデル・ベース・プランニングを容易にするシステム及び方法に関する。
【背景技術】
【０００２】
処理能力及び記憶容量が増加すると、機械にシステム能力を十分に利用させることを可能にする制御機構の必要性が生じる。プリンタ、写真複写機などの場合、従来の制御機構は、情報を処理し、資源を配分し、ジョブやタスクを実行するなどのように制限されていた。機械のための制御システムを設計する場合、コストを軽減し、処理能力（スループット）を増加させるために資源の配分及び利用を最適化することが望ましい。たとえば、多数の同時配分ができる資源は、プリンタや写真複写機などの機械における性能向上をもたらすために用いることもできる。従来、単一の資源は単一のコンポーネントに配分されたり、あるいは一定の時間に単一のタスクに対して配分されたりすることがあった。しかしながら、マルチ容量資源（例えば、一定の時間に多数の配分ができる資源）の場合には、制御機構はこれまで、資源容量を最適化するプランニング及びスケジューリングのそれぞれの機構を提供することはできなかった。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
たとえば、マルチ機能・マルチ資源並列処理システムのための制御最適化における一部の試みは、手動でコード化されたルールが用いられ、これらは、これまで最適又は完全であるとは結論付けられていなかった。コンポーネントの記述をプランニング・エンジンに関連付けられる負担に追加するような他の方式は、機能的でもあり得るが、プランナ性能において組み合わせ的課題をもたらすこともある。しかしながら、マルチ容量資源利用の最適化を容易にし、同時に計算の諸経費を最小限に抑えて処理能力を向上させ、機械制御に関連付けられるコストを軽減するシステム及び／又は方法に対する技術的にまだ対処されていない必要性が存在する。
【課題を解決するための手段】
【０００４】
本明細書中に記載される種々の態様に従って、マルチ容量資源を使用して資源配分のモデル・ベース・プランニングを容易にするシステム及び方法が説明される。たとえば、機械制御のための方法は、マルチ容量資源のアロケーションの順序付けリストのモデルを評価することと、新しいアロケーションに対する挿入地点をマルチ容量資源のアロケーションの順序付けリスト内に選択することと、アロケーションの実行順序を決定する１つ以上の時間的制約条件を掲示することと、新しいアロケーションの選択された挿入地点での挿入後にモデルの実行が実現可能であるか決定することと、を有することができる。この方法はさらに、実現可能である場合、比較及び／又は実行のためのモデルを格納することと、複数のモデルを比較することと、を有し、これらモデルのそれぞれに、新しいアロケーションに対する異なる選択された挿入地点が設けられ、他のモデルに対する実現可能性のレベルに基づいて実行のためのモデルを選択することをさらに有する。１つ以上の時間的制約条件は、先入先出制約条件及び／又は連続的制約条件を有することもあり、これはＮ番目（Ｎが整数である）の先行するアロケーションが、新しいアロケーションが開始される前に完了していることを保証する。
【０００５】
本明細書中に記載される別の特徴によれば、マルチ容量資源に対するモデル・ベース・プランニングを容易にするシステムは、新しいアロケーションに対する挿入地点をマルチ容量資源の既存するアロケーションのオーダリングに選択するプランナと、マルチ容量資源のアロケーションの少なくとも１つ以上の時間的制約条件を特定するプラン生成器と、選択された挿入地点における新しいアロケーションを有する新しいアロケーションのオーダリングが特定の制約条件を考慮して実現可能であるかどうかを決定するプラン・テスタと、を有することができる。このマルチ容量資源は、電子写真機械におけるシートバッファでもよく、アロケーションのオーダリングは、シートバッファを通過されるページのオーダリングでもよく、新しいアロケーションは、ページのオーダリングに挿入される新しいページでもよい。さらに、少なくとも１つの時間的制約条件は、第１のページが、第２のページがシートバッファに入る前にシートバッファに入り、第２のページがシートバッファから出る前にシートバッファから出ることを保証する先入先出（ＦＩＦＯ）制約条件と、シートバッファに関連付けられる最大容量を超えないことを保証する容量ベースの制約条件と、を有することもできる。容量ベースの制約条件は、Ｎ番目（Ｎはシートバッファの最大容量に等しい整数である）の先行するページがシートバッファから出るまで現在のページがシートバッファに入らないことを規定する。
【０００６】
さらにもう１つの特徴は、印刷プラットフォームに関し、これは、電子写真プロセスを実行するための命令を実行する１つ以上の電子写真コンポーネントと、マルチ容量資源の既存のアロケーション・オーダリングへの新しいアロケーションに対する挿入地点を選択し、更新されたアロケーション・オーダリングを生成し、少なくとも１つの時間的制約条件を割り当ててアロケーション・オーダリングを決定するプランナと、更新されたアロケーション・オーダリングがこうしたオーダリング時間的制約条件を侵害するか否かについての機能として更新されたアロケーション・オーダリングの実現可能性を決定するプラン・テスタと、を有する。アロケーション・オーダリングを決定する時間的制約条件は、少なくとも先入先出（ＦＩＦＯ）制約条件と、マルチ容量資源に対する最大容量を記述する容量制約条件を含むこともある。
【発明を実施するための最良の形態】
【０００７】
本明細書中に記載される種々の特徴に従って、マルチ容量資源を取り扱うために個々の専門的なソフトウエアの必要性を緩和するために現在のモデル・ベース・プランニング・アルゴリズムを拡張し、一方で最適プランを出力するためにオンライン・プランナの能力を保持するフレームワークが提示される。たとえば、マルチ容量資源のアロケーションを示す適切な時間地点と、それらの間の時間的制約条件を追加することによって、プランナは、目的関数が与えられると、マルチ容量資源を利用する最適な方法で決定することもできる。プランナによって使用されるモデリング言語は、そのプランナが異なるタスクに１つ以上の資源を共有させることができるかを決定するために解析され得る。このようにして、モデル・ベースの汎用オンライン・プランナは、時間的制約条件を用いてマルチ容量資源を最適に制御するために使用され得る。
【０００８】
図１を参照すると、カラー印刷シートバッファを備えた汎用製品プリンタで用いられるような複数のコンポーネントを描画するシステム１００が示される。このシステム１００は、ペーパ・ソース１０２を有し、これは、１枚以上の用紙を有し、カラーエンジン１０４とインサータ１０８と作動的に関連付けられる。ペーパ・ソース１０２からの用紙は２つの経路のうち一方のほうへ進む。たとえば、用紙はペーパ・ソース１０２からカラー印刷エンジン１０４、及びカラー印刷バッファ１０６へと経路指定されてもよく、その後にインサータ１０８に入る。さらに、あるいはまた、用紙はトランスポータ１１６を用いて（カラーエンジン１０４及びカラー印刷バッファ１０６を迂回して直接ペーパ・ソース１０２からインサータ１０８へと経路指定されてもよい。
【０００９】
ペーパ・ソース１０２からインサータ１０８へと直接に経路指定された用紙は白黒印刷エンジン１１０に送られ、白黒ページとカラーページをマージするマージャ１１２を経由して、その後、フィニッシャ１１４へと進み、ユーザに表示するための文書を仕上げる。インサータ１０８によって挿入される前に、用紙はトランスポータ１１６を通過してもよい。一時記憶のためにカラー印刷エンジン１０４を介してカラー印刷バッファ１０６へと経路指定された用紙は、カラー印刷ページがインサータ１０８及びトランスポータ１１８を通過するような時に至って、白黒エンジン１１０によって印刷される他の白黒ページと、マージャ１１２によってマージされる。その他の例によれば、ページがシステム１００のすべてのコンポーネントを通過し、カラー部分と白黒部分の両者を有し得ることは理解されたい。
【００１０】
従来のシステムにおいて、モデル・ベース・プランニングが明示的に資源を取り扱うために使用され得るが、一般には、このような資源は「ユニット資源」の形式であり、タスクは、マルチ容量資源とは対照的に、同時に資源を共有することができず、これらは複数のタスク又はアロケーションによって共有され得る。本明細書中に記載される種々の特徴によれば、プランニング・フレームワークは、異なるタスクがその容量まで所与の資源を共有できるマルチ容量資源を取り扱うために作成されることもある。配分時間が制限されていないこの種のマルチ容量資源は、製造領域における材料の保管及びバッファ位置の提供を容易にすることができ、それゆえ、マルチ容量資源の最適な使用を促進することもできる。マルチ容量資源に対するこのようなモデル・ベース・プランニングの１つの用途は、緊密統合並列印刷（ＴＩＰＰ）に対するプランニングであり、カラー印刷シートバッファ１０６などのシートバッファがマルチ容量資源としてモデル化することができ、混合したカラー用紙と白黒用紙でジョブの印刷を高速化することを可能にする。これを実行する方法の一例は、低速のカラーエンジン１０４を使用してカラー用紙を早期に印刷し、次に、必要に応じて一時記憶バッファ１０６からそれらを迅速に送り出して、高速の白黒エンジン１１０によって印刷された用紙とマージさせる。
【００１１】
たとえば、製造タスクが容量Ｃを備えたマルチ容量資源Ｒに対し資源配分を要求するとき、プランナは、時間的制約条件を新しい配置及びＲ上の前の配置の間に追加し、Ｃ配置までのみが所定の時間のちょうどよい時にオーバーラップできることを保証する。すなわち、Ｃは、資源Ｒの重複するアロケーションの最大許容容量を表わす。プランナは、新しい資源配分を追加して目的関数を考えて最適なプランに導く一方を見いだすためにすべての可能な方法から選択することもできる。たとえば、目的関数がすべてのタスクを完了させるために全体的な終了時間を最小限に抑える場合、プランナは、資源がまだ容量内にあってタスクを可能な限り速やかに終了させ得るように、出来るだけ多くのオーバーラップする資源を配置しようとすることもある。プランナがマルチ容量資源の異なるアロケーション間に時間的制約条件を追加し維持するような方法は、所与の潜在的な解決を除外する必要はなく、完全性若しくは最適性などのプランナによって使用される探索アルゴリズムの特性を変化させる必要はない。
【００１２】
一部の連続的プランニング／再プランニング・システムは、オンライン・プランニング環境において機能し、ＴＩＰＰ環境と類似したリアルタイム制約条件に対応する。しかしながら、このようなシステムはプランニング及びプラン・リペアの各処理を導くためにユーザ定義のローカル・ルールに依存するが、これらは完全性若しくは最適性のいずれも保証しない。対照的に、本明細書中で論じたようにモデル・ベース・プランニング内のマルチ容量資源の取り扱いは一般的であり、ローカル・ルールに依存せず、使用される根本的な探索アルゴリズムの完全性若しくは最適性を侵害しない。
【００１３】
従来のシステム及び方法は、マルチ容量資源を直接に取り扱う汎用プランニング・システムを提供していない。どちらかといえば、マルチ容量資源は一般に、特殊ソルバー若しくはスケジューラを用いて処理される。マルチ容量資源配分を表示する適切な時点と、それらの間の時間的制約条件を追加しようとして、プランニング・アルゴリズム及び本明細書中に記載されたシステムは、目的関数を考えるとマルチ容量資源（結果的に最適解をもたらす）を使用するような最適な方法を決定することができる。
【００１４】
図２は、種々の態様にしたがって、マルチ容量資源の新しい配置を配置の既存のオーダリングに挿入するために使用され得る複数の潜在的プランニング・スケジュールの順列を表わす１セットの事象２００を説明する図である。本明細書中に記載されるように、プランニングは所与の目的を達成するために動作を選ぶことを含み、スケジューリングは、選ばれた動作をいつ開始すべきかを決定することを含む。プランニング及びスケジューリングは、最適プランに関する詳細な情報を得た上での決断をするのを容易にするために統合されてもよい。スケジューリング問題を解消するために使用される制約条件はまた、制約条件ベースのプランニング・システムの一部として利用されることもある。例として、マルチ容量資源に関して、一部の動作は、資源の入手困難さのために同時に実行できないこともある。たとえば、プリンタは、ページが更なる動作を待ち受けるときに蓄積するプリント・バッファ（例えばマルチ容量資源）を有し、バッファは容量が制限されていることもある。複数の制約条件及びアロケーション・オーダリングが格納され評価され得る一時的なデータベース及びネットワークを利用することによって、アロケーション・スケジューリング／プランニング・モデルは、マルチ容量資源の最適な利用のためのモデル・ベース・プランニングを容易にするために実行可能性に対し評価されることもできる。
【００１５】
説明を簡単にするために、（例えば資源Ｒの）資源配分が２の最大容量Ｃを有するように記載されるが、本明細書中に示される種々の特徴と関連していずれの容量も用いることができることを理解されたい。一例によれば、第１のアロケーション（１）は、１つだけの可能なオーダリング、若しくはモデル２０２について描画される。第２のアロケーション（２）が追加される場合、２つの可能なオーダリングがある。即ち、第２のアロケーション（２）がアロケーション（１）の後に挿入されるオーダリング２０４と、アロケーション（２）がアロケーション（１）の前に挿入されるオーダリング２０６である。２つの時間的制約条件（実線矢印）によって、２つのアロケーションが時間的に互いに重複することは妨げられないが、それらは、先に開始したアロケーションが早く終了することを強制することに留意されたい。たとえば、オーダリング２０４は、アロケーション（１）が時間ｓ1に開始し時間ｅ1に終了することを図示するが、一方、アロケーション（２）が時間ｓ2に開始し時間ｅ2に終了することができる。ｓ１からｅ１までの実線矢印はわずかに右側に（正の時間に）傾斜されて、ｓ２が時間的にｓ１の後に発生することを示し、ｅ１からｅ２までの実線矢印は、アロケーション（１）がアロケーション（２）が終了する前に終了するように制約されることを示す。このように、アロケーション（１）及び（２）は、制約が順守されている限り時間的に重複することが可能とされる。
【００１６】
別の例によれば、オーダリング２０４は他のアロケーション（３）を加えることによって拡張されることもあり、その結果、アロケーション(３)を加える３つの可能な順列があり、これらはシナリオ２０８、２１０及び２１２にそれぞれ示される。それぞれのシナリオ（破線矢印）に加えられる新しい制約条件は、いずれのシナリオにおいても３つの連続的なアロケーションが単一の時点に重複することができないことを保証する制約条件である。最適なオーダリングを決定するためにこのような可能な順列を用いるプランナは、新しいオーダリングの中から更なる拡張に対して最適なオーダリングを選択することもできる。
【００１７】
さらに上記の例に対し、マルチ容量資源は２シート容量シートバッファでもよく、資源の２つのアロケーションだけが一定の時間に発生可能とされることを保証するために制約条件が適用され得る。たとえば、２０４の実線矢印は、アロケーション（１）がアロケーション（２）の前に来ることを保証する制約条件を示すこともある。オーダリング２０８によって描画されるように第３のアロケーションが加えられると、時間的オーダリング（直線的破線矢印）と、容量（曲線の破線矢印）を実行するために制約条件が加えられ、ここで、容量制約条件は、２枚のシートのみが一定時間にシートバッファに存在することを保証する。すなわち、ｅ1からｓ3まで拡張する曲線の破線矢印は、アロケーション（１）がアロケーション（３）が開始する前に終了する制約条件を表示する。このようにして、オーダリング２０８は、最初のシート（１）が、第２のシート（２）がそれぞれの開始時間ｓ2にバッファに入る前の開始時間ｓ1にバッファに入り、第２のシートがｅ2でバッファから出る前に終了時間ｅ1にシートバッファから出ることを示している。同様に、シート（３）は、シート（２）がバッファに入るまでバッファに入らないこともあり、シート（２）がバッファから出るまでバッファから出ないこともある。曲線の破線矢印は、資源の２シート最大アロケーションを実行するために、シートの１枚がシートバッファから出るまでシートバッファに入らないようにさらに制約する。
【００１８】
オーダリング２１０及び２１２は、シート（３）に対する他の可能な挿入地点を図示する。オーダリング２１２に関して、実線の曲線矢印は、オーダリング２０６に示される制約条件を表示し、それは、シート（３）がシート（２）及び（１）の間に挿入されるときに冗長的になることがある。記憶装置を維持する見地から、このような冗長的制約条件は、内部の記憶空間を最小化するために、例えば制約条件データベースから削除されることもある。さらに、あるいはまた、冗長的制約条件は、一般に費用がかかる削除動作と関連付けられる計算上の諸経費を回避するために、制約条件データベースに残されることもある。さらにまた、モデル２０８、２１０及び２１２などの複数のモデルが、処理時間を最小化することが望ましいとされる場合、並行して（例えば、むしろ連続的に）評価されることがあることを理解されたい。多数のモデル及び／又はオーダリング順列が最適化の目的のために同時に評価され、記述された特徴が上記の例に関して記載されたように３つのモデルに限定されないこともまた理解されたい。
【００１９】
図３は、本明細書中に記載される１つ以上の特徴にしたがって、マルチ容量資源に対するアロケーション・オーダリングをプランニングするための方法３００の説明図である。３０２において、マルチ容量資源の既存のアロケーションのオーダリングが決定及び評価され得る。たとえば、マルチ容量資源は、Ｎ枚（Ｎは整数である）のシートの最大容量を有するシートバッファであってもよい。３０４において、新しいアロケーション（例えばページなど）に対する挿入地点が選択されることもある。図２に関して上記したような時間的制約条件は３０６において掲示(post)されてもよい。たとえば、第１の時間的制約条件、すなわちアロケーションに対する先入先出オーダリングを要求することが加えられ、別のアロケーションの前にマルチ容量資源の使用を開始するアロケーションは、別のアロケーションが資源の使用を完了する前に資源を使用することを終了するように制約されることもある。第２の制約条件は、マルチ容量資源が最大容量を超えないように保証することに関することがある。上述した制約条件が事実上例示的であり、所与のプランニング・セッションに対して掲示され得る制約条件の数、又は、制約条件がマルチ容量資源のアロケーションを組織化するように動作する方法を制限することが意図されないことを理解されたい。
【００２０】
３０８において、選択された挿入地点における新しいアロケーションの挿入が掲示された制約条件と対立する（例えば、制約条件の失敗をもたらす）かに関して判断がなされる。掲示の失敗が存在しないことが判断されると、３１０においてアロケーションの新しいオーダリング(新しいアロケーションが挿入される)がアロケーションの実現可能なオーダリングとして記録され、この方法は、挿入地点の選択、制約条件の掲示、オーダリング評価の更なる反復に対して３０４に戻ることもある。３０８において１つ以上の掲示された制約条件が失敗したと判断されると、３１２において新しいオーダリングが実現不能であると記録された後で、この方法は、新しいアロケーションに対する異なる挿入地点のある別のオーダリングの評価に対して３０４に戻ることもある。このようにして、アロケーション・オーダリングの複数の順列は、マルチ容量資源に対するアロケーションの所望のオーダリングの選択を容易にするために評価されることもできる。さらに、新しいアロケーションに対する異なる挿入地点を有する異なるアロケーション・オーダリングの評価が図３から図５における反復方法を介して連続的に発生するものとして描画されているが、複数のアロケーション・オーダリングは、所与のアロケーション・セットの種々のオーダリング順列を評価することと関連して処理時間を軽減すると同時に評価され得る。たとえば、図２におけるアロケーション（３）の追加に対するモデル２０８、２１０及び２１２の３つの順列は処理時間を最小化するために並行して評価され得る。
【００２１】
図４は、本明細書中に開示された１つ以上の特徴に従って、マルチ容量資源のアロケーションなどの一連の事象の複数の可能なオーダリングを評価し、最適なアロケーションのオーダリングを選択するための方法４００を図示する。４０２において、マルチ容量資源に対する既存のアロケーションの実在のオーダリングは、オーダリングへの新しいアロケーションに対する挿入地点を選択することを容易にするために評価されることもあり、これは４０４で起こることがある。４０６において、１つ以上の時間的制約条件は特定され、これは、相対的なアロケーションのタイミングを制御する。４０８では、１つ以上の特定された制約条件が失敗したかどうか（例えば選択された挿入地点が結果として有効なオーダリングになるかどうか）に関して判断がなされる。４０８における判断が、特定された制約条件がいずれも侵害されなかったことを表示する場合、４１０において新しいオーダリングが実現可能なオーダリングとして記録され、この方法は、新しいアロケーションに対する異なる挿入地点を有する別のオーダリングの評価に対して４０４に戻ることがある。１つ以上の特定された制約条件が、選択挿入地点によって侵害されていると判断されると、新しいオーダリングが４１２において実現不能として記録され、この方法は、異なる選択挿入地点を備えた別のオーダリングの評価のために４０４に戻ることがある。
【００２２】
４１４において、実現可能であると記録されている新しいオーダリングに対して比較が実行されることがある。最適なオーダリングは、４１６において実行のために選択されスケジューリングされることもある。一例によれば、実現可能であると記録されている２つのオーダリングは、どれが所定の測定基準（メトリック）に対してより好ましい値を有するかを決定するために比較され得る。たとえば、第１の実現可能なオーダリングは、特定された制約条件のセットを考慮すると実行時間がより短縮することもあり、それゆえ第２の実現可能なオーダリングにわたって選択されることもある。実現可能なオーダリングが別の実現可能なオーダリングにわたって選択される測定基準が実行期間に制限されず、むしろ２つ以上の実現可能なオーダリングを比較し、測定基準に基づいて最適オーダリングを決定するための好適な測定基準でもよいことは当業者には明白である。
【００２３】
図５は、マルチ容量資源に対するモデル・ベース・プランニングを容易にするために時間的制約条件を利用するための方法５００の説明図である。この図によれば、５０２において、挿入地点は、マルチ容量資源アロケーションの既存のオーダリングにおいてマルチ容量資源の新しいアロケーションに対して選択されることもできる。たとえば、既存のアロケーションのオーダリングは、絶対時間よりもむしろ時間的変数に関して定義すればよい。それゆえ、新しいアロケーションが検出される場合、挿入地点の選択は他のアロケーションのタイミングと相対的であればよく、必ずしも特定の時間に相対的でなくてもよい。５０４において、第１のセットの時間的制約条件は掲示され、例えば、先入先出（ＦＩＦＯ）制約条件などであり、これは、別のアロケーションが終了する前に開始するアロケーションがその他のアロケーションの前に終了することを保証する。５０４において掲示されるＦＩＦＯ制約条件は、オーダリングにおいて実在のアロケーションに対して新しいアロケーションの挿入地点を付加的に表示することもできる。
【００２４】
５０６において、第２のセットの時間的制約条件は、所与の時間に、マルチ容量資源に関連付けられる最大容量を超えないことを保証するために加えられることもある。たとえば、マルチ容量資源が、５シートの最大容量を備えたプリンタ装置内のシートバッファである場合、５０６において掲示される制約条件は、現在のシートより前にある第５のシート(例えば新しいアロケーション）が、現在のシートがバッファに入る前にシートバッファから出ていることを保証できる。５０８において１つ以上の制約条件が失敗したかどうかに関して判断がなされ得る（たとえば、新しいアロケーションに対する選択挿入地点が、掲示された制約条件を考慮して実現可能でないオーダリングになるという結果になるかどうかの判断）。もしそうでない場合、５１０において、新しいオーダリングが実現可能オーダリングとして記録（データベースにおいて格納）され得る。１つ以上の掲示された制約条件が失敗すると、５１２において新しいオーダリングが実現不能であると記録され得る。
【００２５】
図６は、種々の態様による、マルチ容量資源アロケーションに対するモデル・ベース・プランニングの実行を容易にするシステム６００の説明図である。このシステム６００は、マルチ容量資源６０４、及び１つ以上のアロケーション６０６1−６０６N（以下、これらを集合的に「アロケーション６０６」と称する）を評価するプランナ６０２を有し、アロケーション６０６の既存のオーダリングを識別する。システム６００が、電子画像形成環境及び電子写真環境などの種々の環境を含み、さらに／あるいはそれらの環境において利用されることができ、それにより、１つ以上の電子写真コンポーネントが電子写真手順若しくは機能を実行するために利用される。プランナ６０２は、プラン生成器６０８、プラン・テスタ６１０、制約条件ライブラリ６１２を有し、図１に関して上述されたような印刷プラットフォームなどの機械と関連付けられてもよい。一部の態様によれば、（６０１によって表示される）スケジューラには、プランナ６０２に関して記載されたようなプランニング機能が備えられていることもある。たとえば、スケジューラは、マルチ容量資源を処理するためにプランナ６０２と作動上関連付けられ、マルチ容量資源に近似するように一般的な理論的プランナによって処理される連続的数量を利用することがある。
【００２６】
プラン生成器６０８は、先の図面に関して詳述されたようなマルチ容量資源の新しいアロケーションに対する挿入地点を選択することもあり、制約条件ライブラリ６１２にアクセスして、１つ以上の制約条件を特定し挿入された新しいアロケーションを備えたアロケーションのオーダリングの実行を制御することもある。たとえば、制約条件は、時間的制約条件（例えばＦＩＦＯ、ＬＩＦＯなど）、容量制約条件（例えば所与の時間におけるＮ個のアロケーションの最大数であり、Ｎは整数である）などを有することもある。プラン・テスタ６１０は、新しいアロケーションの挿入後、プラン生成器６０８によって掲示された制約条件に対してアロケーションの所与のオーダリングを評価して、所与のアロケーション・オーダリングモデルが有効であるかどうかを判断する。有効モデル６１６は、プランナ６０２によって後における評価及び／又は実施のためにメモリ６１４に格納されることもある。
【００２７】
一例によれば、ＦＩＦＯマルチ容量資源上に配分するために非決定論的擬似コードは、以下を有するが、これらに限定されない。
１．既存のアロケーション（ｓ1，ｅ1）、（ｓ2,ｅ2）の既存のオーダリングリストを考慮して、新しいアロケーション、即ち、地点（ｓi，ｅi）を挿入するために位置を選択する。
２．配列を実施するために、時間的制約条件ｓi-1→ｓi，ｅi-1→ｅi，ｓi→ｓi+1及びｅi→ｅi+1を掲示する。
３．(ｉ−Ｃ) < j < (ｉ＋Ｃ)であるように、すべてのｊに対して時間的制約条件ｅj→ｓj+Cを掲示して、すべてのアロケーションに対し、Ｃ番目のそれが開始する前に終了される（これらのアロケーションのどれも存在しない場合、その制約条件を無視する）。
４．これまでの掲示のいずれも失敗しなかった場合、そのオーダリングを実現可能として記録する。
【００２８】
上記の例は、プランニング・タスクが容量Ｃを備えたマルチ容量ＦＩＦＯ資源Ｒを要求するときに資源アロケーション６０６を追加するための擬似コードを説明し、ここでＣは資源Ｒの重複する（即ち、同時の）アロケーションの最大許容数を表示する。それぞれのアロケーションは、互いに対してこれまで適切に制約されることが仮定される一対の時間地点（開始、終了）によって表示される（例えば固定持続時間によって分離される）。プランナは、新しいアロケーションを最初の若しくは最後のアロケーションとして追加することに加えて、２つの連続的な既存のアロケーション間に新しいアロケーションを挿入するすべての可能な順列を評価することもできる。それは、新しいアロケーションのＣアロケーション内のすべてのアロケーション間に制約条件を追加してＣによって分離される指標を備えた２つのアロケーションが重複しないことを保証する。このようにして、所与の時間において資源ＲのＣアロケーション以下である必要がある。「選択」動作が結果として多くの可能性をもたらすことになり、これらはそれぞれ、所有する時間的制約条件の独立セットで分離して探索されるように、擬似コードが非決定論的方式で書き込まれることに留意されたい。「掲示」動作は、時間的制約条件が非一貫性になったことを検出してもよいが、この場合、検索されている可能性は放棄される（例えば実現不能であると記録される）。残りの実現可能なオーダリングは検索キューに追加されることもある。プランナは、すべての他のプランニング制約条件を考慮し、所与の目的関数にしたがってＲ上の最良のアロケーションのオーダリングを選択する（例えば製造プラントの処理能力を最大にし、実行時間を最小化する）。上記したことは、非ＦＩＦＯ制約条件、例えば、後入先出（ＬＩＦＯ）、ランダムアクセス、及び他のタイプの可能とされる資源をサポートするために容易に修正変更され得ることを理解されたい。
【００２９】
上記に開示され、及びその他の特徴と機能、若しくはそれらの代替物が多くの他の異なるシステムや用途に望ましく組み合わせされ得ることを理解されたい。さらに、種々の現在予見できない若しくは予期されない代替手段、修正、変更又はその点における改善は、当業者によってその後実行されることもでき、添付の請求の範囲によって包含されることもまた意図される。
【図面の簡単な説明】
【００３０】
【図１】カラー印刷シートバッファを備えた汎用製品プリンタで利用されるような複数のコンポーネントを描画したシステムの説明図である。
【図２】種々の態様に従って、マルチ容量資源の新しいアロケーションを既存のアロケーションのオーダリングに挿入するために利用され得る複数の潜在的なプランニング・スケジュールの順列を表示する１セットの事象の説明図である。
【図３】本明細書中に記載される１つ以上の特徴に従って、マルチ容量資源のアロケーション・オーダリングをプランニングするための方法の説明図である。
【図４】本明細書中に開示される１つ以上の特徴に従って、マルチ容量資源の配分などの１セットの事象の複数の可能なオーダリングを評価し、最適なアロケーション・オーダリングを選択するための方法の説明図である。
【図５】マルチ容量資源に対するモデル・ベース・プランニングを容易にするために時間的制約条件を利用するための方法の説明図である。
【図６】種々の態様に従って、マルチ容量資源の配分のためのモデル・ベース・プランニングの実行を容易にするシステムの説明図である。
【符号の説明】
【００３１】
６００  システム
６０２  プランナ
６０８  プラン生成器
６１０  プラン・テスタ
【図１】
0005433166.tif 000002
【図２】
0005433166.tif 000003
【図３】
0005433166.tif 000004
【図４】
0005433166.tif 000005
【図５】
0005433166.tif 000006
【図６】
0005433166.tif 000007