JPH0923293A - プリントエンジンスケジューリングシステム - Google Patents

Abstract

(57)【要約】 【課題】 モジュールから構成される印刷装置におい
て、装置の利用性及び構成のしやすさを強化する。 【解決手段】 本発明により、印刷装置の動作をスケジ
ューリングするシステムが提供される。印刷装置の各コ
ンポーネントの能力及びそれらの能力に対するリソース
及びタイミング等の制約に基づき印刷装置をモデル化す
る有限状態マシンが自動的に生成され、この有限状態マ
シンに基づいて印刷装置の全体的動作がスケジューリン
グされる。このような自動化スケジューリングによっ
て、モジュールから構成される印刷装置において装置の
利用性及び構成のしやすさが強化される。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は印刷装置技術に関
し、特に複写装置のような写真式複製装置に関する。

【０００２】本発明は特に、有限状態マシンを生成し、
プリントエンジンにおいて所望のドキュメントを生成す
るために必要とされる動作をスケジューリングするシス
テムに適用可能である。本発明のシステムは、印刷装置
を形成するモジュール方式コンポーネントに関連した能
力に従うプリントジョブの自動化スケジューリングを可
能とし、特にそのようなことに関して記述される。しか
し、モジュール方式コンポーネントを考慮した装置能力
の自動化アセスメントの提供や、同様のことを考慮した
ジョブの特定な効率的利用のような幅広いアプリケーシ
ョンを本発明が有することが認められる。

【０００３】

【従来の技術及び発明が解決しようとする課題】写真式
複写装置のような今日の装置は、予め製造されたコンポ
ーネントから頻繁に製造される。そのような製造は、装
置の各サブアセンブリの大量生産を可能にすると同時
に、消費者のニーズに対してカスタム化を可能にする。
さらに、消費者は、既存のベース装置の能力を変更する
ことができるか又はアップグレードすることができる手
段を与えられる。

【０００４】本発明と共通の譲り受け人によって所有さ
れるＵ．Ｓ．特許第 5,287,194号及び第5,363,175 号に
おいて、分散型印刷及び分散型ジョブスケジューリング
のための初期のシステムが見いだされる。

【０００５】集積化装置のモジュール方式アセンブリの
１つの関心事項は、完成されたシステムの利用の構成及
び最適化である。このことは初期装置の製造者に対する
関心事項である一方、おそらくエンドユーザーに対して
もより大きい関心事項である。エンドユーザーは、技術
的に充分な知識を有していないことがほとんどである。
しかし、エンドユーザーは、初期投資値を維持すること
を所望する一方で装置能力の増加を所望する。消費者は
また、既存の装置をアップグレードするか又は構成する
ために専門家を雇うことに関連する出費を望まない。

【０００６】従来のシステムにおいて、プリントエンジ
ン能力の自動的スケジューリングがある程度望まれてい
た。そのようなスケジューリングは、開発者がプリント
エンジンの詳細を予め知っている場合にのみ達成されて
いた。個別のモジュールが使用された場合であっても、
それらの相互作用が解析されなければならず、結果とし
て得られたプリントエンジン情報は一般的に再使用不可
能であった。

【０００７】

【課題を解決するための手段】本発明に従って、有限状
態マシンを生成し、印刷装置動作の自動的スケジューリ
ングを容易にするシステムが提供され、これにより前述
及びその他の問題が克服される。本発明は、装置出荷前
及び出荷後の両方において利用性及び構成のし易さが強
化されたシステムを提供する。

【０００８】本発明に従って、有限状態マシンを自動的
に生成し、多様な個々のモジュール方式装置コンポーネ
ントの記述からプリントエンジン動作のスケジューリン
グを行うシステムが提供される。

【０００９】本発明の他の態様に従って、プリントエン
ジン能力のタイミング制約を自動的に分析してパタメー
タを確定し、有限状態マシンを自動的に生成するシステ
ムが提供される。

【００１０】本発明の他の態様に従って、システムは有
限状態マシンを生成し、これに対して小規模で適切なサ
ーチが行われる。

【００１１】本発明の他の態様に従って、システムは有
限状態マシンジェネレータを提供し、これにより、動作
中チェックのために制約の一部を選択的に残して有限状
態マシンサイズを低減することが可能となる。

【００１２】本発明の利点は、多様な変化するサブアセ
ンブリに容易に自動的に構成可能な印刷装置動作スケジ
ューリングのための有限状態マシンの生成である。

【００１３】本発明の利点は、多様な又は変化するサブ
アセンブリに簡単に、そして、自動的に構成されること
ができる印刷装置モデルの提供である。

【００１４】本発明の他の利点は、エンドユーザによっ
て最大ポテンシャルに簡単に構成されることができる印
刷装置の提供である。

【００１５】本発明の他の利点は、ユーザーにより指定
されたプリントジョブに従ってモジュール方式サブアセ
ンブリを効率的にスケジューリング及び利用することに
よって印刷スループットを最大にする印刷装置の提供で
ある。

【００１６】本発明の更なる利点は、本明細書により当
業者に対して明らかとなる。本発明の１態様は、プリン
トエンジンの能力を分析して有限状態マシンを生成し、
プリントエンジンをスケジューリングするシステムであ
って、複数のプリントエンジンコンポーネント能力を受
信する手段を備え、各コンポーネント能力はコンポーネ
ント能力データセットによって定義され、各データセッ
トから信号データ及びタイミング制約を導出する導出手
段を備え、信号を定義する信号データは対応するプリン
トエンジンコンポーネント上の非オーバーラップイベン
トのシーケンスとして形成され、イベントは、動作を完
了するための時間インターバルに関連する対応するプリ
ントエンジンコンポーネントのアクションであり、タイ
ミング制約データは、対応するプリントエンジンコンポ
ーネントに対する１値か又は２値のインターバル制約の
いづれか一方として定義され、複数のプリントエンジン
コンポーネント能力データセットの各々を０に例示化す
る例示化手段を備え、各信号を規格化する信号規格化手
段を備え、各信号関連する最新のインターバルの最大の
開始点とその信号の最初のインターバルの最小の開始点
との間の距離としてリーチバック値を定義するリーチバ
ック手段を備え、各データセットのタイミング制約デー
タに従って最小の増分を決定する増分決定手段を備え、
選択されたクロック値に対して制限されたインターバル
から定義される期間を識別する期間識別手段を備え、最
大リーチバック値及び期間に従って境界値を定義する拡
張手段を備える。

【００１７】

【発明の実施の形態】本発明は、特定の部分において及
び特定の部分構成において物理的な形態をとることが可
能である。それらの好ましい実施の形態は、本明細書に
おいて図面に例示され、詳細に記述される。

【００１８】以下、図面を参照して説明を行う。図は、
本発明の好ましい実施の形態の例示のみを目的としてお
り、本発明を制限するものでない。図１は、モジュール
方式プリントエンジンＡを有する本発明の実施の形態を
示す。プリントエンジンＡは、複数のモジュール又はサ
ブアセンブリＢを含み、構成及びスケジューリングのた
めのデータプロセッサユニットＣを含む。本明細書にお
いて、”プリントエンジン”は、プリンタ、複写装置、
ファクシミリ装置等のような任意の複製装置を含む。

