(57)【要約】【課題】リソグラフィ装置またはリソグラフィ処理セルの少なくとも部分を形成する機械を操作するスケジュールの作成方法を開示する。【解決手段】この方法では、リソグラフィプロセスの結果に影響を及ぼす複数の品質の個々の品質について、複数の重み係数を受信する。前記リソグラフィプロセスを完了するために実行すべきタスクの最適スケジュールを作成し、前記最適スケジュールは、最大の合計品質値を有する結果をもたらすスケジュールであり、合計品質とは、前記品質のそれぞれの値と個々の重み係数の合計である。【選択図】図１
2005191571.tif 000002
【特許請求の範囲】
【請求項１】
リソグラフィ装置またはリソグラフィ処理セルの少なくとも部分を形成する機械を操作するスケジュールを作成する方法であって、
−  リソグラフィのプロセスの結果に影響を及ぼす複数の品質のうち個々の品質の複数の重み係数を受信することと、
−  前記リソグラフィプロセスを完了するために実行すべきタスクの最適スケジュールを作成することとを含み、前記最適スケジュールは、最大の合計品質値を有する結果をもたらすものであり、合計品質とは、前記品質のそれぞれの値と個々の重み係数の積の合計である方法。
【請求項２】
前記スケジュールが、前記機械によって実行すべきタスクの順序、および前記タスクの少なくとも幾つかの相対的タイミングを規定する、請求項１に記載の方法。
【請求項３】
前記スケジュールがさらに、少なくとも１つのタスクについて少なくとも１つのパラメータを規定する、請求項２に記載の方法。
【請求項４】
前記重み係数が、基板のロットについて定義される、請求項１に記載の方法。
【請求項５】
前記品質が、
露光後遅延の合計時間と、
露光後遅延時間の変動と、
実行すべき位置合わせタスクの数および／またはタイプと、
基板調整の最適化の程度と、
マスク洗浄および検査タスクの数、タイプおよび／またはタイミングと、
走査を実行する速度と、
露光経路の最適化の程度と
を含むグループから選択される、請求項１に記載の方法。
【請求項６】
前記最適スケジュールの作成が、
複数のスケジュールを作成することと、
作成されたスケジュールごとに合計品質値を計算することと、
前記作成されたスケジュールから、最高の合計品質値を有するスケジュールを選択することと、
を含む、請求項１に記載の方法。
【請求項７】
前記最適スケジュールの作成が機械のモデルに基づく、請求項１に記載の方法。
【請求項８】
請求項１の方法によりリソグラフィ投影装置の１つまたは複数のタスクを操作することと、パターン形成した放射線のビームを基板の目標部分に投影することとを含むデバイス製造方法。
【請求項９】
リソグラフィ装置またはリソグラフィ処理セルの少なくとも部分を形成する機械を操作する方法であって、
−  初期状態の機械のモデルを提供することと、
−  前記モデルの状態に基づいて、機械が実行できる適格タスクを決定することと、
−  少なくとも１つの所定の基準に従い、前記タスクのうち１つまたは複数を選択することと、
−  １つまたは複数の選択したタスクを部分的スケジュールに追加することと、
−  前記１つまたは複数の選択したタスクの終了を反映して、前記モデルを更新することと、
−  機械がアイドル状態であるか検出し、そうであれば前記部分的スケジュールを実行するよう制御することと、
−  前記決定、選択、追加、更新および検出を、リソグラフィのプロセスを終了するために必要な全てのタスクがスケジュール作成されるまで繰り返すことと、
を含む方法。
【請求項１０】
さらに、前記リソグラフィの結果に影響を及ぼす複数の品質のうち個々の品質の複数の重み係数を受信することを含み、前記選択が、前記リソグラフィプロセスを完了するために実行すべきタスクの最適スケジュールを作成する可能性が最も高いタスクを選択することを含み、前記最適スケジュールが、最大の合計品質値を有する結果をもたらすスケジュールであり、合計品質が、前記品質それぞれの値と個々の重み係数との積の合計である、請求項９に記載の方法。
【請求項１１】
さらに、
前記リソグラフィプロセスの結果に影響を及ぼす複数の品質のうち個々の品質の複数の重み係数を受信することと、
リソグラフィプロセスを完了するために必要な全てのタスクをスケジュール作成した後、合計品質の値を最大にするためにスケジュールを最適化することとを含み、合計品質が、前記品質それぞれの体と個々の重み係数との積の合計である、請求項９に記載の方法。
【請求項１２】
前記最適化が、前記スケジュールのうち、できるだけ遅く実行すべき少なくとも１つのタスクを選択することを含む、請求項１１に記載の方法。
【請求項１３】
できるだけ遅く実行するよう選択されたタスクが、移送タスクである、請求項１２に記載の方法。
【請求項１４】
リソグラフィプロセスを完了するために必要な全てのタスクをスケジュール作成した後に、少なくとも１つの第二スケジュールを作成するために少なくとも１つの異なる選択をする状態で、前記決定、選択、追加および検出を繰り返し、さらに、
前記スケジュールおよび少なくとも１つの第二スケジュールから最適スケジュールを選択することと、
前記最適スケジュールを実行するために前記機械を制御することと、
を含む、請求項９に記載の方法。
【請求項１５】
前記機械によって実行可能なタスクの中に、第一結合タスクおよび第二結合タスクがあり、
−  前記適格タスクの決定において、前記第二結合タスクも適格になるよう決定された場合のみ、前記第一結合タスクが適格になるよう決定され、
−  前記第一結合タスクを、前記スケジュールに追加するよう選択した場合に、前記第二結合タスクも、前記スケジュールに追加するために自動的に選択される、請求項９に記載の方法。
【請求項１６】
前記機械の前記モデルが、機械の資源のセットに存在する材料の数のカウントを含み、材料を追加すると、前記カウントが所定の閾値より上まで上昇してしまう場合は、資源のセットに材料を追加するタスクが不適格である、請求項９に記載の方法。
【請求項１７】
−  前記機械が、機械の資源間で衝突の可能性がある少なくとも１つの衝突危険区域を含み、
−  前記モデルが、少なくとも１つの衝突危険区域に対応する仮想資源を含み、
−  少なくとも１つの衝突危険区域に入るか、それと交差する資源を伴うタスクを選択すると、対応する仮想資源が、前記タスクの継続時間の間に占有されたものとしてマークされ、衝突危険区域に入るか、それと交差する資源を伴う他のタスクは、前記仮想資源が占有されたものとしてマークされている間、選択にとって不適格である、請求項９に記載の方法。
【請求項１８】
請求項９の方法に従いリソグラフィ投影装置の１つまたは複数のタスクを操作することと、パターン形成した放射線のビームを基板の目標部分に投影することとを含むデバイス製造方法。
【請求項１９】
リソグラフィ装置またはリソグラフィ処理セルの少なくとも部分を形成する機械を操作する監視制御システムであって、
−  リソグラフィプロセスの結果に影響を及ぼす複数の品質のうち個々の品質の複数の重み係数を受信するよう構成された入力デバイスと、
−  前記リソグラフィプロセスを完了するために実行すべきタスクの最適スケジュールを作成するよう構成されたスケジューラとを有し、前記最適スケジュールは、最大の合計品質値を有する結果をもたらすスケジュールであり、合計品質が、前記品質のそれぞれと個々の重み係数との値の積の合計である、制御システム。
【請求項２０】
前記スケジュールが、前記機械によって実行すべきタスクの順序、および前記タスクの少なくとも幾つかの相対的タイミングを規定する、請求項１９に記載のシステム。
【請求項２１】
前記スケジュールがさらに、少なくとも１つのタスクについて少なくとも１つのパラメータを規定する、請求項２０に記載のシステム。
【請求項２２】
前記重み係数が、基板のロットについて定義される、請求項１９に記載のシステム。
【請求項２３】
前記品質が、
露光後遅延の合計時間と、
露光後遅延時間の変動と、
実行すべき位置合わせタスクの数および／またはタイプと、
基板調整の最適化の程度と、
マスク洗浄および検査タスクの数、タイプおよび／またはタイミングと、
走査を実行する速度と、
露光経路の最適化の程度と
を含むグループから選択される、請求項１９に記載のシステム。
【請求項２４】
前記スケジュールが、複数のスケジュールを作成し、作成されたスケジュールごとに合計品質値を計算し、前記作成されたスケジュールから、最高の合計品質値を有するスケジュールを選択するよう構成される、請求項１９に記載のシステム。
【請求項２５】
前記最適スケジュールが機械のモデルに基づく、請求項１９に記載のシステム。
【請求項２６】
リソグラフィ装置であって、
−  放射線のビームを提供するよう構成された照明システムと、
−  パターニングデバイスを保持するよう構成された支持構造とを有し、パターニングデバイスが、ビームの断面にパターンを与えるよう構成され、さらに、
−  基板を保持するよう構成された基板テーブルと、
−  パターン形成したビームを基板の目標部分に投影するよう構成された投影システムと、
−  請求項１９による制御システムとを有するリソグラフィ装置。
【請求項２７】
基板取り扱いデバイスと、前処理および後処理デバイスと、請求項１９による制御システムとを有するトラックユニット。
【請求項２８】
リソグラフィ装置と、トラックユニットと、請求項１９による制御システムとを有するリソグラフィ処理セル。
【請求項２９】
リソグラフィ装置またはリソグラフィ処理セルの少なくとも部分を形成する機械を制御するコンピュータプログラムであって、プログラムはプログラムコードを有し、これはコンピュータシステム上で実行されると、コンピュータシステムに命令して、
−  リソグラフィのプロセスの結果に影響を及ぼす複数の品質のうち個々の品質の複数の重み係数を受信することと、
−  前記リソグラフィプロセスを完了するために実行すべきタスクの最適スケジュールを作成することとを実行し、前記最適スケジュールは、その結果が最大の合計品質値を有するものであり、合計品質とは、前記品質のそれぞれの値と個々の重み係数の積の合計であるコンピュータプログラム。
【請求項３０】
前記スケジュールが、前記機械によって実行すべきタスクの順序、および前記タスクの少なくとも幾つかの相対的タイミングを規定する、請求項２９に記載のコンピュータプログラム。
【請求項３１】
前記スケジュールがさらに、少なくとも１つのタスクについて少なくとも１つのパラメータを規定する、請求項３０に記載のコンピュータプログラム。
【請求項３２】
前記重み係数が、基板のロットについて定義される、請求項２９に記載のコンピュータプログラム。
【請求項３３】
前記品質が、
露光後遅延の合計時間と、
露光後遅延時間の変動と、
実行すべき位置合わせタスクの数および／またはタイプと、
基板調整の最適化の程度と、
マスク洗浄および検査タスクの数、タイプおよび／またはタイミングと、
走査を実行する速度と、
露光経路の最適化の程度と
を含むグループから選択される、請求項２９に記載のコンピュータプログラム。
【請求項３４】
コンピュータシステム上で実行されると、最適スケジュールの作成を実行するようコンピュータシステムに命令する前記プログラムコードが、コンピュータシステム上で実行されると、
複数のスケジュールを作成することと、
作成されたスケジュールごとに合計品質値を計算することと、
前記作成されたスケジュールから、最高の合計品質値を有するスケジュールを選択することとを実行するよう、コンピュータシステムに命令するプログラムコードを有する、請求項２９に記載のコンピュータプログラム。
【請求項３５】
前記最適スケジュールの作成が機械のモデルに基づく、請求項２９に記載のコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、２００３年１２月２３に位置出願の米国特許出願第１０／７４３，３２０号の部分継続出願にもとづくものである。
【０００２】
本発明はリソグラフィ装置およびリソグラフィ処理セル、およびそれを作動する方法に関する。
【背景技術】
【０００３】
リソグラフィ装置は、所望のパターンを基板の目標部分に適用する機械である。リソグラフィ装置は例えば、集積回路（ＩＣ）の製造において使用可能である。この状況で、マスクなどのパターニングデバイスは、ＩＣの個々の層に対応する回路パターンの生成に使用することができ、このパターンを、放射線感光原料（レジスト）の層を有する基板（シリコンウェハ）上の目標部分（例えば１つあるいはそれ以上のダイから成る）に描像することができる。一般的に、１枚の基板は、順次照射される近接目標部分の全体ネットワークを含んでいる。既知のリソグラフィ装置は、全体マスクパターンを目標部分に１回の作動にて露光することによって各目標部分が照射される、いわゆるステッパと、所定の基準方向（「走査」方向）にマスクパターンを投影ビームで徐々に走査し、これと同時に基板テーブルをこの方向と平行に、あるいは反平行に走査することにより、各目標部分が照射される、いわゆるスキャナとを含む。
【０００４】
一般的に「ｆａｂ」または「ｆｏｕｎｄｒｙ」と呼ばれ、半導体デバイスを製造している工場では、各リソグラフィ装置を一般的に、基板取り扱いデバイスおよび前処理および後処理デバイスを有する「トラック」でグループ分けし、「リソセル」を形成する。リソグラフィ装置およびトラックは両方とも、通常は監視制御システムを有し、これ自体もさらなる監視制御システムの制御下にある。無垢であるか、１つまたは複数のプロセス層またはデバイス層を含むよう既に処理されている基板を、処理するためにロット（バッチとも呼ぶ）単位でリソセルに送出する。ロットとは、一般的に同じ方法でリソセルによって処理される基板のグループであり、実行すべきプロセスを指定する「レシピ」が付随する。ロットのサイズは、自由裁量によるか、工場で基板の運搬に使用するキャリアのサイズによって決定することができる。レシピは、適用すべきレジストコーティングの詳細、露光前および露光後ベークの温度および継続時間、露光すべきパターンおよびその露光設定の詳細、現像時間などを含む。任意のバッチでレシピを完了するには、多数のタスクを実行しなければならず、これを実行できる多くの方法がある。というのは、多くの場合、トラックとリソグラフィ装置とは両方とも、一度に複数のタスクを実行できるからであり、例えばトラックが複数のスピンコーティング機または多目的ステーションを含むか、リソグラフィ装置が、測定ステーションおよび露光ステーションを有するデュアルステージ装置である場合である。したがって、実行すべきタスクのスケジュールを作成し、例えばスループットを最大にするために、そのスケジュールを最適化することは、複雑なタスクである。
【０００５】
ほとんどの場合、オンザフライ式スケジュール作成は制限され、タスクの大部分のシークエンスは、装置の制御ソフトウェアまたは監視制御システムでハードコードされる。スケジュール作成のためのより柔軟性があるアプローチは、終了すべきタスクおよびその優先順位関係に基づいてツリーを構築することである。このようなツリーでは、起点から開始して、枝は実行できる可能なタスクが順次存在して、葉へとつながり、そこからさらなる枝が、実行できる可能なタスクを表す。これで、スケジュール作成は、ツリーを通しての路を選択する作業となる。しかし、このようなスケジュール作成は、装置の物理的レイアウトによって引き起こされる制約も、タスク間の選択の可能性も考慮しないことがある。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
したがって、例えばリソグラフィ装置およびリソグラフィ処理セルなどの機械に改良されたスケジュール作成タスク方法を提供すると有利である。
【課題を解決するための手段】
【０００７】
一態様によると、リソグラフィ装置またはリソグラフィ処理セルの少なくとも部分を形成する機械を操作するスケジュールを生成する方法で、
−  リソグラフィのプロセスの結果に影響を及ぼす複数の品質のうち個々の品質の複数の重み係数を受信することと、
−  前記リソグラフィプロセスを完了するために実行すべきタスクの最適スケジュールを作成することとを含み、前記最適スケジュールは、最大の合計品質値を有する結果をもたらすものであり、合計品質とは、前記品質のそれぞれの値と個々の重み係数の積の総和である方法が提供される。
【０００８】
この方法により、実行時（最適）スケジュールを生成することができるので、機械の挙動を改善することができる。アプリケーションドメインの有効な直感的規則を取り込む発見的方法を使用して、スケジュール生成プロセスを指示する。設計時間シミュレーション／検証によって、作成されたスケジュールが有効であることを保証することができる。検証の技術については、以下で検討する。機械が引き続き活動している状態で、可能な／有望なスケジュールを反復し、より良いスケジュールが発見されたら、即座にそれに動的に対応することによって、スケジュールを最適化すると、オーバヘッドを追加せずに、製造されるデバイスのスループットおよび／または品質を改善することができる。例えば全ロットの基板のタイミングの知識を考慮に入れるなど、完成したスケジュールで後処理ステップによってスケジュールをさらに最適化することが可能である。
【０００９】
スケジュールの最適化は、タスクのパラメータの調節を含むことがある。例えば、走査速度を落として実行すると、露光または位置合わせタスクをさらに正確に実行することができ、したがって特にクリティカルパスに影響を及ぼさない場合は、スケジュールを最適化することにより、走査速度を遅くすることができる。
【００１０】
一つの実施形態では、スケジュールの作成を機械のモデルに対して実行する。機械のモデルは、基本的にタスク（実行すべき事柄）および資源（タスクを実行するために使用できる事柄）で構成される。タスクの実効順序は、優先順位関係によって制約される。
【００１１】
本発明の一実施形態は、一般化されたジョブショップスケジューリング技術の延長と見なすことができ、これは従来、タスクの順序および資源の割り当てしか考慮しない。延長部は、タスクに対する代替物、任意選択タスク、材料の制約、資源の競合およびデッドロックの回避を含む。
【００１２】
タスクに対する代替物は、本発明の実施形態では同等タスクのグループ（特定の実施形態では、グループとは１組のノードと定義され、ここでノードとはタスク、タスクのクラスタまたは別のグループでよい）およびそのグループから選択できるタスク数の限度を定義することによって取り扱う。選択できるタスクの数は、１などの特定の値で、そのグループからまさにその数のタスクを選択しなければならないことを示すか、または１組の値でもよく、選択するタスクの数に対して選択を可能にすることができる。したがって、任意選択のタスクの場合、限界を０以上に設定することができる。例示により、基板に２５のマーカ対を設けることができ、最低レベルの位置合わせ精度を提供するために、そのうち１６対を走査しなければならない。追加のマーカ対を走査すると、追加の精度を提供することができる。したがって、タスクは、各マーカおよびクラスタを対にして走査することと定義することができる。クラスタをグループに入れ、これは１６から２５という選択限界を有する。
【００１３】
本発明の別の態様によると、リソグラフィ装置またはリソグラフィ処理セルの少なくとも部分を形成する機械の操作方法で、
−  初期状態の機械のモデルを提供することと、
−  前記モデルの状態に基づいて、機械が実行できる適格タスクを決定することと、
−  少なくとも１つの所定の基準に従い、前記タスクのうち１つまたは複数を選択することと、
−  １つまたは複数の選択したタスクを部分的スケジュールに追加することと、
−  前記１つまたは複数の選択したタスクの終了を反映して、前記モデルを更新することと、
−  機械がアイドル状態であるか検出し、そうであれば前記部分的スケジュールを実行するよう制御することと、
−  前記決定、選択、追加、更新および検出を、リソグラフィのプロセスを終了するために必要な全てのタスクがスケジュール作成されるまで繰り返すこととを含む方法が提供される。
【００１４】
スケジュールは建設的な方法で作成され、最初から実行すべき次の「有効」または「適格」タスクを決定すること（つまり機械および製造プロセスの制約に従うこと）から開始する。全ての可能なスケジュールを決定するのではなく、発見的フィルタを使用して、スケジュールの作成を指示することができる。発見的規則の例には、最初が最初に開始する(First Start First)、好ましい資源、および優先タスクがある。
【００１５】
機械がアイドル状態にある場合に部分的スケジュールを指名すると、スケジュール作成のオーバヘッドが全て解消される。このような部分的スケジュールを１つのタスクのみで構成することができ、したがって状態に基づく制御の利点も提供する。
【００１６】
タスクの継続時間を考慮に入れる。これは資源の準備またはセットアップに必要な継続時間を含み、これは以前に実行したタスクおよび資源が残されている状態によって決定される。継続時間は幾つかの手段によって、つまり１）様々なコンテキストで常に同じ継続時間を有するタスクの場合（各タスクのタイミングは、１回測定し、システムに記憶することができる）は、設計または校正によって、２）座標、露光量、速度、加速度などの実効時間中にのみ分かる多くのパラメータによって決定されるタスクの場合は、専用の数学的係数を使用することによって、および／または３）継続時間が時間の経過とともにゆっくり変化することがあるタスクの場合は、継続時間を動的に監視し、移動平均（ＭＡ）を使用することによって決定することができる。
【００１７】
タスクのスケジュールを作成するデフォルトの発見的方法は、「できるだけ早く」（ＡＳＡＰ）でよい。機械がアイドル状態にある場合、選択される最初のタスクは即座に指名され、これはスケジュールが建設的な方法で作成されるにつれ、実行することができる。このアプローチでは、単に機械のタスクを開始させるために、（場合によっては）次善のスケジュール解決法が許される。システムがアイドル状態ではない場合は、次のタスクを待ち行列に加え、これは「ヒープオブピーセズ」に相当し、さらにその結果のスケジュールに対して、これを最適化するために後処理ステップを実行することができる。
【００１８】
後処理ステップは、タスクの相対的タイミングおよびタスクの調節可能なパラメータを調節することを含むが、選択したタスク、スケジュールにおけるタスクの順序または資源の割り当ての調節は含まない。特に、露光後に基板を基板テーブルから移送したり、露光のために基板をプレアライナから移送したりするなどの運搬タスクは、「できるだけ遅く」実行するようスケジュール作成することができる。つまり、クリティカルパスを遅延することなく、タスクをできるだけ遅く実行することができる。できるだけ遅くがいつであるかの決定は、資源を使用する他のタスク、および遅延しているタスクと干渉するような他のタスクを考慮に入れることができる。このアプローチは、運搬タスクが基板をこれが調整されている資源、つまり温度制御するか、清浄な空気を浴びせる資源から移動させることを含む。というのは、調整されていない環境で費やす時間が最短になることを保証するからである。
【００１９】
多くの場合、「有効／適格」なタスクについて複数の解決法が可能である。システムは既に（場合によっては次善の）スケジュールで作業している間に、スケジューラはスケジュール作成プロセスを繰り返し、その都度、より良いスケジュールを発見しようとして、異なる有効パスを選択する。建設的なスケジュール作成と同じ理由で、最初から最後まで可能性を探求する。より良いスケジュールが発見される度に、スケジューラは、既に実行または指示されているタスクを考慮して、このより良いスケジュール（キャッシュ）に変更することができる。
【００２０】
作業可能なスケジュールを確実に生成するために、様々な設定可能な制約条件を適用することができる。これは、ロジスティックの完全性、材料の流れのデッドロックおよびハードウェアの干渉に関する。
【００２１】
例えば、ロジスティックの完全性を維持するために、スケジューラは、「材料の寿命」中に特定のタスクを実行するよう割り当てられた資源が一定であることを確証しても良い。例えば、基板をデュアルステージ装置の第一基板テーブルに装填したら、これはその後、その基板テーブルで処理しなければならない。また、スケジューラは、材料運搬に関わる資源の組み合わせが実行可能であることを確証しても良い。例えば、マスクは移送ロボットから１つのタレットエレベータまで運搬するだけで、他のタレットエレベータには運搬しないようにすることができる。さらなる例は、個々に、またはセットで機械の資源の材料容量を超えないことを確証する。例えば、マスクライブラリは、制限された数のタスクしか含むことができず、マスクテーブルは１つしか有することができない。このような追加の制約を満足するために、ロジスティックタスクの情報を定義し、ロジスティックのブックキーピングをスケジューラに統合する。スケジュールの構築中は最初から最後まで、制約をチェックする。
【００２２】
材料の寿命におけるデッドロックに対処する方法は、例示により示すことができる。マスクを、その後の２つのタスクロックロボットおよびロボットタレットによってマスク入力ロックからタレットに事前ロードすべき場合は、ロックロボットを実行するばかりでなく、その後にロボットタレットも実行することが可能でなければならない。このタイプのデッドロックを回避するために、「結びつけた優先順位」を使用することができる。「結び合わされた」タスクの１つのスケジュール作成を決定するには、「結合」全体の適格性を考慮する。つまり、第一タスクは、結合全体をスケジュール作成できる場合のみ、スケジュール作成される。複数の材料寿命に関するデッドロックの例は、タレットおよびマスクテーブルが合計で２つのマスクしか含むことができないという限界である。つまり、マスクテーブルに既に１つのマスクがあり、タレットに別のマスクがある場合は、事前ロードすることができない。このタイプのデッドロックを回避するために、工程中タスクの制約を使用する。
【００２３】
ハードウェア干渉の制約は、基板テーブルの交換などの特定の動作で、幾つかの資源を同期して移動させねばならないことを含む。このような状況は、「セットアップ」または「準備」タスクを決定する場合にスケジューラが定義し、考慮することができる。別の制約は、特定の衝突危険区域で幾つかの資源が衝突する可能性があることである。このタイプの干渉を回避するには、各衝突危険区域を、手動で除外できる資源として定義することができる。次に、物理的資源（例えばロボット）が区域と交差する場合、これらの資源をスケジューラで自動的に割り当てる。
【００２４】
機械は、リソグラフィ処理ユニットの全体でよく、リソグラフィ装置と、基板取り扱いデバイスおよび前処理および後処理デバイスを有するトラックユニットと、またはリソグラフィ装置のみ、またはトラックユニットのみ、またはリソグラフィ装置またはトラックユニット内のサブシステムのみを有する。
【００２５】
本発明のさらなる態様によると、リソグラフィ装置またはリソグラフィ処理セルの少なくとも部分を形成する機械を操作する監視制御システムが提供され、制御システムは、
−  リソグラフィプロセスの結果に影響を及ぼす複数の品質のうち個々の性質の複数の重み係数を受信するよう構成された入力デバイスと、
−  前記リソグラフィプロセスを完了するために実行すべきタスクの最適スケジュールを作成するよう構成されたスケジューラとを有し、前記最適スケジュールは、最大の合計品質値を有する結果をもたらすスケジュールであり、合計品質が、前記品質のそれぞれと個々の重み係数との値の積の合計である。
【００２６】
さらなる態様によると、それぞれが上述したような制御システムを含むリソグラフィ処理セル、リソグラフィ装置およびトラックユニットが提供される。
【００２７】
リソグラフィ装置の使用法に関して、本文ではＩＣの製造において詳細なる参照説明を行うものであるが、本明細書で説明するリソグラフィ装置が他の用途も有することを理解されたい。例えば、これは、集積光学装置、磁気ドメインメモリ用ガイダンスおよび検出パターン、液晶ディスプレイパネル、薄膜磁気ヘッド等の製造に使用され得る。こうした代替的な用途においては、本文にて使用した「ウェハ」または「ダイ」といった用語は、それぞれ「基板」または「目標部分」といった、より一般的な用語に置き換えて使用され得ることは当業者にとって明らかである。本明細書で言及する基板は、露光前または露光後に、例えばトラック（通常はレジストの層を基板に塗布し、露光したレジストを現像するツール）または計測または検査ツールで処理することができる。適宜、本明細書の開示は、以上およびその他の基板処理ツールに適用することができる。さらに、基板は、例えば多層ＩＣを生成するために、複数回処理することができ、したがって本明細書で使用する基板という用語は、既に複数の処理済み層を含む基板も指す。
【００２８】
本明細書では、「放射線」および「ビーム」という用語は、イオンビームあるいは電子ビームといったような粒子ビームのみならず、紫外線（ＵＶ）放射線（例えば、３６５ｎｍ、２４８ｎｍ、１９３ｎｍ、１５７ｎｍ、あるいは１２６ｎｍの波長を有する）および超紫外線（ＥＵＶ）放射線（例えば、５ｎｍ〜２０ｎｍの範囲の波長を有する）を含むあらゆるタイプの電磁放射線を網羅するものとして使用される。
【００２９】
本明細書において使用する「パターニングデバイス」なる用語は、入射する放射線ビームに、基板の目標部分にパターンを生成するよう、投影ビームの断面にパターンを与えるために使用し得るデバイスまたは構造を指すものとして広義に解釈されるべきである。投影ビームに与えられるパターンは、基板の目標部分における所望のパターンに正確に対応しないことがあることに留意されたい。一般的に、投影ビームに与えられるパターンは、集積回路などの目標部分に生成されるデバイスの特別な機能層に相当する。
【００３０】
パターニングデバイスは透過性または反射性でよい。パターニングデバイスの例には、マスク、プログラマブルミラーアレイ、およびプログラマブルＬＣＤパネルがある。マスクはリソグラフィにおいて周知のものであり、これには、様々なハイブリッドマスクタイプのみならず、バイナリマスク、レベンソンマスク、減衰位相シフトマスクといったようなマスクタイプも含まれる。プログラマブルミラーアレイの一例は小さなミラーのマトリクス配列を用いる。そのミラーの各々は、異なる方向に入射の放射線ビームを反射するよう個々に傾向することができる。このようにして、反射されたビームはパターン形成される。パターニングデバイスの各例では、支持構造はフレームもしくはテーブルでよく、これは必要に応じて、固定式となるか、もしくは可動式となり、パターニングデバイスが例えば投影システムなどに対して所望の位置にあることを保証することができる。本明細書において使用する「レチクル」または「マスク」なる用語は、より一般的な「パターニングデバイス」なる用途と同義と見なすことができる。
【００３１】
本明細書において使用する「投影システム」なる用語は、例えば使用する露光放射線、または浸漬流体の使用や真空の使用などの他の要因に合わせて適宜、例えば屈折光学システム、反射光学システム、および反射屈折光学システムを含むさまざまなタイプの投影システムを網羅するものとして広義に解釈されるべきである。本明細書において「レンズ」なる用語を使用した場合、これはさらに一般的な「投影システム」なる用語と同義と見なされる。
【００３２】
照明システムは、放射線の投影ビームの誘導、成形、あるいは制御を行う屈折、反射、および反射屈折光学構成要素などの様々なタイプの光学構成要素も含むことができ、こうした構成要素もまた以降において集約的に、あるいは単独的に「レンズ」と称する。
【００３３】
リソグラフィ装置は２つ（デュアルステージ）あるいはそれ以上の基板テーブル（および／または２つもしくはそれ以上のマスクテーブル）を有するタイプのものである。このような「多段」機械においては、追加のテーブルが並列して使用される。もしくは、１つ以上の他のテーブルが露光に使用されている間に予備工程が１つ以上のテーブルにて実行される。
【００３４】
リソグラフィ装置は、投影システムの最終要素と基板との間の空間を充填するよう、基板を水などの比較的高い屈折率を有する液体に浸漬するタイプでもよい。浸漬液は、例えばマスクと投影システムの第一要素との間など、リソグラフィ装置の他の空間に適用してもよい。浸漬技術は、投影システムの開口数を増加させるため、当技術分野で周知である。
【００３５】
本発明の実施形態を添付の略図を参照に、例示の方法においてのみ説明する。図面では対応する参照記号は対応する部品を示すものとする。
【発明を実施するための最良の形態】
【００３６】
図１は、本発明の特定の実施形態によるリソグラフィ投影装置を概略的に示したものである。この装置は、
−  放射線（例えばＵＶ放射線またはＤＵＶ放射線）の投影ビームＰＢを供給する照明システム（照明装置）ＩＬと、
−  パターニングデバイス（例えばマスク）ＭＡを支持し、かつ、品目ＰＬに対して正確にパターニング構造の位置決めを行う第一位置決めデバイスに連結を行った第一支持構造（例えばマスクテーブル）ＭＴと、
−  基板（例えばレジスト塗布したシリコンウェハ）Ｗを支持し、かつ、品目ＰＬに対して正確に基板の位置決めを行う第二位置決めデバイスＰＷに連結を行った基板テーブル（例えばウェハテーブル）ＷＴと、
−  パターニング手段ＭＡによって投影ビームＰＢに与えられたパターンを基板Ｗの目標部分Ｃ（例えば、１つあるいはそれ以上のダイから成る）に描像する投影システム（例えば反射性投影レンズ）ＰＬを有する。
【００３７】
ここで示しているように、本装置は透過タイプである（例えば透過マスクを使用する）。あるいは、装置は反射タイプでもよい（例えば上記で言及したようなタイプのプログラマブルミラーアレイを使用する）。
【００３８】
照明装置ＩＬは放射線ソースＳＯから放射線のビームを受け取る。ソースとリソグラフィ装置とは、例えばソースがエキシマレーザである場合に、別個の存在でよい。このような場合、ソースはリソグラフィ装置の一部を形成すると見なされず、放射線ビームは、例えば適切な誘導ミラーおよび／またはビームエキスパンダを介して、ソースＳＯから照明装置ＩＬへと渡される。他の場合、例えばソースが水銀ランプの場合は、ソースが装置の一体部品でもよい。ソースＳＯおよび照明装置ＩＬは、必要に応じてビーム送出システムＢＤとともに、放射線システムと呼ぶことができる。
【００３９】
照明装置ＩＬは、ビームの角度強度分布を調節する調節デバイスＡＭを有してよい。一般的に、照明装置の瞳面における強度分布の外部および／あるいは内部放射範囲（一般的にそれぞれ、σ−ｏｕｔｅｒおよびσ−ｉｎｎｅｒと呼ばれる）を調節することができる。また、照明装置は一般的に、積分器ＩＮおよびコンデンサＣＯなどの様々な他の構成要素を有する。照明装置は、投影ビームＰＢと呼ばれ、その断面に亘り所望する均一性と強度分布とを有する、調整された投影ビームを提供する。
【００４０】
投影ビームＰＢは、マスクテーブルＭＴ上に保持されているマスクＭＡに入射する。投影ビームＰＢはマスクＭＡを通過して、基板Ｗの目標部分Ｃ上にビームを集束するレンズＰＬを通過する。第二位置決めデバイスＰＷおよび位置センサＩＦ（例えば干渉計デバイス）の助けにより、基板テーブルＷＴは、例えばビームＰＢの経路における異なる目標部分Ｃに位置を合わせるために正確に運動可能である。同様に、第一位置決めデバイスＰＭおよび別の位置センサ（図１には明示せず）を使用して、例えばマスクライブラリから機械的に検索した後に、あるいは走査運動の間に、ビームＰＢの経路に対してマスクＭＡを正確に位置決めすることができる。一般的に、オブジェクトテーブルＭＴおよびＷＴの運動は、位置決めデバイスＰＭおよびＰＷの部分を形成するロングストロークモジュール（粗動位置決め）およびショートストロークモジュール（微動位置決め）にて行われる。しかし、ステッパの場合（スキャナとは対照的に）、マスクテーブルＭＴはショートストロークアクチュエータに連結されるだけであるか、あるいは固定される。マスクＭＡおよび基板Ｗは、マスクアラインメントマークＭ１、Ｍ２および基板アラインメントマークＰ１、Ｐ２を使用して位置合わせすることができる。
【００４１】
ここに表した装置は以下の好ましいモードにて使用可能である。
１．ステップモードにおいては、マスクテーブルＭＴおよび基板テーブルＷＴは基本的に静止状態に保たれている。そして、投影ビームに与えたパターン全体が１回の作動（すなわち１回の静止露光）で目標部分Ｃに投影される。次に基板テーブルＷＴがＸ方向および／あるいはＹ方向にシフトされ、異なる目標部分Ｃを露光することができる。ステップモードでは、露光フィールドの最大サイズが、１回の静止露光で描像される目標部分Ｃのサイズを制限する。
２．走査モードにおいては、マスクテーブルＭＴおよび基板テーブルＷＴを同期走査する一方、投影ビームに与えられたパターンを目標部分Ｃに投影する（つまり１回の動的露光）。マスクテーブルＭＴに対する基板テーブルＷＴの速度および方向は、投影システムＰＬの拡大（縮小）および像反転特性によって決定される。走査モードでは、露光フィールドの最大サイズが、１回の動的露光で目標部分の（非走査方向における）幅を制限し、走査動作の長さが目標部分の（走査方向における）高さを決定する。
３．別のモードでは、マスクテーブルＭＴが基本的に静止状態に維持されて、プログラマブルパターニングデバイスを保持し、投影ビームに与えられたパターンを目標部分Ｃに投影する間に、基板テーブルＷＴが動作するか、走査される。このモードでは、一般的にパルス状放射線ソースを使用して、基板テーブルＷＴを動作させるごとに、または走査中に連続する放射線パルス間に、プログラマブルパターニングデバイスを必要に応じて更新する。この動作モードは、以上で言及したようなタイプのプログラマブルミラーアレイなどのプログラマブルパターニングデバイスを使用するマスクなしリソグラフィに容易に適用することができる。
【００４２】
上述した使用モードの組合せおよび／または変形、または全く異なる使用モードも使用することができる。
【００４３】
図１で示したリソグラフィ装置ＬＡは、図２で示したリソグラフィ処理セル、つまりリソセルＬＯの一部分となる。リソグラフィ装置ＬＡに加えて、リソセルＬＯは入出力ポートＩ／Ｏ１およびＩ／Ｏ２（１つでも２つ以上のポートを設けても良い）、基板を冷却するチラープレートＣＨ、基板を加熱するベークプレートＢＫ、基板にレジストなどを塗布する（スピンコータ通常は４つ）現像装置ＤＥ（この場合も通常は４つ）、および基板を様々なデバイスとリソグラフィ装置ＬＡのローディングベイＬＢとの間で移動させる基板ハンドラ、つまりロボットＲＯを含む。前述したデバイスは通常、集合的にトラックと呼ばれ、適切なレシピに従って基板を処理するよう、トラック制御ユニットＴＣＵによって制御される。通常は、基板をポートＩ／Ｏ１またはＩ／Ｏ２の一方に入れ、チラープレートＣＨ上で冷却して、スピンコータＳＣを使用してレジストを塗布し、ベークプレートＢＫ上で露光前ベークしてレジスト内の余分な溶剤を追い出し、リソグラフィ装置ＬＡで露光する前に再度冷却する。露光後、基板はソフトベークし、冷却して現像し、ハードベークし、再度冷却してから、ポートの１つを介して出力する。
【００４４】
リソグラフィ装置ＬＡの電子機械技術システムの調整は、図３で示す監視機械制御装置ＳＭＣの担当である。監視機械制御装置は、機械（リソグラフィ装置の全てまたは部分）のモデルＭｏ、ジョブのパラメータおよび他の情報の入力に使用することができる入出力デバイスＩ／Ｏ（例えばキーボードと画面、リムーバブルディスクドライブまたはネットワーク接続部）、スケジュールジェネレータＳＧ（以下でさらに説明）およびスケジュールエバリュエータおよびオプティマイザＳＥを含む。性能を最適化するために、監視制御装置は融通性があり、実際に実行する前に「ホワット−イフ」のシナリオを評価できることが望ましい。この評価のベースとして、システムのモデルが必要である。スケジュールジェネレータＳＧおよびエバリュエータＳＥを有し、ＳＭＣに組み込まれたスケジューラが、評価を行う。以下では、スケジュール作成の問題、機械のモデルおよび実行すべき製造タスクの根拠、および本発明の実施形態により組み込まれたスケジューラの基本的アルゴリズムについて説明する。
【００４５】
監視機械制御の観点から、機械はタスク資源システム（ＴＲＳ）と見なすことができる。製造プロセスはタスクを伴うことができ、電子機械技術システムは資源を伴うことができる。機械挙動の最適化は、２００３年のヨーロッパコントロール会議におけるＮ．Ｊ．Ｍ．ｖａｎ  ｄｅｎ  Ｎｉｅｕｗｅｌａａｒ、Ｊ．Ｍ．ｖａｎ  ｄｅ  Ｍｏｒｔｅｌ−Ｆｒｏｎｃｚａｋ、Ｊ．Ｅ．Ｒｏｏｄａ著の「監視機械制御装置の設計（Ｄｅｓｉｇｎ  ｏｆ  Ｓｕｐｅｒｖｉｓｏｒｙ  Ｍａｃｈｉｎｅ  Ｃｏｎｔｒｏｌ）で記載されているように、幾つかのＴＲＳ定義レベルから開始することができ、詳細については、当該文献を参照されたい。定義レベルが高いほど、選択の余地が大きくなる。選択することにより、ＴＲＳ定義はより低いレベルへと変形することができ、最終的に一時的な機械の挙動になる（ＴＲＳ定義レベル０：タイミングをとったＴＲＳ、図４参照）。「監視機械制御装置の設計」という論文では、下の方の２つのＴＲＳ定義レベル（１、０）およびその（層Ａの）間の適切な変換機能が形式的に説明され、高い方の定義レベルおよび関連する問題が紹介されている。さらに、設計時間または（ＳＭＣによる）実行時間を選択することを決定する場合に考慮すべき考慮事項が記載されている。最後に、ＳＭＣの設計を支援する既知の技術の概要が検討されている。
【００４６】
本発明の実施形態に関する以下の説明には、２つの部分がある。第一に、最適化問題の開始ポイントの定義レベルを１から２に上げる（未選択ＴＲＳ）。第二に、「監視機械制御装置の設計」に記載された技術的考察を考慮して、クラス２のシステム定義から始まる最適化問題の解を提示する。このアプローチの重要な要件は、定義レベル３への拡張性、およびＳＭＣにおける実行時間の不安定性である。このアプローチは、本発明の実施形態による製造機械のモデルベースの監視制御のベースを形成し、これは一般的に使用されている状態ベースの制御と比較して幾つかの利点を有する。監視制御は、このモデルを使用して、制御の決定に対する「ホワット−イフ」シナリオを評価し、単に次々にではなく、間に合うようにタスクのスケジュールを作成することができる。さらに、モデルによって監視制御は「予見」することができるので、この予言的情報を使用して、別の制御範囲にある関連機械（の部分）と同期することが可能である。さらに、このアプローチは融通性があり、これは保守性を改善する。
【００４７】
インスタンス作成した未選択のＴＲＳの定義（Ｄ2）から開始する最適化の問題を、以下で形式的に定義する。ｆAB（Ｄ2）＝Ｄ0を、Ｄ2で変換ＡおよびＢを実行して、機械の一時的挙動Ｄ0に復帰させる最適化関数とする。ｆAB（Ｄ2）について満足すべき制約条件は、別個の変換ＡおよびＢの制約条件を組み合わせることによって構築される。最初に、定義Ｄ0およびＤ1と変換Ａ（ｆA（Ｄ1））に関する制約条件を列挙する。これは「監視機械制御装置の設計」から抜粋したものである。その後、製造機械のアプリケーションドメインで直接関連する選択肢を分析し、この分析に基づいてＤ2を公式化する。その後、定義レベル１（変換ＢまたはｆB（Ｄ2））に到達するために、定義レベル２で定義された選択肢から選択する場合に考慮すべき制約条件について検討する。最後に、ｆAB（Ｄ2）＝ｆA（ｆB（Ｄ2））ということを使用して、全問題ｆAB（Ｄ2）を定義する。
【００４８】
タイミングをとったＴＲＳ  Ｄ0のタイミング挙動は、５個組の（Ｔ0、Ｒ、Ｉ0、τS0、τF0）によって記載することができる。つまり、
Ｔ0は、タスクと呼ばれる要素を有する有限のセットであり、
Ｒは、資源と呼ばれる要素を有する有限のセットであり、
Ｉ0：Ｔ0→Ｐ（Ｒ）は、特定のタスクに関与する資源のセットであり、
2005191571.tif 000003
は、特定のタスクの開始時間と終了時間であり、これが全ての関係する資源で同じであることを示唆する。
【００４９】
規則により、定義レベルを各定義要素に下付き文字で加えることに留意されたい。特定レベルでない定義要素には添字がない。さらに、Ｄ0はガントチャートとして視覚化できることに留意されたい。
【００５０】
定義要素のインスタンスについて満足すべき制約条件は、以下の通りである。
０ａ：資源ごとに、タスク開始時間とタスク終了時間との対の時系列シークエンスがある。
【００５１】
タスク資源システムのタイミング挙動は、資源の物理状態の遷移によって誘導される。機械資源は、特定の性能限界を有する電子機械システムである。したがって、システムは物理状態遷移を実行する場合、特定の挙動の制約条件に従わなければならない。タスクは、この物理状態遷移の開始状態および終了状態を課し、さらに遷移軌跡の挙動制約条件中間に課す。さらに、タスクは特定の順序で実行しなければならない。選択され、タイミングをとっていないＴＲＳ  Ｄ1は６個組の（Ｔ1、Ｒ、Ｉ1、Ｐ1、Ｓｂ1、Ｓｅ1）で記載することができる。つまり、
Ｔ1およびＩ1は、それぞれＴ0およびＩ0と等しい。
【００５２】
Ｐ1∈Ｐ（Ｔ1×Ｔ1）は、タスク間の優先順位関係である。
【００５３】
Ｓｂ1、Ｓｅ1：Ｔ1×Ｒ→Ｓは、特定タスクに関係する各資源の（物理的）開始および終了状態を与え、ここでＳは可能な全ての物理資源状態のセットである。
【００５４】
定義要素のインスタンスについて満足すべき制約条件は、以下の通りである。
１ａ：資源ごとのタスクのシークエンスはチェーンである（０ａに一致する）。
１ｂ：Ｐ1はサイクルを含まない。
１ｃ：タスクに関与するどの資源についても、開始状態および終了状態を定義しなければならない。
【００５５】
これらの定義要素を、図４ａでＵＭＬクラス図表として表す。
【００５６】
変換Ａは、タイミングをとっていない選択済みＴＲＳの定義Ｄ1のタスクのタイミングを含む。ｆA（Ｄ1）について満足すべき制約条件は、以下の通りである。
ａ１：タスクおよび（関係した）資源に関しては、何も変化しない。
Ｔ0＝Ｔ1、Ｉ0＝Ｉ1
ａ２：規則により、時間は０で開始する。さらに、タスクの終了時間は、その開始時間プラス継続時間と等しい。
【数１】
2005191571.tif 000004
ａ３：その後のタスクでは、次のタスクの開始時間が、前のタスクの終了時間より大きいか、それと等しいことが成立する。
【数２】
2005191571.tif 000005
ａ４：同じ資源でその後のタスクの状態と一致するため、資源のセットアップ状態遷移が必要になることがある。このような場合、次のタスクの開始時間は、前のタスクの終了時間に、タスク間のセットアップ資源状態遷移の継続時間を加えた値より大きいか、それと等しい。
【数３】
2005191571.tif 000006
ここで、
Ｐ’1⊆Ｐ1は、全ての資源タスクチェーンの和集合である。
2005191571.tif 000007
は、タスクおよびタスクに関連する資源によって課された挙動の制約条件を考慮して、特定のタスクの継続時間を与える。
2005191571.tif 000008
は、資源によって課された挙動の制約条件を考慮して、ある状態から別の状態へと資源セットアップの継続時間を与える。τt0およびτr0に関するさらなる情報については、上記で言及した「監視機械制御装置の設計」を参照されたい。
【００５７】
複雑な製造機械では、Ｄ1の様々な要素に対して選択肢が存在する。まず最初に、優先順位に関して選択肢が存在する。レベル１に関する優先順位により、資源ごとにタスクのチェーンが保証されるが、この順序は基本的でない。基本的なことは、様々な製造エンティティの製造プロセスに関するタスクが、製造インスタンスごとに適正な順序で実行されることである。さらに、相互に排他的な制約条件がある。つまり、資源は一度に１つしかタスクを実行することができない。製造プロセスおよび相互に排他的な制約条件によって課せられた基本的順序があるので、様々な製造エンティティを編成するのに幾つかの可能性が存在する。優先順位に対する代替物は、１９９５年にエングルウッドクリフのプレンティスホールから刊行されたＭ．Ｐｉｎｅｄｏ著の「スケジューリング：理論、アルゴリズムおよびシステム」（”Ｓｃｈｅｄｕｌｉｎｇ：Ｔｈｅｏｒｙ，Ａｌｇｏｒｉｔｈｍｓ，ａｎｄ  Ｓｙｓｔｅｍｓ”）に記載されたジョブショップスケジューリング（ＪＳＳ）の問題に類似している。
【００５８】
第二に、資源に関する選択肢が存在する。場合によっては、機械内に同じ種類の複数の資源が存在する。特定のタスクに関わるか、それに割り当てるため、幾つかの資源を選択することができる。これは、１９９５年のアイントホーフェン工科大学のＭ．Ｗｅｎｎｉｎｋによる博士論文「自動化した計画ボードのアルゴリズム支援」（Ａｌｇｏｒｉｔｈｍｉｃ  Ｓｕｐｐｏｒｔ  ｆｏｒ  Ａｕｔｏｍａｔｅｄ  Ｐｌａｎｎｉｎｇ  Ｂｏａｒｄｓ）に記載された一般化したジョブショップスケジューリングの問題にも当てはまる。
【００５９】
最後に、タスクに関する選択肢が存在する。これは、場合によっては、製造プロセスに同等の影響を与える複数のタスクがシステムに存在するという事実によって示唆される。例えば、材料を１つの場所から別の場所に移送する複数の路、または１つのサブセット（ｎ）しか選択しなくてよい（ｍ個の）タスクのセットである。タスクに関する選択の余地を画成するＤ2の要素に必要な表現力を決定するために、基板スキャナからの幾つかの例を分析する。ダイの露光走査に関して、２つの表現のうち１つが必要である。つまり、ダイは２つの方向で露光（走査）することができ、そのうち一方を選択しなければならない。これは、田舎の郵便配達人問題に類似している。つまりｍ個のうちｎ個で、ｎ＝１およびｍ＝２である。（例えば、１９８５年にチチェスターのウィリーインターサイエンスから刊行されたＥ．Ｌ．Ｌａｗｌｅｒ、Ｊ．Ｋ．Ｌｅｎｓｔｒａ、Ａ．Ｈ．Ｇ．Ｒｉｎｎｏｏｙ  Ｋａｎ、Ｄ．Ｂ．Ｓｈｍｏｙｓ著の「巡回セールスマン問題：組み合わせ最適化のガイド付き旅行」（Ｔｈｅ  Ｔｒａｖｅｌｉｎｇ  Ｓａｌｅｓｍａｎ  Ｐｒｏｂｌｅｍ：Ａ  Ｇｕｉｄｅｄ  ｔｏｕｒ  ｏｆ  Ｃｏｍｂｉｎａｔｏｒｉａｌ  Ｏｐｔｉｍｉｚａｔｉｏｎ）参照）。基板上のマーカ対の測定に関すると、要件がさらに困難になる。基板上の（ｍ個の）マーカ対から、最低数（ｎ個）を測定しなければならない。マーカ対は幾つかのマーカで構成され、それぞれがいずれかの方向で測定走査タスクを必要とする（ｎ0＝１）。この場合、タスクの選択は、ｍ個からの選択と定義することができ、ここで選択されたマーカ対の数ｎ0は、許容された数でなければならず、選択されたマーカ対にある全てのマーカについて、１つの走査タスクを選択する。ここから、ネスティングが必要であり（ｎ個中のｎ0個）、選択肢の許容数は複数でよい
2005191571.tif 000009
と結論することができる。さらに、複合機械はバッファ位置を含むことができる。製造工程の幾つかの点で製造構成要素をバッファリングすることも可能である。直感的にこの可能性を定義するために、バッファリングが許容されないということも記述することが可能でなければならない。つまり、０も許容数になり得る
2005191571.tif 000010
。
【００６０】
選択すべき選択肢の余地を画成するために、可能な限り多くの知識に従う。基本的な優先順位を概略するために、新しい定義要素を導入する必要はない。ＪＳＳと同様に、基本的な優先順位の関係式Ｐ2⊆Ｐ1のみを含むよう、レベル１に対して優先順位の要素を取り除く。取り除いた優先順位インスタンスＰ1＼Ｐ2は、選択Ｂの結果であるインスタンスのスケジューリングされた編成に関する。優先順位の選択肢を、Ｐ2と相互の排他性を保証する制約条件とによって画成される。資源の関与を画成するには、機能と呼ばれる追加の定義要素を導入する。つまり一般化したＪＳＳに類似したＣである。特定のタスクにどの機能が関与するかを示すために、関与関数を変更する。つまりＩ2：Ｔ2→Ｐ（Ｃ）である。追加の可用性関数Ａ：Ｃ→Ｐ（Ｒ）を導入して、特定の機能にどの資源が使用可能であるか記述する。資源の関与の選択は、関与した機能ごとに１つの使用可能な資源を選択することを示唆する。
【００６１】
タスクに対する選択肢に必要なスペースを画成するために、知識に従うことができない。したがって、推論は基本的事項から開始する。一般的に、タスクとその優先順位関係は、「ノードに関する活動」タイプのグラフで視覚化することができる。タスクに関する選択の代替物をモデル化する目的で、より一般的なノード要素Ｎ2を導入する。同等の代替物は、ノードのクラスタで構成することができる（ネスティング）。このようなクラスタを識別するために、追加のノードタイプのクラスタ（Ｌ2）を導入する。関数Ｌｎ2：Ｌ2→Ｐ（Ｎ2）を導入して、どのノードがどのクラスタに属するか定義する。さらに、何も選択しないという可能性も含め、代替ノードの複数の数を選択できるようにすることが可能である。どのノードがこのようなグループの代替物に属するか定義できるようにするために、ノードタイプグループを導入する：G2。関数Ｇｎ2を導入して、どのノードがどのグループにあるか定義し、関数Ｇａ2を導入して、これらのノードを選択できる数を定義する。新たに導入された定義要素は、幾つかの選択の制約条件とともに、タスクに対する選択の余地を画成する。その結果生じたモデルは、［ｍ個のうちのｎ1個］または［ｍ個のうちのｎ2個］などのタスク（の集合）を表し、これは［ｍ個のうちの｛ｎ1、ｎ2、・・・ｎx｝個］と省略することができる。
【００６２】
この分析を列挙すると、未選択のＴＲＳ  Ｄ2を１４個組（Ｔ2、Ｌ2、Ｇ2、Ｎ2、Ｒ、Ｃ、Ｉ2、Ａ、Ｐ2、Ｌｎ2、Ｇｎ2、Ｇａ2、Ｓｂ2、Ｓｅ2）で定義することができる。ここで、
Ｔ2は、コールされたタスクである要素を有する有限のセットであり、
Ｌ2は、コールされたクラスタである要素を有する有限のセットであり、
Ｇ2は、コールされたグループである要素を有する有限のセットであり、
Ｎ2は、コールされたノードである要素を有し、前述したモデル要素の一般化、つまりＮ2＝Ｔ2∪Ｌ2∪Ｇ2である有限のセットであり、
Ｒは、コールされた資源である要素を有する有限のセットであり、
Ｃは、コールされた機能である要素を有する有限のセットであり、
Ｉ2：Ｔ2→Ｐ（Ｃ）は、特定のタスクに関与する機能のセットを与え、
Ａ：Ｃ→Ｐ（Ｒ）は、特定の機能に使用可能である資源のセットを与え、
Ｐ2∈Ｐ（Ｎ2×Ｎ2）は、ノード間の優先順位関係であり、
Ｌｎ2：Ｌ2→Ｐ（Ｎ2）は、特定のクラスタにあるノードのセットを与え、
Ｇｎ2：Ｇ2→Ｐ（Ｎ2）は、グループを構成するノード（代替物）のセットを与え、
2005191571.tif 000011
は、グループから選択すべきノードの許容数（０を含む）を与え、
Ｓｂ2、Ｓｅ2：Ｔ2×Ｃ→Ｓは、あるタスクに関与する各機能の（物理的）開始および終了状態を与える。
【００６３】
これらの定義要素を、図４ｂのＵＭＬクラス図表として示す。
【００６４】
モデル要素のインスタンスについて満足すべき制約条件は、以下の通りである。
２ａ：Ｐ2はサイクルを含まない（１ｂ参照）。
２ｂ：タスクに関与するどの機能についても、開始および終了状態を定義しなければならない（１ｃ参照）。
２ｃ：選択されたノードの許容数として０しか持たないグループはない。
【数４】
2005191571.tif 000012
２ｄ：グループの要素であるノードには、先行または後続ノードがない。
【数５】
2005191571.tif 000013
２ｅ：優先順位はグループの境界をまたがない。
【００６５】
選択Ｂをすることにより、クラス２のＴＲＳ定義はクラス１のＴＲＳ定義に変換される。選択の一つは、タスクに対する選択肢からの選択と関係がなければならない。その中にあるタスクの少なくとも１つを選択する場合は、選択すべきノードを定義する。Ｎ1を、選択したノードのセットとすると、ｆB（Ｄ2）の制約条件は以下のように公式化することができる。
ｂ１：資源ごとに選択されたタスクのシークエンスはチェーンである（１ａに等しい）。
ｂ２：選択した各タスクについて、関与する機能ごとに使用可能な資源を選択しなければならない。
【数６】
2005191571.tif 000014
【００６６】
開始および終了状態の定義は、選択した資源の機能からコピーする。
ｂ３：優先順位関係は引き継ぐ。
【数７】
2005191571.tif 000015
ここで関数ＴｉｎＮ（ｎ）は、特定のノードｎにある全てのタスクを返す。
【数８】
2005191571.tif 000016
ｂ４：何も選択しないことが許されているグループ（「ニルグループ」）を除き、別のノードの一部ではない全てのノードを選択しなければならない。
【数９】
2005191571.tif 000017
ｂ５：ニルグループを除き、選択されたクラスタの一部である全てのノードを選択しなければならない。
【数１０】
2005191571.tif 000018
ｂ６：ニルグループを考慮しない場合、グループの制約条件は、選択されたグループの一部である選択済みノードの数が以下を許容しなければならないことである。
【数１１】
2005191571.tif 000019
グループ内に選択されていないニルグループが存在することにより、この制約条件は多少緩和される。グループ内で選択されるノードの許容数に関して、選択されていないニルグループをカウントしても、しなくてもよいからである。これを承知すると、制約条件は以下のように記述することができる。
【数１２】
2005191571.tif 000020
【００６７】
最適化問題の正式な定義を完了するために、目的関数ｆg：Ｄ0→Ｒを定義し、これは特定の一時的挙動の性質を定量化する。この関数である役割を果たすタクタの例は、システムの合計継続時間およびタスクの数である。さらに、ｆAおよびｆBについて２セットの有効関数を導入する。つまり、それぞれＦAおよびＦBである。これで、最適化問題は以下のように記述することができる。
【数１３】
2005191571.tif 000021
【００６８】
本発明の実践的な実施形態では、実行時間の使用可能性要件は重要な結果を有する。制御装置が「最適」スケジュールを演算するのを待つ間に機械が休止するのを回避するために、本発明の実施形態によるアルゴリズムは、非常に小さい時間遅れで実行を開始するためにタスクを指名できるようなアルゴリズムである。これを達成するために、スケジュールは建設的な方法で決定する。つまりスケジュール時間の最初から最後まで、ということである。このアプローチは、レベル３のＴＲＳ定義を扱うことへ拡張しても安全である。さらに、追加される各タスクの後に部分的スケジュールを発することが可能である。発されたスケジュールは許容可能なスケジュールであることをそれを保証するために、発見的フィルタを使用して、選択Ｂに関与するスケジューリングの選択を指示する。スケジュールを指名するためにアルゴリズムが中断された場合は、単に機械を作業させるために次善に最適なスケジュールの解決法を当然とし、その結果、非反復的挙動になることがある。さらに、発見的フィルタは、状態に基づく制御アーキテクチャの挙動をコピーするように構成することができ、これはソフトウェアの移動目的に都合がよい。選択肢Ａに関して、タスクと、タスク間のセットアップ資源状態遷移の継続時間は、効率およびＳＭＣへの組み込み可能性のために、専用の数学的関数を使用して決定される。さらに、選択Ａに対するアプローチのデフォルトの発見法は、選択されたタスクを「できるだけ早く」ＡＳＡＰスケジュール作成することであり、その結果、「活動」スケジュールになる。メモリの効率のために、コンパクトなデータ構造を適用して、選択Ｂの結果を記憶し、選択Ｂは、選択Ａの発見的な建設的およびＡＳＡＰスケジューリングとも整合する。つまりヒープオブピーセズである（１９８６年にニューヨーク、スプリンガ社が刊行した数学講義ノートのＣｏｍｂｉｎａｔｏｉｒｅ  Ｅｎｕｍｅｒａｔｉｖｅ，  Ｌａｂｅｌｌｅ  ａｎｄ  Ｌｅｒｏｕｘ，  Ｅｄｓ．，  ｎｏ．１２３４のｐｐ．３２１〜３５０にあるＧ．Ｘ．Ｖｉｅｎｎｏｔ著の「ヒープスオブピーセズ、Ｉ：基本的定義と組み合わせの補題」（Ｈｅａｐｓ  ｏｆ  Ｐｉｅｃｅｓ，  Ｉ：Ｂａｓｉｃ  Ｄｅｆｉｎｉｔｉｏｎｓ  ａｎｄ  Ｃｏｍｂｉｎａｔｏｒｉａｌ  Ｌｅｍｍａｓ）参照）。ピースは、選択されたタスクおよび選択された関与資源を定義し、ここでヒープにあるピースのシークエンスは、選択した優先順位関係を定義する。目的関数に応じて、選択Ａに対して処理後ステップを実行し、スケジュールを改善するために一部のタスクを延期する。その後、選択Ｂに関する他の選択を考察する。実行時間の側面を考慮に入れ、このアプローチは、スケジュールの開始時に他の選択肢を最初に探索する。これらのタスクが最初に指名されるからである。図５では、このアプローチを流れ図で示す。要約すると、アプローチは、所望に応じて早期に作業を指名する多数の「エスケープ」ポイントを有し、制約条件で誘導された発見的サーチアルゴリズムである（上記で参照したＭ．Ｐｉｎｅｄｏ著の「スケジューリング：理論、アルゴリズムおよびシステム」参照）。
【００６９】
方法の第一ステップは、適格タスク（ピース）を決定することである。変換機能Ｂの間に、選択した選択肢をヒープオブピーセズに記憶する。ピースｐは、どのタスクｔ∈Ｔ2を選択するか、および関与する選択済み資源ｒｒ⊆Ｒ2を記述する。つまりｐ∈Ｔ2×Ｐ（Ｒ2）である。ヒープｈ∈Ｐ（（Ｔ2×Ｐ（Ｒ2））*）内のピースのシークエンスは、Ｐ2（本質的に制約条件ｂ１を満足する）内の優先順位関係に加えて、選択された優先順位関係を記述する。タスクに関して選択肢を考慮せず、パスされた（＝それまでに選択された）タスクｔp⊆Ｔ2を含むヒープｈを考える場合は、タスクｔおよび関与する資源ｒｒで構成された次のピースｐが、以下の場合に、および以下の場合にのみ、拡張ヒープｈｐを形成するのに適格である。
・ｔの先行点がヒープｈのピース内にあり、ｔがそうではない場合、
【数１４】
2005191571.tif 000022
・ｒｒに関して制約条件ｂ２を満足する。
【数１５】
2005191571.tif 000023
・シークエンスｈの次の適格ピースの設置を、下式のように定義することができる。
【数１６】
2005191571.tif 000024
【００７０】
実行可能なヒープのセットＨ⊆Ｐ（（Ｔ2×Ｐ（Ｒ2））*）は、以下のような帰納法によって定義することができる。
【数１７】
2005191571.tif 000025
【数１８】
2005191571.tif 000026
（１．５）で、εは空のヒープを指す。
【００７１】
タスクに対する選択肢を考察して、関数Ｅｔ（ｈ）を拡張しなければならない。選択プロセス中に、選択されず、これ以上選択されないタスクを「バイパスされた」と呼ぶ。選択プロセス後、バイパスされたタスクのセットはＴ2＼Ｔ1と等しい。関数Ｅｔ（ｈ）は、パスもバイパスもされないタスクのみ考察する必要がある。パスもバイパスもされないタスクの場合は、先行点の関係をチェックしなければならない。タスクに対する選択肢を考察しない場合、全ての先行点はヒープ内になければならない（式１．２参照）。全ての（場合によっては引き継いだ、制約条件ｂ３参照）先行点が「継承可能」でなければならないタイプグループの先行点の場合は、この条件は、緩和される。
【００７２】
関数ａｎｃ：Ｎ2→Ｐ（Ｎ2）を、ノードの祖先を決定する帰納的関数であるとし、この祖先は、ノードｎが含まれる複数のノードである。
【数１９】
2005191571.tif 000027
【００７３】
この帰納法は、ノードが、この関数でのみ上方向に探索される階層構造を有するので有限である。
【００７４】
関数ｓｕｃｃ：Ｎ2→Ｐ（Ｎ2）を、ノードｎの後続点を決定する関数であるとする。
【数２０】
2005191571.tif 000028
【００７５】
タスクは、パスされた場合に継承可能であり、クラスタは、その中にある全てのノードが継承可能である場合に継承可能である。継承可能なグループにある継承不可能なノードは、パスされたタスクを含まないことがある。さらに、グループのノードがいずれの継承不可能で、ゼロが許容された数である場合、その先行点が全て継承可能であると、グループは継承可能である。他の場合、その継承可能なノードの数（ゼロ以外）が許容数であると、グループは継承可能である。
【００７６】
2005191571.tif 000029
を、ノードｎが継承可能か否か決定する帰納的関数であるとする。
【数２１】
2005191571.tif 000030
【００７７】
この帰納法は、ノードが下方向にのみ探索する階層構造を有し、先行点がループを有さず、後方にのみ探索するので有限である。継承可能なノードｎsのセットは次のように定義することができる。つまりｎs＝｛ｎ∈Ｎ2｜ｎｓ（ｎ）｝である。
【００７８】
ｎiを、開始したノードのセットであるとする。ノードは、継承可能ではなく、パスされたタスクを含む場合に開始される。このセットは、以下のように定義することができる。
【数２２】
2005191571.tif 000031
【００７９】
タスクは、パスされず、継承可能でないか、開始されたグループ（のノード）にあって、グループのノードの最大数が継承可能であるか、開始された場合、またはその継承ノードがいずれか継承可能である場合に、タスクは、バイパスされる。バイパスされたタスクｔbのセットは、以下のように定義することができる。
【数２３】
2005191571.tif 000032
ここで、関数ｓｕｃｃｎｉｌ：Ｔ2→Ｐ（Ｎ2）は、継承するニルグループの後続点を含むタスクｔの継続点を決定する。
【数２４】
2005191571.tif 000033
【００８０】
これを使用すると、タスクに対する選択肢を考慮した場合に関数Ｅｔ（ｈ）を以下のように定義することができる。
【数２５】
2005191571.tif 000034
【００８１】
方法の第二ステップは、用途によって決定されるが、第三ステップは一般的に説明することができる。
【００８２】
タイミングに関する選択の「できるだけ早く」（ＡＳＡＰ）の発見法は、直感的解釈、つまりヒープオブピーセズの直感的解釈を伴うことができる（１９８６年にニューヨーク、スプリンガ社が刊行した数学講義ノートのＣｏｍｂｉｎａｔｏｉｒｅ  Ｅｎｕｍｅｒａｔｉｖｅ，  Ｌａｂｅｌｌｅ  ａｎｄ  Ｌｅｒｏｕｘ，  Ｅｄｓ．，  ｎｏ．１２３４のｐｐ．３２１〜３５０にあるＧ．Ｘ．Ｖｉｅｎｎｏｔ著の「ヒープスオブピーセズ、Ｉ：基本的定義と組み合わせの補題」（Ｈｅａｐｓ  ｏｆ  Ｐｉｅｃｅｓ，  Ｉ：Ｂａｓｉｃ  Ｄｅｆｉｎｉｔｉｏｎｓ  ａｎｄ  Ｃｏｍｂｉｎａｔｏｒｉａｌ  Ｌｅｍｍａｓ）参照）。ＴＲＳのタイミング挙動は、ガントチャートを使用して視覚化することができる。ガントチャートを９０°反時計回りに回転すると、タスクが占有する資源を、ヒープオブピーセズｐ∈Ｔ2×Ｐ（Ｒ）として解釈することができる。この組変数の第一要素ｐ0は、考察されるタスクと等しく、第二要素ｐ1は、このタスクに関与する資源に等しい、つまりｐ＝（ｔ，Ｉ1（ｔ））である。資源は、横軸上のスロットに関連することができ（タスク継続）時間は縦軸で表される。タスクは長方形のピースで表される。タスク継続時間τt0は長方形の高さで表され、関与する資源は「幅」で表される。「ＡＳＡＰ」発見法は、「重力」の影響で積み重なって落下するピースに関連することができる。
【００８３】
ヒープの上部輪郭は、資源がヒープ内のピースによって占有されるまでの時間に関連する。これは、Ｒ次元の行ベクトルｕH（ｈ）と定義され、ここでｕH（ｈ，ｒ）は、スロットｒ上のヒープの高さである。上部輪郭の状態は、Ｒ次元の行ベクトルｕHs（ｈ）と定義され、ここでｕHs（ｈ，ｒ）は時間ｕH（ｈ，ｒ）における資源ｒの（物理的）状態である。
【００８４】
０で開始する時間に関連づけることができる水平グラウンド規則（制約条件ａ２参照）で、以下が得られる。
【数２６】
2005191571.tif 000035
【００８５】
ヒープｈの上にピースｐを積み重ねた結果得られるヒープｈｐの上部輪郭は、ｔによって占有された資源のタスクｔの終了時間に等しく、他の資源のｈの上部輪郭と等しい。
【数２７】
2005191571.tif 000036
【００８６】
ヒープｈの上にピースｐを積み重ねた結果得られるヒープｈｐの上部輪郭状態は、ｔによって占有された資源のタスクｔの終了状態と等しく、他の資源のｈの上部輪郭状態と等しい。
【数２８】
2005191571.tif 000037
【００８７】
タスクｔの終了時間は、その継続時間を開始時間に加算することによって獲得する（制約条件ａ２参照）。
【数２９】
2005191571.tif 000038
【００８８】
ヒープｈの上に積み重ねられているピースｐに関連するタスクｔの開始時間は、２つの成分の影響を受ける。つまり一方では先行タスク（制約条件ａ３参照）から、および他方では関与する資源のセットアップ状態遷移（制約条件ａ４参照）から影響を受ける。この優先順位の制約条件は、１９９８年にイギリス、ケンブリッジのケンブリッジ大学印刷局が刊行したアイデンポテンシのｐｐ．１３３〜１４４のＳ．ＧａｕｂｅｒｔおよびＪ．Ｍａｉｒｅｓｓｅ著による「タスク資源モデルおよび（最大、＋）オートマトン」（Ｔａｓｋ  Ｒｅｓｏｕｒｃｅ  Ｍｏｄｅｌｓ  ａｎｄ  （ｍａｘ，＋）Ａｕｔｏｍａｔａ）の理論の拡張であることに留意されたい。これは、先行タスクの最高終了時間τS0p（ｔ，ｈ）、または関与する資源のセットアップ後にピースの下にあるヒープｈのジョブ輪郭の最高部分τS0r（ｔ，ｈ）の最高値をとることによって決定することができる。
【数３０】
2005191571.tif 000039
【００８９】
先行タスクに関して、タスクｔの開始時間は、ｔが存在する任意のノードに先行するパスされたタスクの最大終了時間と等しい。ｔは：
【数３１】
2005191571.tif 000040
ここで関数ｔｐｐ：Ｎ2×（Ｔ2×Ｐ（Ｒ））*→Ｐ（Ｔ2）は、ノードに先行するパスされた全てのタスクを決定する。これらの先行点のいずれかが未選択のニルグループである場合、そのニルグループの先行点にあってパスされたタスクを検索しなければならない。そのため、関数は帰納的であり、以下のように定義される。
【数３２】
2005191571.tif 000041
【００９０】
資源のセットアップに関して、タスクｔの開始時間は以下のように獲得することができる。
【数３３】
2005191571.tif 000042
【００９１】
上記の一般的状況を、上述したようなデュアルステージのリソグラフィ装置に適用することができる。例示により、二重露光レシピの基板５枚のうちそれぞれ３ロットを考察する。ロットごとに異なるマスク、つまり第一ロットにはマスク１および２、第二ロットにはマスク３および４、および第三ロットにはマスク５および６が必要である。各基板は、２６×１３ｍｍ2のサイズのダイ１７１個で構成され、１３ｍｍが走査方向にある。ダイを露光する前に、各基板を測定しなければならない。この測定セットアップは、アラインメントマーカ対の測定を含む。２５のアラインメントマーカ対を各基板に配置し、そのうち少なくとも１６対を各マーカのいずれかの方向で測定し、必要な最低製造精度に到達していなければならない。
【００９２】
この例のためには、タスクおよびその順序の選択のみが関係する。
【００９３】
選択肢は以下の領域にある。
１．どの順序および方向で、各基板のダイの露光を実行するか。
２．どのマーカ測定タスクが、どの順序で実行するか。
３．どのマスク取り扱いタスクが、どの順序で実行するか。
【００９４】
図１のリソグラフィ装置のマスク取り扱い構成をさらに詳細に示す図６では、１つのマスクに対して実行できる一連のマスク取り扱いタスクを、矢印を使用して示し、そのシークエンス番号で分類する。点線の矢印は、バッファの使用（タスクＭＴａ６およびＭＴａ７）に関し、これは任意選択である。各資源を正方形で示す。
【００９５】
例示のため、発見的フィルタの２つの異なる設定から生じたタイミングの挙動について説明する。
【００９６】
第一設定、つまり設定Ｉの説明は、以下の通りである。
１．露光シークエンスは水平の蛇行である。
２．最低数（１６）のマーカ対を測定する。
３．できるだけ早くマスクの前処理を開始する。マスクがマスクステージへと通過できない場合は、バッファ（ＩＲＬ）に入れる。
【００９７】
図７では、設定ＩのＡＳＡＰ時間挙動をガントチャートで示す。このチャートでは、タスクは基板またはタスクに従って影／色が与えられ、露光タスクはマスクの影／色を獲得している。図８では、時間挙動のクリティカルパスをガントチャートで示す。
【００９８】
第二発見的設定、つまり設定ＩＩの説明は、以下の通りである。
１．露光シークエンスは垂直の蛇行である。
２．全てのマーカ対（２５）を測定する。
３．マスクの前処理は、次の露光に使用可能な前処理済みマスクが４個未満の場合のみ開始する。ロボットが、マスクをタレットに載せるか、次のマスクの前処理を開始するか選択できる場合、これは、マスクをタレットに載せることを選択する。この、マスクの待期が要され、次のロットが別の未処理のマスクを必要とする場合のみ、前処理後にマスクはＩＲＬバッファに入れられる。
【００９９】
図９では、設定ＩＩを使用した結果の時間挙動をガントチャートで示す。３つのロットの製造に必要な時間が、設定Ｉと比較すると５％以上減少する。この半分は、変化した露光シークエンスによるものであり、これ自体も継続時間が約１０％減少する。他の半分は、変化したマスクの取り扱いによるものである。副作用として、測定されるマーカ対が多くなるので、製品品質の向上が獲得される。これは時間をそれ以上費やすことがない。図１０で見られるように、測定がまだクリティカルパス上にないからである。
【０１００】
したがって、本発明の実施形態は、インスタンス作成した未選択のＴＲＳ定義から開始する機械の製造の、モデルを根拠にした監視制御の形式的根拠を提供する。ＴＲＳ挙動の最適化問題を形式的に定義するために、選択機能ＡおよびＢを変換関数と見なす。選択をした結果の挙動の品質の数量化にも同じことが言え、これは目標関数を使用して実行される。変換ＡおよびＢについて満足しなければならない制約条件を、数学的に定義する。これを使用して、挙動最適化問題を、制約条件に関する変換ＡおよびＢを満足すべき目標関数の最大値と定義する。
【０１０１】
複雑な製造機械のドメインにあるインスタンス作成した未選択のＴＲＳは、トラック、資源およびタスク順序に関して、選択の余地（選択Ｂ）を残す。選択する選択肢を定義するには、資源およびタスク順序に対する選択肢に関して、一般化したＪＳＳアプローチ（上記で言及した「自動化した計画ボードのアルゴリズム支援」参照）に従い、タスクに対する選択肢に関しては新しいアプローチを開発する。このアプローチは、以前のアプローチより意味深長である。
【０１０２】
選択機能ＡとＢを、監視機械制御の実行時間アプリケーションに適した最適化アプローチで組み合わせる。このアプローチの根拠は、トップダウンで反復性の発見的フィルタリングをしたビームサーチアルゴリズムであり、良好な挙動品質を小さい制御オーバヘッドと組み合わせるために使用可能なサーチ時間と結合される。このアルゴリズムは、機械固有の問題のために拡張可能であり、これは追加の選択制約条件と定義することができる。
【０１０３】
本発明の第二の実施形態は、投影ビームに超紫外線（ＥＵＶ）放射線を使用するリソグラフィ装置に適用される。この放射線は空気に吸収されるので、露光は真空で実行しなければならず、装置は大気圧中にある。基板を大気圧から真空へと運搬するために、２つのロードロックＬ０、Ｌ１を設ける。異なるサブシステム間で基板を移送するために、２つのロボットＲ０、Ｒ１を設ける。装置の概略的レイアウトを図１１に示す。
【０１０４】
図１１では、考察する平行な電子機械システム、つまりトラックＴ０、ロードロックＬ０、Ｌ１、ロボットＲ０、Ｒ１、アライナＡ０、Ａ１および基板テーブルＳ０、Ｓ１（以下ではステージとも呼ぶ）を円で示し、可能な移送路を矢印で示す。各電子機械システム（トラックを除く）は基板を１つしか担持することができず、これを括弧の中に示す。装置のレイアウトが窮屈であるので、ロボットが両方ともロックへと行き来すると、ロボットが衝突する可能性があり、これを網掛け区域で示す。装置は、別個の測定および露光ステーション（図１１では図示せず）があるデュアルステージ装置である。測定ステーションでは、基板をロード位置およびアンロード位置それぞれで基板テーブルにロードし、そこからアンロードすることができる。
【０１０５】
様々な電子機械システムの状態遷移図表またはオートマトンを、図１２から図１６で示す。これらの図では、初期状態を余分な円で示し、遷移を継続時間またはタスク名で分類するが、これについては以降で説明する。テーブルの区域の切り換えは、基板ステージの衝突を回避するために同期状態で実行しなければならない。チャックスワップである。これを、図１２にある２つのテーブルの図表間の点線の接続部で示す。一例として、スケジュール作成すべき作業は、１５の基板の典型的バッチ（ロット）に関する。
【０１０６】
上記で検討したように、スケジュール作成の問題は、図４のインスタンス作成した未選択ＴＲＳの定義（レベル２）に関連づけることができる。ジョブショップスケジュール作成問題は、６個組（Ｔ2、Ｒ、Ｉ2、Ｐ2、Ｓｂ2、Ｓｅ2）で定義することができ、ここで、
Ｔ2は、コールされたタスクである要素を有する有限のセットであり、
Ｒは、コールされた資源である要素を有する有限のセットであり、
Ｉ2：Ｔ2→（Ｐ）Ｒは、特定のタスクに関与する資源を与え、
Ｐ2⊆Ｔ2×Ｔ2は、タスク間の優先順位関係であり、
Ｓｂ2、Ｓｅ2：Ｔ2×Ｒ→Ｓは、特定のタスクに関与する資源の（物理的）開始および終了状態を与える。
【０１０７】
規則により、定義レベルを各定義要素に下付き文字で追加することに留意されたい。レベルに固有でない定義要素は添字を有さない。
【０１０８】
定義要素のインスタンスについて満足すべき制約条件は、以下の通りである。
２ａ  Ｐ2はサイクルを含まない。
２ｂ  タスクに寄与するどの資源についても、開始および終了状態を定義しなければならない。
【０１０９】
しかし、複合機械においては、全てが同じ作業をする能力がある複数の資源が存在することができる。さらに、一部のタスクは、複数の資源の同期遷移を伴う。これはジョブショップにも当てはまるので、この問題を組み込むために、ジョブショップスケジュール作成問題を一般化した（上記で言及した「自動化した計画ボードのアルゴリズム支援」を参照）。
【０１１０】
一般化したジョブショップスケジュール作成問題は、８個組（Ｔ2、Ｒ、Ｃ、Ｉ2、Ａ、Ｐ2、Ｓｂ2、Ｓｅ2）で定義することができ、ここで、
Ｔ2は、コールされたタスクである要素を有する有限のセットであり、
Ｒは、コールされた資源である要素を有する有限のセットであり、
Ｃは、コールされた機能である要素を有する有限のセットであり、
Ｉ2：Ｔ2→Ｐ（Ｃ）は、特定のタスクに関係する機能のセットを与え、
Ａ：Ｃ→Ｐ（Ｒ）は、特定の機能について使用可能な資源のセットを与え、
Ｐ2⊆Ｔ2×Ｔ2は、タスク間の優先順位関係であり、
Ｓｂ2、Ｓｅ2：Ｔ2×Ｃ→Ｓは、あるタスクに関係する各機能の（物理的）開始および終了状態を与える。
【０１１１】
定義要素のインスタンスについて満足すべき制約条件は、以下の通りである。
２ａ  Ｐ2はサイクルを含まない。
２ｂ  タスクに寄与するどの資源についても、開始および終了状態を定義しなければならない。
【０１１２】
どれが資源をタスクに割り当てるよう決定するか選択し、資源ごとにタスクを実行する順番を決定することにより、未選択のＴＲＳを、選択されて、タイミングをとっていないＴＲＳに変換し、これは６個組（Ｔ1、Ｒ、Ｉ1、Ｐ1、Ｓｂ1、Ｓｅ1）で定義することができ、ここで、
Ｔ1は、コールされたタスクである要素を有する有限のセットであり、
Ｒは、コールされた資源である要素を有する有限のセットであり、
Ｉ1：Ｔ1→Ｐ（Ｒ）は、特定のタスクに関係する資源のセットを与え、
Ｐ1⊆Ｔ1×Ｔ1は、タスク間の優先順位関係であり、
Ｓｂ1、Ｓｅ1：Ｔ1×Ｒ→Ｓは、特定のタスクに関係する各資源の（物理的）開始および終了状態を与える。
【０１１３】
定義要素のインスタンスについて満足すべき制約条件は、以下の通りである。
１ａ  資源ごとのタスクのシークエンスはチェーンである。
【０１１４】
変換の選択について満足すべき制約条件は、以下の通りに公式化することができる。
ｂ１  資源ごとに選択したタスクのシークエンスはチェーンである（１ａに等しい）。
ｂ２  選択したタスクごとに、関係する機能ごとに使用可能な資源を選択しなければならない。
【数３４】
2005191571.tif 000043
【０１１５】
タイミングをとることにより、選択され、タイミングをとっていないＴＲＳを、タイミングをとったＴＲＳに変換し、これは５個組（Ｔ0、Ｒ、Ｉ0、τS0、τF0）で定義することができ、ここで、
Ｔ0は、コールされたタスクである要素を有する有限のセットであり、
Ｒは、コールされた資源である要素を有する有限のセットであり、
Ｉ0：Ｔ0→Ｐ（Ｒ）は、あるタスクに関係する資源のセットであり、
2005191571.tif 000044
は、特定タスクの開始時間および終了時間であり、これは、関係する全ての資源で同じであることを示唆する。
【０１１６】
さらに、タイミングをとったＴＲＳをガントチャートとして視覚化できることに留意されたい。
【０１１７】
定義要素のインスタンスについて満足すべき制約条件は、以下の通りである。
０ａ  資源ごとに、タスク開始時間とタスク終了時間の対の時系列シークエンスがある。
【０１１８】
タイミング変換について満足すべき制約条件は、以下の通りである。
ａ１  タスクおよび関係する資源に関して変化はない。
Ｔ0＝Ｔ1、Ｉ0＝Ｉ1
ａ２  慣例により、時間は０で開始する。さらに、タスクの終了時間は、その開始時間にその継続時間を加えた値に等しい。
【数３５】
2005191571.tif 000045
ａ３  その後のタスクでは、次のタスクの開始時間が、先行タスクの終了時間より大きいか、それと等しい。
【数３６】
2005191571.tif 000046
ａ４  同じ資源のその後のタスクの状態と一致するために、資源のセットアップ状態遷移が必要になることがある。その場合、次のタスクの開始時間は、先行タスクの終了時間に、タスク間のセットアップ資源状態遷移の継続時間を加えた値より大きいか、それと等しい。
【数３７】
2005191571.tif 000047
【０１１９】
ここでＰ’1⊆Ｐ1は、全ての資源タスクチェーンの和集合である。
【０１２０】
2005191571.tif 000048
は、タスクによって課される挙動の制約条件、さらにタスクに関係する資源を考慮に入れて、特定のタスクの継続時間を与える。
【０１２１】
2005191571.tif 000049
は、資源によって課される挙動の制約条件を考慮に入れて、ある状態から別の状態への資源セットアップの継続時間を与える。τt0およびτr0に関するさらなる情報は、上記で言及した「監視機械制御の設計」を参照されたい。
【０１２２】
この実施形態のスケジュール作成問題を、一般化したジョブショップスケジュール作成問題の定義にマッピングすることは、２つのセクションに分割することができる。つまりシステム依存の要素と作業依存の要素である。システム依存の要素は以下の通りに定義することができる。
【０１２３】
５つの機能、つまりステージ、ロボット、アライナ、ロックおよびトラックがある。
Ｃ＝｛Ｓ，Ｒ，Ａ，Ｌ，Ｔ｝
【０１２４】
９つの資源、つまりステージ０、ステージ１、ロボット０、ロボット１、アライナ０、アライナ１、ロック０、ロック１、トラック０がある。
Ｒ＝｛Ｓ０，Ｓ１，Ｒ０，Ｒ１，Ａ０，Ａ１，Ｌ０，Ｌ１，Ｔ０｝
【０１２５】
各機能で使用可能な資源は、以下の通りに定義される。
Ａ＝｛（Ｓ，｛Ｓ０，Ｓ１｝），（Ｒ，｛Ｒ０，Ｒ１｝），（Ａ，｛Ａ０，Ａ１｝），（Ｌ，｛Ｌ０，Ｌ１｝），（Ｔ，｛Ｔ０｝）｝
【０１２６】
作業依存の要素を定義するには、装置を通した基板ごとのタスクのシークエンス（基板の寿命）を分析する。図１７で示すように、最初に基板をトラックからロックに移送する（Ｔ２Ｌ）。その後、ポンプで圧力を低下させ（ＰＤ）、基板をロボット上に移送する（Ｌ２Ｒ）。ロボットはロックからアライナへと回転して（ＲＬＡ）、基板をアライナ上に配置し（Ｒ２Ａ）、位置合わせが実行される（ＡＬ）。その後、ロボットは基板をアライナから取り出し（Ａ２Ｒ）、ステージへと回転して（ＲＡＳ）、基板をステージ上に配置する（Ｒ２Ｓ）。ステージ上で測定が実行され（ＭＥＡ）、ステージスワップ（ＳＷ）後、基板を露光する（ＥＸＰ）。次に、ステージは、測定区域のアンロード位置へと入れ替わり（ＳＷ）、ここでロボットは基板をステージから取り出す（Ｓ２Ｒ）。ロボットはロックへと回転し（ＲＳＬ）、基板をロックに入れる（Ｒ２Ｌ）。最後に、ロックがポンプで圧力を上昇させ（ＰＵ）、トラックによって基板をロックから取り出す（Ｌ２Ｔ）。基板の寿命は、Ｔ2およびＰ2で定義し、図１７で示すように、タスクのグラフにより図表で表示することができる。バッチ全体でタスクのグラフを定義する最初の試みは、この同一シークエンスのうち１５個でよい。
【０１２７】
しかし、さらに詳細に見ると、図１７のタスクの幾つかは、材料の寿命におけるタスク以外で必要なものもあるようである。例えば、ロックがその後に２つの基板をポンプで低下させるべき場合、その間ではポンプで上昇させねばならない。回転タスクおよびテーブルのスワップについても、同じことが当てはまる。ジョブショップスケジュール作成では、このようなタスクをセットアップと呼び、これは同じ資源にある正規タスクのシークエンスの結果であることを示唆する。同じ資源にあるタスクの選択されたシークエンスに応じて、セットアップが必要になるか、必要にならない。特に、何らかの資源で先行タスクの終了状態が、後続タスクの開始状態と一致しない場合は、このギャップを埋めるためにセットアップを挿入する。これは、図１８で示すように、基板の寿命からセットアップタスクを除外できることを示唆する。
【０１２８】
１つの基板、例えば基板１に関して、作業依存の要素を以下のように定義することができる。
2005191571.tif 000050
【０１２９】
慣例により、状態名は小文字であり、タスク名は大文字であって、関連する材料で開始する。
【０１３０】
上述した一般化されたジョブショップスケジュール作成の定義は、複合機械のスケジュール作成問題の良好な根拠を形成するが、実行不可能なスケジュールを回避するには、幾つかの基本的制約条件が欠けている。その幾つかは、材料のロジスティックスに関係する。例えば、材料移送は、トラックからロック機能のロック資源のいずれへも実行可能であるが、ロックから任意のロボットへの移送は不可能である。つまり、ロジスティックフローの実行可能性である。さらに、例えば基板をロックのうちの１つに移送する場合は、これを同じロックから取り出すものと仮定しなければならない。つまり、ロジスティックフローの完全性である。さらに、物理的余地が与えられないので、同時にロックの１つに多数基板が存在しないことを仮定しなければならない。つまり、材料容量の実行可能性である。
【０１３１】
資源の干渉も追加の制約条件を引き起こす。ジョブショップスケジュール作成の場合とは異なり、セットアップは他の遷移のみ、例えばステージスワップのみと同期して実行するよう制約することができる。これに対して、複数のセットアップは、１回に１つずつ実行するよう制約することができる。というのは、例えばロボットがロックの前で回転していて同じ危険な区域を通る場合があるからである。これらの複雑な状況は両方とも、セットアップ遷移の一部のみに適切である。例えば、状態＠ａから状態＠ｌへのロボット回転は、中間状態＠ｃａから状態＠ｌまでの危険な区域のみを通る。したがって、場合によっては複合の状態遷移またはセットアップを、基本の遷移に分解しなければならない。＠ｅから＠ｌｍへの基板ステージの状態遷移についても同じことが言え、これは状態＠ｕを介して進行しなければならない。
【０１３２】
最後に、必要なナノメートルの精度が、幾つかの時間ウィンドウに制約条件を課す。基板は、プレアライナとステージの上で調整され、その間では調整されないので、その間にある時間は必要時間を超えてはならない。つまり、タスクＡ２ＲおよびＲ２Ｓは、遅延なく実行する。さらに、露光からトラックへの移送までの時間（露光後ベーク時間）は、良好な描像の均一性を達成するために、可能な限り一定でなければならない。
【０１３３】
材料に関して実行可能な機械の挙動を保証するために、資源をロードしすぎてはならない。材料のためのスペースが制限されているからである。材料移送タスクもある役割を果たすので、資源が、材料インスタンスと、材料インスタンスの位置に関するタスクの結果とによって占有されるということを記述することが可能でなければならない。
【０１３４】
資源に関する選択が役割を果たさず、各資源に１つの材料インスタンスのためのスペースがある場合は、材料の概念を導入せずに、実行可能な機械の挙動を確保することが可能になる。材料インスタンス、さらに資源における物理的材料位置を、資源としてモデル化することができた。しかし、材料は物理的タスクの後も資源に存在し続けるので、各物理的移送タスクの後に、追加の「材料占有」タスクを導入する。この「材料占有」タスクは、資源が何らかの材料インスタンスによって占有され、移送タスクがこれを引き継ぐことができ、その後、材料が別の資源に存在することを示す。「材料占有」タスクは、その後の移送タスクが開始すると終了する。これを図１９で示す。
【０１３５】
しかし、資源に関する選択が役割を果たす場合、以前に提示したアプローチは不完全である。この場合、使用可能な全ての資源が、ただ選択できるというわけではない。材料のロジスティックフローの完全性を保証しなければならないからである。例えば、機能Ｓの２つの資源Ｓ１およびＳ２が存在する場合、資源Ｓ１へと移送される材料は、Ｓ１からの移送もしなければならない。これは、使用可能であっても、資源Ｓ２がこの場合に適格でないことを示唆する。ロジスティックの完全性の問題を直感的な方法で記述するために、材料の概念をＴＲＳ定義レベル２に追加する。
【０１３６】
タスクがそれに関係する材料インスタンスに及ぼすロジスティック的（材料構成の）効果が、関係する材料インスタンス全部で同じであるものと仮定する。
【０１３７】
以下の５つの要素を、未選択のＴＲＳ定義Ｄ2に定義する。
・Ｍは、コールされた材料インスタンスである要素を有する有限のセットである。
・Ｃｂ2、Ｃｅ2：Ｔ2→Ｐ（Ｃ×Ｐ（Ｍ））は、タスクの開始点および終了点に、占有され、関係した各機能およびそれに存在する材料インスタンスを定義する組のセットとして材料構成を与える。
・
2005191571.tif 000051
は、特定の資源に存在できる材料インスタンスの数を与える。
・Ｍｆ⊆Ｒ→Ｒは、どの資源からどの資源へと材料が流れることができるか定義する組のセットとして、物理的に可能な材料フローを表す。
【０１３８】
Ｄ2に関して満足しなければならない追加の制約条件は、以下の通りである。
２−ｉ  Ｃｂ2およびＣｅ2の機能は、Ｉ2と一致しなければならない。
【数３８】
2005191571.tif 000052
２−ｉｉ  タスクに関係する機能ごとに、タスクのロジスティック効果は、関係する全ての材料で同じである（例えば、同じ機能から２つの異なる他の機能へと２セットの材料を移送することは、１つのタスクでは可能でない）。
【数３９】
2005191571.tif 000053
この制約条件は、閉じたシステムのみを考察することを示唆する。つまり、材料がシステムに入らず、ここから出ない。
【０１３９】
Ｐ2m：Ｄ2×Ｍ→Ｐ（Ｔ2×Ｔ2）を、ＴＲＳ定義Ｄ2∈Ｄ2の各材料ｍ∈Ｍを記述する関数とすると、冗長縁部がないが、一致する機能を有する関連のタスク間の優先順位関係（材料「寿命」）を記述する関数は、以下の通り。
【数４０】
2005191571.tif 000054
ここで関数の冗長性：
2005191571.tif 000055
は、優先順位縁部（ｔ，ｔ’）が優先順位関係Ｐにて冗長か否かを決定する。
【数４１】
2005191571.tif 000056
【０１４０】
さらに、関数路
2005191571.tif 000057
が、優先順位関係Ｐの２つのタスクｔとｔ’の間に路があるか否かを決定する場合、以下となる。
【数４２】
2005191571.tif 000058
Ｄ2からＤ1への変換Ｂについて満足しなければならない追加の制約条件は、以下の通りである。
ｂ−ｉ  ＴＲＳ定義Ｄ2∈Ｄ2の材料インスタンスｍ∈Ｍの寿命に関係する資源が一致する（ロジスティックフローの完全性）。
【数４３】
2005191571.tif 000059
ｂ−ｉｉ  材料移送において関係する資源の組み合わせが物理的に可能である（ロジスティックフローの実行可能性）。
【数４４】
2005191571.tif 000060
ｂ−ｉｉｉ  資源の材料容量を超えない（材料容量の実行可能性）。Ｐ1r：Ｄ1×Ｒ→Ｐ（Ｔ1×Ｔ1）を、ＴＲＳ定義Ｄ1∈Ｄ1の各資源ｒについて、関連するタスク間の線形優先順位関係を記述する関数であるものとし、ここで線形とは、関連するタスクがチェーンを形成するという意味である。
【数４５】
2005191571.tif 000061
ｔｃｈａｉｎｒ：Ｐ（Ｔ1×Ｔ1）→Ｔ*１は、線形優先順位関係Ｐ1に対応するタスクチェーンを戻す関数である。
【数４６】
2005191571.tif 000062
【０１４１】
ここでａ＋＋ｂは、シークエンスａおよびｂをａｂに連結することを示し、
【０１４２】
関数ｆｉｒｓｔｐ：Ｐ（Ｔ1×Ｔ1）→Ｔ1×Ｔ1が、線形優先順位関係Ｐ1の第一優先順位縁部を決定するものとすれば以下の通りになる。
【数４７】
2005191571.tif 000063
【０１４３】
Ｓm（γ，ｓ）を、タスクシークエンスｓ実行後の資源ｒの材料構成とすれば、任意のタスクを実行する前に、資源の材料構成が与えられ、初期材料構成Ｓm（γ，ε）＝Ｓm-i（γ）で与えられ、かつ定義される。タスクシークエンスｓｔ実行後の材料構成は、以下のように定義される。
【数４８】
2005191571.tif 000064
【０１４４】
関数ｍａｔ：Ｐ（Ｃ×Ｐ（Ｍ））×Ｒ→Ｐ（Ｍ）が、それに使用可能な資源を有する機能と関連する材料を返すものであれば、
【数４９】
2005191571.tif 000065
【０１４５】
次に、ＴＲＳ定義Ｄ1∈Ｄ1の材料容量の制約条件は、以下のように定義することができる。
【数５０】
2005191571.tif 000066
【０１４６】
建設的スケジュールの構築中に無効な挙動を回避するために、選択の有効拡張を画成する追加の制約条件を導入する。
【０１４７】
例えば図２０で示したような場合などに、システムがロックされるとデッドロックになる可能性がある。これを回避するために、資源ｒＣのサブセットに存在する材料インスタンスの数が、何らかの数ｒcを超えないことを保証することが必要である。例えば図２０の場合、破線の正方形それぞれの材料インスタンスの数は、２を超えてはならない。
ｂ−ｉｖ  建設的スケジュール作成アルゴリズムを考察する場合、部分選択Ｄ1p∈Ｄ1は、拡張した部分選択についてＷＩＰ上昇限度制約条件に違反しない場合に、拡張した部分選択Ｄ’1p∈Ｄ1を形成するために、タスクｔ’および関連する定義要素でのみ拡張することができる。
2005191571.tif 000067
を、前述したような該当する組み合わせＲｃおよびｎcのセットであるものとする。これで、追加の制約条件が以下のように定義される。
【数５１】
2005191571.tif 000068
【０１４８】
多くの場合、材料の移送は、１つの材料インスタンスしか含むことができない資源で実行する（１レーンのロジスティック路）。つまり、このような資源で可能な唯一の次の移送タスクは、材料インスタンスをさらに移送することである。しかし、建設的スケジュール作成アルゴリズムを適用すると、これがデッドロックにつながることがある。材料を受け取るために使用可能な資源がなく、同じ資源がこれらの資源上で場所を空けねばならないからである。この種のデッドロック状況を回避するために、スケジュール作成アルゴリズムは、この材料インスタンスの寿命内で次のタスクのみよりわずかであるが多く調べなければならない。
【０１４９】
これらの状況を記述するために、結合された優先順位Ｐｔ2⊆Ｐ2の概念を導入する。一般化したジョブショップスケジュール作成問題のようにタスクの選択を考察しない場合、これは、次々に中断なく実行しなければならない特定材料インスタンスのその後の移送タスクを、結合した優先順位で接続することを示唆する。結合とは、結合した優先順位によって接続されるタスクのチェーンと定義される。開放結合とは、少なくとも１つであるが、全部ではないタスクを選択する結合と定義される。
【０１５０】
建設的スケジュール作成アルゴリズムを考察する場合、結合に関する追加の制約条件は、以下の通りである。
ｂ−ｖ  部分選択Ｄ1p∈Ｄ1は、その後に結合全体を選択することが可能であれば、拡張した部分選択Ｄ’1p∈Ｄ1を形成するために、ある結合からのタスクｔ’のみで拡張することができる。
ｂ−ｖｉ  部分選択が開放結合を含む場合、これは結合したタスクのみで拡張することができる。
【０１５１】
以下では、建設的スケジュール作成アルゴリズムにとって可能なスケジュールの拡張を公式化する。
【０１５２】
Ｔ1p、Ｉ1p、Ｐ1pを、タスク、関係する資源、および部分選択Ｄ1pの優先順位関係とするとし、Ｔ1e、Ｉ1e、Ｐ1eを、タスクｔ’、ｔ’と関係した資源、および選択の拡張Ｄ1eのｔ’への優先順位縁部であるとするとし、Ｔ’1p、Ｉ’1p、Ｐ’1pを、タスク、関連した資源、および拡張した部分選択Ｄ’1pの優先順位関係であるとすると、これは以下に等しい。
【数５２】
2005191571.tif 000069
【０１５３】
関数Ｅｔ：（Ｄ2×Ｄ1）→Ｐ（Ｔ1）を、結合した優先順位関係を考察して、部分選択Ｄ1pについて全ての適格で結合された次のタスクを決定する関数であるとする。
【数５３】
2005191571.tif 000070
【０１５４】
関数Ｅｔt：（Ｄ2×Ｄ1）→Ｐ（Ｔ1）を、結合した優先順位関係を考察して、部分選択Ｄ1pについて全ての適格な次のタスクを決定する関数であるとすると、
【数５４】
2005191571.tif 000071
【０１５５】
関数Ｅｒ：（Ｄ2×Ｔ1）→Ｐ（Ｒ）を、関係する機能に使用可能な資源を考察して、タスクについて関係する資源の全ての適格セットを決定する関数であるとすると、
【数５５】
2005191571.tif 000072
【０１５６】
関数ｃｈｅｃｋCb-iから
2005191571.tif 000073
を通して、次のタスクｔ’および関係する資源ｒｒ’について制約条件ｂ−ｉからｂ−ｉｉｉが成立するか否かをチェックする関数であるとすると、
【数５６】
2005191571.tif 000074
【数５７】
2005191571.tif 000075
【数５８】
2005191571.tif 000076
【０１５７】
関数
2005191571.tif 000077
を、次のタスクｔ’および関連する資源ｒｒ’について制約条件ｂ−ｉｖが成立するか否かをチェックする関数であると、
【数５９】
2005191571.tif 000078
【０１５８】
関数Ｅ：（Ｄ2×Ｄ1）→Ｐ（Ｔ1×Ｐ（Ｒ）×Ｐ（Ｔ1×Ｔ1））を、未選択のＴＲＳ定義について、タスクｔ’の形態である全ての可能な拡張ｅ、関連する資源ｒｒ’、および拡張部分選択Ｄ’1pを形成するために部分スケジュールＤ1pを拡張することができる優先順位ｐｒ’を返す関数であるとする。Ｄ1eは、Ｔ1eについて０を、Ｉ1eについて（ｅ．０，ｅ．１）を、Ｐ1eについてｅ．２をとることにより、ｅから決定することができる。これで、関数Ｅを以下のように定義することができる。
【数６０】
2005191571.tif 000079
【０１５９】
関数Ｅでは、一般化したジョブショップスケジュール作成に関係する制約条件と、追加の機械特有のスケジュール作成の制約条件ｂ−ｉからｂ−ｖｉとの両方を認識することができる。
【０１６０】
（制約条件ｂ−ｉｖからｂ−ｖｉの代わりに）材料の方向を考慮に入れたデッドロック回避の制約条件を適用することも可能である。このような制約条件は、構成可能な関数の形態で公式化し、この材料の流れ方向（材料の寿命の残りから導出することができる）を含む特定の材料構成Ｓmが安全か（デッドロックにつながらないか）チェックすることができる。このような関数は、例えばピッツバーグのカーネギーメロン大学によって入手可能になったＳｙｍｂｏｌｉｃ  Ｍｏｄｅｌ  Ｖｅｒｉｆｉｅｒ（ＳＭＶ）ソフトウェアＰＡ１５２１３−３８９０などのモデルチェッカを使用して構成することができる。
【０１６１】
以下のテキストでは、実行不可能なタイミング挙動を回避するために、最初に追加の機械特有の制約条件を紹介し、次に変換関数について説明する。
【０１６２】
ハードウェアの干渉を説明するために、幾つかの追加の定義要素を定義する。その後、この追加の要素を使用して、制約条件を定義する。さらに、選択されたＴＲＳのタイミングをとるために満足しなければならない制約条件について説明する。最後に、タスクの開始および終了時間に関する制約条件について説明する。
【０１６３】
幾つかの資源の状態遷移のなかには、他の資源の状態遷移と同期状態でしか実行できないものもある。
ＴS⊆Ｐ（Ｒ×Ｓ×Ｓ）は、同期資源状態遷移のサブセットを与える。
【０１６４】
機械の中には、資源が衝突し得る特定の区域が存在する。これらの区域は、資源が相互に排他的に通ることができるようにする。この追加の制約条件は、このような危険な区域について資源をＲに追加することによって記述され、上述したように、この区域を訪問する全ての資源状態遷移においてこの資源に関係する。衝突区域の資源については、物理的状態が役割を果たさない。
Ｒcは、コールされた衝突区域である要素を有する有限のセットである。
ＴC：Ｒ×Ｓ×Ｓ→Ｒc∪｛Φ｝は、特定の資源状態遷移に関係する衝突区域資源を与える。
【０１６５】
セットアップ遷移は、幾つかの基本的下位遷移で構成することができ、これはそれぞれ強制同期または衝突回避に関連することがある。
【０１６６】
Ｔｅ：Ｒ×Ｓ×Ｓ→（Ｒ×Ｓ×Ｓ）*は、資源状態遷移の基本的下位遷移を与える。基本的下位遷移がない場合は、元の状態遷移を戻す。
制約条件：
ｉ  どのタスクも基本的である。
【数６１】
2005191571.tif 000080
ｉｉ  どのタスクもＴSに一致し、これは各タスクｔで、関係する資源状態遷移ｓが、ＴSから同期状態遷移の何らかのセットを捕捉するか、ＴSからのどのｓでも関係する資源状態遷移が発生しないことを示唆する。
【数６２】
2005191571.tif 000081
ｉｉｉ  どのタスクもＴCに一致し、これは各タスクおよび各資源状態遷移を目指す関係各資源（危険な区域を除く）で、関係する衝突区域がタスクにも関係することを示唆する。
【数６３】
2005191571.tif 000082
【０１６７】
これらの制約条件が、基本的にどのＴＲＳ定義レベル（主要＝レベル１）にも成立することに留意されたい。
１−ｔ  選択されたＴＲＳ  Ｄ1∈Ｄ1は、資源ごとにタスクのチェーンにある後続タスクの終了状態および開始状態が以下に一致する場合は、タイムテーブルである。
【数６４】
2005191571.tif 000083
【０１６８】
選択によって示唆される何らかの可能な資源状態遷移間の基本的資源状態遷移で、幾つかの可能なシークエンスが許容されるが、関数Ｔｅによって遷移を１つしか定義しないことに留意されたい。さらに、基本的状態遷移ごとに、関数Ｔｅによってせいぜい１つの衝突区域が定義される。
【０１６９】
強制同期および基本的状態遷移の問題を考慮に入れると、資源のセットアップ状態遷移が、他の資源のセットアップ状態遷移を示唆することが可能である。これは、状態遷移も資源の状態に一致しなければならないことを示唆し、これは他の状態遷移などを示唆する。ループによって無限のチェーン反応が生じるのを回避するために、追加の制約条件を定義する。
【０１７０】
コアセットアップ遷移を、ｒに関する前のタスクの終了状態からタスクｔ∈Ｔ2の開始状態までの資源ｒの資源状態遷移として、これらの状態が一致しない場合に定義される。タイミング可能なＴＲＳへと変換する間にループを防止するために、この定義を使用して、以下の制約条件を満足しなければならない。
・１つのタスクｔに２つのコアセットアップ遷移が必要な場合、各コアセットアップ遷移によって示唆されたセットアップ遷移に関与する資源のセットは重複しない。例えば、資源ＡおよびＢに２つのコアセットアップがあり、資源Ａのコアセットアップが資源Ｃの同期状態遷移を示唆する場合、資源Ｂのコアセットアップによって示唆される状態遷移は、資源Ｃに関係しない。
・資源ｒ’（コアまたは他のセットアップ遷移によって示唆されたもの）のどのセットアップ遷移についても、このセットアップ遷移によって示唆されるセットアップ遷移に関与する資源のセットは、ｒ’自体を含まない。例えば、資源Ａの状態遷移によって示唆された資源Ｂの状態遷移が、自分の順番で資源Ａの状態遷移を示唆することは許容されない。
ａ−ｉ  一般的問題の定義で示した制約条件以外に、タイミング可能な選択済みＴＲＳ  Ｄ1をタイミングをとったＴＲＳ  Ｄ0に変換するために、特定のタスクの開始時間または終了時間の間の時間に、追加の制約条件を導入することができる。その例は、露光後ベーク時間、および基板がロードロボットに存在する時間である。
【０１７１】
選択済みＴＲＳ  Ｄ1からタイミング可能な選択済みＴＲＳ  Ｄ1Tの１つの可能な有限変換Ａを確保する制約条件のために、この変換を、関数によって定義することができる。定義Ｄ1の資源ごとのタスクのチェーンでは、制約条件ｉ、ｉｉ、ｉｉｉおよび１−ｔを満足するタスクのチェーンが結果として生じ、タイミング可能な選択済みＴＲＳ  Ｄ1Tとなるよう、追加のセットアップタスクを導入する。
【０１７２】
ｉｎｓｅｒｔを、ｉｎｓｅｒｔ（Ｄ1）＝D’1によって定義された全ての非一致後続タスク終了および開始状態について、セットアップタスクおよび優先順位縁部を選択されたＴＲＳ  Ｄ1に挿入する関数であるとし、したがって以下のようになる。
【数６５】
2005191571.tif 000084
およびＴ’1、Ｐ’1、Ｉ’1、Ｓｂ’1およびＳｅ’1は最小である。
【０１７３】
ｅ＝Ｔｅ（ｒ，Ｓｂ1（ｔ，ｒ），Ｓｅ1（ｔ，ｒ））であるとし、ｄｅｃｏｍｐを、ｄｅｃｏｍｐ（Ｄ1）＝Ｄ’1によって定義されたＴｅに一致するよう、選択済みＴＲＳのセットアップタスクのいかなる複合遷移も分解する関数であるとし、したがって以下のようになる。
【数６６】
2005191571.tif 000085
およびＴ’1、Ｐ’1、Ｉ’1、Ｓｂ’1およびＳｅ’1は最小である。
【０１７４】
ｎｏｔｓｙｎｃ：Ｄ1→Ｔ1を、選択済みＴＲＳのどのタスクがＴSと一致していないか決定する関数であるとする。
【数６７】
2005191571.tif 000086
【０１７５】
ａｄｄｓｙｎｃを、ａｄｄｓｙｎｃ（Ｄ1）＝D’1によって定義されたＴSと一致していない選択済みＴＲＳのセットアップタスクに、強制同期資源状態遷移を追加する関数であるとし、したがって以下のようになる。
【数６８】
2005191571.tif 000087
【０１７６】
ａｄｄｃｏｌｌを、Ｔｃ：ａｄｄｃｏｌｌ（Ｄ1）＝Ｄ’1に従わない選択済みＴＲＳのセットアップタスクに衝突区域を追加する関数であるとし、したがって以下のようになる。
【数６９】
2005191571.tif 000088
【０１７７】
制約条件１−ｔを満足しない選択済みＴＲＳ  Ｄ1｜を、制約条件１−ｔを満足する選択済みＤ1Tに変換するために、関数ｔｒａｎｓA-t：Ｄ1→Ｄ’1を以下のように定義する。
【数７０】
2005191571.tif 000089
【０１７８】
ｔｒａｎｓA-tは、建設的アルゴリズムにも使用できることに留意されたい。
【０１７９】
タイミングの制約条件ａが与えられたタイミング可能な選択済みＴＲＳ  Ｄ1Tのタイミングを最適化するアルゴリズムは、周知の技術で解決可能である線形プログラミング問題である。線形プログラミングは、建設的アルゴリズムにも使用することができる。
【０１８０】
一例のシステムでは、追加の要素を以下のように定義することができる。
2005191571.tif 000090
【０１８１】
単純な発見法を使用して、つまり可能な限り多く、かつ「最初が最初に開始する」状態でシステムを満たすことにより、実行可能な有効スケジュールが獲得される。その後、タイミング後処理ステップを実行して、追加の時間ウィンドウの制約条件を満たす。
【数７１】
2005191571.tif 000091
【０１８２】
その後、図２１のスケジュールが獲得される。スケジュールは追加の制限に全て一致すると結論することができる。
【０１８３】
図２２で示すようなクリティカルパスは、所望の通りであり、定常状態露光がクリティカルパス上にある。
【０１８４】
本発明の第三の実施形態は、露光放射線として超紫外線放射線を使用し、トラックに接続されたリソグラフィ装置である。第三実施形態の基板の流れを、図２３で概略的に示す。図の円は、モデルの資源、つまり１つのトラックＴ、４つのロードロックＬ０〜Ｌ３、２つのロボットＲ０、Ｒ１、および２つの基板テーブルＷＴ０、ＷＴ１（チャックとも呼ぶ）を表す。図の矢印は、装置を通ることができる基板の流れを表す。新しい基板はトラックで開始して、テーブルの１つへと移送され、ここで測定されて露光され、最終的にトラックへと戻される。
【０１８５】
トラックは新しい基板をリソグラフィ装置に送出し、露光した基板をリソグラフィ装置から回収する。この説明のために、トラックＴの単純なモデルを使用し、ここで基板を回収するか、新しい基板を送出すべき場合ごとに、トラックは内部動作を実行するために特定量の時間を必要とする。
【０１８６】
ロードロックＬ０〜Ｌ３は、１つの基板のためのスペースがあって、双方向性である。つまり１つのロードロックを、入る基板と出る基板との両方に使用することができる。基板をロードロックに入れた後、ロードロック内の圧力を入り基板のために真空にするか、出る基板のために大気圧にする。
【０１８７】
基板ハンドラのロボットＲ０、Ｒ１は両方とも、相互に対して１８０°反対に配置された２本のアームを有する。各アームは１つの基板を担持することができる。ロボットは、ロードロックとチャックの間でそのアームを回転する。ロボットアームは、ロック側にある場合は４つのロックのうち２つに届くことができ、チャック側にある場合は両方のチャックに届くことができる。
【０１８８】
チャックまたは基板テーブルＷＴ０、ＷＴ１はそれぞれ、１つの基板のためのスペースを有する。基板テーブルは、複数の位置、つまりロード／アンロード位置、測定位置および露光位置を採用することができる。しかし、基板テーブルが２つの位置のみとすることができるよう、ロード／アンロード位置を測定位置と組み合わせることも可能である。基板テーブルが測定位置にある場合、基板はロボットの一方によってロードまたはアンロードすることができる。測定でも、基板テーブルがこの位置にある必要がある。露光は露光位置で実行される。両方の基板テーブルは、いわゆる「チャックスワップ」中に同期状態で位置を変更する。
【０１８９】
第一および第二の実施形態と同様に、システムをインスタンス作成した未選択のＴＲＳ定義（クラス２）について説明することができる。第三実施形態の制御戦略は、発見的フィルタ構成で実現される。
【０１９０】
この実施形態では、１つのトラックがあって、４つのロードロック、２つのロボットおよび２つの基板テーブルがあり、つまり９つの資源になる。しかし、２つの基板の基板容量を有するロボットをモデル化する代わりに、ロボットのロボットアームを、別個の一意の基板位置を表す別個の資源として定義する。そうするのは、ロボットの回転に関する挙動に影響を与えるので、基板の位置がロボットに分かっていなければならないからである。ロボットを、２つの基板の材料容量を有する１つの資源としてモデル化する場合、基板がどのアームに存在するかは不明である。つまり、１１の資源があり、これが０から１０まで番号付けられ、Ｒに記憶される。
【０１９１】
モデルには４つの機能、つまりトラック、ロック、ロボットアームおよび基板テーブルがあることは明白である。これらの機能に０から３の番号を与え、Ｃに記憶する。
【０１９２】
システムは幾つかの挙動を実行することができる。挙動の大部分は、２つの資源間の基板移送に関する。この移送挙動を表すストリングは「機能２機能」の形態である。例えば、トラック（Ｔ）からロックロード（Ｌ）への移送を「Ｔ２Ｌ」と呼ぶ。移送挙動は６つある。つまり「Ｔ２Ｌ」、「Ｌ２Ｒ」、「Ｒ２Ｌ」、「Ｃ２Ｒ」、「Ｒ２Ｌ」および「Ｌ２Ｔ」である。このような移送挙動以外に、他の２つの挙動、つまり「測定」および「露光」がある。８つの挙動は全て、ある機能に関係し、これはＩ2で定義される。移送挙動については、関係する機能が、材料をその間で移送する機能であることが明白である。「測定」および「露光」挙動については、関係する機能は基板テーブルである。
【０１９３】
機能ごとに使用可能な資源をＡで定義し、これは単純明快である。トラック以外の全ての資源は、１つの基板という材料容量を有し、これはＲｍで定義される。モデルのトラックは、基板のための無限のスペースを有するが、便宜上、トラックの材料容量を基板１００個に設定する。資源間に可能な材料の流れを、Ｍｆで定義する。基板は、トラックから４つのロードロックのそれぞれに移送することができ、各ロードロックから基板を４本のロボットアームのうち２本に移送することができる。これがどのロボットアームであるかは、図２３の矢印に対応するロードロックの番号によって決定される。基板は、ロボットアームから各基板テーブルへと移送することができる。基板テーブルからトラックへと戻す基板の移送において、上述したような逆の材料の流れが可能である。静止システムの定義のうち最後の２つの定義要素ＴｅおよびＴｓは、資源の状態遷移に関する。これについて説明する前に、各資源の可能な状態および状態遷移を定義する。
【０１９４】
トラックには、基本的下位遷移で構成された、つまり「回収した露光済み基板」から「回収準備完了」までの１つの可能な状態遷移がある。この状態遷移が必要なのは、トラックがその後に２つの露光済み基板を回収する場合である（スケジュールの最後に生じる）。この遷移は、２つの基本的状態遷移で構成される。つまり、「回収済み露光基板」から「送付準備完了」（図２４参照）までのトラック内部動作、および「送付準備完了」から「回収準備完了」までのバイパス遷移である。このような基本的下位遷移への分割をＴｅで定義する。ロックの場合、状態は空気が大気圧か真空であるかを示す。
【０１９５】
ロックに関する移送タスクは、ロックの状態を変化させない。ポンプで真空へと下げ、空気を換気すること（両方とも資源のセットアップである）は、状態を変化させる可能性がある状態遷移である。ロックの自動化を図２５で示す。
【０１９６】
ロボットアームおよび基板テーブルは両方とも、２つの可能な状態を有し、その間に遷移がある。ロボットアームは、状態としてロック側または基板テーブル側にその位置を有する。基板テーブルの状態は、それが測定位置にあるか露光位置にあるかを示す。ロボットおよび基板テーブルは両方とも、図２６および図２６のオートマトン（資源状態を変化させないタスクも示す）のＴSで示した強制同期を有する。ロボットが回転すると、ロボットアームが位置を切り換える。つまり両アームの状態遷移が同期状態で実行される。同じことが、チャックスワップ中の基板テーブルでも成立し、一方の基板テーブルが位置を変化させると、他方の基板テーブルも位置が変化する。
【０１９７】
ロボットアームおよび基板テーブルのこの同期状態遷移を、ＴSで定義する。
【０１９８】
上述した静止システムの定義以外に、他の静止情報も定義しなければならない。各挙動および全ての基本的資源状態遷移のゼロ次継続時間を、それぞれＤｔｚおよびＤｓｚで定義する。（加速および最高速度と同様に）Ｈｃで定義されたハードウェア容量を必要とする、これより高い次数の継続時間関数が定義されていないので、このようなハードウェア容量を定義する必要がない。最後に、資源の記述をｒｅｓｄｅｓｃｒで定義する。
【０１９９】
作業構成は、ＴＲＳの全ての動的情報を含み、これは動的システム定義および初期状況で構成される。
【０２００】
動的システム定義は、定義要素Ｔ2、Ｌ2、Ｇ2、Ｌｎ2、Ｇｎ2、Ｇａ2、Ｐ2、Ｐｔ2、Ｔｂ2、Ｓｂ2、Ｓｅ2、Ｃｂ2およびＣｅ2で構成される。
【０２０１】
第三の実施形態では、タスクに関する代替物がないので、タスクのみが定義され、クラスタまたはグループは定義されない。基板ごとに、以前のセクションで言及した挙動に対応する８つのタスクが定義される。基板ごとに適正な製造プロセスを獲得するために、Ｐ２で１つの基板について８つのタスク間にて本質的な優先順位関係を定義し、その結果、基板の処理は以下の通りになる。つまり「Ｔ２Ｌ」、「Ｌ２Ｒ」、「Ｒ２Ｃ」「測定」、「露光」、「Ｃ２Ｒ」、「Ｒ２Ｌ」、および最終的に「Ｌ２Ｔ」である。リソグラフィ装置に入る基板の順序も、様々な基板処理過程の流入タスク（この場合は「Ｔ２Ｌ」）間の優先順位関係を使用して定義し、その結果、基板の番号の昇順で流入する。これらの優先順位関係はいずれも結合されていないので、Ｐｔ2は空である。
【０２０２】
上述した挙動を、Ｔｂ2で各タスクに割り当てる。３つの基板処理過程を示す対応のタスクのグラフを、図２８に示す。
【０２０３】
Ｓｂ2およびＳｅ2では、関係する各機能の開始状態および終了状態を、タスクごとに定義する。第三の実施形態では、全ての移送タスクで、移送を実行できるよう、関係する機能が適正な位置にある必要がある。その状態（その位置）はタスク間では変化せず、したがって終了状態は開始状態と等しい（図２４から図２７のオートマトンも参照）。しかし、トラックの状態は移送タスク中に実際は変化する。新しい基板を送出するために（挙動「Ｔ２Ｌ」）、トラックは「送付準備完了」状態にある必要があり、一方、タスクの終了時にはトラック状態が「回収準備完了」になっている。露光した基板を回収するために（挙動「Ｌ２Ｔ」）、必要な開始状態は「回収準備完了」であり、終了状態は「回収された露光基板」である。「測定」および「露光」タスクでは、開始状態および終了状態はそれぞれ「測定位置」および「露光位置」にある。
【０２０４】
最後に、開始および終了材料構成を、それぞれＣｂ2およびＣｅ2で定義する。移送するために、送出機能は材料をタスクの開始点に保持し、受け取り機能は、材料をタスクの終了点に保持することが明白である。「測定」および「露光」タスクでは、材料は機能（この場合は基板テーブル）上にとどまり、したがってこれらのタスクではＣｂ2およびＣｅ2が等しい。
【０２０５】
上述した動的システム定義に加えて、初期状況を定義しなければならない。初期ヒープは、まだ何もタスクが実行されていないので空である。各資源で、初期時間（初期輪郭で定義される）はゼロである。初期輪郭に、全ての初期資源状態も含み、これはトラックでは「送付準備完了」であり、ロードロックでは「大気圧」である。ロボットアームおよび基板テーブルでは、初期状態は、可能な２つの位置のうちの一方であり、反対のアームまたは他方の基板テーブルは、初期状態として他の可能な位置を有する。
【０２０６】
次に、第三実施形態で基板が流れるための発見的フィルタ構成の設計について説明する。
【０２０７】
ＴＲＳで交差するロジスティックでの材料の流れは、デッドロックの状況をもたらすことがあり、これが本実施のケースである。資源構成および可能な材料の流れを検査した後、以下の可能なデッドロック状況が認識される。最初に、２つのロードロックと１つのロボットとの組み合わせで、両方のロックが自身内に新しい基板を有し、両方のロボットアームが露光した基板を保持することが可能である。この場合は、新しい基板のために自由なロボットアームがなく、露光した基板のために空のロックがない。つまり、これ以上のタスクを実行することができない。このタイプのデッドロックの例を図２９で示し、ここで矢印は、その材料の処理過程内に次の移送タスクの方向を有する基板を示す。
【０２０８】
ロックの背後では、ロボットと基板テーブルの間でデッドロック状況も発生することがある。これは、４本のロボットアームが全て新しい基板を有し、両方の基板テーブルが露光済み基板に占有されているケースである。この状況を図３０に示す。
【０２０９】
デッドロックは無効挙動の例であるので、制約を与えるフィルタを使用して、これを防止する。このケースでは、ＷＩＰｃｅｉｌｉｎｇを使用する。上述したような３つの可能なデッドロック状況（ロックとロボットとの組み合わせが２つと、ロックの背後の１つ）のそれぞれで、資源のそのグループのＷＩＰｃｅｉｌｉｎｇ制約条件をチェックするｍａｘｗｉｐフィルタを定義する。Ｔ−ＲｅＣＳスケジューラの実装時には、ｍａｘｗｉｐフィルタのこの３つのインスタンスを組み合わせて、フィルタのパラメータとしてＷＩＰｃｅｉｌｉｎｇ制約条件を有する１つのｍａｘｗｉｐフィルタにする。
【０２１０】
両方のロックロボットの組み合わせ（２つのロックと２本のロボットアーム）について、３つの基板のＷＩＰｃｅｉｌｉｎｇをフィルタのパラメータで設定する。このｍａｘｗｉｐフィルタのパラメータは、２つのロックおよび２本のロボットアームの資源番号と、３つの基板の最大ＷＩＰを併せたものである。この発見的フィルタを使用すると、図２９で示したタイプのデッドロックが防止される。第三のｍａｘｗｉｐフィルタは、ロックの背後の全資源（４本のロボットアームおよび２つの基板テーブル）に関し、パラメータとしてその資源番号および５つの基板の最大ＷＩＰを有する。このフィルタを使用すると、図３０で示した状況にはもはや到達し得ない。
【０２１１】
反例のデッドロック状況を分析した後、４つの基板に対するロックの背後の最大ＷＩＰレベルを下げると、このデッドロック状況が防止されることが明白になる。この状況以外に、リソグラフィ装置内に８つの基板がある場合は、図３１のような同様のデッドロック状況になお到達することがある。全てのロックおよび各ロボットの一方のロボットアームが新しい基板を保持し、各基板テーブルが露光した基板を保持している場合は、どのＷＩＰ上昇限界制約条件（４つの基板に低下させるという制約条件を含む）も違反しないが、これ以上のタスクを実行することができない。この状況を図３２で示す。この場合も、これはモデル化したＴＲＳおよび使用したフィルタでのみデッドロックであることに留意されたい。８つの基板がある最後のデッドロック状況を防止するために、第四のｍａｘｗｉｐフィルタを追加する。このフィルタは、パラメータとして７つの基板の最大ＷＩＰおよびトラックを除いて全資源の資源番号を有する。
【０２１２】
上述した設計プロセスは、制約を与えるフィルタにのみ関し、このケースでは、４つのｍａｘｗｉｐフィルタになる。この発見的フィルタ構成内で生成された全てのスケジュールは、有効挙動を有し、これはこのケースでは、確認された特性、つまりデッドロックがないことを常に満足している、という意味である。しかし、有効挙動において一部の挙動が他の挙動より好ましい。したがって、２つの比較フィルタを発見的フィルタ構成に追加する。
【０２１３】
高い資源の利用率を獲得するため、リソグラフィ装置内の基板の数は可能な限り多いことが望ましい。したがって、ｆｉｌｌｍａｘｗｉｐフィルタを発見的フィルタ構成に追加する。このフィルタのパラメータは、ＷＩＰレベルを可能な限り高くすべき資源であり、したがってこのケースでは、トラックを除く全ての資源である。
【０２１４】
最後に、合計スケジュール時間は可能な限り低くしなければならない。これは、最低開始時間を有するタスクを好むことによって達成することができる。したがって、最初が最初に開始する（ＥＳＦ）フィルタを使用する。
【０２１５】
最終的に、発見的フィルタ構成は、制約するｍａｘｗｉｐフィルタ（１つのフィルタに実装されている）の４つの具体例、および２つの比較フィルタ、つまりｆｉｌｌｍａｘｗｉｐおよび最早開始第１（ＥＳＦ）フィルタで構成される。
【０２１６】
その結果のガントチャートを図３３で、クリティカルパスを図３４で示す。全基板の処理経過はきちんと編成され、全ての露光タスクはクリティカルパス上にある。重要な露光は望ましい挙動でもある。というのは、このタスクに関係するレンズはリソグラフィ装置で最も高価な部品であり、最大の利用率を持たねばならないからである。全ての露光がクリティカルパス上にあるので、投影レンズは可能な限り最高の利用率を有する。つまりこれは、最適スケジュールに関係する露光である。
【０２１７】
しかし、基板の流入および流出（図の基板番号参照）を見ると、順番はＦＩＦＯではない。
【０２１８】
次の実験は、基板の流入および流出に関係するＦＩＦＯの順序でスケジュールを作成することが可能であることを実証する。スケジューラは、基板が相互に追い越せないことを保証する追加の発見的フィルタを適用することにより、この挙動に向けて誘導される。このフィルタは、異なる材料につき同じ挙動のより多くのタスクが適格である場合に、材料番号が最低のタスクを選択するｉｎｃｒｍａｔｎｒフィルタである。このフィルタを使用できるのは、全ての基板が同じロジスティック経路を辿り、基板番号が少ない方からリソグラフィ装置に入るからである。ｉｎｃｒｍａｔｎｒフィルタの唯一のフィルタパラメータは、フィルタを適用しなければならない挙動を含むリストである。このフィルタを全挙動に適用すると、基板が相互に追い越すことができず、基板番号が小さい方からシステムを出ることが保証され、これはＦＩＦＯの順序を意味する。この発見的フィルタ構成をスケジューラに使用すると、（１ショットスケジュール作成を使用して）生成されたヒープは、実際にＦＩＦＯである。基板番号を有するこのスケジュールのガントチャートを、図３５に示す。スケジュールはなお露光（全てクリティカルパス上にある）に関して最適であり、スケジュールの合計時間は、以前に発見されたスケジュールと比較して増加していない。つまり、このスケジュールの方が優れている。
【０２１９】
最終の実験は、露光後ベーク（ＰＥＢ）時間のばらつきを平坦にする実施形態に関する。タイミングポストプロセッサツールを適用し、重み関数の微調整後に、ＰＥＢ時間の機械の流れのばらつきをゼロに減少させる。ＰＥＢ時間のばらつきを平坦にしたＦＩＦＯスケジュールのガントチャートを、図３６で示し、ここでは（基板テーブル０の）第二露光を遅延させる（その結果、スケジュールにギャップが生じる）。図３７は、非ＦＩＦＯスケジュール（Ｉ）、ＰＥＢ平坦化を含まないＦＩＦＯスケジュール（ＩＩ）、およびＰＥＢ平坦化を含むＦＩＦＯスケジュール（ＩＩＩ）の各基板のＰＥＢ時間を示す。ＦＩＦＯスケジュールは、非ＦＩＦＯスケジュールと比較して、ＰＥＢ時間のばらつきに妥当な改善を示すが、これはゼロではなく、これはタイミング後処理を使用することによって達成される。
【０２２０】
スケジュール作成の確認
上述したスケジュールは、デッドロックまたは衝突のような望ましくない状況を引き起こすようなスケジュールまたは部分スケジュールの作成を回避するため、発見法を使用する。これらの発見法は、適正に機能するよう適切なパラメータ化することが望ましい。このような確認は、スケジューラを構成する、つまりそのパラメータを設定する「設計時間」に実行するだけでよい。
【０２２１】
上述したスケジューラのような、モデルに基づく問題を確認する従来のアプローチは、そのシステムまたはモデルで可能なそれぞれの状態を考察し、その結果として望ましくない状態になるかチェックすることである（状態スペース探査）。これを自動的に実行するために、様々なソフトウェアのモデルチェッカが存在する。しかし、リソグラフィ装置またはリソセルなどの複合機械では、可能な機械の状態数が、設計時でも既知のモデルチェッカで確認するには多すぎる。
【０２２２】
したがって、本発明のこの実施形態では、モデルチェッカによって考察する必要がある状態の数を減少させるために、幾つかのアプローチをとる。
【０２２３】
全ての可能な状態、つまりシステムの定義によって定義されるような装置の物理的に実行可能な挙動の完全なツリー内で、スケジューラのデッドロック回避規則などによって決定され、有効挙動を表す状態のセットが減少する。有効挙動のツリー内では、良好な挙動または好ましい挙動を表すツリーがさらに減少する。設計時に、有効挙動のツリー内で全ての状態をチェックし、これがデッドロックなどの望ましく状況であるか、またはそれにつながるかを決定することが望ましい。そうでない場合、スケジューラは、実行時に望ましくない状況で終了するスケジュールも作成しない。
【０２２４】
この確認のために必要な処理をさらに減少させるために、状態スペースの探査中に省略できる状態を識別することが必要である。そのための幾つかのアプローチは、以下の通りである。
【０２２５】
タスクＡに続く２つ（以上）のタスクＢおよびＣを並列に実行できる場合、状態スペース探査では、最初に本文するのがＢかＣかは問題ではない（τ合流点を有するタスク）。したがって、パスされた状態（ｔｐ）に関する状態を考察すると、
ｔｐ：｛Ａ｝
ｔｐ：｛Ａ，Ｂ｝
ｔｐ：｛Ａ，Ｂ，Ｃ｝
の状態のみを考察し、
ｔｐ：｛Ａ，Ｃ｝
の状態を考察する必要がない。省略できる状態の数が、３つ以上のタスクを並列で実行する場合に急速に増加することは明白である。この減少は、状態スペース探査中にこのようなτ合流点を有するタスクに優先権を与えることによって、実行することができる。
【０２２６】
装置が基板テーブル、ロードロック、エレベータなどの同じ機能の複数の資源を含む場合、スケジュールをそれに反映することができる。したがって後続タスクＡ、タスクＢを基板テーブル１または基板テーブル２で実行できる場合は、これをテーブルの一方で実行することにより生成した状態をチェックするだけでよい。
【０２２７】
非ロジスティックタスク、つまりデッドロックまたはＦＩＦＯ条件などのモデルチェッカで確認すべき特性に影響を及ぼさないタスクは、省略してよい。このようなタスクの例は、測定および露光タスクである。というのは、全ての材料がその時に同じ資源に残るからである。この減少、および資源の対称性の低下は、ハッシュ関数によって実行することができる。
【０２２８】
このような状態スペース減少技術を使用して、状態スペースの爆発をもたらす組み合わせ効果を減少させることができ、したがって実際的なケースをなお確認することができる。
【０２２９】
以上、本発明の特定の実施形態を説明したが、説明とは異なる方法でも本発明を実践できることが理解される。本説明は本発明を制限する意図ではない。
【図面の簡単な説明】
【０２３０】
【図１】本発明の実施形態によるリソグラフィ装置を示したものである。
【図２】本発明の実施形態によるリソグラフィ処理セルを示したものである。
【図３】図１のリソグラフィ装置の制御システムを示したものである。
【図４】タスク資源システム（ＴＲＳ）の定義レベルを示したものである。
【図４ａ】ＴＲＳ定義レベル１および２のＵＭＬクラス図表である。
【図４ｂ】ＴＲＳ定義レベル１および２のＵＭＬクラス図表である。
【図５】本発明の実施形態による方法の流れ図である。
【図６】本発明の実施形態による装置のマスク取り扱い構成と、装置によって実行できる特定のタスクを示したものである。
【図７】本発明の実施形態による方法で作成した例示的タスクスケジュールのガントチャートである。
【図８】図７の例示的スケジュールのクリティカルパスを示すガントチャートである。
【図９】本発明の実施形態による方法で作成した第二の例示的タスクスケジュールのガントチャートである。
【図１０】図９の例示的スケジュールのクリティカルパスを示すガントチャートである。
【図１１】本発明の実施形態による装置の基板取り扱い構成を示したものであり、可能な資源競合の区域を示す。
【図１２】様々な資源オートマトン（オートメーション)を示したものである。
【図１３】様々な資源オートマトンを示したものである。
【図１４】様々な資源オートマトンを示したものである。
【図１５】様々な資源オートマトンを示したものである。
【図１６】様々な資源オートマトンを示したものである。
【図１７】基板の寿命におけるタスクのシークエンスを示したものである。
【図１８】設定タスクを省略した基板寿命におけるタスクのシークエンスを示したものである。
【図１９】移送タスクおよび材料占有タスクを示したものである。
【図２０】図１１と同様の図であり、可能なデッドロックも示す。
【図２１】本発明の実施形態による方法で作成した第三の例示的タスクスケジュールのガントチャートである。
【図２２】図２１の例示的スケジュールのクリティカルパスを示すガントチャートである。
【図２３】本発明の特定の実施形態による基板取り扱い構成を示したものである。
【図２４】本発明の特定の実施形態の資源のオートマトンである。
【図２５】本発明の特定の実施形態の資源のオートマトンである。
【図２６】本発明の特定の実施形態の資源のオートマトンである。
【図２７】本発明の特定の実施形態の資源のオートマトンである。
【図２８】３つの基板の寿命におけるタスクのシークエンスを示したものである。
【図２９】可能なデッドロック状況を示す、特定の実施形態の基板取り扱い構成の図表である。
【図３０】可能なデッドロック状況を示す、特定の実施形態の基板取り扱い構成の図表である。
【図３１】可能なデッドロック状況を示す、特定の実施形態の基板取り扱い構成の図表である。
【図３２】可能なデッドロック状況を示す、特定の実施形態の基板取り扱い構成の図表である。
【図３３】本発明の実施形態による方法で作成した第四の例示的タスクスケジュールのガントチャートである。
【図３４】図３３の例示的スケジュールのクリティカルパスを示すガントチャートである。
【図３５】本発明の実施形態による方法で作成した第五の例示的タスクスケジュールのガントチャートである。
【図３６】本発明の実施形態による方法で作成した第六の例示的タスクスケジュールのガントチャートである。
【図３７】図３３、図３５および図３６のスケジュールの露光後ベーク時間を示すグラフである。
【図１】
2005191571.tif 000092
【図２】
2005191571.tif 000093
【図３】
2005191571.tif 000094
【図４】
2005191571.tif 000095
【図４ａ】
2005191571.tif 000096
【図４ｂ】
2005191571.tif 000097
【図５】
2005191571.tif 000098
【図６】
2005191571.tif 000099
【図１１】
2005191571.tif 000100
【図１２】
2005191571.tif 000101
【図１３】
2005191571.tif 000102
【図１４】
2005191571.tif 000103
【図１５】
2005191571.tif 000104
【図１６】
2005191571.tif 000105
【図１７】
2005191571.tif 000106
【図１８】
2005191571.tif 000107
【図１９】
2005191571.tif 000108
【図２０】
2005191571.tif 000109
【図２３】
2005191571.tif 000110
【図２４】
2005191571.tif 000111
【図２５】
2005191571.tif 000112
【図２６】
2005191571.tif 000113
【図２７】
2005191571.tif 000114
【図２８】
2005191571.tif 000115
【図２９】
2005191571.tif 000116
【図３０】
2005191571.tif 000117
【図３１】
2005191571.tif 000118
【図３２】
2005191571.tif 000119
【図３７】
2005191571.tif 000120
【図７】
2005191571.tif 000121
【図８】
2005191571.tif 000122
【図９】
2005191571.tif 000123
【図１０】
2005191571.tif 000124
【図２１】
2005191571.tif 000125
【図２２】
2005191571.tif 000126
【図３３】
2005191571.tif 000127
【図３４】
2005191571.tif 000128
【図３５】
2005191571.tif 000129
【図３６】
2005191571.tif 000130
【外国語明細書】
2005191571000001.pdf