(57)【特許請求の範囲】
【請求項１】
（ｉ）トラバーサを選択し、
（ｉｉ）装置のモデルにもとづいてポリシーのライブラリから該装置に適用可能なポリシーを選択するセレクタを有し、
適用可能なポリシーは構成ポリシーおよび選択ポリシーを含み、
前記トラバーサは（ｉ）モデルトラバーサおよび（ｉｉ）記憶部トラバーサを含み、
前記セレクタは、前記装置の電源をオンにするときに、適用可能な前記ポリシーとして前記構成ポリシーを選択し、前記トラバーサとして前記モデルトラバーサを選択し、
前記モデルトラバーサは、前記構成ポリシーにもとづいて前記装置のモデルをサーチし、有効な予定表のリストを記憶することができ、
前記セレクタは、ジョブを実行するときに、前記適用可能なポリシーとして前記選択ポリシーを選択し、前記トラバーサとして記憶部トラバーサを選択し、
前記記憶部トラバーサは、前記選択ポリシーおよびジョブの記述にもとづいて有効な予定表のリストをサーチし、該ジョブを処理するために該予定表を探すことができ、
前記モデルトラバーサは、サーチアルゴリズムライブラリから前記セレクタによって選択される第１のサーチアルゴリズムを含み、
前記第１のサーチアルゴリズムは、
第１のデータメンバーとしての前記構成ポリシーと、
第２のデータメンバーとしての前記装置のモデルと、
前記モデルトラバーサに有効な予定表を報告するために、前記第１のデータメンバーにもとづいて前記第２のデータメンバーを前記第１のサーチアルゴリズムで定義される順序でサーチするロジックと、
を含み、
前記記憶部トラバーサは、前記サーチアルゴリズムライブラリから前記セレクタによって選択される第２のサーチアルゴリズムを含み、
前記第２のサーチアルゴリズムは、
第１のデータメンバーとしての前記選択ポリシーと、
第２のデータメンバーとしての記憶された有効な予定表の前記リストと、
前記記憶部トラバーサに有効な予定表を報告するために、前記第１のデータメンバーにもとづいて前記第２のデータメンバーを前記第２のサーチアルゴリズムで定義される順序でサーチするロジックと、
を含み、
前記装置はプリンタであり、
前記ポリシーは前記ジョブを処理するために満たさなければならない基準であり、
構成ポリシーは目標とする装置の構成および環境に関するポリシーであり、
選択ポリシーは選択される予定表に関するポリシーであり、
前記装置のモデルは、装置のモジュールおよび装置のモジュールの機能を含む表現であり、
前記モデルトラバーサは、
前記構成ポリシーのすべてにしたがって、可能な予定表が有効であるか否かを判断する前記予定表バリデータと、
前記可能な予定表が有効であると判断された場合に、有効な予定表の前記リストに該可能な予定表を追加するモジュールと、
を備え、
前記記憶部トラバーサは、
有効な予定表の前記リストから選択された可能な予定表が前記選択ポリシーおよび前記ジョブの記述のすべてにしたがっているか否かを判断する予定表バリデータを備え、
ジョブに対する予定表は、ジョブの処理に必要な装置のモジュール並びにモジュールの機能及び制約のスケジュールであり、
前記装置のモデルは、該装置のモジュールおよび該装置のモジュールの機能を含む表現である、
装置内のジョブを処理するために予定表を検出する装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プリント装置用の、プリント装置の複数のモジュールを通る用紙の処理をスケジューリングするためのスケジューラに関する。詳細には、本発明は、プリント装置を構成するために組合わされるプリンタモジュール及び機能の多様なセットに自動的に適応するスケジューラに関する。
【背景技術】
【０００２】
プリント装置を通って処理される用紙は、スケジューリングソフトウェアによって制御されるスケジューラモジュールを用いて各ステージを通してスケジューリングされる。ある手法は、プリントジョブを処理するために満足されなければならない基準を指定するスケジューリングポリシー（例えば、"トレー２の用紙が不足している場合はトレー１を使用"）を用いる。既知の装置では、そのようなポリシーは、プリント装置開発のソフトウェア開発フェーズ中に、スケジューリングソフトウェアの論理として書かれる。ポリシーはスケジューリングソフトウェアの論理としてコード化され、プリント装置の出荷前に、スケジューリングソフトウェアはＲＯＭなどのメモリに記憶される。
【０００３】
スケジューリング規則及びポリシーは、一般的に、開発中の装置のハードウェアに依存する。例えば、スケジューリングソフトウェアの開発者は、開発期間中に、特定の製品のデュプレックス・ペーパーパス（例えば、両面コピーのプリント用）が、最大で８枚の8.5インチ×11インチ用紙を保持できることを知るであろう。デュプレックス・ペーパーパスはノンストップ・ループなので、これは、デュプレックス・ペーパーパスに入る用紙が、8ピッチ後に再び現れることを意味する。1ピッチは、１つの画像を作成するのに要する時間である。デュプレックス・ループの長さが変わるようにハードウェアが変更された場合は、ソフトウェアも変更される必要があろう。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許第５，７０１，５５７号明細書
【特許文献２】米国特許第５，６９６，８９３号明細書
【特許文献３】米国特許第５，７１０，６３５号明細書
【特許文献４】米国特許第５，６０４，６００号明細書
【特許文献５】米国特許第５，１２９，６３９号明細書
【非特許文献】
【０００５】
【非特許文献１】フロイダー（Ｆｒｅｕｄｅｒ）、ウォレス（Ｗａｌｌａｃｅ）、「部分的な制約の満足（Ｐａｒｔｉａｌ  Ｃｏｎｓｔｒａｉｎｔ  Ｓａｔｉｓｆａｃｔｉｏｎ）」、人工知能（Ａｒｔｉｆｉｃｉａｌ  Ｉｎｔｅｌｌｉｇｅｎｃｅ）、１９９２年、Ｖｏｌ．５８、頁２１〜７０
【非特許文献２】フリーマン−ベンソン（Ｆｒｅｅｍａｎ−Ｂｅｎｓｏｎ）、マロニー（Ｍａｌｏｎｅｙ）、ボーニング（Ｂｏｒｎｉｎｇ）、「増分的制約解決器（Ａｎ  Ｉｎｃｒｅｍｅｎｔａｌ  Ｃｏｎｓｔｒａｉｎｔ  Ｓｏｌｖｅｒ）」、ＡＣＭ通信（Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ＡＣＭ）、１９９０年、Ｖｏｌ．３３、Ｎｏ．１、頁５４〜６３
【非特許文献３】マックワース（Ｍａｃｗｏｒｔｈ）、「関係のネットワークにおける一貫性（Ｃｏｎｓｉｓｔｅｎｃｙ  ｉｎ  Ｎｅｔｗｏｒｋｓ  ｏｆ  Ｒｅｌａｔｉｏｎｓ）」、人工知能（Ａｒｔｉｆｉｃｉａｌ  Ｉｎｔｅｌｌｉｇｅｎｃｅ）、１９９７年、Ｖｏｌ．８、頁９９〜１１８
【非特許文献４】ミントンら（Ｍｉｎｔｏｎ，  Ｓ．  ｅｔ  ａｌ．）、「矛盾の最小化：制約の満足及びスケジューリング問題のためのヒューリスティックな修復法（Ｍｉｎｉｍｉｚｉｎｇ  Ｃｏｎｆｌｉｃｔｓ：  Ａ  Ｈｅｕｒｉｓｔｉｃ  Ｒｅｐａｉｒ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｃｏｎｓｔｒａｉｎｔ  Ｓａｔｉｓｆａｃｔｉｏｎ  ａｎｄ  Ｓｃｈｅｄｕｌｉｎｇ  Ｐｒｏｂｌｅｍｓ）」、人工知能（Ａｒｔｉｆｉｃｉａｌ  Ｉｎｔｅｌｌｉｇｅｎｃｅ）、１９９２年、Ｖｏｌ．５８、頁１６１〜２０５
【非特許文献５】デクター（Ｄｅｃｈｔｅｒ）、「制約処理のための強化スキーム：バックジャンプ、学習、及びカットセット分解（Ｅｎｈａｎｃｅｍｅｎｔ  Ｓｃｈｅｍｅｓ  ｆｏｒ  Ｃｏｎｓｔｒａｉｎｔ  Ｐｒｏｃｅｓｓｉｎｇ：  Ｂａｃｋｊｕｍｐｉｎｇ，  Ｌｅａｒｎｉｎｇ，  ａｎｄ  Ｃｕｔｓｅｔ  Ｄｅｃｏｍｐｏｓｉｔｉｏｎ）」、人工知能（Ａｒｔｉｆｉｃｉａｌ  Ｉｎｔｅｌｌｉｇｅｎｃｅ）、１９８９年、Ｖｏｌ．４１、頁２７３〜３１２
【非特許文献６】ガマら（Ｇａｍｍａ，ｅｔ  ａｌ．）、「設計パターン：再使用可能なオブジェクト志向ソフトウェアの要素（Ｄｅｓｉｇｎ  Ｐａｔｔｅｒｎｓ：  Ｅｌｅｍｅｎｔｓ  ｏｆ  Ｒｅｕｓａｂｌｅ  Ｏｂｊｅｃｔ−Ｏｒｉｅｎｔｅｄ  Ｓｏｆｔｗａｒｅ）」、アディソン−ウェズリー（Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ  Ｐｕｂｌｉｓｈｅｒｓ）、１９９５年
【非特許文献７】ジェントら(Ｇｅｎｔ，ｅｔ  ａｌ．）、「制約満足問題のためのダイナミックに変化する順序付けヒューリスティックの経験的な研究（Ａｎ  Ｅｍｐｉｒｉｃａｌ  Ｓｔｕｄｙ  ｏｆ  Ｄｙｎａｍｉｃ  Ｖａｒｉａｂｌｅ  Ｏｒｄｅｒｉｎｇ  Ｈｅｕｒｉｓｔｉｃｓ  ｆｏｒ  ｔｈｅ  Ｃｏｎｓｔｒａｉｎｔ  Ｓａｔｉｓｆａｃｔｉｏｎ  Ｐｒｏｂｌｅｍ）」、制約プログラミングの原理及び実践（Ｐｒｉｎｃｉｐｌｅｓ  ａｎｄ  Ｐｒａｃｔｉｃｅ  ｏｆ  Ｃｏｎｓｔｒａｉｎｔ  Ｐｒｏｇｒａｍｍｉｎｇ）、１９９６年、ＬＮＡＩ  Ｓｅｒｉｅｓ  ＃１，１１８、頁１７９〜１９３
【発明の概要】
【発明が解決しようとする課題】
【０００６】
既知のシステムでは、スケジューリングポリシーは、スケジューリングソフトウェアの論理へと、予めコード化されるので、スケジューリングソフトウェアは静的で、更新が困難であり、他のプリント装置での再使用はできない。例えば、プリント装置はモジュール設計され、給紙モジュール、マーカ（マーキング）モジュール、及びスタッカモジュールを用いることがあるが、製品リリース後に、新たな機能(capability)を追加するためにマーカモジュールが再設計されるかもしれない。たとえ、モジュール自体は互換性があるように設計されていても、スケジューリングソフトウェアは書き直されなければならない。
【課題を解決するための手段】
【０００７】
本発明の一態様は、装置内のジョブを処理するために予定表を検出する装置であって、（ｉ）少なくとも１つのトラバーサを選択し、（ｉｉ）装置のモデルにもとづいてポリシーのライブラリから該装置に適用可能なポリシーを選択する、セレクタを有し、適用可能なポリシーは構成ポリシーおよび選択ポリシーの少なくとも一方を含み、少なくとも１つの前記トラバーサは（ｉ）モデルトラバーサおよび（ｉｉ）記憶部トラバーサの少なくとも一方を含み、前記セレクタは、適用可能な前記ポリシーとして前記構成ポリシーを選択し、少なくとも１つの前記トラバーサとして前記モデルトラバーサを選択し、前記モデルトラバーサは、前記構成ポリシーにもとづいて前記装置のモデルを横断し、有効な予定表のリストを記憶することができ、前記セレクタは、前記適用可能なポリシーとして前記選択ポリシーを選択し、少なくとも１つの前記トラバーサとして記憶部トラバーサを選択し、前記記憶部トラバーサは、前記選択ポリシーおよびジョブの記述にもとづいて有効な予定表のリストを横断し、該ジョブを処理するために該予定表を探すことができ、前記モデルトラバーサは、サーチアルゴリズムライブラリから前記セレクタによって選択される第１のサーチアルゴリズムを含み、前記第１のサーチアルゴリズムは、第１のデータメンバーとしての前記構成ポリシーと、第２のデータメンバーとしての前記装置のモデルと、前記モデルトラバーサに有効な予定表を報告するために、前記第１のデータメンバーにもとづいて前記第２のデータメンバーを横断するロジックと、を含み、前記記憶部トラバーサは、前記サーチアルゴリズムライブラリから前記セレクタによって選択される第２のサーチアルゴリズムを含み、前記第２のサーチアルゴリズムは、第１のデータメンバーとしての前記選択ポリシーと、第２のデータメンバーとしての記憶された有効な予定表の前記リストと、前記記憶部トラバーサに有効な予定表を報告するために、前記第１のデータメンバーにもとづいて前記第２のデータメンバーを横断するロジックと、を含み、前記装置はプリンタであり、前記ポリシーは前記ジョブを処理するために満たさなければならない基準である。
【図面の簡単な説明】
【０００８】
【図１】本発明の機能ブロック図である。
【図２】本発明に従った代表的装置グラフ（装置モデル）の図である。
【図３】本発明に従ったモニタのフロー図である。
【図４】本発明の予定表実証処理のフロー図である。
【図５】本発明のモデル横断処理のフロー図である。
【図６】本発明の記憶部横断処理のフロー図である。
【図７】本発明の戦略選択処理のフロー図である。
【図８】本発明のパワーアップシーケンスのフロー図である。
【図９】本発明の選択時シーケンスのフロー図である。
【図１０】本発明に従った簡略化された装置モデルを示す図である。
【図１１】本発明に従ったバックトラックアルゴリズムの前方サーチ部のフロー図である。
【図１２】本発明に従ったバックトラックアルゴリズムの後方サーチ部のフロー図である。
【図１３】本発明に従った構成可能な横断アルゴリズムを有するモデルトラバーサのフロー図である。
【図１４】戦略設計パターンに従って構成可能なアルゴリズムフラグメントを有する記憶部トラバーサのフロー図である。
【発明を実施するための形態】
【０００９】
添付の図面を参照して本発明を説明する。
【００１０】
本発明のスケジューラは、プリンタを通るプリントジョブを、柔軟且つ拡張可能な方法でスケジューリングする。最もシンプルな実施の形態では、本発明は、パワーアップ時に操作され、装置モデルを処理して有効な用紙予定表リストを生成するモデルトラバーサ（横断器）と、有効な用紙予定表リストを処理して所望のプリントジョブの処理に適した１つの予定表を選択する記憶部トラバーサとを含む。モデルトラバーサ及び記憶部トラバーサは両方とも、予定表バリデータ（実証器）を用いて、一般的にデータファイルとして記憶されているプリントスケジューリングポリシーに照らして予定表をチェックする。
【００１１】
プリントスケジューリングポリシーは、選択された予定表がプリントジョブを処理するために満たさなければならない基準であり、用紙１枚のプリントジョブに対する予定表は、用紙の処理に必要な装置モジュール並びにモジュールの機能及び制約のスケジュールである。ポリシーは、装置非依存型又は装置依存型であり得る。装置非依存型ポリシーは、全製品にわたって共通となるポリシーである。予定表から出力される用紙の特性は要求されるプリント用紙の特性とマッチしなければならないというマッチングの要件は、装置非依存型基準の一例である。装置依存型ポリシーは、特定の製品の所望の特徴を優先するポリシーである。例えば、大容量給紙装置を有することも有さないこともあるプリンタは、大容量給紙装置を有する場合には大量のジョブに対して大容量給紙装置の使用を優先するが、少量のジョブに対しては優先しないポリシーを有するように設計され得る。しかし、他のプリンタは、大量のジョブに対して、たとえ有していても大容量プリンタを優先しないポリシーを有するように設計され得る。そのような場合には、各製品のポリシーが異なることがある。
【００１２】
本発明は、パワーアップ時スケジューリング処理、及びジョブ実行時スケジューリング処理を提供する。パワーアップ時スケジューリング処理（例えば図８）は、戦略セレクタ(Strategy Selector)を用いてモデルトラバーサを選択し、目標とする装置の構成及び環境に基いてポリシーのライブラリから構成ポリシーを選択し、モデルトラバーサを用いて、選択されたポリシーに従って装置モデルを処理し、有効な予定表のリストを作成する。
【００１３】
ジョブ実行時スケジューリング処理（例えば図９）は、記憶部トラバーサ（ステップＳ５２）、プリントジョブ明細、及び可能な実行時選択ポリシー（例えば実行時基準）を用いて、装置モデルに基き、予定表記憶部に記憶されている有効予定表リストをサーチし、目標の装置でプリントジョブを処理できる予定表を見つける。予定表は、プリントジョブの処理に必要な特定のモジュール及び機能を含む。パワーアップ時に、戦略セレクタによって特定の記憶部トラバーサ（ライブラリには複数の記憶部トラバーサが存在し得る）が選択される（ステップＳ５１）か、又は可能であれば、実行時に、特別な戦略セレクタが選択される。
【００１４】
本発明は、特に、プリント装置におけるプリントジョブのための柔軟且つ拡張可能なスケジューラ構成処理に適用できる。しかし、本発明はより広範な用途を有することが認識されよう。例えば、"プラグアンドプレイ(plug and play)"モジュール互換性を達成しつつ、ジョブの実行のために個々のモジュールをコーディネートする必要がある、自動化された工場生産技術から自動化された農業生産技術までの任意の装置に、本発明が好ましく用いられよう。本発明は、（１）装置の自動的な記述を取得し、（２）一般的には装置モジュールのコーディネーションによって記述されるが本明細書では予定表と呼ぶ、操作の装置モードのリストを（適用可能なポリシーに基いて）決定し、（３）装置によって実行されるジョブに適用可能な装置モードを選択するための、処理を提供する。
【００１５】
プリント装置の装置コントローラは、電子的装置モデル（ＭｏＭ）を作成及び記憶する。ＭｏＭは、装置モジュール及びそれらの機能等の表現を含む階層的データ構造である。
【００１６】
本明細書に参照として援用するウェブスターら(Webster, et al.)の特許文献１は、コントローラ及び複数のモジュールを有する画像処理装置並びに画像処理装置の構成を定義する方法を述べている。本明細書に参照として援用するフロムハーツら(Fromherz, et al.)の特許文献２は、物理的要件、ソフトウェアインタフェースの要件、及び内部リソースの要件、並びに挙動モデルで構成モデルを指定して、ワークユニットの記述、ワークユニットの変換、時限式イベント、リソース割当て、制約、及び制限で、構成要素の機能を記述する、プリント装置のモデリング方法を述べている。
【００１７】
プリントジョブ明細は、用紙サイズ及び、片面又は両面プリントのどちらが要求されているか等の、そこにプリントされるタイプを記述する。本明細書に参照として援用するウェブスターらの特許文献３は、プリントジョブ又はドキュメントの表現、及びその表現をコントローラがジョブのプリントに用いることが可能なものに変換し得る方法を述べている。本明細書に参照として援用するウェブスターの特許文献４は、装置非依存型で"即プリント可能(print-ready)"なプリントジョブ又はドキュメントの表現を述べている。本明細書に参照として援用するデホリティ(DeHority)の特許文献５は、プリントジョブの要件をプリンタの機能と比較するプリンタ構成制御システムを述べている。
【００１８】
図１では、プリント装置１０は、複数のモジュール１２、１４、１６、マークファシリティ・インタフェース(Mark Facility Interface)１８（概括的にオペレータインタフェース）、及び装置コントローラ２０を含む。例えば、一般的な装置は、装置に供給する用紙を提供する給紙モジュール１２と、用紙に画像をマーキングするマーカモジュール１４と、出力された用紙をスタックするスタッカモジュール１６とを含む。プリント装置は、装置モデル（ＭｏＭ）によって記述される。各モジュールは１つ以上の機能によって特徴づけられ、各機能は対応する制約によって特徴づけられる。全てのモジュール、機能、及び制約は、コンポーネント記述言語（ＣＤＬ）を用いて記述及びコード化されるのが好ましい。ＣＤＬは、装置コントローラの再プログラムを必要とせずに、異なる装置間の異なるモジュールの互換を容易にするように、標準化されている。各モジュールは、好ましくは、読取り専用メモリ（ＲＯＭ）２４、及び再プログラム可能不揮発性フラッシュメモリ又は消去可能プログラム可能読取り専用メモリ（ＰＲＯＭ）２６を有するメモリである、モジュール記述メモリ２２を含む。各モジュールは、メモリ２２へのアクセスを制御するための装置モジュールインタフェース（Machine Module Interface:ＭＭＩ）と呼ばれるインタフェース２８（例えばメモリコントローラ又は汎用プロセッサ若しくはマイクロプロセッサ）を含み、各モジュールは、モジュールの状態を感知するための（例えば"用紙不足"インジケータ）、インタフェース２８に接続された１つ以上のマイクロスイッチ３０又はセンサを含み得る。各モジュールはＣＤＬを用いて完全に記述され、記述は、装置コントローラによるアクセスのために、モジュール記述メモリ２２に記憶される。
【００１９】
図２では、装置モデル（ＭｏＭ）は、装置モジュール＃１及び装置モジュール＃２を含む。装置モジュール＃１は、それが処理可能な消耗品のリストと、入力ポート及び出力ポートのリストを含む。装置モジュール＃１は機能のリストも含み、各機能は、処理できる各消耗品に対する制約（例えば寸法）、並びに入力ポート及び出力ポートに参照される通信の入力及び出力の仕様を含む。
【００２０】
給紙モジュールは、一般的に、給紙モジュールが供給できる用紙を保持するための複数のトレーを含み、総称的にそれらを機能と呼ぶ。例えば、給紙モジュールは、8.5インチ×11インチ用紙用のトレー１と、Ａ４用紙用のトレー２と、8.5インチ×13インチから8.5インチ×14インチまでのサイズの用紙に合うように調節可能なトレー３とを含み得る。この例示的なケースでは、給紙モジュールはこれらの３つの機能を有することになる。
【００２１】
各機能は制約に関して記述される。例えば、トレー１（8.5インチ×11インチ用紙）については、メモリ２２は、"DIM（寸法）.x=850; DIM.y=1100"又は同等のコードとして、その中に、制約をコード化してもよい。トレー２（Ａ４用紙）については、メモリ２２は、"DIM.x=826; DIM.y=1171"又は同等のコードとして、制約をコード化できよう。調節可能トレー３（8.5インチ×13インチ又は8.5インチ×14インチのいずれかの用紙）については、メモリ２２は、長さｙが13インチから14インチの間に制限されることを示すために、"DIM.x=850; 1300<DIM.y<1400"又は同等のコードとして、制約をコード化できよう。より普遍的なトレーの制約は、長さｙが11インチから14インチの間に制限されることを示すために、"DIM.x=850; 1100<DIM.y<1400" 又は同等のコードとして、コード化できよう。トレーの寸法がある範囲の値をとることが可能であることを示す制約に遭遇した場合は、装置コントローラ２０は、どこか他の場所を見て最終的に決定された値を見つけなければならない。例えば、コントローラ２０は、モジュール記述メモリ２２のフラッシュメモリ部２６から報告される情報を見ることができる。オペレータが、トレー内の選択可能フェンスを、正しいサイズの用紙を適切なアラインメントで保持するように設定する場合には、オペレータは、プリント装置の別のモジュール（ＰＳＩＰモジュール）を用いて、用紙の属性（例えば用紙のサイズ又は色）を指定する。ＰＳＩＰモジュールは、これらの属性を、装置モジュールインタフェース２８（ＭＭＩ２８）を介して給紙モジュール１２に報告する。そこから、ＭＭＩは情報をフラッシュメモリ２６に記憶し、装置コントローラ２０に"消耗品"（この場合は用紙）の属性の更新に関する情報を与える。或いは、マイクロスイッチ３０が可動フェンスを感知してトレー内の用紙サイズをＭＭＩ２８に示し、ＭＭＩが装置コントローラ２０に"消耗品" 属性の更新に関する情報を与える。
【００２２】
ホームオフィスはトレーが１つか２つのプリンタを有するかもしれない。中規模のプリントショップはトレーが３つか４つの給紙モジュールを有するかもしれない。しかし、大規模のプリントショップは、20個以上のトレー、又は、個々に複数のトレーを有する５、６個の給紙モジュールを望むかもしれない。装置におけるモジュール数及び給紙モジュールにおけるトレー数は様々であろう。用紙のサイズ、重量、及び用紙タイプ（例えば、透明フィルム又は紙、用紙の色、レターヘッド、タブ付きシート、封筒等）によって、たちまち20個以上のトレーが必要になろう。用紙サイズなどといったトレー機能に対する幾つかの制約は固有の特徴であり、これらは、モジュール記述メモリ２２のＲＯＭ部２４に記憶される機能及び制約に記述される。
【００２３】
しかし、トレーの固有の特徴は、装置オペレータがどのようにトレーに（用紙を）入れるかを定めないであろう。例えば、トレーに入れられる用紙の色はトレーの固有の特徴ではない。これらの、オペレータが機能に対して課す制約については、オペレータがモジュールの制約をパーソナル化しなければならない。オペレータは、用紙重量及び用紙のタイプ（例えば、透明フィルム又は紙、用紙の色、レターヘッド、タブ付きシート、封筒等）をパーソナル化できる。装置のオペレータは、これらの選択をプリント装置の別のモジュール（ＰＳＩＰモジュール）を介して装置に入力して、トレー内の用紙のパーソナル化属性を指定する。
【００２４】
ＰＳＩＰは、装置のオペレータが、プリンタのパーソナル化、診断の開始、ジョブの提出等のために用いるインタフェースである。ＰＳＩＰモジュールは、装置コントローラの全体的なワークフローを上流に向かって処理する、プリントシステムのソフトウェアコンポーネントである。ＰＳＩＰモジュールは、装置モジュールインタフェース２８（ＭＭＩ２８）を介して給紙モジュール１２にパーソナル化属性を報告する。そこから、ＭＭＩは情報をフラッシュメモリ２６に記憶し、装置コントローラ２０に"消耗品"の属性の更新に関する情報を与える。
【００２５】
同様に、スタッカモジュール１６の機能及び制約は、スタッカモジュールにおいて使用可能な丁合い、及び綴じ又はホチキス止めパターンを定義するであろう。機能は、サイズの制約を有する特定のスタッカトレーを含み得る。スタッカモジュールは、左上の角のホチキス止め、又は左余白若しくは上余白に２回のホチキス止めが可能であるかもしれない。シートの向きを横又は縦にしてホチキス止めするバリエーションも可能であろう。先進的な機能としては、他の綴じ技術、シュリンク包装、様々な折り方の形式（新聞セクションのように）等が挙げられよう。スタッカモジュールの機能及び制約は、ＣＤＬで記述され、モジュール記述メモリに記憶される。
【００２６】
マーカモジュール１４の機能及び制約は、マーカモジュールから入手可能なプリントオプションを定義するであろう。例えば、マーカモジュールは、8.5インチ×11インチ又はＡ４の用紙を片面モード（表面のみ）、両面モード（左余白に沿って綴じたときに読み易いようにアレンジされた表面及び裏面）、及び逆転両面モード（上余白に沿って綴じたときに読み易いように裏面が逆さまになった表面及び裏面）でプリントできるかもしれない。しかし、マーカモジュールは、11インチ×17インチを片面モードだけでプリントできるということもある。マーカモジュールの機能は、拡大又は縮小の量の制約によって定義される拡大及び縮小フィーチャ（機能）を含むこともある。これらの機能も、ＣＤＬを用いて、それらの制約によって記述され、モジュール記述メモリに記憶される。
【００２７】
各モジュールは、ポイント対ポイント接続で、又は好ましくは全モジュールが接続される共通バス３２を介して、装置コントローラ２０に接続される。装置が最初にパワーアップされる時に、全モジュールはそれらの機能及び制約をコントローラに伝え、コントローラは装置モデルを構築する。例えば、給紙モジュールのモデルは、
(TRAY1)"DIM.x=850; DIM.y=1100"
(TRAY2)"DIM.x=826; DIM.y=1171"
(TRAY3)"DIM.x=850; 1300<DIM.y<1400"
となり得、装置コントローラ内に記憶される。装置がパワーアップされる度ごとに装置モデル（ＭｏＭ）が構築されるので、同じコントローラを有する装置に異なる給紙モジュールを用いてもよい。モジュール記述メモリの内容をコントローラに転送するために、コントローラは、幾つかの許容モジュールステーションアドレスに対してポーリングして、モジュールステーションが応答したら内容をアップロードしてもよい。或いは、パワーアップ時に、各モジュールがその記述メモリの内容を転送するためのアクセスを要求してもよく、コントローラが要求の競合を解消してから転送を命令してもよい。装置のトータル又はダイナミックモデルは、"給紙トレー１が空"、マーカの準備ができていない、又は"スタッカトレー３が満杯"、などといった装置状態パラメータも含み、それらのパラメータは、個々のモジュール又は装置コントローラの動作中に、センサによってピックアップされるか又は制御信号（例えば準備完了又は準備できていない）によって生成される。
【００２８】
装置コントローラ２０は、好ましくは、プロセッサ３４（例えば、マイクロプロセッサか又は１つ以上のＡＳＩＣ即ち特定用途向け集積回路に実装され得る特殊な論理のいずれか）と、オペレータインタフェース１８と通信するためのインタフェース３６及びバス３２と通信するためのインタフェース３８とを含む。装置コントローラ２０はメモリ４０も含み、メモリ４０は、ＲＯＭ、ＲＡＭ、及び消去可能ＰＲＯＭ即ちフラッシュメモリを含み得る。メモリ４０は、好ましくはＲＯＭに、複数の名前付きモジュールとして組織された制御プログラムを記憶する。装置コントローラ２０は、独立型モジュール内にあってもよく、他のモジュール（例えばモジュール１２、１４、１６）のうちの１つに収容された回路基板であってもよく、又は装置内のどこかに好ましく実装された回路基板の一部であってもよいことを、当業者は認識するであろう。
【００２９】
メモリ４０は、１つ、又は他の形式のデータも記憶する。永久的なデータはＲＯＭに記憶され、一次的なデータはＲＡＭに記憶される。装置の作動中、装置モデル（ＭｏＭ）が構築され、好ましくはＲＡＭに、又は、一部がＲＡＭに、一部が消去可能ＰＲＯＭに記憶される（パワーアップ）。装置オペレータのパーソナル化操作によって生じたパラメータは、一般的に、消去可能ＰＲＯＭに記憶される。更に、本明細書により詳細に述べるように、装置は、好ましくはＲＯＭに記憶されるポリシーのライブラリを有して出荷される。しかし、戦略セレクタと呼ばれるプログラムモジュールは、装置モデルに適したポリシーを識別し、選択したポリシーへの参照を好ましくは消去可能ＰＲＯＭに記憶する。
【００３０】
これらの教示に照らして、本発明をサポートするためにメモリ４０の他の構成を構成してもよいことを、当業者は認識するであろう。例えば、プログラム及びデータの一部又は全てが、ＣＤ−ＲＯＭ又は磁気フロッピー（登録商標）ディスクに記憶され、装置コントローラ２０内部の磁気ディスクに転送され、そこからＲＡＭにロードされてもよい。
【００３１】
戦略セレクタは、本明細書で更に説明するように、他のモジュール及びポリシーを条件的に追加又は削除する条件ステートメント（例えばif-then-elseステートメント）を含むソフトウェアモジュールである。例えば、パワーアップ（時）スケジューリング処理（例えば図８のステップＳ４２）では、戦略セレクタは、モデルトラバーサを選択して、目標とする装置の構成及び環境に基き、ポリシーのライブラリから構成ポリシーを選択する。一方、選択時スケジューリング処理（例えば図９のステップＳ５１）では、戦略セレクタは記憶部トラバーサを選択して、選択ポリシーを選択する。１つの戦略セレクタを、（ｉ）パワーアップ時に用いるモデルトラバーサ及び構成ポリシーの選択、及び（ｉｉ）選択時に用いる記憶部トラバーサ及びパワーアップ時の選択ポリシーの選択の両方に用いることができる。
【００３２】
戦略セレクタを、例えばモデルトラバーサ（ソフトウェアモジュール）及び構成ポリシー（if-then-elseステートメントでできている同じくソフトウェアモジュール）のメモリへのロードをメモリローダに指示するものとして、考えることもできよう。モデルトラバーサは、特定のメモリロケーションで始まり、特定数のバイト分だけ続いてロードされる。同様に、各構成ポリシーは、特定のメモリロケーションにロードされ、特定数のバイト分だけ続く。戦略セレクタのメモリローダ機能（例えば、ユーティリティソフトウェアモジュール）は、ロードされたモジュールがどこに記憶されたかを記録し、構成ポリシー及び装置モデル（ＭｏＭ）がどこに記憶されているかをモデルトラバーサが知るように、戦略セレクタは必要なロケーションでモデルトラバーサを構成する。このようにして、モデルトラバーサは構成ポリシーに基き装置モデルを横断できる。記憶部トラバーサ及び選択ポリシーのロードにも同様のロード手順が用いられる。
【００３３】
本発明の異なる実施の形態は、モニタと協働して、スケジューラを装置の現在の状態に適応させるための情報を取得する。モニタは、装置状態（例えば、マーカの準備ができていない）、装置性能（例えば、最初のコピー出力に対して経過した時間）及び/又は装置環境（即ち、割増し料金顧客ジョブのプリント）をモニタするハードウェア要素及び/又はソフトウェアモジュールである。モニタがソフトウェアモジュールである場合は、本発明の実施の形態は、戦略セレクタを用いて、本明細書に述べるようにモニタモジュール及びモニタポリシー、又は他のモジュールを選択する。
【００３４】
次に、まだパワーアップシーケンスにある間に、装置コントローラはモデルトラバーサを用いて、選択された構成ポリシーに従って装置モデルを処理し、有効予定表リストを作成する。後で、ジョブ明細を受け取ったときに、装置コントローラは記憶部トラバーサを用いて、選択ポリシー及びプリントジョブ明細に基き有効予定表リストをサーチし、目標とする装置でプリントジョブを処理できる特定のモジュール及び機能を含む予定表を決定する。
【００３５】
一般的に、トラバーサは、装置コントローラ２０を制御して１つ以上の有効予定表をサーチするプログラムモジュールのうちの１つのモジュールである。本発明は、例えばメモリ４０（図１）に記憶されるライブラリに含まれる複数のタイプのトラバーサを用いる。１つのタイプのトラバーサはパワーアップ時に用いられるモデルトラバーサである。モデルトラバーサは、本明細書で述べるように複数のタイプのアルゴリズムを用いて実装されてもよく、パワーアップトラバーサ（又は構成トラバーサ）と呼ばれることもあり、装置モデル（ＭｏＭ）に基き全ての可能な予定表のリストを作成し、構成ポリシー及びＭｏＭに基き、どの予定表が有効であり、どの予定表が無効であるかを決定するために用いられる。
【００３６】
一般的なパワーアップバージョン（即ち、構成バージョン）では、モデルトラバーサは、モジュール及び機能の制約及び相互接続によって各サイクルについて異なる可能な予定表（即ち、モジュール及び機能の独自の組み合わせ）を特定することを可能とされた、モジュール及びそれらの機能の全ての組合せ及び順列を通ってループする。各サイクルでは、モデルトラバーサは予定表バリデータ（本明細書で述べる）を用いて、可能な予定表が有効であるか無効であるかを決定する。
【００３７】
好ましいバージョンでは、モデルトラバーサは、実際に横断を行うために用いられるアルゴリズムから分離できる。この分離により、本明細書で更に述べるように、システム内への異なるアルゴリズムの入れ替えが容易になる。モデルトラバーサは、戦略セレクタによって、特定のサーチアルゴリズムを用いるか、又は含むように構成される（本明細書で述べる）が、モデルトラバーサ自体は、いかなる特定のアルゴリズムへの依存関係からも分離される。
【００３８】
戦略セレクタを、例えば、モデルトラバーサ（いかなる特定のアルゴリズムへの依存関係からも分離されたソフトウェアモジュール）及びモデルサーチアルゴリズム（同じくソフトウェアモジュール）のメモリへのロードを、メモリローダに指示するものとして、考えることもできよう。モデルトラバーサは、特定のメモリロケーションで始まり、特定数のバイト分だけ続けて、ロードされる。モデルサーチアルゴリズムは、特定のメモリロケーションに、特定数のバイト分だけ続けてロードされる。戦略セレクタのメモリローダ機能（例えば、ユーティリティソフトウェアモジュール）は、ロードされたモジュールがどこに記憶されたかを記録し、モデルサーチアルゴリズム、構成ポリシー、及び装置モデル（ＭｏＭ）がどこに記憶されているかをモデルトラバーサが知るように、戦略セレクタは必要なロケーションでモデルトラバーサを構成する。このようにして、モデルトラバーサはいかなる特定のサーチアルゴリズムからも分離されることができる一方で、依然としてモデルサーチアルゴリズムを用いて構成ポリシーに基いて装置モデルを横断できる。記憶部トラバーサ及び選択ポリシーのロードにも同様のロード手順が用いられる。
【００３９】
モデルサーチアルゴリズムは、１つのデータメンバー（例えばＭｏＭ）を、別のデータメンバー（例えば構成ポリシー）に基いて横断するように記述されるのが好ましい。同様に、記憶部サーチアルゴリズムは、１つのデータメンバー（例えば記憶されている有効予定表リスト）を、別のデータメンバー（例えば選択ポリシー及びジョブ明細）に基いて横断するように記述されるのが好ましい。このようにして、戦略セレクタは、トラバーサがいかなる特定のアルゴリズムへの依存関係からも分離されるように、トラバーサ、関連アルゴリズム、並びに第１及び第２データ要素を構成する。トラバーサの最良の期待性能を達成するために、トラバーサは、ライブラリ内の置換可能なアルゴリズムから最適なアルゴリズムを選択することによって、ＭｏＭに適合される。
【００４０】
代替のバージョンでは、アルゴリズムは、アルゴリズムシェル及び複数の置換可能なアルゴリズムフラグメント（例えば、置換可能サブルーチン）を含んでもよい。戦略セレクタは、戦略設計パターン（本明細書で論じる）に基いて、アルゴリズムシェル及び１組のアルゴリズムフラグメントを、トラバーサ用アルゴリズムとして選択する。
【００４１】
予定表は、有効又は無効であり得る。例えば、マーカモジュールに、11インチ×17インチの用紙を片面モードだけでマーキングする機能がある場合は、両面モードでマーキングされる11インチ×17インチの用紙をマーカモジュールを通して送ることを指定する予定表は、無効な予定表となる。
【００４２】
モデルトラバーサは全ての可能な予定表をサーチし、有効な全予定表を後の使用のために記憶する。
【００４３】
プリントジョブが実行される時（即ち選択時）、プリント装置の装置コントローラは、ジョブ明細をプリント予定表と照合する。１枚の用紙のためのプリント予定表は、用紙の処理に必要な、必要モジュール及び各モジュールの必要機能のスケジュールである。例えば、特定の予定表は、用紙が給紙モジュールのトレー１から選択され、マーカモジュールを介して片面モードで処理され、綴じられずに、スタッカモジュールのトレーに送出されることを指定し得る。別の予定表は、用紙が給紙モジュールのトレー２から選択され、マーカモジュールを介して両面モードで処理され、プリントジョブの最後に左上の角をホチキス止めされて、スタッカモジュールのトレーに送出されることを指定し得る。ジョブ明細と予定表との照合タスクは、記憶部トラバーサが行う。
【００４４】
記憶部トラバーサは、ジョブ明細（又はアセンブリツリー）を解析し、記憶されている有効予定表のリストをサーチして、プリントジョブ明細を処理できる予定表を選択する。
【００４５】
例えば、プリント装置は、Ａ４又はＡ５サイズの用紙を給紙できる給紙モジュールと、Ａ４又はＡ５の用紙に片面プリントできるマーカモジュールと、Ａ４又はＡ５の用紙をスタックできるスタッカモジュールとを含む（即ち、Feed（給紙）A4及びFeedA5機能を有する給紙モジュールと、Simplex（片面）A4及びSimplexA5機能を有するマーカモジュールと、Stack（スタック）A4及びStackA5機能を有するスタッカモジュール）。モデルトラバーサはパワーアップ時に、１. FeedA4-SimplexA4-StackA4、及び２. FeedA5-SimplexA5-StackA5の２つの予定表を見出すことになる。
【００４６】
モデルトラバーサは、FeedA4機能はＡ４サイズの用紙を出力するが、SimplexA5機能はＡ５用紙だけを受け入れ可能なことが（ＭｏＭ内の機能自体の記述によって）わかるので、FeedA4-SimplexA5-StackA4のような他の予定表を除外することになる。
【００４７】
ジョブ明細は、装置非依存型の、プリントされることを所望される用紙の指定である。装置コントローラ２０の上流のシステムモジュール（マークファシリティインタフェース又はＭＦＩと呼ばれる）は、ジョブ明細のユーザが指定したジョブの属性（例えば、横置きモード、２コピー、ブルーの表紙、等）を、アセンブリツリーとして再定式化する。アセンブリツリーは、ＭＦＩから装置コントローラ２０に入力される装置非依存型の記述である。ジョブ明細及びアセンブリツリーは、本明細書に参照として援用する特許文献３及び特許文献４に述べられている。ジョブ明細のパラメータは、その最もシンプルな形態で、ＭＦＩを介して装置コントローラへと送られる。例えば、１つのジョブは、Ａ４用紙が片面モードでプリントされ、スタック及びホチキス止めされることを指定し得る。
【００４８】
プリントジョブを実行するには、まず、そのジョブ明細を処理できる予定表を見つける必要がある。ジョブが装置コントローラに到達し、まず、用紙が例えばＡ４用紙であることを要求すると、装置コントローラは記憶部トラバーサを用いて記憶されている各予定表を巡回し、各サイクルで、記憶部トラバーサは予定表バリデータを用いて、現在選択されている予定表を選択ポリシー及びジョブ明細に照らしてチェックし、それが所望のＡ４用紙を生成できるか否かを確認する。
【００４９】
予定表バリデータは、各ポリシーにわたって、現在選択されている予定表をポリシーに照らしてチェックしながら反復するモジュールである。予定表バリデータはこのように１つ以上のポリシーによってサポートされる。予定表バリデータは、モデルトラバーサによって、記憶部トラバーサによって、又はそれらの両方によって用いられ得る。例えば、予定表バリデータは、FeedA5-SimplexA5-StackA5という予定表を最初に試みてもよい。バリデータが有し得る１つのポリシー（ポリシー１と呼ぶ）は、要求されている用紙特性が、予定表によって生成できる用紙の用紙特性とマッチする（即ち"適合する"）か否かをチェックして確認する。ポリシー１は、FeedA5-SimplexA5-StackA5予定表の出力の記述をチェックし、それを要求されている用紙の用紙記述と照合する。ポリシー１でのチェックの結果は、特性の幾つかはマッチしない（即ち、予定表の出力用紙サイズはＡ５であるが、要求されている用紙特性はＡ４である）というものである。従って、この予定表はポリシー１をパスしないので、選択されない。
【００５０】
次に、記憶部トラバーサは前進して、予定表バリデータを用いて次の予定表である予定表２（FeedA4-SimplexA4-StackA4）をチェックし、予定表２はポリシー１をパスする。予定表バリデータが検討しなければならない、予定表の機能が全て"準備完了"状態でなければならないことを指定し得る別のポリシー（ポリシー２）があるかもしれない。ポリシー２もパスした場合には、予定表２が、要求されている用紙を生成する予定表として選択される。
【００５１】
選択ポリシーは、選択される予定表がジョブ明細を処理するために満足しなければならない基準である。ポリシーは、一般的に、if-then-elseステートメントの形態である。ポリシーは、そのif-then-elseステートメントを用いて、装置（又は装置モデル若しくは処理すべきジョブ）に関する決定を行う。例えば、ポリシーを用いて、装置が所望される働きを実行するのに必要な機能及び制約を有するか否かを決定してもよい。ポリシーを用いて、装置モジュールの機能が準備完了状態にあるか否かを解釈してもよい。或いは、ポリシーを用いて、装置モジュールの機能が存在するか（例えば、給紙モジュールが、用紙が入った8.5インチ×11インチトレーを含むか）否かを解釈してもよい。ポリシーは、プログラムがサブルーチンに分解されるのと同じ方法で分解される下位ポリシーを含んでもよい。
【００５２】
これらのポリシーは、プリント装置ごとに、及び同じプリント装置内でもその時々で、異なり得る。各プリント装置は、選択されるための可能なポリシーの"ライブラリ"を有して出荷される。パワーアップ時に、戦略セレクタは、この特定の装置構成に対してどのポリシーが妥当であるかを、装置モデルに照らして判別する。例えば、戦略セレクタは、本明細書に更に述べるように、装置モジュールの数が所定の数（例えば７）より大きいか否かに応じて異なるポリシーを選択し得る。戦略セレクタは、選択されたポリシーだけにわたって反復するために、予定表バリデータを構成する装置コントローラの一部である。
【００５３】
ポリシーを装置構成に基いて構成できるだけでなく、別個のモニタモジュールが装置の１つ以上の操作をモニタでき、戦略セレクタに、装置状態の検出、モニタされた性能、及び動作環境に基いて、選択された構成へ及び選択された構成から、ポリシーをダイナミックにスワップすることを要求できる。モニタモジュールは、装置のダイナミックモデルの一部である情報を用いる。装置状態が変わると、モニタモジュールは戦略セレクタに、装置の新たなダイナミックモデルに基いてポリシーを再構成するよう要求する。このようにして、１つのジョブの処理中に予定表バリデータが"予定表はスタッカＡで終了しなければならない"というポリシーＡを有するが、次のジョブを処理する際、戦略セレクタによってポリシーＡが外されて、その代わりに"予定表はスタッカＢで終了しなければならない"というポリシーＢが加えられるように、処理中にポリシーをダイナミックに迅速にスワップできる。モニタ自体が、戦略セレクタによって選択される、サポートするモニタポリシーを用いてもよい。
【００５４】
例えば、戦略セレクタによって診断モニタが選択され、装置の性能をモニタしており、その日はマーカ２の片面機能の画質が悪いことがわかった場合には、診断モニタは戦略セレクタに、マーカ２を無視せよというポリシー３２を加えるように伝える。別の例では、ジョブモニタは、自分のプリントのために割増し料金を払った顧客に関する情報を有するモジュールである。
【００５５】
図３のＳ０２では、ジョブモニタは、ジョブが送られてきたときに、これは"優先される顧客"のジョブであるか否かを確認する。肯定される場合は、ステップＳ０３で、ジョブモニタは戦略セレクタに、優先される顧客のジョブが他のマーカよりも良好な画質を有するマーカ４でプリントされることを保証するポリシー３３を加えるよう求める。普通の顧客のジョブが送られてきたときには、スケジューラが低コストのマーカによるプリントを再開するように、ステップＳ０４でジョブモニタは戦略セレクタに、この"割増し料金"ポリシーを外すように求める。
【００５６】
一般的に、モニタを用いることで、スケジューラが特定の動作環境を学習して適応し、それに従って処理を調整することが可能になる。モニタモジュールは、モニタした状況（例えば、装置状態、装置性能、及び/又は装置環境）及び処理構成（例えば、その時々に選択される構成及び選択ポリシー）を記録して覚える。
【００５７】
例えば、モニタは、ある用紙のプリントに要する時間を測定及び記録する。時間を超過すると、選択ポリシーは、記憶部トラバーサに、同じ用紙タイプを処理するために異なる予定表を選択させる（例えば、ポリシーの採択によって、準備完了しているプリンタモジュール機能を選択するため）。モニタは、異なる予定表を用いて同じ用紙をプリントするのに要する時間を測定及び記録する。一定時間経過後、予定表と、その予定表を用いた用紙のプリントに要する時間との間の、統計的な関係が明らかになる。この統計的な関係は、より速い予定表を優先する選択ポリシーとして記録される。新たなポリシーを記録する際、モニタモジュールは、戦略セレクタに、このポリシーをアクティブな選択ポリシーに追加するよう要求する。
【００５８】
代替例では、ハードウェアモニタが、ある特定のジョブだけに対して（例えば両面ジョブ）、マーカモジュール（例えばマーカ４）の悪い画質を見つける。モニタモジュールは、この観察を、両面ジョブの処理にマーカ４を選択することを嫌う選択ポリシーとして記録する。このようにして、スケジューラは、過去の性能がどうであったかを認識して覚えることができ、性能目標をより良く達成するように適応する。
【００５９】
より詳細には、予定表バリデータは、装置コントローラ２０を制御するプログラムモジュールのうちの１つのモジュールであり、このモジュールは、選択された各ポリシーにわたって、提案された予定表（即ち候補予定表）を１つ又は複数のポリシーに照らしてチェックしながら反復するためのものである。この選択されたポリシーは、戦略セレクタによって、本明細書で更に述べる可能なポリシーのライブラリから選択されたポリシーである。図４では、予定表バリデータＳ１はステップＳ１１からステップＳ１７を含む。ステップＳ１１では、バリデータは、選択されたポリシーとの一致をチェックされるべき提案された予定表を入力する。ステップＳ１２Ａ及びステップＳ１２Ｂの間では、バリデータはステップＳ１３及びステップＳ１４の周りでループを形成し、選択された各ポリシーを巡回する。ステップＳ１３では、バリデータは現在のポリシーのif-then-elseステートメントを用いて、提案された予定表が装置内で処理され得るか否かを、装置モデル（ＭｏＭ）に含まれる記述に基いて評価する。ステップＳ１４で、バリデータは分岐し、予定表がＭｏＭに対して有効であり現在のポリシーと一致すると評価が決定した場合には、次のポリシーの評価を続ける。しかし、予定表がＭｏＭに対して無効及び/又は現在のポリシーと一致しないと評価が決定した場合には、バリデータはステップＳ１６へと分岐して、ステップＳ１７の呼出しモジュールに戻る前に、そこで無効な予定表を報告する。しかし、バリデータがステップＳ１２Ａ及びステップＳ１２Ｂ間における選択された全ポリシーを通るループを完了した場合には、ステップＳ１５で、バリデータは有効な予定表を報告し、ステップＳ１７の呼出しモジュールに戻る。従って、予定表バリデータＳ１は、選択された全ポリシーに照らして、可能な予定表の有効性をチェックする手段を提供する。
【００６０】
モデルトラバーサ又は記憶部トラバーサのいずれかであるトラバーサは、装置コントローラ２０を制御するプログラムモジュールのうちの１つのモジュールである。モデルトラバーサは、全ての可能な予定表にわたって反復し、装置モデル及び選択された構成ポリシーの両方と一致する予定表のリストを記憶するためのものである。記憶部トラバーサは、記憶されている全ての有効な予定表にわたって反復し、選択ポリシー及びジョブ明細の両方と一致する有効な予定表を見つけるためのものである。
【００６１】
図５では、モデルトラバーサＳ２はステップＳ２１からステップＳ２６を含む。ステップＳ２１では、モデルトラバーサは、装置モデルを受け取るか、入力するか、又は見る。ステップＳ２２Ａ及びステップＳ２２Ｂの間では、モデルトラバーサはステップＳ２３、ステップＳ２４、及びステップＳ２５の周りでループを形成し、可能な各予定表を巡回する。
【００６２】
モデルトラバーサ用には、１組の可能な予定表を生成するための多くの可能なアルゴリズムがある。本明細書では、一例としてバックトラック（後戻り）アルゴリズムを説明する。ステップＳ２３では、モデルトラバーサは、予定表バリデータＳ１を用いて、提案された各予定表が装置内で処理され得るか否かを、装置モデル（ＭｏＭ）に含まれる記述に基いて評価する。予定表バリデータＳ１が、予定表がＭｏＭに対して無効及び/又は選択された全ポリシーと一致しないことを決定した場合には、ステップＳ２４でモデルトラバーサはステップＳ２２Ｂへと分岐して、次の可能な予定表の評価を続ける。しかし、予定表バリデータＳ１が、予定表がＭｏＭに対して有効であり選択された全ポリシーと一致すると決定した場合には、モデルトラバーサはステップＳ２５へと分岐し、ステップＳ２２Ｂで、及びそこからステップＳ２２Ａへと、次の可能な予定表の評価を続ける前に、そこで、新たに評価された予定表を有効予定表リストに追加する。全ての可能な予定表が評価されたら、トラバーサはステップＳ２６の呼出しモジュールに戻る。このように、モデルトラバーサＳ２は、装置モデル及び選択されたポリシーに基いて、有効な全予定表のリストを作成する手段を提供する。
【００６３】
図６では、記憶部トラバーサＳ２'はステップＳ２１'からステップＳ２４'及びステップＳ２６'を含む。ステップＳ２１'では、記憶部トラバーサは、有効予定表リストを受け取るか、入力するか、又は見る。ステップＳ２２Ａ'及びステップＳ２２Ｂ'の間では、記憶部トラバーサはステップＳ２３'及びステップＳ２４'の周りでループを形成し、記憶されている各予定表を巡回する。
【００６４】
記憶部トラバーサの動作は、有効予定表リストの予定表がサーチされる順序によって異なり得る。ステップＳ２３'では、記憶部トラバーサは、予定表バリデータＳ１を用いて、記憶されている各予定表がジョブ明細を処理し得るか否かを評価する。予定表バリデータＳ１が、予定表がジョブ明細を処理できないこと及び/又は選択された全ポリシーと一致しないことを決定した場合には、ステップＳ２４'でトラバーサはステップＳ２２Ｂ'へと分岐して、次の可能な予定表の評価を続ける。しかし、予定表バリデータＳ１が、予定表がジョブ明細を処理できるとともに選択された全ポリシーと一致すると決定した場合には、記憶部トラバーサは予定表が見つかったことを宣言し、ステップＳ２２Ａ'及びステップＳ２２Ｂ'にセットアップされたループを終え、ステップＳ２２Ｂ'へと分岐し、そこで、ステップＳ２６'の呼出しモジュールに戻る。このように、記憶部トラバーサＳ２'は、選択ポリシーに基いて、ジョブ明細を処理できる有効な予定表を見つける手段を提供する。
【００６５】
代替の記憶部トラバーサを図１４に関して説明すると、記憶部トラバーサは、戦略設計パターンに従って構成される選択可能アルゴリズムフラグメントを有する。
【００６６】
戦略セレクタは、装置コントローラ２０を制御するプログラムモジュールのうちの１つのモジュールであり、このモジュールは、モデルトラバーサと、記憶部トラバーサと、任意の関連アルゴリズム及び設計パターンテーブル（本明細書で述べる）と、目下構成されている装置に適用可能な又は装置の動作環境に従って、ポリシーライブラリからのポリシーとを選択するためのものである。
【００６７】
図７では、戦略セレクタＳ３はステップＳ３１からステップＳ３６を含む。ステップＳ３１では、戦略セレクタは、装置モデル及びポリシーライブラリ内の全ポリシーを受け取るか、入力するか、又は見る。戦略セレクタは、装置に関して知るためのそこにある全てを知っている。戦略セレクタは、装置がパワーアップフェーズにあるか否かを知っている。オペレータがトレーに用紙を再充填するために給紙モジュールのトレーを開けたか否かを知っている。現在処理中の用紙の、予定表によって指定されるパス内のロケーションを知っている。ステップＳ３２Ａ及びステップＳ３２Ｂの間では、戦略セレクタはステップＳ３３、ステップＳ３４、及びステップＳ３５の周りでループを形成し、ポリシーライブラリ内の各ポリシー（及び、同様のライブラリに記憶されているトラバーサアルゴリズムなどの複数のアルゴリズムの各々）を巡回する。メモリ４０（図１）の一部であるＲＯＭ内にライブラリを記憶でき、戦略セレクタはポリシー及びアルゴリズムのサブセットを選択し、このサブセットをメモリ４０の一部であるＲＡＭに記憶する。好ましくは、ＲＡＭ内には間接アドレスベクトルだけが記憶され、選択されたポリシー又はアルゴリズムを指し示すアドレスベクトルはＲＯＭに記憶される。ステップＳ３３では、戦略セレクタは、ライブラリ内の各ポリシー又はアルゴリズムが装置に適用可能か否かを、装置モデル（ＭｏＭ）に含まれる記述及び装置の現在の環境に基いて評価する。
【００６８】
例えば、装置がパワーアップ時の構成フェーズにあるか、又は現在のジョブの実行時の選択フェーズにあるかに応じて、異なるトラバーサアルゴリズムが用いられることが望ましいことは、あり得るとともに、よくあることである。構成フェーズでは、モデルトラバーサの１つを、バックトラックアルゴリズムの１つのバージョン及びあるポリシー（例えばポリシー１及びポリシー３）とともに用いることが望ましい。しかし、選択フェーズでは、記憶部トラバーサアルゴリズム及び異なるポリシー（例えばポリシー２３及びポリシー４４）を用いることが望ましいかもしれない。
【００６９】
戦略セレクタは、その時点で何が進行中かに関する知識に基き、使用するアルゴリズム及びポリシーを選択するソフトウェアモジュールである。上述の例に対しては、戦略セレクタは次のように記述され得る。
if(configuration_phase),
add BacktrackTraverser
add policy1
add policy3
else if(selection_phase),
add StoreTraverser
add policy23
add policy44
この例示的な戦略セレクタの拡張は、装置構成の性能に関して集められた又は集められる統計的な情報を用いる。例えば、プリント装置の出荷前に、様々なサイズの装置構成、様々な機能等の選択を行うのに要する時間に関する情報を作成してＲＯＭに記憶できる。或いは、装置の実際の使用中に情報を集めて消去可能ＰＲＯＭに記憶できる。この場合は、戦略セレクタも、この計量的な知識を利用するif-then-elseステートメントを含むことになろう。上述の例に対しては、戦略セレクタは次のように記述され得る。
if(number of machine modules in MoM > 7) and (configuration_phase),
add Combined_Traverser
add policy1B
else if(number of machine Module <= 7) and (configuration_phase),
add BacktrackTraverser
add policy1
add policy3
この戦略セレクタは、装置構成が７個以上の装置モジュールを有する場合には、"全ての"可能な予定表をサーチして記憶するには、時間が長くかかりすぎるか、又は使用するメモリが多すぎることがわかっているという事実を活用する。むしろ、構成フェーズでは、"幾つか"の可能な予定表を識別して記憶する"組合わせた"トラバーサ（本明細書で述べる別のトラバーサアルゴリズム）が、選択される。そして、選択フェーズでは、記憶されている有効予定表リストのサーチには記憶部トラバーサが用いられるが、有効な予定表が見つからない場合は、トラバーサが、装置モデルに従って、可能なより有効な予定表をサーチできるように、バックトラックトラバーサアルゴリズムの１バージョンが選択される。また、ある装置構成に対して"最適化された"幾つかのポリシーもあるかもしれず、特定の種類の構成に遭遇した場合にはそれらのポリシーを用いることができる。
【００７０】
ステップＳ３４（図７）では、戦略セレクタが現在のポリシーは適用不可であると決定した場合は、戦略セレクタはステップＳ３２Ｂへと分岐し、次のポリシーの評価を続ける。しかし、戦略セレクタがそのポリシーが適用可能であると決定した場合は、戦略セレクタはステップＳ３５へと分岐し、ステップＳ３２Ｂで、及びそこからステップＳ３２Ａへと、ポリシーライブラリからの次のポリシーの評価を続ける前に、そこで、新たに評価されたポリシーを選択されたポリシーのリストに追加する。ライブラリ内の全ポリシーが評価されたら、戦略セレクタはステップＳ３６の呼出しステップに戻る。このように、戦略セレクタＳ３は、ポリシーライブラリからポリシーを選択するとともに現在の装置に適応可能な横断アルゴリズム又は他のアルゴリズムを選択する手段を提供する。
【００７１】
装置１０（図１）は、パワーアップ時にパワーアップモジュールのシーケンスを実行する。図８では、パワーアップシーケンサＳ４はステップＳ４１からステップＳ４５を含む。ステップＳ４１では、パワーアップシーケンサはモジュール記述メモリを読んで装置モデルを構築する。ステップＳ４２では、パワーアップシーケンサは、戦略セレクタＳ３を用いて、装置に適用可能なポリシー並びにトラバーサアルゴリズム及び/又は他のアルゴリズムを選択する。これは、パワーアップモデルトラバーサの選択を含むとともに、記憶部トラバーサの選択を含み得る。ステップＳ４３では、パワーアップシーケンサは、トラバーサＳ２を用いて装置モデルを横断し、有効予定表のリストを作成する。そして、ステップＳ４４では、パワーアップシーケンサは、ステップＳ４５の呼出しモジュールに戻る前に、有効予定表を記憶する。このように、パワーアップシーケンサＳ４は、装置コントローラ２０（図１）に、パワーアップシーケンス中に有効予定表リストを作成する手段を提供する。
【００７２】
ジョブがプリントされる時には、装置１０（図１）は選択時モジュールのシーケンスを実行する。図９では、選択時シーケンサＳ５はステップＳ５１からステップＳ５２を含む。ステップＳ５１では、選択時シーケンサは、戦略セレクタＳ３を用いて、記憶部トラバーサ（パワーアップ時の間に選択されない場合）及び装置に適応可能なポリシーを選択する。例えば、戦略セレクタＳ３は、前に記憶された有効予定表リストから予定表を選択する記憶部トラバーサを選択するとともに、現在のジョブ明細に照らした予定表の実証に適したポリシーを選択する。ステップＳ５２では、選択時シーケンサは、記憶部トラバーサを用いて、有効予定表リストに記憶されている各予定表を横断する。そして、記憶部トラバーサは予定表バリデータを用いて、現在の予定表がジョブ明細を処理できるか否かを確認する。予定表バリデータが、特定の予定表がジョブ明細を処理できることを確認したら、記憶部トラバーサは停止し、選択された予定表がタイミングのために使用可能となる。
【００７３】
記憶部トラバーサは、ジョブ明細を処理できる予定表を求めて有効予定表リストをサーチする。戦略セレクタは、記憶部トラバーサ及び選択ポリシーを前に選択しており、それは予定表バリデータをサポートし、ひいては選択された記憶部トラバーサをサポートする。記憶部トラバーサは、記憶されている有効予定表を通ってループして可能な予定表を選択し、予定表バリデータを用いてジョブ明細（又はアセンブリツリー）が選択された予定表によって処理され得るか否かをチェックする。否である場合は、記憶されている次の予定表を試みる。予定表バリデータが、選択された全ポリシーに基いて、ジョブ明細（又はアセンブリツリー）が１つの予定表によって処理され得ると決定した場合には、その予定表が選択され、更に別のタイミングされるべきシステムコンポーネントに渡される。スケジューラの目的は、プリントジョブを処理できる有効な予定表を見つけること、及び、後の装置による実行のために、その予定表をタイミングすることである。
【００７４】
ジョブ明細を処理できる予定表が２つ以上あるということが生じ得る。そのような場合には、トラバーサは、最初に見つけた予定表を選択する。両方ともそのプリントジョブを処理する能力があり、一方の予定表を用いた方が他方の予定表を用いるよりも何かしらの利益があるという場合には、その利益が特徴づけられ、特徴づけられたパラメータが条件ステートメントとして追加ポリシーステートメントに含まれる。すると、その追加ポリシーステートメントがあるので、好ましい予定表だけが選択される。
【００７５】
或いは、選択ポリシーはハードポリシーとソフトポリシーとに区別できる。ハードポリシーは、"満足しなければならない"ポリシーであり、ソフトポリシーは"望ましい"ポリシーである。例えば、ソフトポリシーは"入手可能であれば8.5インチ×11インチの用紙にプリントし、入手できなければ次に入手可能なより大きなサイズにプリントする"、又は"白又はバフ（淡黄色）にプリントする。但し入手可能であれば白へのプリントを優先する"というものである。このタイプの状況では、トラバーサは、単なる"有していなければならない"ハードポリシー以上のものを探している。即ち、トラバーサは"好ましい"ポリシーを満足するためにも探している。
【００７６】
ハードポリシー及びソフトポリシーの使用は、機能選択をより複雑な最適化の問題にする。本明細書に参照として援用する非特許文献１は、"十分"な解決法が許容可能な場合に、問題を部分的に解決できる様々なアルゴリズムの調査を述べており、調査された技術の部分的問題解決における有効性を示す実験的な結果も提供している。本明細書に参照として援用する非特許文献２は、新たな制約が追加されたとき、又は古い制約が取り除かれたときの、制約の解決法を維持するための方法を述べており、必要且つ好ましい制約の階層表現を述べており、ユーザインタフェースアプリケーションにおけるそのような制約の階層を解決するためのアルゴリズムを提案している。本発明の柔軟性及び様々な戦略を扱う能力は、ダイナミックポリシー選択及びソフトポリシー選択によって呈示される最適化問題が、同じアーキテクチャの枠組み内で解決されることを可能にする。
【００７７】
ソフトポリシー評価基準を用いる特定の実施の形態は、選択された各ポリシーに重みを割当てる。予定表は、予定表バリデータ内で、その予定表によっていくつのポリシーが満足されるか、それらのポリシーがどのくらい重要か（重み）のグローバルな尺度である、トータルの重みに基いて評価される。トラバーサは、ポリシーを満足する最初の予定表を見つける代わりに、１つの予定表を見つけるとそのトータルの重み（即ちスコア）を計算し、トラバーサが閾値を超える予定表を見つけるまで、時間切れまで、又はトラバーサが最適な予定表を見つける（可能な予定表が全てサーチされたとき）まで、サーチを続ける。
【００７８】
パワーアップ戦略セレクタは、プリントジョブが要求されたときに、パワーアップ時に用いるモデルトラバーサ及び可能であれば後で用いる記憶部トラバーサを選択する。プリント装置の１つのバージョンでは、パワーアップ時に用いられるモデルトラバーサはバックトラックトラバーサである。
【００７９】
本明細書に参照として援用する非特許文献３は、"制約満足問題(constraint satisfaction problems)"（以降、ＣＳＰと呼ぶ）として定式化される問題の解決に適用できる、公知のバックトラックサーチを述べている。ＣＳＰは、変数、各変数に対する１組の可能な値、及び値間の制約を用いて記述される問題である。ＣＳＰに対する解決法は、全ての制約を満足する、変数に対する値の１つ又は全ての割当てを見つけることを含む。例えば、一般的なＣＳＰは、隣接する州(state)が同じ色にならないように、所定数（例えば３）の色でマップを色づけすることが望まれる、公知の"マップ色づけ問題"である。この問題をＣＳＰとして定式化すると、変数は州であり、値は各州に対する可能な色（例えば、赤、緑、及び青）であり、２つの隣接する州に同じ色が割当てられ得ることがないように制約が定式化される（例えば、各州の近傍が識別されて、異なる色になるように制約される）。解決法は、隣り合う全ての州が異なる色を有するように、各州に１つの色を割当てることである。
【００８０】
バックトラックは、ＣＳＰに対する１つ又は全ての解を見つけることができるサーチアルゴリズムである。一般的なバックトラックアルゴリズムは、前方にサーチするルーチン（図１１のステップＳ６を参照）と後方にサーチするルーチン（図１２のステップＳ７を参照）との２つのルーチンを含む。図１０は、本明細書で例として用いる簡略化したプリンタの装置モデルＭｏＭを示している。本発明のスケジューラでは、バックトラックアルゴリズムの変数はＭｏＭの３つの装置モジュールである（即ち、給紙モジュール、マーカモジュール、及びスタッカモジュールであり、個々に１、２、及び３の番号をつける）。各変数に対して２つの可能な値が存在し、これらの可能な値は個々のモジュールの機能である（例えば、ＭｏＭ内の各モジュールがＡ４及びＡ５の用紙を処理する機能を有する）。満足されなければならない制約は、１つのモジュールのどの機能が他のモジュールの機能と両立するかに関する装置の制約に基く。解は、どの制約にも違反しないように組合わされた各モジュールにおける1つの機能として定式化された予定表である。
【００８１】
図１１では、ステップＳ６１Ａ及びステップＳ６１Ｂの間で、バックトラックトラバーサは、予定表が見つかるまで、全モジュールを用いてループする。まず、ステップＳ６２で、バックトラックトラバーサは、値を割当てられる次の変数として１つのモジュールを選択し、この変数をNextVarと呼ぶ。予定表は給紙モジュールで始まるので、給紙モジュールが最初のモジュールとして選択される。ステップＳ６３では、給紙モジュールに対して有効な候補の値が、その機能、feedA4及びfeedA5となるように定式化される。ステップＳ６４では、バックトラックトラバーサは、NextVar（現在は給紙モジュール）に対する値が存在するか否かを尋ねる。存在する値が２つある（feedA4及びfeedA5）ので、バックトラックトラバーサは、ステップＳ６５で値を順序付けする（例えば、feedA4の後にfeedA5）。ステップＳ６６では、バックトラックトラバーサは、現在のNextVar（即ち給紙モジュール）に、最初の値（即ちfeedA4）を割当てることによって、ラベル付けする。次に、ステップＳ６１Ａ及びステップＳ６１Ｂを介してループを繰り返すことにより、サーチを続ける。
【００８２】
バックトラックトラバーサが選択する、ラベル付けされるべき次の変数は、マーカモジュールである。今回のNextVarはマーカモジュールである（ステップＳ６２）。ステップＳ６３では、給紙モジュールは選択されたfeedA4機能からＡ４用紙を出力するので、マーカモジュールに対する唯一の有効な候補の値はmarkA4機能であることがわかる。ステップＳ６４は、NextVarに対する値が存在するか否かをテストし、１つの値が存在するので、ステップＳ６５で、その値が順番に配置される。１つの値だけが存在するので、ステップＳ６５はトリビアルである。ステップＳ６６では、バックトラックトラバーサは、現在のNextVar（即ちマーカモジュール）に、最初の値（即ちmarkA4）を割当てることによって、ラベル付けする。
【００８３】
同様に、バックトラックトラバーサは、ラベル付けすべき次の変数がスタッカモジュールであることを見出し、給紙モジュール及びマーカモジュールに対して現在選択されている値と両立するのはstackA4機能であることを見出す。バックトラックトラバーサは、ステップＳ６２でラベル付けされていない変数が残っていないことを見出し、従って、feedA4-markA4-stackA4という予定表を見つけた。ラベル付けされていない変数がないので、ステップＳ６３及びステップＳ６４で次の変数に対して見つけるべき値もなく、従って、ステップＳ６７で、バックトラックトラバーサはGoBack（即ち、後方サーチ）部に進む。
【００８４】
バックトラックトラバーサは、"バックトラック"によって更に多くの予定表を見つけ続ける。ステップＳ７２では、バックトラックトラバーサは、スタッカモジュールに対して有効な値が更に存在するか否かを決定する。この例では、stackA5は、既にラベル付けされた給紙モジュール及びマーカモジュール（即ち、マーカモジュールからのＡ４用紙出力）と両立しないので、有効な値ではない。従って、ステップＳ７３では、最後の変数（即ち、スタッカモジュール）のラベルが外され、Gobackは更に後戻りする。次に、ステップＳ７２で、マーカモジュールに対する有効な値（給紙モジュールに対して選択されたfeedA4機能と両立する値）が残っていないことがわかり、ステップＳ７３で、マーカモジュールのラベルが外され、Gobackは更に後戻りする。次の回のステップＳ７２が処理され、他の全てのラベル付けされた変数と両立する値（即ち機能）が見つけられる。実際には、マーカモジュール及びスタッカモジュールのラベルは外されているので、給紙モジュールの機能が両立しなければならない他のラベル付けされた変数はない。ステップＳ７４で、最初の変数（即ち、給紙モジュール）が、その機能の中から見つけられた唯一の他の値で再度ラベル付けされる。他の値とはfeedA5機能である。
【００８５】
ステップＳ７５で、トラバーサのGoBack部は、バックトラックトラバーサの始めに進む。次に、バックトラックトラバーサは前方にサーチして迅速に検出し、マーカモジュールをmarkA5機能で、及びスタッカモジュールをstackA5機能でラベル付けし、このように、feedA5-markA5-stackA5という第２の最後の有効な予定表を見つける。
【００８６】
第２の最後の予定表が識別されたら、ステップＳ６４及びステップＳ６７で、トラバーサはトラバーサのGoBack部に進む（最初の予定表を見つけた後と同様）。次に、ステップＳ７１で、最後にラベル付けされた変数は、全てのモジュール及びそれらの機能の検討を尽くし、見つけるべき更なる解がないので、ステップＳ７６でトラバーサは終了する。
【００８７】
本発明の代替の実施の形態では、パワーアップシーケンス時間の短縮又はメモリの節約が望まれる場合、パワーアップ時に予定表を記憶する必要がないように、パワーアップモデルトラバーサが完全に削除される。そして、選択時に、ジョブをプリントする際、記憶部トラバーサを用いる代わりに、戦略セレクタは装置モデルを横断する選択時モデルトラバーサを用いて、まず、推定上の予定表が全ての構成ポリシーを満足するか否かをチェックし、次に、その予定表が選択ポリシーを満足してプリントジョブを処理できるか否かをチェックして確認する。選択時モデルトラバーサは、プリントジョブを処理できる予定表を見つけるために装置モデルを"迅速に"横断するために、完全なバックトラックトラバーサを用いてもよい。この実施の形態の使用は、迅速なパワーアップが必要で、装置が異なるモジュール及びモジュール内の機能を有し得る場合に、好ましいことがある。
【００８８】
本発明の更に別の実施の形態では、パワーアップトラバーサは、パワーアップ時に、装置モデルに従って、可能な幾つかの有効な予定表のリストを生成する、修正されたモデルトラバーサである。この予定表の短いリストは、任意の所望の手段によって（例えば、メモリ記憶を最小にする、最も頻繁に用いられる、等）選択され得る。しかしながら、この手段は、この装置を用いるプリントショップで最も用いられそうな予定表を選択するのが好ましい。そして、選択時には、修正された記憶部トラバーサが、この有効な予定表の短いリストを横断し、プリントジョブを処理できる予定表を求めてサーチする。ジョブを処理できる予定表が見つからない場合は、記憶部トラバーサの操作の後に、装置モデルを"迅速に"横断するための第２の修正されたモデルトラバーサの操作が続き、パワーアップシーケンス中にサーチされなかった残りの可能な予定表の中から、プリントジョブを処理できる予定表を見つける。
【００８９】
この"迅速な"選択時モデルトラバーサの変形では、モデルトラバーサの選択時操作中に識別された有効な予定表が、メモリに記憶されるか、又は既存の有効予定表を記憶しているメモリに追加される。その後、プリントのために別のジョブが提出されたときに、選択時記憶部トラバーサは、まず、その時点で"迅速な"選択時モデルトラバーサの操作中に識別されて記憶された予定表を含む記憶されている予定表の中から使用可能な予定表を求めてサーチする。このようにして、記憶されている予定表は、最も頻繁に用いられる予定表を反映する。
【００９０】
有効な予定表を記憶するためのメモリスペースが限られているアプリケーションでは、"迅速な"トラバーサは、ある基準（例えば、最も長時間使われずに記憶部に残っている予定表を削除）に基いて記憶されている予定表を削除するためのモジュールを含む。このようにして、予定表の記憶は、最も頻繁に用いられる予定表を反映する。このようにして、スケジューラは、プリントショップで最も頻繁に用いられる予定表を"学習"する。
【００９１】
通常、パワーアップ時とは、１日に1回、１週間に１回、又はメンテナンス後にプリンタを再びオンにするときに、プリンタに最初に電力を加える時のことである。しかし、予定表の記憶部は不揮発性メモリ（例えば、磁気ディスク、フラッシュメモリ、又は電気的に消去可能な不揮発性メモリ）であってもよいので、電力が新たに加えられる度ごとにパワーアップ処理を開始する必要はないかもしれない。不揮発性の予定表記憶部は、既に、電源が切られる前から記憶されている予定表を有しているであろう。しかし、プリント装置構成の修正後（即ち、修正されたＭｏＭ）は、新たなＭｏＭに合わせて調整するために、パワーアップ処理を開始する必要があろう。例えば、夜にスイッチを切って翌朝にスイッチを入れる装置に対しては、構成の修正がない限り、毎朝、全てのパワーアップ処理を実行する必要はない。そのような場合には、朝、装置のスイッチが入れられたときに、装置は装置構成の監査を行い、構成の変更を検出する。しかし、変更が検出されない場合は、装置は、不揮発性メモリ記憶部から、記憶されている有効予定表を再ロードする。新たなモジュールがインストールされるか、又は既存のモジュールが修正された場合は、技術者が"リセット"ボタンを押してリブートし、完全なパワーアップシーケンスを開始させる。
【００９２】
代替の実施の形態では、モデルトラバーサは、予定表を見つけるために横断アルゴリズムを用いることだけを知っており、どのように予定表を見つけるかは知らないように構成される。このようにして、モデルトラバーサは、横断アルゴリズム自体をモデルトラバーサの他の機能から切り離す。従って、モデルトラバーサは、装置非依存という意味での実際の横断アルゴリズムの分離を利用でき、異なる横断用アルゴリズムをシステム内に容易に入れ替えできる。例えば、モデルトラバーサは、バックトラックトラバーサアルゴリズムを用いて装置モデル（装置グラフ）上を反復して、予定表を見つけることができよう。上述したように、非特許文献３は、制約満足問題として表現される問題の１つ又は全ての解を見つけるために使用可能なバックトラックアルゴリズムを述べている。
【００９３】
バックトラックトラバーサアルゴリズムを遺伝的トラバーサアルゴリズムと入れ替えることによって、"遺伝的"アルゴリズムを用いる別の手法を実施することもできよう。たとえ基本アルゴリズムが異なっていても、いずれの場合にも、モデルトラバーサは同じ機能性を提供するであろう。これは、新しいアルゴリズム（例えば、最小矛盾アルゴリズム及びバックジャンプアルゴリズム）が開発され、経験的にテストされ、性能強化を提供することが示されるときに、モデルトラバーサを継続して改良するための、柔軟性及び機会を可能にする。値の順序付け(value-ordering)ヒューリスティックを用いて、バックトラックアルゴリズムを、サーチ中の制約違反を最小化する解を優先するように強化できる方法を述べている、本明細書に参照として援用する非特許文献４を参照されたい。また、本明細書に参照として援用する非特許文献５は、基本的なバックトラックアルゴリズムの性能を高めるための種々のアルゴリズムを述べている。
【００９４】
図１３では、モデルトラバーサは、選択セレクタによって、特定の横断アルゴリズム（例えば、ある特定の設計のバックトラックアルゴリズム、遺伝的アルゴリズム等）を用いるように構成されている。モデルトラバーサは横断ステップＳ８を実行する。ステップＳ８は、ステップＳ８１で、予定表を見つけるために特定の横断アルゴリズムを呼び出し、ステップＳ８２で、横断アルゴリズムによって見つけられた予定表を記憶する。ステップＳ８３で、モデルトラバーサは、見つけるべき更なる予定表があるか否かをチェックして確認する。更なる予定表がない場合は、モデルトラバーサはステップＳ８４の呼出しプログラムに戻る。更なる予定表がある場合は、ステップＳ８１で再び横断アルゴリズムが呼び出される。これにより、モデルトラバーサ及びモデルトラバーサを用いる任意のシステムコンポーネントが、予定表の検出に用いられる特定の横断アルゴリズムに依存しないことが可能になる。このようにして、異なる状況に対して異なるアルゴリズムを開発できるとともに、戦略セレクタがパワーアップ時に適切なアルゴリズムを選択できる。
【００９５】
更に別の代替の実施の形態では、モデルトラバーサ内の横断アルゴリズムは、その戦略設計パターンとしての表現に因って複数の代替の実施の形態を可能とするように構成される。本明細書に参照として援用する非特許文献６は、基本的な戦略設計パターンの概念を述べている。本発明では、横断アルゴリズムのインプリメンテーションは、戦略設計パターンに従って組み合わされるアルゴリズム部分の小さな構築ブロックを用いるように設計される。これにより、横断アルゴリズムの様々な部分を柔軟にすることができる。アルゴリズムの（及びそれに対応してサーチ性能における）可変性は、アルゴリズムに追加される異なる変数及び値の順序付けヒューリスティックに起因して生じる。本明細書に参照として援用する非特許文献７は、様々な可変順序付けヒューリスティックの有効性をサーチ効率において比較している。横断アルゴリズムは、制約満足問題（ＣＳＰ）のある変数（例えば、本発明の定式化におけるモジュール）が処理される順序（例えば、図１１のステップＳ６２におけるモジュール選択の順序）に応じて異なる効率性で性能を発揮し得る。リアルタイムモニタを用いて統計を集めることにより（又は単にヒューリスティックにより）、又はおそらくは"オフライン"でシミュレーションにより、又は出版された比較（例えばジェントらによる論文）を検討することにより、図１１のステップＳ６２でモジュール（一般的に、ＣＳＰにおける変数）を検討する好ましい順序に関する戦略（戦略設計パターンアーキテクチャと呼ぶ）を開発可能である。
【００９６】
戦略設計パターンアーキテクチャは、他のファクター（例えば、小さなプリントショップ対大きなプリントショップ）に応じて異なり得る。横断アルゴリズムの戦略設計パターンアーキテクチャは、アルゴリズムが様々な変数及び値の順序付けヒューリスティックで構成されるのを可能にする。これらのヒューリスティック及び/又は戦略は、様々な装置構成及びジョブ要求に対して開発可能である。戦略セレクタを用いて、モデルトラバーサのアルゴリズムによって用いられる所望のヒューリスティックを選択できる。戦略セレクタは、現在の装置構成の複雑さを評価し、そのような構成において効果的又は効率的であることが示されているいずれかの戦略を選択する。
【００９７】
バックトラックアルゴリズムの要素は、評価が終了されるときの終了条件を定義する(EndCondition)ステップＳ６１Ａ及びステップＳ６１Ｂ（図１１）と、評価される変数の順序を定義する(VariableOrderer)ステップＳ６２（図１１）と、制約満足問題の値が評価される順序を定義する(ValueOrderer)ステップＳ６３（図１１）と、を含む。戦略設計パターンとして定式化される際、バックトラックアルゴリズムは、どのようにステップが実行されるかを正確に知らずに、単に、EndConditionステップ、VariableOrdererステップ、及びValueOrdererステップが実行されることを求める。例えば、横断アルゴリズムはVariableOrdererを呼出して、検討されるべき次の変数を与えるように要求する。ValueOrderer自体は、多くの異なるインプリメンテーションのうちの任意のインプリメンテーションであり得る（例えば、次の装置モジュールについてチェックするもの、又は最も制約の数が多い装置モジュールについてチェックするもの等）。戦略設計パターンは、アルゴリズムの基礎をなすステップが異なるインプリメンテーションと互換可能であっても、バックトラックアルゴリズムの骨組み（例えば図１１）は同じであり続けることを可能にする。
【００９８】
別の実施の形態では、記憶部トラバーサは、最初に検討する予定表を決定するために記憶部トラバーサが用いる構成可能な検索基準又は選択ポリシーに従って、記憶されている有効予定表リストを通って反復する。例えば、記憶部トラバーサは、"準備完了した機能を有する最初の全予定表を検討する"ことを指定する検索基準１を用いてもよく、次に、記憶部トラバーサは、"内部で保留中の機能を有する次の全予定表を検討する"ことを指定する検索基準２に移る、等。検索基準は、バックトラックアルゴリズムの部分又はポリシーと同様に、戦略セレクタ又はモニタモジュールによって記憶部トラバーサの構成から追加及び削除される。
【００９９】
図１４では、記憶部トラバーサは、処理ステップＳ９に二重ループ構成を含む。内側ループはステップＳ９３Ａ及びステップＳ９３Ｂによって制御される。内側ループでは、記憶されている全予定表が基準（例えば、"準備完了"である予定表）に照らしてチェックされ、基準に見合う有効な予定表が検出される。外側ループは、ステップＳ９１Ａ及びステップＳ９１Ｂによって制御される。外側ループでは、基準リストに載っている全ての基準が選択されて、"予定表が見つかりませんでした"という条件が宣言されるまで、基準に見合う有効な予定表を見つけるために内側ループによって処理される。複数の異なる基準が記憶されてもよい（例えば、"準備完了"であるモジュール機能だけを用いる予定表を選択、大容量給紙モジュールを用いる基準を選択、高画質マーカモジュールを用いる基準を選択、等）。
【０１００】
記憶されている基準は選択ポリシーであり、戦略セレクタは１つ以上の基準を選択して、戦略セレクタが用いる基準のリストを作成する。ステップＳ９２では、次の基準が処理のために選択される。ステップＳ９４では、チェックのために次の予定表が選択され、ステップＳ９５では、選択された予定表が現在選択されている基準に照らしてチェックされる。ステップＳ９６では、予定表が現在の基準の要件に見合う場合には、その予定表が有効であると宣言される。予定表が有効であると宣言された場合には、ステップ９７で、予定表が見つかったと言われ、記憶されている全予定表が全基準に照らしてチェックされた後に予定表が有効であると宣言されない場合は、ステップＳ９８で、予定表が見つからなかったと言われる。
【０１０１】
予定表のリストが長い場合もあり、記憶部トラバーサの効率性は予定表リストがサーチされる順序に依存し得ることが認識されよう。また、基準のリストが存在することもあり、記憶部トラバーサの効率性は基準リストがサーチされる順序に依存し得ることも認識されよう。モデル横断アルゴリズムの場合のように、ステップＳ９２、ステップＳ９４、及びステップＳ９５が単にアルゴリズムのフラグメントである他のルーチンを呼び出すように、図１４に示されている記憶部横断アルゴリズムが分離されてもよい。これらのアルゴリズムフラグメントの代替バージョンを開発してもよく、モデル横断アルゴリズムの場合のように、戦略セレクタは所望の戦略設計パターンに基き特定のアルゴリズムフラグメントで記憶部トラバーサを構成する。
【０１０２】
開示された本発明の特定の実施の形態に、添付の特許請求の範囲によって定義される本発明の範囲及び精神の範囲内の変更がなされ得ることを理解されたい。
【０１０３】
以上のように本発明を説明したが、特許請求され、特許証による保護が望まれるものを、添付の特許請求の範囲に記載する。
【符号の説明】
【０１０４】
１０    プリント装置
１２    給紙モジュール
１４    マーカモジュール
１６    スタッカモジュール
２０    装置コントローラ
３４    プロセッサ
【図１】
0004833310.tif 000002
【図２】
0004833310.tif 000003
【図３】
0004833310.tif 000004
【図４】
0004833310.tif 000005
【図５】
0004833310.tif 000006
【図６】
0004833310.tif 000007
【図７】
0004833310.tif 000008
【図８】
0004833310.tif 000009
【図９】
0004833310.tif 000010
【図１０】
0004833310.tif 000011
【図１１】
0004833310.tif 000012
【図１２】
0004833310.tif 000013
【図１３】
0004833310.tif 000014
【図１４】
0004833310.tif 000015