【００１９】以下に記述されるように、モジュールＢの
各々に与えられる様々な能力は、データプロセッサユニ
ットＣにおいて確認され相互に関連付けられる。そのよ
うな相互に関連付けられ分析されたデータは、所望のプ
リンタ動作又は一連のプリンタ動作を定義するユーザー
入力を考慮してさらに分析される。これらは次に、印刷
装置の動作を最適化、スケジュール、及び制御するため
に使用され、一連の印刷タスクがほぼ効率的に達成され
る。本発明のシステムは、例示として複写装置によって
記述される。任意のモジュール方式マテリアルハンドリ
ングシステムに対して、一般的な記述、リソースアセス
メント、及びスケジューリングが実行可能であることが
理解される。

【００２０】図１の特別な例により、モジュールＢは複
数のペーパーストレージビン（ｂｉｎ）を含んで図示さ
れる。この図において、これらはビン１０、１２、及び
１４を含む。複数のビンは、異なるペーパーサイズの、
又は２次的な、又は確保されたストレージ能力を有する
ことが可能である。シートフィーダーメカニズムが概略
的に１６に示される。当業者にとって明らかなように、
１６に示されるようなシートフィーダーは、１つ以上の
ビンからシートストックを得るために機能する。

【００２１】フィーダー１６は、コンベヤー１８へシー
トストックをフィードする。次にコンベヤーは、プリン
トメカニズム２０へシートストックをフィードする。該
メカニズムの特定な構成は当業者にとって周知である。
同じく、コンベヤー１８に沿って進行するシートストッ
クを選択的に反転するか又はフリップすることができる
インバーターメカニズム３０が図に示される。両面印刷
のためにシートストックをプリンターメカニズム２０へ
戻すためのフィードバックユニット３２が提供される。

【００２２】図において、コンベヤー１８は、印刷され
たドキュメントの選択的なステープリングを行うための
ステープリングメカニズム３４に対してパスを提供す
る。モジュールＢグループの最後のコンポーネントは、
ビン３８と４０によって表される複数の出力ビンであ
る。

【００２３】いくつかのモジュールは完全にメカニカル
であることが可能であり、いくつかはメカニカル及びコ
ンピュータデバイスの混合で構成可能であり、そしてい
くつかはコンピュータデバイスのみで構成可能であるこ
とが理解される。後者の例として、モジュールは、プロ
セッサ、データストレージ及びインストラクションスト
レージ、及び１セットの機能から構成可能である。該機
能は、ユーザーインプットからイメージデータを受入れ
て処理し、それを印刷するために他のモジュールに送り
出すことが可能である。これらの機能の速度に基づい
て、そのようなモジュールは、他の全てのモジュールＢ
と同様にスケジュール及び制御される。いくつかのモジ
ュールの例が、以下に図４と関連して記述される。

【００２４】データプロセッサユニットＣは、データ入
力／出力（Ｉ／Ｏ）ユニットを含み、該ユニットは、中
央プロセッサユニット（ＣＰＵ）／ストレージスケジュ
ーリングユニット４２とデータ通信を行う。この詳細に
ついて以下に記述される。モジュールＢの各々とデータ
Ｉ／Ｏユニット４０との間にデータ経路が提供される。

【００２５】好ましい実施の形態において、各モジュー
ルＢは様々な機能と能力に関連した記述を含む。そのよ
うな一般的な記述の例が以下に詳述される。図に示され
たモジュールの各々とデータＩ／Ｏユニットの間のデー
タ経路は、データプロセッサーユニットＣへの全てのそ
のような記述の取得を可能にする。好ましい実施の形態
において、任意のモジュールＢは、モジュール方式プリ
ントエンジンＡとの接続に際して、その関連する記述を
データＩ／Ｏユニットに伝達する。この能力は、本発明
のシステムの”プラグアンドプレイ（ｐｌｕｇ−ａｎｄ
−ｐｌａｙ）”能力を可能にする。

【００２６】データプロセッサーＣのデータＩ／Ｏユニ
ット４０と様々なモジュールＢとの間のデータ相互接続
は、コントローラの起動を可能にする。従って、データ
プロセッサーユニットＣは、有効なモジュールからモジ
ュール方式プリントエンジンＡの能力の完全なセットを
確認する。ユーザー入力４４からＩ／Ｏユニット４０へ
結合されるこの情報は、有効なモジュール方式リソース
を効率的にスケジューリングし有効なコンポーネントの
使用によって一連の印刷ジョブを達成することを可能に
する。

【００２７】図２を参照し、一般的なプリントエンジン
の記述のための基本的フォーマットとスケジューリング
について記述する。先に述べたように、自動プリントエ
ンジンスケジューリングソフトウェアのための過去の試
みは、完全なエンジン構成の分析に基づくものであっ
た。この分析の結果は、特別なユニット構成に対して仕
様化された専用のソフトウェアの書込みのために必要と
される。逆に言えば、本発明のシステムは、スケジュー
リングソフトウェアを２つの部分に分離する。第１の部
分において、スケジューラアーキテクチャは汎用アルゴ
リズムを備えている。第２の部分において、以下に詳述
されるフォーマットで装置固有の情報が提供される。

【００２８】与えられたプリントエンジンに印刷される
ドキュメントが与えられると、ドキュメントを生成する
ための装置動作を識別し、スケジュールし、初期化する
ためのスケジューラが提供される。図１において、その
ような動作は、シートのフィード、シートの移動、画像
の生成、シートへの画像の転写等を含む。印刷されるド
キュメントは、通常は増分的に（例えば１枚ずつ）到着
することが理解される。スケジューリングとスケジュー
ルの実行（印刷）は通常並列に発生する。結果として、
スケジューラによって使用される装置固有の情報は、所
望のシートを生成する動作をスケジューラが識別可能な
ように構造化される。さらに、システムは、動作をスケ
ジューリングする際に必ず発生する制約を認識していな
ければならない。さらに、システムは、適切なコマンド
をモジュールに与えてモジュールの有効な動作を達成す
る手段を備えている。

【００２９】図２において、装置固有の情報を与える特
別なシステムが示される。該システムは、ブロック１０
０においてプリントエンジンモジュールの宣言記述（モ
デル）を使用することによって始まる。そのようなモデ
ルは、モジュール構造の記述とそのコンポーネントの潜
在的な動作を含む。図１の例において示されるように、
可能なコンポーネントは、フィードトレイ、トランスポ
ートベルト、転写コンポーネント、インバータ、ゲー
ト、その他を含む。潜在的な動作は、例えば、インバー
タのバイパス、又はシートを逆転するためのインバータ
の使用を含むことができる。モデル化のステップは、モ
デル化を行う言語を使用してエンジニアによって通常は
実行される。これに関する好ましい実施の形態の詳細が
以下に記述される。

【００３０】ブロック１０２において、モジュールはそ
のコンポーネントによってすでにモデル化されている。
次に、コンポーネントモデルから得られた情報からモジ
ュール全体の潜在的な動作の自動的導出が実行される。
例えば、この導出は、シミュレーション又は部分的な評
価によって、及び推定（エンビジョンメント）によって
実行可能である。シミュレーションは、現実のシステム
の実行を反映するモデルの実行として一般的に理解され
る。部分的な評価は、プログラムの部分的な実行として
一般的に理解され、プログラムの特定の部分は後に評価
されるものとして未実行のまま残される。推定は、シス
テムの全ての潜在的な動作の探査として一般的に理解さ
れ、これは例えば、システムのモデルのシミュレーショ
ン又は部分的評価を繰り返し多様な方法で実行すること
によって行われる。結果として生ずる全体的モジュール
動作は、特定の動作によって生成される出力、その出力
が生成される入力、その全体的動作を生成するために必
要な個別動作（その”道のり”）、及び、個別動作を実
行する際に観測されるリソース及びタイミングに対する
多様な制約から構成される。この情報の特定の部分又は
全ては、有利にプリコンパイルされることができる。例
えば、これは有限状態マシンにコンパイルされることが
できる。

【００３１】複数のプリントエンジンモジュールＢ（図
１）がいっしょにプラグインされて新たな構成を形成す
る場合、異なるモジュール動作はデータプロセッサＣを
介して収集及び自動的に合成され、プリントエンジンＡ
全体の潜在的動作が生成される。

【００３２】前述の合成は、ダイナミックに（即ち、１
つの動作がスケジューラによって選択されるたびごと
に）発生するよう適切にイネーブルにされ、前述の合成
によってモジュール動作が装置動作中に合成される。従
って、合成は、（モジュールがいっしょにプラグインさ
れた後に）一度だけ、又はそれが必要とされるたびごと
に実行されることが可能である。後者のオプションは、
ダイナミックなモジュール変更を可能とする利点を有す
る。従って、装置動作が選択されるたびごとに、システ
ムは図２のシーケンスを完了することができる。時間の
かかるコンピュータ処理のために、そうすることが禁止
されることができる。しかし、これは特定の状況におい
てはより効率的なアプローチであり得る。

【００３３】ブロック１０４において、前述の全体的動
作は、前述の個々のモジュール動作と関連するフォーマ
ットに類似のフォーマットで有利にモデル化される。異
なる全体的動作ごとに、システムは、（動作識別のため
の）出力記述、（シーケンス化のための）リソース及び
タイミング制約、及び（装置動作の次の制御のための）
道のりを含むデータを提供する。

【００３４】次に、システムはブロック１０６へ進み、
マッチングスケジューラアルゴリズムにおける効率的使
用のために装置動作情報部分は有利にコンパイルされ
る。例えば、タイミング及びリソース制約の潜在的なイ
ンタラクションのコンパイルは、有限状態マシンに形成
されることができる。ブロック１０８において、コンパ
イルされた動作のフルセットが得られる。

【００３５】最後に、ブロック１１０において、装置動
作の出力記述が汎用スケジューラによって使用され、
（オリジナルフォーム又はコンパイルされたフォーム
で）オリジナルな制約を与えられた出力ドキュメントを
生成する動作が識別される。これらが使用されて、特定
の全体的動作に必要とされる個別動作の各々に対する適
正なタイミング、及び、モジュールＢに必要な動作を実
行させるために使用される道のりが見いだされる。

【００３６】前述の説明は好ましい実施例によって与え
られたが、有用なシステムを提供するために前述のステ
ップ全てが必ずしも必要とされないことが理解される。
例えば、全てのコンポーネントの内の一部のみがモデル
化されることが必要とされ、全ての制約のコンパイルは
必ずしも必要とされない。

【００３７】前述のシステムにより、プリントエンジン
モジュールのモジュール方式（”プラグアンドプレ
イ”）スケジューリングが容易にされる。該システムは
また、広範囲にわたる構成のためのスケジューリングソ
フトウェアの再利用を可能にする。該システムはまた、
装置を形成している離散的なモジュールの初期記述を得
るステップを除く全てのステップの自動化、及び、一般
的なスケジューリングアルゴリズムの形成を提供する。

【００３８】図３を参照し、コンポーネント動作をモデ
ル化するための特別なシステムが記載される。好ましい
実施例としてのこの特別なシステムは、プリントエンジ
ン分析、シミュレーション、及びスケジューリングのた
めのプリントエンジンコンポーネント動作の記述のため
のものである。前述のように、基本的、一般的な記述方
法は多様な他のモジュラーシステムに等しく適用でき
る。

【００３９】本発明の記述方法において、コンポーネン
トの構造及び動作は能力（潜在的動作）に関して記述さ
れ、この能力に対して、ワークユニット、タイミング、
及びリソースについての制約が記述される。このモデル
化システムは、プリントエンジンにおけるコンポーネン
トインタラクションの分析とシミュレーションのための
コンポーネントの構造及び動作の合成を可能にする。本
システムは、モジュール方式プリントエンジンのスケジ
ューリング動作に特に適用可能である。

【００４０】本発明の方法によって、形成されるプリン
トエンジンがコンポーネント記述の合成によって記述可
能となるようプリントエンジンコンポーネントが記述さ
れる。さらに、結果として生ずるプリントエンジン記述
の上で多様なアプリケーションが自動的に実行されるこ
とができる。これによって、そのような情報を分析、シ
ミュレーション、スケジューリング、及び関連するプリ
ントエンジンアプリケーションのために自動的に使用す
ることが可能になる。図３の実施例において、（図１の
インバータ３０に類似の）インバータ１５０に関連する
記述にモデル１５０’が与えられる。モデル化された構
造のコンポーネント及び動作は、コンポーネント自体の
物理的特性、及びモデルが使用されるアプリケーション
の内容の両方によって決定される。

【００４１】本システムにおいて、コンポーネントの構
造モデルは、その物理的なインターフェース、ソフトウ
ェアインターフェース、及び内部リソースから構成され
るものとして定義される。例えば、物理的なインターフ
ェースは、ワークユニット（シート）が入力される入力
ポート１５２、及び前記ワークユニットが出力されるる
出力ポート１５４である。関連するソフトウェアインタ
ーフェースは、主に制御コマンドとパラメータに対して
機能する。内部リソースは、特定の動作を実行するため
に必要とされるオブジェクトとして定義され、この場
合、動作の反復実行によるオブジェクトの複数使用が限
定される。図３の例において、関連するゲート１５６の
位置としてリソースが定義される。リソースのもう一つ
の例は、インバータ１５０の対向する出力ローラー間の
スペース１５８である。ここで、ペーパーパスのほとん
どのポイントと同様に、任意の単一ポイントにおいて時
間内に１つのシートに対してのみ充分なスペースが存在
する。従って、スペース１５８はリソースとして定義さ
れる。

【００４２】コンポーネントの動作モデルは、当該コン
ポーネントを介して移動するワークユニットに対して当
該コンポーネントがどのように作用するかに関して特定
のコンポーネントの能力を記述するために使用される。
さらに、動作モデルは、関連する動作を行う際にどのよ
うな制約が観測されなければならないかを示す。

【００４３】コンポーネント能力は、ワークユニットの
記述、ワークユニットの処理の記述、ワークユニットの
入力及び出力のようなタイミングのとられたイベントの
記述、処理に対するリソースの割当の記述、及びイベン
トのタイミング及びリソース割当に対する制約の記述か
ら構成されるものとして定義される。ワークユニット
は、それらの属性に関して有利に記述される。ワークユ
ニットの制限及び処理は、それらの属性に対する制約に
関して有利に記述される。

【００４４】図３において、いくらかの付加的モデル記
述が提供される。これらは、１６４で示されたシートの
ような特定のワークユニットに関連した記述を含む。イ
ンバータ１５０をバイパスするかしないか、もしくは反
転のためにそれを使用するかしないかといったような制
御状態が１６６に示される。パスの長さやローラー速度
の仕様のようなタイミングパラメータが１６８で提供さ
れる。例えば、関連するタイミング制約は、パスの長さ
とローラー速度に基づく規則を使用して適切に得られ、
例えば、出力時間は、パスの長さをローラー速度で除算
した値に入力時間を加えたものとして定義されることが
できる。特定の値は同じく適切に当該モデルのパラメー
タである。例えば、与えられたインバータのパスの長さ
が固定される一方で、ローラー速度が変化することがで
きて、従って使用されるモデルに対する環境によって設
定されることができる。ローラー速度パラメータは１７
０で示される。

【００４５】例えば、以下のリストは、図３に関連して
示されたインバータの適切なモデルを提供する。

【００４６】

【数１】

【００４７】このモデルは、２つのパラメータ（ｌｅｎ
ｇｔｈ及びｓｐｅｅｄ）、１つの入力ポート（ｉｎ）、
１つの出力ポート（ｏｕｔ）、３つのリソース（ｉｎ
Ｒ、ｏｕｔＲ、及びｇａｔｅＲ）、及び６つの変数を宣
言する。また、このモデルは２つの能力（ｂｙｐａｓｓ
（バイパス）及びｉｎｖｅｒｔ（反転））を定義する。
バイパス能力に対して、シートｓが時間ｔ＿ｉｎで入力
されて時間ｔ＿ｏｕｔで出力されること、３つのリソー
スの全てにおいてｔ＿ｉｎ、ｔ＿ｏｕｔ、及びｔ＿ｇａ
ｔｅのそれぞれで割当がなされること、及び、入力から
出力までの移動時間を反映する多くのタイミング制約が
インターバル間で維持されることが定義される。シート
がその配勾を１８０°変えること（ｙ軸の回りに回転さ
れること）と移動時間がより長いこと（そのシートサイ
ズに比例する）とを除いて反転能力も同様に定義され
る。このように、任意のコンポーネントの完全な機能の
記述が提供されることが理解される。

【００４８】本発明のモデル化システムにより、他のコ
ンポーネントの記述及び他のコンポーネントとの相互作
用の記述の参照に依らずにコンポーネント構造が記述さ
れる。そのようなコンポーネント動作は、他のワークユ
ニットに依らず１つのワークユニットに対して記述され
る。さらに、本発明のモデル化システムは、プリントエ
ンジンの一般的な増分的分析、シミュレーション、及び
スケジューリングに対するコンポーネント能力の自動的
な動作的合成を可能にする。この記述フォーマットは、
連結されたコンポーネント（例えば、プリントエンジン
モジュール）を記述するモデルに対して、コンポーネン
トモデルの自動的な構造上の合成を可能とする。

【００４９】逆に言えば、従来のアプローチでは、能力
及び制約は、コンポーネント間の特定な相互作用及びシ
ート又はイメージシーケンス間の相互作用の両方に関し
て表現されていた。このことは、それらを定義するのを
より困難にし、それらを再使用不可能にし、さらにそれ
らを合成不可能にする。システムをモデル化するフォー
マットは、前述の自動的な構成、最適化、及びスケジュ
ーリングを可能にする。

【００５０】前述の説明から理解されるように、プリン
トエンジンのスケジューリングはその大部分が関連リソ
ースのスケジューリングである。これを効果的に行うた
めに、プリントエンジン動作の適正なシーケンスを増分
的にスケジューリングために情報が使用可能となるよ
う、プリントエンジン動作によって使用されるリソース
をモデル化しなければならない。広範囲のプリントエン
ジン動作に適用可能であることに加えて、リソースはま
た、スケジューラと、装置内の変化の情報を伝えるプリ
ントエンジン制御ソフトウェアの残りの部分との間の一
般的なインターフェイスとして適切に作用することがで
きる。

【００５１】プリントエンジンのような装置のコンポー
ネントは、それらの能力を実行するためのリソースを通
常必要とする。例えば、特に印刷装置に関して、リソー
スは、ベルト上のスペース、特定の位置になければなら
ないゲート、又は、複数又はオーバーラップ使用のため
に配置されるいくつかのエレメントであり得る。ペーパ
ービンの容量はそのような複数又はオーバーラップ使用
の１例である。

【００５２】リソースの割当は、コンポーネント動作記
述の一部分として明示的に適切にモデル化される。本明
細書において、リソース割当は、リソースについての要
求の仕様として定義され、この要求はその期間中に特定
のリソースが必要とされる時間インターバルを伴う。例
えば、画像形成能力は、特定の時間について受光体ベル
ト上にスペースを必要とする。この他の例として、イン
バータ能力は、シートが反転されている期間中にインバ
ータゲートが適正位置になければならないことを必要と
する。

【００５３】本明細書において定義されるリソース要求
は、特定のリソースタイプに依存して選択される。可能
なリソースタイプは、ブーリアン（Ｂｏｏｌｅａｎ）リ
ソース（使用されるかされないかいづれかのリソー
ス）、計数された又は状態リソース（有効な状態の内の
１つに置かれたリソース）、容量リソース（同時使用が
追加される）、等のアイテムを含む。このようなリソー
スタイプはリソース制約によって一般的に有利に記述さ
れる。リソース制約は、同一リソースに対する複数割当
に対してそれ自体で整合性を決定する。

【００５４】例えば、ベルト上のスペースのようなブー
リアンリソース割当は、同時にオーバーラップしてはな
らない。逆に、状態リソース割当は、同一の状態が必要
とされる場合はオーバーラップ可能である。容量リソー
ス割当は、要求の合計が所与の容量を越えない限りオー
バーラップ可能である。このようなリソースタイプは前
述のリソース制約を変更又はそれに特定の制約を付加す
ることによって容易に拡張可能である。

【００５５】リソース割当の時間インターバルは、イン
ターバル制約によって適切に連結される。本明細書にお
いて、リソース制約システムとインターバル制約システ
ムは相互に直交する。リソース割当とタイミング制約の
記述は、スケジューリングに対する合成によるモデル化
パラダイムに良好にフィットする。

【００５６】全てのコンポーネントが完全にモデル化さ
れると、プリントエンジンは最終的にランタイム状態に
移行される。図４を特に参照すると、プリントエンジン
モジュール２０２とデータ通信状態にあるスケジューラ
２００が示される。プリントエンジンモジュール２０２
はいくつかのコンポーネントから構成され、コンポーネ
ントの各々はペーパー／画像パス２０４に沿って選択的
に配置されたリソースを使用する。そのようなリソース
は、コンポーネント２１０、２１２、２１４、２１６、
２１８、及び２２０で示される（それぞれは各コンポー
ネントに対応するリソースである）。これらリソースの
各々は同一の形態で適切に記述され、その内の１つが２
１６’で詳細に示される。このシステムは、制御コード
部分２２０、コンポーネント／モデル部分２２２、及び
多くの通信パスを含む。制御パス２２４は、制御コマン
ドを制御コード部分２２０からコンポーネント／モデル
部分２２２へ伝送することを可能にする。同様に、セン
サーパス２２６は、センサーデータをコンポーネント／
モデル部分２２２から制御コード部分２２０へ伝送する
ことを可能とする。パス２２８は、コンポーネントによ
るリソースのスケジューリングされた使用を表す。より
詳細には、パス２２８は、コンポーネントを記述するモ
デル２２２から知識をスケジューラへ伝送し、この知識
が使用されてリソースの適正な使用がスケジューリング
される。パス２３０は、制御及びセンサー情報を同様に
スケジューラ２００へ伝送することを可能とする。

【００５７】ランタイムにおいて、スケジュール動作が
行われている場合、スケジューラ２００は、同一のリソ
ースに対する対応する割当が、要求されたリソース制約
を満たすようインターバルを保証する。このことはま
た、過去のリソース割当を記録することによって適切に
増分的に実行される。

【００５８】通常動作期間中において、スケジューラ２
００は自身の割当のみを考慮する。これを行うために、
スケジューラ２００は、システムのモデルを使用して該
スケジューラがすでにスケジューリングした動作に対す
るリソースの使用を記述する。

【００５９】このシステムはまた、リアルタイムでリア
クティブな環境に容易に適用可能であり、そのような環
境では、リソースが時々無効になるか又は通常容量のサ
ブセットに限定される。現実のハードウェアにおけるそ
のような変化は、例えば制御コード部分２２０に設けら
れたモジュールの制御ソフトウェアによって通常はモニ
ターされる。従来のシステムにおいては、スケジューラ
に特別なインターフェイスをもたせてモデルと現実のハ
ードウェアとの間の変移を伝送するために、又は制御さ
れたソフトウェアにスケジューラをアクセス可能とする
ために制御ソフトウェアが必要とされていた。

【００６０】スケジューラ２００内のリソース管理は、
適切に環境にアクセス可能にされる。より詳細には、こ
れはコンポーネント制御コード２２０に対して有効とさ
れる。スケジューラ２００と同様に、制御コード２２０
は、そのようなリソースの計算を補助してハードウェア
の変化を反映することを可能にされる。このことは、ス
ケジューラ２００が自動的にシステムの変化を考慮する
ことを可能とする。

【００６１】モデルが使用されてコンポーネント能力の
デフォルト動作（リソース割当）が定義される。一方、
制御コード自体は現行の状況を反映するようその動作を
適応させる。このことは、環境によってリソース制約が
変化する場合においても適切に拡張される。一般的に、
このことは、スケジューラがリソースを使用しつつ（デ
フォルト定義から開始して）制御ソフトウェアがリソー
スを制御するように見える。

【００６２】現実のオンラインによる実施において、ス
ケジューラはそのような未来の割当を自動的に作成し、
それらを考慮する。スケジューラが先を見越してさらに
割当を作成する場合、割当は、それがスケジューラ２０
０（それぞれモデル２２２）からのものか又は制御コー
ド２２０からのものかに依存して異なる優先度を適切に
タグ付けされる。これによって、環境による割当と矛盾
するスケジューラによる任意の割当は、適切に自動的に
識別されて修正される。

【００６３】本発明のシステムは、プリントエンジンに
固有の情報に関連するソフトウェアの一般的なスケジュ
ーリングを提供する。このスケジューリングは、プリン
トエンジンが個々のモジュールからカスタマーによって
合成される場合であっても提供される。システムは、モ
ジュール能力に従って作成されたプリントエンジンモジ
ュールの記述に基づいて動作する。本明細書において、
モジュール能力は本質的に、潜在的なモジュール出力で
ある。例えば、プリントエンジンモジュールのモジュー
ル能力によって生成されるモジュール出力は、２つの画
像を有して画像面を下にして搬送されるＡ４サイズのシ
ートであることが可能である。

【００６４】より詳細には、モジュール能力は、特定の
出力の生成のトレースと考えられる。このトレースは、
モジュールポートにおける入力及び出力の両者の記述を
適切に有する。図５を参照すると、例示としてのプリン
トエンジン２５０はモジュール２５２、２５４、及び２
５６を含み、これらはポート２７０及び２７２にそれぞ
れ接続される。これらモジュールは図示された能力２６
０、２６２、及び２６４をそれぞれ与えられている。モ
ジュール２５２、２５４、及び２５６に対してデータ通
信パス２７４が与えられ、それらの能力をプリントエン
ジン制御ソフトウェアへレポートする。

【００６５】例えば、モジュール２５２は入力トレイ２
８０を有する。モジュール２５４は受光体２８２及びデ
ュープレックスフィードバックメカニズム２８４を有す
る。モジュール２５６は出力トレイ２８６を有する。

【００６６】モジュール能力は、モジュール入力及び出
力ポートにそれぞれ関連する入力及び出力ワークユニッ
ト両者の記述、所望の生成動作に対して必要とされるリ
ソース割当、及び出力が生成される道のりを適切に有す
る。ワークユニットは、それらの属性に対する制約によ
って適切に記述される。リソース割当は、それらの時間
インターバルに対する制約と共に記述される。

【００６７】モジュールのリソース割当は、コンパイル
された形態で適切に存在可能である。例えば、リソース
割当は、有限状態マシンにおける可能な割当のバリエー
ションとして存在可能である。

【００６８】例示目的のために、＜Ｉ，Ｏ，Ｒ，Ｃ＞
は、入力Ｉ、出力Ｏ、リソース割当Ｒ、及び道のりＣを
有する特定の能力を表すものとする。新たなプリントエ
ンジンを形成するモジュールがいっしょにプラグインさ
れてエンジンが始動する場合、接続２７４、２７４’、
及び２７４”を介して全てのプリントエンジンモジュー
ルから得られるモジュール能力２９０を収集及び合成す
ることによってスケジューラ又は他の連結されたソフト
ウェアコンポーネントが構成される。

【００６９】１つのポートで接続された２つの装置モジ
ュールのモジュール能力を繰り返し合成することによっ
て装置能力に対してモジュール能力が合成される。例え
ば、第１及び第２のモジュールがポートｐで接続される
場合、（Ｏ1 で定義される）ｐでの出力を生成する第１
モジュールのモジュール能力＜Ｉ1 ，Ｏ1 ，Ｒ1 ，Ｃ1
＞の全てに対して、及び、（Ｉ2 で定義される）ｐでの
入力を予期する第２モジュールのモジュール能力＜Ｉ2
，Ｏ2 ，Ｒ2 ，Ｃ2 ＞の全てに対して、Ｏ1 及びＩ2
での出力及び入力それぞれが一体化（１対１対応）可能
な場合には、それら能力は適切に合成される。属性制約
はこのプロセスにおいて伝搬する。

【００７０】例えば、Ｏ1 がシートサイズを制限する場
合、このことはＩ2 を介して第２の能力へ伝搬される。
一体化が達成されると、Ｉ2 におけるポートｐの入力を
伴わずにＩをＩ1 ＋Ｉ2 に設定し、ＯをＯ2 に設定し、
ＲをＲ1 ＋Ｒ2 に設定し、ＣをＣ1 ＋Ｃ2 に設定するこ
とによって合成能力＜Ｉ，Ｏ，Ｒ，Ｃ＞が生成される。

【００７１】このモジュール能力の合成は、結果として
生じる能力がモジュール間ポートにおける入力及び出力
でない入力及び出力のみを有するようになるまで実行さ
れる。即ち、入力又は出力に連結されるモジュール能力
がさらに存在しないこととなる。結果として生じるその
ような能力はプリントエンジン能力となる。モジュール
は一般にいくつかの異なる能力を有するため、全ての代
替に対してモジュール能力の合成が各々実行され、複数
のプリントエンジン能力が結果として生じる。例えば、
図５の各モジュールが２つの能力を有する場合、いくつ
かのモジュール能力の入力が他のモジュール能力の出力
と一体化不可能でない限り、プリントエンジン全体は潜
在的に８つの能力を有する。

【００７２】ワークユニットの属性が１回の循環パスで
１回だけ変化し、入力及び／又は出力で有限数の許容可
能な属性値が存在する場合に限り、前述の方法は循環パ
スに対しても動作する。そのようなパスにおいては、同
一のワークユニットが（いくつかのモジュールを介し
て）１回以上同一ポートへ移動される。

【００７３】モジュール能力のそのような合成が効率的
に実行されることが可能である。プリントエンジン始動
時間が理想的に小さい範囲内でこのことは重要である。
このシステムの特別な利点は、スケジューラがランタイ
ムにおいてプリントエンジンのモジュールにおける動作
を一般的にスケジューリング可能となるモジュール方式
プリントエンジンの記述を生成することである。ワーク
ユニット属性制約の伝搬及びタイミング制約を伴うリソ
ース割当の合成を通じて、スケジューラはモジュール間
の適正な相互作用のみを可能とすることを保証される。
例えば、仕上げモジュールでシート間の遅延が必要とさ
れる場合、システムは適切に及び自動的にこのことを全
ての必要とされる先行するモジュールへ伝搬する。先に
述べたように、このことは、スケジューリングソフトウ
ェアが開発される時点でプリントエンジンモジュール間
の潜在的な相互作用が既知でなければならない従来のア
プローチとは対照的である。

【００７４】バリエーションとして、プリントエンジン
始動時にモジュール能力の合成が行われない代わりに、
スケジューラによって時間ごとにプリントエンジン全体
の能力が識別される。この場合、１つのプリントエンジ
ン出力ポートにおける所望出力の属性記述から開始し、
その出力記述をそのポートで出力を生成するモジュール
能力の記述とマッチングすることで前述の方法はモジュ
ールを通じて適切に後戻りして実行される。次に、この
方法は選択されたモジュール能力の入力と、連結された
先行するモジュール能力の出力とを再び一体化する。１
つの入力と、連結された先行するモジュール能力の出力
とが一体化不可能な場合（即ち、所望入力が先行するモ
ジュールによって生成不可能な場合）、この方法はバッ
クトラックを行って代替的モジュール能力を試行する。
このような合成は、結果として生じる能力の全ての入力
がプリントエンジンの入力となるまで実行される。結果
として、所望出力を生成可能なプリントエンジン能力が
得られる。残りのデータ、リソース、タイミング、及
び、道のり情報は前述のように合成され、結果として生
じる能力の適正なスケジューリング及び実行のために使
用されることが可能である。

【００７５】次に、プリントエンジンにおいて所望ドキ
ュメント生成するために必要な動作を一般的にスケジュ
ーリングシステムについて説明を行う。この動作は、一
般的なスケジューリングアルゴリズムとプリントエンジ
ン固有の情報との分離に基づく。このことは、アルゴリ
ズムとプリントエンジンアーキテクチャの両者を広範囲
なプリントエンジンファミリーに対して再使用すること
を可能とする。このことは、スケジューラに対するプリ
ントエンジンの情報がスケジューリングアルゴリズムに
組み込まれていた従来の方法とは対照的である。従っ
て、これら従来のシステムにおいては、組み込まれたア
ルゴリズムは容易に再使用不可能であった。

【００７６】図６を参照すると、プリントエンジン能力
のセット３００が示される。印刷装置動作の現実のスケ
ジューリングは、所望の結果を達成するために必要な動
作のセットを識別するステップ３０２を含む。次に、こ
れら動作のシーケンスがブロック３０４で決定される。
ブロック３０６において、印刷装置動作のスケジューリ
ングの始動が達成され、コンポーネント制御コマンドの
セットがスケジューリングシステムからの出力として３
０８で提供される。

【００７７】図６から、プリントエンジン能力３００
は、出力、制約、及び道のりに関する情報を含む。ブロ
ック３０２の識別によって、そのような能力のサブセッ
ト３２０が発生する。次に、選択された能力３２０が、
シーケンス動作３０４及び始動動作３０６と共に使用さ
れる。

【００７８】図６のシステムを通じた実際のドキュメン
トのフローのトレースは、所望のドキュメントに対する
実際の入力が識別ブロック３０２に与えられる場合に開
始する。この時点から、所望ドキュメントの形成を達成
するために必要な能力が決定される。識別ブロック３０
２の出力は、そのような生の能力をタイミングがとられ
ていない形態で提供する。シーケンスブロック３０４に
おいて、ドキュメントの形成を達成するために必要なタ
イミング情報が提供される。従って、ブロック３０４か
らブロック３０６への出力は、時間能力の参照を伴って
提供される。前述のように、このことは、３０８でコン
ポーネント制御コマンドをリターンする。

【００７９】本発明のシステムにおいて、スケジューリ
ングは一般的に、シート毎ベースのように、プリント動
作に対して増分的に同時進行的に動作しなければならな
い。従って、図６において、システムは、各々が所定の
タスクを達成するいくつかのコンポーネントに分割され
る。

【００８０】図６の３００に見られるようなプリントエ
ンジン能力の適切な例は、潜在的なプリントエンジン出
力であり得る。例えば、そのような出力は、２つの画像
を有して画像面を下にしたＡ４シートであり得る。より
詳細には、プリントエンジン能力は、装置の出力ポート
で定義される出力の記述、出力を生成するために必要な
リソース割当の記述、及び、出力が生成される道のりの
記述を有する。プリントエンジンにおけるシートのよう
なワークユニットは、先に詳述したようにそれらの属性
に対する制約によって適切に記述される。そのようなリ
ソース割当は、それらの時間インターバルに対する制約
と共に記述される。

【００８１】次に、自動的に有限状態マシンを生成して
プリントエンジン能力のスケジューリングを可能とする
システムについて説明を行う。

【００８２】能力タイミング制約はインターバル制約で
ある。能力のタイミング制約が、同等でない制約を全く
有さない場合、それらは有限なリーチバックを有する。
即ち、それらのインターバルセットは常に有限なインタ
ーバル内に存在する。このことは、最適なスケジュール
をサーチするスケジューリングアルゴリズムに対して２
つの重要な結果をもたらす。スケジューラは能力セット
の最大リーチバックを越えてサーチを行う必要が全くな
く、また、最大リーチバックはスケジュールに対する同
等な関係を定義する。（同等なものを有さない能力はリ
ジッドな能力と呼ばれる。同等でないものを同等となる
よう近似することによって、この方法全体はまたフレキ
シブルな能力（即ち、同等な制約を有する能力）に適用
可能である。しかし、結果として生じる有限状態マシン
は最適でない可能性がある。） 能力の導出は、信号及びタイミング制約を結果として生
じる。（以後、用語”能力”は、１つの導出された能力
の信号及び制約のセットを示すために使用される。）信
号は、（構成コンポーネントの出力ポートの）非オーバ
ーラップイベントのシーケンスである。イベントは、イ
ンターバルに関連するアクションである。タイミング制
約は、１値及び２値のインターバル制約である。

【００８３】ｍ個の能力を仮定する。各能力ｊにおい
て、ｎ個の順序づけられた信号Ｓ_i （ｊ）＝〔ｔ
₁ （ｉ，ｊ）， ．．． ，ｔ_n(i,j)（ｉ，ｊ）〕（ｉ
＝１，．．． ，ｎであり信号インデックスと呼ばれ、
ｊ＝１， ．．． ，ｍであり能力インデックスと呼ば
れる。）ここで、信号のイベントのインターバルｔのみ
が表される。ｎ（ｉ，ｊ）は０になり得る。ｔ
_out （ｊ）＝（ｓ_out （ｊ），ｄ_out （ｊ））を能力ｊ
のエンドインターバルとする。即ち、出力ポートに対応
する、当該信号におけるインターバルである。全てのタ
イミング制約は信号Ｓ_i（ｊ）におけるインターバルに
関する。

【００８４】有限状態マシンの状態スペースを少なくす
るために制約が無視されてランタイム中にチェックされ
る場合、このことはいくつかの点で不都合を生じる可能
性がある。例えば、位置合わせされた当該期間内にある
制約が後の分析から排除される場合、能力期間は一般に
非常に短くなる。代替的に、信号全体及びそれらの制約
が排除されることが可能であり、このことは同等関係を
強化する可能性がある。

【００８５】増分的な最適スケジューリングのために、
以下の分析及びその結果生じるパラメータが必要であ
る。

【００８６】例示化（ｉｎｓｔａｎｔｉａｔｉｏｎ）：
分析は、各能力エンドを０に例示化することによって
開始する。

【００８７】

【数２】

【００８８】全ての２値制約は同等な制約であるため、
このことは全ての他のインターバルも同様に例示化し、
２値制約は除去可能になる。残りの制約（例えば、位置
合わせされ、当該期間内にあり、パスのない制約）は統
合制約（ｉｎｔｅｇｒａｔｉｏｎ ｃｏｎｓｔｒａｉｎ
ｔｓ）と呼ばれる。例示化の後、能力は現行のスケジュ
ールに統合されることが可能であり、これは全てのイン
ターバルを一定量シフトすること及び統合制約をチェッ
クすることによって行われる。

【００８９】規格化（ｎｏｒｍａｌｉｚａｔｉｏｎ）：
各信号インデックスｉに対して、信号の最後のインタ
ーバルと能力のエンドとの間の全ての能力にわたる最小
距離を規格化シフトｕ_i とする。即ち、例示化された能
力に対して次式が成り立つ。

【００９０】

【数３】

【００９１】（ｓ_n(i,j)（ｉ，ｊ）はｔ_n(i,j)（ｉ，
ｊ）（信号Ｓ_i （ｊ）の最後のインターバル）のスター
トである。規格化定数ｕ_i は負又は０である。） 全ての能力において信号ｉがｕ_i だけシフトされる場
合、特定の能力ｊにおける少なくとも１つの信号Ｓ
_i （ｊ）はその最後のインターバルを０でスタートす
る。

【００９２】リーチバック（ｒｅａｃｈ−ｂａｃｋ）：
各信号ｉに対して、任意の能力における信号の最後の
インターバルの最大のスタートと任意の能力における信
号の最初のインターバルの最小スタートとの間の距離を
規格化されたリーチバックｒ _i とする。即ち、規格化シ
フトを伴う例示化された能力に対して次式が成り立つ。

【００９３】

【数４】

【００９４】（ｓ₁ （ｉ，ｊ）はｔ₁ （ｉ，ｊ）（信号
Ｓ_i （ｊ）の最初のインターバル）のスタートであ
る。） 最大リーチバックｒ_max をｒ_max ＝ｍａｘ_{i=1, ... ,n}
（ｒ）とする。

【００９５】インクリメント（ｉｎｃｒｅｍｅｎｔ）：
能力の最適配置をサーチする場合、スケジューラはミ
リ秒ごとに試行を行う必要はない。その代わりに、最小
インクリメントがタイミング制約から算出可能である。
これは、例示化された能力の継続時間及び全てのインタ
ーバルのスタート、及び全ての制約を位置合わせされて
当該期間にある制約から収集し、これらの数値の最大共
通分母（”ＧＣＤ”）を算出することによって実行可能
である。結果として得られるインクリメントをｉｎｃと
する。

【００９６】期間（ｐｅｒｉｏｄ）： 特定のクロック
に対してインターバルを制限する、位置合わせされた当
該期間にある制約が与えれる場合、能力期間が識別され
ることが可能である。（例えば、複数の特定のタイミン
グが特定の１つの期間を法として同一である場合、これ
らタイミングは同等なものとして識別可能である。） 全ての能力について当該期間にある任意の制約における
最大の期間定数、又は、そのような期間定数が存在しな
い場合には、全ての能力について位置合わせされた任意
の制約における最大の位置合わせファクタ、又は、前記
期間及び前記位置合わせされた制約のいづれもが存在し
ない場合には、インクリメントｉｎｃを期間ｐとする。

【００９７】拡張（ｅｘｔｅｎｓｉｏｎ）： 最大リー
チバックｒ_max 及び期間ｐがあたえられる場合、所与の
スケジュールのエンドから新たに統合された能力までの
オフセットを境界付けることが可能である。最小の拡張
境界をｅｘｔ＝ｍａｘ（ｒ_{ma x} ，ｐ）とする。１つの能
力に由来するリソース割当のみを有する状態は基本状態
と呼ばれる。１つの能力によって状態を拡張する場合、
最大の拡張は基本状態に帰結される。特定の期間におい
て、その期間内の全てのエンドに対する全ての基本状態
はそこに到達されなければならない。能力ｊに対してｅ
ｘｔ−ｒ_j ＋ｉｎｃが期間ｐ以上である場合、最小拡張
境界ｅｘｔは状態を拡張して全ての基本状態に至らせる
のに充分である。そうでない場合、拡張境界はその差だ
け増加されなければならない。従って、各能力ｊに対し
て、ｅｘｔ_j ＝ｅｘｔ＋ｍａｘ（０，ｐ−（ｅｘｔ−ｒ
_j ＋ｉｎｃ））とする。

【００９８】前述の能力パラメータが与えられる場合、
最初に全ての初期状態を生成し、次に、多様なオフセッ
トで能力を統合して新たな状態を導出することによって
有限状態マシンが生成可能となる。このことはスケジュ
ール及び状態に対するいくつかの処理を必要とする。即
ち、スケジュールを拡張すること、スケジュールをクリ
ップして状態と得ること、状態を規格化すること、及び
状態の同等性をチェックすることを必要とする。（拡張
及びクリッピングの定義は前進スケジューリングに対し
て与えられ、後戻りスケジューリングに対するこれらに
対応する定義は同様である。） スケジュール拡張： スケジュールは、信号のセット及
び非通過制約のセットから構成される。スケジュールＳ
は能力ｊとオフセットｏによって新たなスケジュールＳ
へ拡張される。この拡張は、例示化された能力をｏだけ
シフトし、その信号と非通過制約とをＳと統合すること
によって実行される。１つの能力は、そのシフトされた
インターバルのいづれもが同一の信号においてオーバー
ラップせず、全ての統合制約が保持される場合に、支障
なく統合可能である。能力は順序付けられてスケジュー
リングされなければならないため、つぎの可能なオフセ
ットｏ’はｏ＋ｄ_out （ｊ）となる。この機能のインタ
ーフェースをｉｎｔｅｇｒａｔｅ（＋Ｓ，＋ｏ，＋ｊ，
−Ｓ’，−ｏ’）とする。

【００９９】スケジュールクリッピング（ｃｌｉｐｐｉ
ｎｇ）： 各拡張の後、未来の信号のリーチバック内に
ある部分のみが関心事項となる。しかるべきクリップを
されたスケジュールをスケジュール状態と呼ぶ。即ち、
スケジュールＳ’が与えられる場合、下部境界ｌ_i ＝ｅ
＝ｒ_i ＋ｕ_i の下となる全ての信号ｓ_i をクリップする
ことによって状態Ｓ”が導出される。ここで、ｅ＝ｏ’
は状態のエンドであり（前述の統合によって算出され
る）、ｒ_i 及びｕ_i は信号インデックスｉに対するリー
チバック及び規格化シフトである。同様に、インターバ
ルが各々の信号の下部境界以下である非通過制約の全て
が除去可能である。クリッピングに対する共通の考え方
は、除去される制約（インターバル及び非通過制約）が
未来の拡張によって阻害され得ないということである。
この機能のインターフェースをｃｌｉｐ（＋Ｓ’，＋
ｅ，−Ｓ”）とする。

【０１００】状態規格化： 状態が比較可能となる前
に、それらは規格化されなければならない。状態規格化
手段は、状態がインターバル〔Ｏ，ｐ〕内で終了するよ
う状態をシフトする。即ち、状態Ｓ”が与えられる場
合、全てのインターバルを（ｅｍｏｄ ｐ−ｅ）だけシ
フトすることによって規格化状態Ｓ’’’が導出され
る。ここで、ｅは状態Ｓ’’’のエンドである。この機
能のインターフェースをｎｏｒｍａｌｉｚｅ（＋Ｓ”，
−Ｓ’’’）とする。

【０１０１】状態同等性： ２つの規格化された状態が
それらの信号内のインターバルの割当において同一であ
り、それらが同一の非通過制約を有する場合、この２つ
の規格化された状態は同等である。

【０１０２】以下、前進スケジューリングのための生成
方法が説明される。後戻りスケジューリングのための対
応する方法は、適切な後戻り拡張及びクリッピング機能
を使用する点においてのみ異なる。

【０１０３】一般に、この生成方法は、規格化された全
ての状態をインデックスと共に記録する（アルゴリズム
において明示的に示されない）。また、ｄだけ変移され
た能力ｊによる状態Ｓ1 からＳ2 への拡張の各々に対し
て、ｔｒａｎｓｉｔｉｏｎ（ｉｎｄｅｘ（Ｓ1 ），ｊ，
ｄ，ｉｎｄｅｘ（Ｓ2 ））が記録される。もちろん、拡
張が、既に存在している状態に到達する場合（同等性機
能によって決定される）、その状態のインデックスが使
用される。変移ｄは、Ｓのエンドと能力ｊの最後のイン
ターバルのスタートｓ_out との間の距離である。

【０１０４】初期状態の生成： ｛Ｏ，ｉｎｃ，
．．． ，ｐ−ｉｎｃ｝における各ｅに対して、リソ
ース毎に１つの割当を有するエンドｅを伴う状態を生成
することによって、初期状態が生成される。ここで、リ
ソースｊに対する割当のインターバルはｅ−ｒ_i からｅ
まで延在する。割当要求は、リソースのタイプに依存
し、初期状態に対応する。初期状態では、対応する現実
のオブジェクトが最初に入力される。Ｉを初期状態のセ
ットとする。

【０１０５】全ての状態及び遷移の生成： メインとな
る生成方法は、初期状態Ｉから開始し、状態を連続的に
拡張して新たな状態を生成してゆく。従って、初期状態
Ｉから開始し、全ての状態Ｓ（エンドｅを有する）及び
全ての能力ｊに対して以下のアルゴリズムが実行され
る。

【０１０６】

【数５】

【０１０７】最適な有限状態マシンのみを生成するより
シンプルなアルゴリズムは以下のようになる。

【０１０８】

【数６】

【０１０９】小規模なスケジューリングのために、各状
態及び能力に対する最初の拡張のみが記録されなければ
ならない。ｅｘｔ以上の変移を伴う全ての拡張は能力ｊ
の初期ステップに帰結する。最適スケジューリングのた
めに、全ての初期状態に対して１つのそのような拡張が
存在しなければならない。

【０１１０】前述の方法はまた、算出されたものより小
さいリーチバック及び拡張を選択することによって小規
模から最適までの範囲での有限状態マシンの生成を可能
とする。結果として得られる遷移関係は有限状態マシン
を定義する。

【０１１１】図７を参照すると、最適な有限状態マシン
を生成する適切なアルゴリズムを示すフローチャートが
提供される。このアルゴリズムはブロック４００で開始
する。この時点において、制約及び初期状態の両者が算
出され、次にブロック４０２へ進む。この時点で状態Ｓ
が残っていない場合、プロセスは完了する。残っている
場合はブロック４０４へ進む。

【０１１２】ブロック４０４において、定数ｊが１に設
定される。次に、ブロック４０６において、定数ｄが０
に設定される。次にプロセスはステップ４０８に進み、
能力ｊがｅ＋ｄで状態Ｓへ統合可能かどうかに関する決
定がなされる。

【０１１３】否定的決定によって、ブロック４１０にお
いてｄが増分値ｉｎｃだけ増分され、次にステップ４０
８へ進む。ブロック４０８における肯定的決定によっ
て、プロセスはブロック４１２へ進む。この時点で、シ
ステムは、クリップ、規格化、新たな状態の記録、及び
遷移の記録を行うよう機能する。

【０１１４】次に、ブロック４１４において、ｄ＝ｅｘ
ｔ_j かどうかに関する決定がなされる。否定的決定によ
ってプロセスはブロック４１０へ進み、前述の増分が与
えられる。ブロック４１４における肯定的決定によっ
て、プロセスはブロック４１６へ進む。

【０１１５】ブロック４１６において、ｊの値がチェッ
クされ、それが最後の能力がどうかが決定される。もし
そうならば、プロセスは前述のブロック４０２へ戻され
る。もしそうでないならば、ブロック４１８において値
ｊは増分され、プロセスは前述のブロック４０６へ進
む。

【０１１６】本発明は、好ましい実施例に関して記述さ
れた。明らかに、本明細書の理解によって変形と代替が
生じる。そのような全ての変形と代替は、請求項及びそ
の同等物の範囲内となる限り本発明に含まれることが意
図される。

【０１１７】

【発明の効果】以上説明したように、本発明により、モ
ジュールから構成される印刷装置において、装置の利用
性及び構成のしやすさが強化される。

【図面の簡単な説明】

【図１】本発明の自動化構成及びスケジューリングを組
み込んだモジュール方式印刷装置の概略図である。

【図２】本発明の自動化構成及びスケジューリングを実
行するための動作の階層的順序付けの詳細を表すフロー
チャートである。

【図３】本発明の自動化構成及びスケジューリングに関
連して使用される印刷装置コンポーネントの一般的記述
を表す図である。

【図４】本発明において与えられるリソースを使用する
スケジューラと制御コードの相互作用を示すブロック図
である。

【図５】モジュール能力からプリントエンジン能力が合
成される本発明のシステムのブロック図である。

【図６】プリントエンジン能力を用いた一般的スケジュ
ーリングを示す図である。

【図７】最適な有限状態マシンを生成する適切なアルゴ
リズムを示すフローチャートである。

【符号の説明】

Ａ プリントエンジン Ｂ モジュール Ｃ データプロセッサユニット

Claims (1)

【特許請求の範囲】
1. 【請求項１】 プリントエンジンの能力を分析して有限
   状態マシンを生成し、プリントエンジンをスケジューリ
   ングするシステムであって、 複数のプリントエンジンコンポーネント能力を受信する
   手段を備え、各コンポーネント能力はコンポーネント能
   力データセットによって定義され、 各データセットから信号データ及びタイミング制約を導
   出する導出手段を備え、信号を定義する信号データは対
   応するプリントエンジンコンポーネント上の非オーバー
   ラップイベントのシーケンスとして形成され、イベント
   は、動作を完了するための時間インターバルに関連する
   対応するプリントエンジンコンポーネントのアクション
   であり、タイミング制約データは、対応するプリントエ
   ンジンコンポーネントに対する１値か又は２値のインタ
   ーバル制約のいづれか一方として定義され、 複数のプリントエンジンコンポーネント能力データセッ
   トの各々を０に例示化する例示化手段を備え、 各信号を規格化する信号規格化手段を備え、 各信号関連する最新のインターバルの最大の開始点とそ
   の信号の最初のインターバルの最小の開始点との間の距
   離としてリーチバック値を定義するリーチバック手段を
   備え、 各データセットのタイミング制約データに従って最小の
   増分を決定する増分決定手段を備え、 選択されたクロック値に対して制限されたインターバル
   から定義される期間を識別する期間識別手段を備え、 最大リーチバック値及び期間に従って境界値を定義する
   拡張手段を備える、プリントエンジンスケジューリング
   システム。