(57)【要約】【課題】  成功率も考慮してスケジューリングを最適化する技術を提供する。【解決手段】  クラスタツール用のスケジューリングを管理する管理方法は、ａ）処理チャンバ間のウエハの移動を定義するスケジューリングアルゴリズムを選択するステップと、ｂ）処理チャンバの成功率を定義するステップと、ｃ）処理チャンバの成功率を考慮して選択したスケジューリングアルゴリズムを実行してクラスタツール内のウエハを位置付けるシミュレーションを実行するステップと、ｄ）選択したスケジューリングアルゴリズムでシミュレーション結果を生成するステップと、ｅ）スケジューリングアルゴリズムを変更するステップと、ｆ）（ａ）から（ｅ）ステップを繰り返して得られた複数のシミュレーション結果を比較して、所定の基準を達成するスケジューリングアルゴリズムを選定するステップと、を備える。【選択図】図４
2009158736.tif 000002
【特許請求の範囲】
【請求項１】
ウエハを処理するための複数の処理チャンバと、前記処理チャンバ間で前記ウエハを運搬するためのウエハ運搬装置と、を含むクラスタツールの偶発的要素によりその挙動が左右されるような確率的生産システムにおけるスケジューリングを管理する管理方法であって、
ａ）  前記処理チャンバへのウエハ投入順序（ジョブ）を規定するステップと、
ｂ）  前記処理チャンバの成功率を定義するステップと、
を備えるスケジューリングの管理方法。
【請求項２】
前記ウエハ運搬装置の使用に関する前記複数の処理チャンバ間のコンフリクトを排除するように前記スケジューリングを選定することを特徴とする請求項１に記載のスケジューリングを管理する管理方法。
【請求項３】
前記スケジューリングを管理する手法として，シミュレーションに基づく最適化手法を適用する管理方法。
【請求項４】
前記シミュレーションに基づく最適化手法において，すべてのジョブが終了するまでの時間（メイクスパン）を最小にするジョブの投入順序と検査の計画を確定するスケジューリングの管理方法。
【請求項５】
前記シミュレーションによる最適化方法として，サンプルパス最適化を用いた解法を利用し，シミュレーションに用いられる乱数系列（サンプル）を固定し，確率的な最適問題を確定的な最適化問題に変換することによってなされるスケジューリングの管理方法。
【請求項６】
前記最適化問題において，最適解はタブーサーチによって近似的に求めることで解決するスケジューリングの管理方法。
【請求項７】
さらに、ｃ）  前記途中に検査工程を加えるかの可否を決定するステップ
を備える請求項１に記載のスケジューリングの管理方法。
【請求項８】
ウエハを処理するための複数の処理チャンバと、前記処理チャンバ間で前記ウエハを運搬するためのウエハ運搬装置と、を含むクラスタツール用のスケジューリングを管理する管理方法であって、
ａ）  前記処理チャンバ間のウエハの移動を定義するスケジューリングアルゴリズムを選択するステップと、
ｂ）  前記処理チャンバの成功率を定義するステップと、
ｃ）  前記処理チャンバの成功率を考慮して前記選択したスケジューリングアルゴリズムを実行して前記クラスタツール内のウエハを位置付けるシミュレーションを実行するステップと、
ｄ）  前記選択したスケジューリングアルゴリズムで前記シミュレーション結果を生成するステップと、
ｅ）  前記スケジューリングアルゴリズムを変更するステップと、
ｆ）  （ａ）から（ｅ）ステップを繰り返して得られた複数のシミュレーション結果を比較して、所定の基準を達成するスケジューリングアルゴリズムを選定するステップと、
を備えるクラスタツール用のスケジューリングを管理する管理方法。
【請求項９】
前記ウエハ運搬装置の使用に関する前記複数の処理チャンバ間のコンフリクトを排除するように前記スケジューリングアルゴリズムを選定することを特徴とする請求項８に記載のスケジューリングを管理する管理方法。
【請求項１０】
ウエハを処理するための複数の処理チャンバと、前記処理チャンバ間で前記ウエハを運搬するためのウエハ運搬装置と、前記処理チャンバで処理されたウエハを検査する検査装置と、を含むクラスタツール用のスケジューリングを管理する管理方法であって、
ａ）  前記処理チャンバ間のウエハ移動を定義するスケジューリングアルゴリズムを選択するステップと、
ｂ）  前記選択したスケジューリングアルゴリズムを実行して前記クラスタツール内のウエハを位置付けるシミュレーションを実行するステップと、
ｄ）  前記選択したスケジューリングアルゴリズムで前記シミュレーション結果を生成するステップと、
ｄ）  前記スケジューリングアルゴリズムを変更するステップと、
ｅ）  （ａ）から（ｄ）ステップを繰り返して得られた複数のシミュレーション結果を比較して、所定の基準を達成するスケジューリングアルゴリズムを選定するステップと、
ｆ）  選定されたスケジューリングアルゴリズムによって前記検査装置が前記ウエハを検査する待ち時間が生じた際に、前記検査装置が前記ウエハを検査するステップと、
を備えるクラスタツール用のスケジューリングを管理する管理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はウエハ処理の分野に関し、特に、ウエハ・クラスタツールのスケジューリング技術に関する。
【背景技術】
【０００２】
半導体素子の高精度化及び高密度化が進み、複数のウエハを同時に処理するバッチ処理から一枚一枚をレシピに応じて処理する枚葉式処理に変わりつつある。このため、１台の処理装置がウエハのクラスタツール（処理モジュールとも呼ばれる）を複数有するシステムや、ある機能を持った複数の処理装置と別の機能を持った複数の処理装置とを連動させるシステムが登場している。
【０００３】
このようなシステム内において、ウエハをクラスタツールへ供給及び排出する際には、半導体素子の生産性を上げるため供給及び排出時間を最短で行う必要がある。すなわち、クラスタツール内でウエハが処理される時間、あるクラスタツールから別のクラスタツールへの搬送ロボットの搬送時間などを総合的に短時間で処理しなければならない。枚葉式処理が主流となるとクラスタツールが複数に増え、作業者が最適なウエハ処理のスケジューリングを作成することは困難になっている。
【０００４】
特許文献１は、ウエハをどのような順番で処理していけばよいかのスケジューリングを遺伝的アルゴリズムなどの最適化手法を使って求めている。つまり、連続的にウエハをクラスタツールに入れることで何等の遅延も被ることがないようなスケジューリングを最適化手法で求めている。
【特許文献１】特開２００７−２１４５５０
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、特許文献１は、クラスタツールがウエハをすべて問題なく処理することを前提に最適なスケジューリングを求めているだけである。現実にはすべてのクラスタツールでの成功率が１００パーセントということはありえない。例えば、あるクラスタツールにおいては成功率９９パーセント（又は不良率１パーセント）であるため、不良となったウエハに対して下流のクラスタツールに搬送する必要がない場合が生じたりする。このように成功率を考慮しないでスケジューリングを最適化しても現実的ではなく、また生産性を大幅に向上させることにはならない。
【０００６】
また、実際のウエハ処理工程では、ウエハ処理工程の途中で抜き取り検査などをすることがある。このような定期的ではないがときどきウエハ検査をすることも考慮してスケジューリングを最適化することが必要である。
【０００７】
本発明は、このような事情に基づいてなされたものであり、その目的は、複数のクラスタツールにおける成功率も考慮してスケジューリングを最適化する技術を提供することである。また、ウエハを抜き取り検査する場合においてスケジューリングを最適化する技術を提供することである。
【課題を解決するための手段】
【０００８】
第１の観点のスケジューリングの管理方法は、ウエハを処理するための複数の処理チャンバと、処理チャンバ間でウエハを運搬するためのウエハ運搬装置と、を含むクラスタツールの偶発的要素によりその挙動が左右されるような確率的生産システムにおけるスケジューリングを管理する管理方法である。そして、管理方法はａ）  処理チャンバへのウエハ投入順序（ジョブ）を規定するステップと、ｂ）  処理チャンバの成功率を定義するステップと、を備える。
この構成により、成功率（又は不良率）を考慮して、複数の処理チャンバのメイクスパンの平均値を最小化するので、より実際の工程に近い精度の良い近似最適解が得られる。
【０００９】
第２の観点のスケジューリングの管理方法は、ウエハを処理するための複数の処理チャンバと、処理チャンバ間でウエハを運搬するためのウエハ運搬装置と、を含むクラスタツール用のスケジューリングを管理する管理方法である。そして、管理方法は、ａ）  処理チャンバ間のウエハの移動を定義するスケジューリングアルゴリズムを選択するステップと、ｂ）  処理チャンバの成功率を定義するステップと、ｃ）  処理チャンバの成功率を考慮して選択したスケジューリングアルゴリズムを実行してクラスタツール内のウエハを位置付けるシミュレーションを実行するステップと、ｄ）  選択したスケジューリングアルゴリズムでシミュレーション結果を生成するステップと、ｅ）  スケジューリングアルゴリズムを変更するステップと、ｆ）  （ａ）から（ｅ）ステップを繰り返して得られた複数のシミュレーション結果を比較して、所定の基準を達成するスケジューリングアルゴリズムを選定するステップと、を備える。
この構成により、成功率（又は不良率）を考慮して、複数の処理チャンバのメイクスパンの平均値を最小化する。
【００１０】
第３の観点のスケジューリングの管理方法は、ウエハを処理するための複数の処理チャンバと、処理チャンバ間でウエハを運搬するためのウエハ運搬装置と、処理チャンバで処理されたウエハを検査する検査装置と、を含むクラスタツール用のスケジューリングを管理する管理方法である。そして、管理方法は、ａ）  処理チャンバ間のウエハ移動を定義するスケジューリングアルゴリズムを選択するステップと、ｂ）  選択したスケジューリングアルゴリズムを実行してクラスタツール内のウエハを位置付けるシミュレーションを実行するステップと、ｄ）  選択したスケジューリングアルゴリズムでシミュレーション結果を生成するステップと、ｄ）  スケジューリングアルゴリズムを変更するステップと、
ｅ）  （ａ）から（ｄ）ステップを繰り返して得られた複数のシミュレーション結果を比較して、所定の基準を達成するスケジューリングアルゴリズムを選定するステップと、ｆ）  選定されたスケジューリングアルゴリズムによって検査装置がウエハを検査する待ち時間が生じた際に、検査装置がウエハを検査するステップと、を備える。
この構成により、複数の処理チャンバのメイクスパンの平均値を最小化しても処理チャンバが処理を行わない空いた時間に、検査装置がウエハを検査することができる。
【発明の効果】
【００１１】
本発明のスケジューリングは、ジョブレシピに対してサンプルパス最適化とタブーサーチを加えることで、１７００秒以上の生産時間短縮が可能となり、また時間を有効に活用して検査工程をも付加しており、半導体の生産コスト削減に大きく寄与することができる。
なお、タブーサーチとは、組合せ最適化問題において局所探索が局所最適解で終了してしまうことを防ぐために、暫定解が改悪されてしまうような解への移行を許し、また同じ領域を繰り返し探索することを防ぐためにこれまでの移行の履歴に基づいたタブーと呼ばれる制約を設け、より大域的な探索を行えるようにした手法である。
【発明を実施するための最良の形態】
【００１２】
図１は複数のチャンバを持つクラスタツール１００である。各チャンバの工程はそれぞれ処理時間が異なる。クラスタツールの処理時間は処理能力の遅いチャンバに左右されることになる。このため処理能力の遅いチャンバの数を増やしたり、別のクラスタツールを追加したりすることで、クラスタツールは処理能力の向上を図っている。
【００１３】
複数のチャンバを持つクラスタツール１００として、本実施形態では少なくとも２枚の半導体ウエハ同士を重ね合わせて１枚の接合した半導体ウエハを製造する加圧装置を例に挙げる。例えば加圧加熱の工程Ｐｒ４に処理時間がかかるため３箇所の処理チャンバＣＢ４を設置し、冷却工程Ｐｒ５に対して２箇所のチャンバＣＢ５を設置している。
【００１４】
クラスタツール１００は２台のウエハローダーＷＬを配置している。ウエハローダーＷＬは主制御装置９０の指示に従い、ウエハ（第１ウエハ及び第２ウエハを含む）又はウエハホルダ（第１ウエハホルダ及び第２ウエハホルダを含む）を各チャンバに搬送する。ウエハローダーＷＬはレールＲＡに沿って自走することができる。ウエハローダーＷＬがあるチャンバから別のチャンバにウエハ又はウエハホルダを搬送する時間はそれぞれ異なる。図１では２台のウエハローダーＷＬを配置しているが、１台のみ配置したり３台以上のウエハローダーＷＬを配置したりしてもよい。
【００１５】
クラスタツール１００の各工程は次のとおりである。チャンバＣＢ０は、例えば第１ウエハと第１ウエハホルダとをプリアライメントの工程Ｐｒ０であり、チャンバＣＢ１は第２ウエハと第２ウエハホルダとをプリアライメントの工程Ｐｒ１である。チャンバＣＢ２は第１ウエハホルダに載置された第１ウエハに対して第２ウエハホルダに載置された第２ウエハを精密に位置合わせする工程Ｐｒ２である。チャンバＣＢ３は位置合わせした２枚のホルダとウエハとを固定する固定工程Ｐｒ３である。
【００１６】
また、チャンバＣＢ４は固定処理したウエハを加圧加熱して結合する加圧加熱の工程Ｐｒ４する工程である。加圧加熱工程Ｐｒ４は時間的に律速なため、本実施形態では３箇所のチャンバＣＢ４を設置している。チャンバＣＢ５は加圧加熱処理された２枚のウエハを冷却する冷却工程Ｐｒ５である。チャンバＣＢ６は抜き取り検査を行う抜き取り検査工程Ｐｒ６である。抜き取り検査工程Ｐｒ６は固定工程Ｐｒ３、加圧加熱工程Ｐｒ４、又は冷却工程Ｐｒ５を終えたウエハに対して顕微鏡などで第１ウエハと第２ウエハとの位置ズレなどの検査を行うことができる。チャンバＣＢ７はウエハとウエハホルダとを分離する分離工程Ｐｒ７である。
【００１７】
クラスタツール１００は上記の工程を主制御部９０で制御している。複数の並行処理を含むクラスタツール１００のスケジューリングは多岐にわたるため、より効率的なスケジューリングを求める必要がある。本発明の主制御装置９０は成功率が変動した場合においても、主制御装置９０が最適な工程を求め直し、効率的な工程をとるよう最適化する。
【００１８】
以下に、主制御装置９０のスケジューリングの実施例を示す。主制御部９０は各工程を監視し、最適なスケジューリングに沿って制御している。
図２は主制御部９０の主な構成を示すものである。
【００１９】
クラスタツール制御部９５はシミュレーション部９３からの最適な工程情報を得ることでクラスタツールを制御する。また、処理工程監視部９４は各処理部における処理時間又は故障状態などを監視する。成功率設定部９１は処理工程監視部９３からの情報を元に設定される。また、成功率設定は操作者が任意で成功率設定部９１に対して入力することもできる。処理工程設定部９２は工程の設定や実際にかかった処理時間を処理工程監視部９４から得ることで設定される。シミュレーション部９３は成功率設定部９１と処理工程設定部９２との情報から、複数のスケジューリングアルゴリズムを計算し最適なスケジューリングを探し、決定する。
【００２０】
例えば、複数設置してある加圧加熱工程Ｐｒ４のチャンバＣＢ４の１台の故障で処理能力が落ちたり停止したりしても、主制御部９０は自動的に最適なスケジューリングを探すことができる。つまり、主制御部９０は常に最適なスケジューリングを提供することができる。
【００２１】
＜＜実施例１＞＞
図３はクラスタツール１００の各工程の処理順序を図示したものである。処理工程設定部９２は、プリアライメントの工程Ｐｒ０及びプリアライメントの工程Ｐｒ１の次に位置合わせする工程Ｐｒ２を経て固定工程Ｐｒ３を経るように工程設定している。さらに、処理工程設定部９２は、固定工程Ｐｒ３の次に加圧加熱工程Ｐｒ４と冷却工程Ｐｒ５とを経て分離工程Ｐｒ７に進むように工程設定する。
【００２２】
図３の各工程に示された（）内の数字は、所定の状態における各工程の成功率を示している。例えば固定工程Ｐｒ３の（Ｓ＝０．８５）は、固定工程Ｐｒ３において成功率が現時点で８５パーセントであることを意味し、冷却工程Ｐｒ５の（Ｓ＝０．９９）は冷却工程Ｐｒ５において成功率が現時点９９パーセントであることを意味する。なお、図３ではウエハローダーＷＬの搬送時の成功率も加味して各工程の成功率を例示している。成功率の初期設定は経験値に基づいて入力され、その後実際の成功率（又は不良率）から順次更新される。
【００２３】
図４は成功率が変動する場合においてのシミュレーション部９３のフローチャートである。以下、制御を簡単に説明するためにウエハローダーＷＬなどの移動手段の制御については述べない。
【００２４】
ステップ１において、シミュレーション部９３は所定のスケジューリングアルゴリズムを選択する。
ステップ２において、シミュレーション部９３は成功率設定部９１に入力された情報とステップ３において処理工程設定部９２に入力された情報とを取得する。成功率設定部９１と工程設定部９２とは工程監視部９４から入る成功率、及び処理時間を常に最新な値にする。
【００２５】
ステップ４において、シミュレーション部９３は選択されたスケジューリングアルゴリズムを用いてシミュレーションを行い、ステップ５において、複数のシミュレーション結果を表示する。
【００２６】
ステップ６において、シミュレーション部９３は所定の基準を満たす結果が得られたかを判断し、満たしていなければステップ７に移りスケジューリングアルゴリズムの変更を行う。所定の基準を満たしていれば、ステップ８に移りシミュレーション結果の比較を行う。
【００２７】
ステップ７では、スケジューリングアルゴリズムの変更を行うが、スケジューリングアルゴリズムにはタブーサーチ法、サンプルパス最適化法とタブーサーチ法とを組み合わせる方法を用いてシミュレーションする。
【００２８】
ステップ８において、シミュレーション部９３は最適なスケジューリングを選択する。
ステップ９において、処理工程監視部９４からの故障情報があるか無いか（成功率が変動したか否か）を判断する。故障情報があるとステップ１に戻りシミュレーションをやり直し、スケジューリングの最適化をする。故障が無ければ、シミュレーション部９３はスケジューリングをクラスタツール制御部９５に入力する。
【００２９】
＜実施例２＞
図５は抜き取り検査工程Ｐｒ６を含むクラスタツール１００の各工程の処理順序を図示したものである。
実施例１では装置トラブルなどの成功率を考慮してスケジューリングを行う場合を示した。実施例２ではウエハの位置合わせ検査などの抜き取り検査工程Ｐｒ６を行う。抜き取り検査工程Ｐｒ６はできるだけ生産性を落とすことなく処理することが望まれる。本実施例は最適化したスケジューリングにおいても、各工程間に余裕時間が発生することがある。シミュレーション部９３はこの余裕時間を利用して抜き取り検査工程Ｐｒ６を挿入し最適なスケジューリングを計画する。
【００３０】
抜き取り検査工程Ｐｒ６を行う処理順序は図５の点線で示すように、固定工程Ｐｒ３、加圧加熱工程Ｐｒ４、又は冷却工程Ｐｒ５の後に実施することができる。例えば抜き取り検査工程Ｐｒ６は、顕微鏡などで第１ウエハと第２ウエハとの位置ズレを測定する検査である。ただし加圧加熱工程Ｐｒ４の後にはウエハ冷却の時間が必要となる。
【００３１】
＜スケジューリングアリゴリズム＞
スケジューリングで用いるスケジューリングアルゴリズムはメタヒューリスティクスな手法をとることで最適なスケジューリングを求めることができる。メタヒューリスティクスな手法は、例えばタブーサーチなどの手法を用いることでスケジューリングの最適化を求める。また、メタヒューリスティクスな手法にサンプルパス最適化法を加えることで、さらに最適化することができる。以下にその具体例を示す。
【００３２】
まず、生産システムでの作業（ジョブ）において，途中検査を任意に行う系についての問題の定式化をおこなう。
【００３３】
ｎ個のジョブの集合をＪ＝｛１，２，・・・，ｎ｝とし、生産システムの決定変数をσおよびｘとする。ただし、σはｎ個のジョブの順列を表す変数で，σ＝（σ１・・・，σｎ）：Ｊ→Ｊである。また、ｘ＝（ｘ１，・・・，ｘｎ），ｘｉ∈｛０，１｝（ｉ＝１，・・・，ｎ）とし、ｘｉ＝１はｉ番目に投入したジョブの検査を実施することを表し，ｘｉ＝０は検査を実施しないことを表す。さらに、ωをｎ個のジョブが良品か不良品かを決定する乱数系列（サンプル）とし，ｋ番目に選択した乱数系列をωｋとする。また、ｆ（ωｋ；σ，ｘ）をジョブの投入順序をσ、検査の計画をｘとしたときの乱数系列ωｋにおけるメイクスパン（すべてのジョブが終了するまでの時間）とする。乱数系列ωｋを選択するとｆ（ωｋ；σ，ｘ）は一意に定まり，簡単な計算によって求めることができる。このとき，メイクスパンの期待値は（数式０１）のように表現できる。
【数０１】
2009158736.tif 000003
…数式０１
【００３４】
したがって，このスケジューリング問題は（数式０２）に示すような最適化問題に
なる。
【数０２】
2009158736.tif 000004
…数式０２
ここで、Ｓｎは１からｎのｎ次対称郡であり、簡単のため以降Ｓ＝Ｓｎ×｛（０，１）ｎ｝と表す。
【００３５】
次に，サンプルパス最適化を行う．
一般に，Ｆ（σ，ｘ）を求めるのは困難であるが，サンプルパス最適化では，この関数を固定した乱数系列のもとでのシミュレーションによって近似することを考える。すなわち、（数式０３）とおけば（数式０４）であるので，十分大きなＮに対して問題（ＰＮ）の最適解が問題（Ｐ）の近似最適解となる。問題（ＰＮ）は（数式０５）で示す。
【数０３】
2009158736.tif 000005
…数式０３
【数０４】
2009158736.tif 000006
…数式０４
【数０５】
2009158736.tif 000007
…数式０５
【００３６】
実際、以下の定理が成り立つ。
定理1
問題（ＰＮ）および（Ｐ）の最適解の集合を，それぞれｏｐｔ（ＰＮ）およびｏｐｔ（Ｐ）とおく。Ｓの要素数が有限個で（数式０６）および（数式０４）が成り立つとき、ある整数（数式０７）が存在し、すべての整数（数式０８）に対して（数式０９）が成立する。
【数０６】
2009158736.tif 000008
…数式０６
【数０７】
2009158736.tif 000009
…数式０７
【数０８】
2009158736.tif 000010
…数式０８
【数０９】
2009158736.tif 000011
…数式０９
【００３７】
証明
Ｓの要素数は有限個であるから、（数式１０）を満たす正数σ＊が存在する。また、任意の解（σ，ｘ）∈Ｓに対して（数式１１）および式（数式０４）が成り立つことから、（数式１２）が成立するような、ある整数（数式０７）が存在する，ただし，ε＜δ*／２とする。
【数１０】
2009158736.tif 000012
…数式１０
【数１１】
2009158736.tif 000013
…数式１１
【数１２】
2009158736.tif 000014
…数式１２
ここで、すべての整数（数式０８）を満たす整数（数式０７）と、（数式１３）を満たす（σ，ｘ）に対して、（数式１４）を仮定する。このとき、（数式１５）を満たす（σ＊，ｘ＊）を考えれば、（数式１６）であり，δ*の定義式（数式１０）より、（数式１７）がなりたつ。
【数１３】
2009158736.tif 000015
…数式１３
【数１４】
2009158736.tif 000016
…数式１４
【数１５】
2009158736.tif 000017
…数式１５
【数１６】
2009158736.tif 000018
…数式１６
【数１７】
2009158736.tif 000019
…数式１７
一方（数式１１）から（数式１８）が成り立つ、したがって（数式１２）〜（数式１７）から（数式１９）となる。
【数１８】
2009158736.tif 000020
…数式１８
【数１９】
2009158736.tif 000021
…数式１９
（数式１９）は（数式１４）に矛盾する。したがって、すべての整数（数式０８）を満たすある整数（数式０７）に対して、（数式１３）であれば（数式２０）であり（数式０９）が成り立つ
【数２０】
2009158736.tif 000022
…数式２０
【００３８】
定理1は，乱数系列を固定したもとでの十分多くの回数のシミュレーションの平均から得られる性能評価関数を最適化すれば、真の最適解が得られることを意味する。通常、Ｆ（σ，ｘ）の値を求めるのは困難であるが、乱数系列を固定したもとではＦＮ（σ，ｘ）の値は（数式０３）によって簡単に計算できるので、問題（ＰＮ）は確定的な最適化問題になることに注意する。ただし，（数式１２）が成り立つような、ある整数（数式０７）の具体的な値、すなわち何回のシミュレーションの平均をとれば十分であるかについては，見積もることは一般に難しい。
【００３９】
＜タブーサーチによる最適解の抽出＞
上記より，あるＮに対する確定的な最適化問題（ＰＮ）の最適解は、元の問題（Ｐ）の近似最適解になることがわかる。しかし、問題（ＰＮ）の許容解の数がｎ！×２ｎで非常に大きいことから、問題（ＰＮ）の最適解を厳密に求めることは困難である。そこで、ここでは近傍をもとにしたメタ解法の1つであるタブーサーチを用いる。タブーサーチでは、現在の解（σ，ｘ）の近傍Ｎ（σ，ｘ）の中から、（σ，ｘ）以外で目的関数を最小にする解（σ´，ｘ´）を選択する。しかし、この選択基準だけでは、局所最適解付近において同じ解の選択を繰り返す巡回が生じるので、Ｎ（σ，ｘ）の要素であっても選択できない禁止リストを用いて巡回を防ぐ。
【００４０】
ここでは解（σ，ｘ）の近傍としてジョブの投入順序を1対だけ入れ替えた解と検査の計画を1箇所だけ反転させた解を考える。すなわち（数式２１）とする。
【数２１】
2009158736.tif 000023
…数式２１
【００４１】
また，タブーリストＬを現在の解（σ，ｘ）の1回前に選択された解とする。このとき、タブーサーチのアルゴリズムは、図６のフローチャートになる。
【００４２】
ステップ２０において、乱数系列（ω１，・・・，ωＮ）を作成する。
ステップ２１において、初期解（σ，ｘ）を選び、初期タブーリストをＬ≠０とする。
【００４３】
ステップ２２において、探索領域Ｎ（σ，ｘ）＼（{（σ，ｘ）∪Ｌ}）の要素から、（数式０３）を最小にする解（σ´，ｘ´）を見つける。
【００４４】
ステップ２３において、タブーリストをＬ＝{（σ，ｘ）}とする。（σ，ｘ）＝（σ´，ｘ´）とし現在の解を更新する。
【００４５】
ステップ２４において、停止条件が満たされていれば探索を終了する。そうでなければステップ２２へ戻る。
【００４６】
図５で説明したとおり、まず第１ウエハ及びそれを載置する第１ウエハホルダに対してプリアライメントの工程Ｐｒ０を行い、第２ウエハ及びそれを載置する第２ウエハホルダに対してプリアライメントの工程Ｐｒ１を行う。そして第１ウエハ及び第２ウエハの精密な位置合わせ工程Ｐｒ２を行う。次にウエハは固定工程Ｐｒ３を経た後に加圧加熱工程Ｐｒ４を行う。そして接合したウエハは冷却工程Ｐｒ５に向かう。固定工程Ｐｒ３、加圧加熱工程Ｐｒ４、又は冷却工程Ｐｒ５を終えたウエハは時間的に余裕がある場合に抜き取り検査工程Ｐｒ６に向かう。冷却工程Ｐｒ５を終えたウエハは分離工程Ｐｒ７を行い、クラスタツール１００から搬出される。
【００４７】
図５で示したとおりクラスタツールは全部で７工程からなる処理系のスケジューリング問題である。しかし、ここではプリアライメントの工程Ｐｒ０から固定工程Ｐｒ３までの工程は省略し，固定工程Ｐｒ３より後の工程をスケジューリング問題としてモデル化する。そして結合後のウエハを一つのジョブとして表す。
【００４８】
スケジューリングの目的はメイクスパンの最小化である。決定変数はＰｒ３（固定工程）でｉ番目に処理されるジョブσｉと、そのジョブが検査を先に行うか否かｘｉ∈{０，１}である。
【００４９】
図７は入力データの一例である。次に入力データは図７に示すように定義する。
今回の数値計算実験では，提供されたデータをスケジューリング問題のデータとして加工し利用した。前節までは、Ｊ＝｛１，・・・，ｎ｝となっているが、本節ではＪ＝｛０，・・・，２４｝である。固定工程Ｐｒ３の処理時間は、各ジョブ共通で、２７０秒である。これは１２０秒（一つ目のウエハの処理時間）＋１２０秒（二つ目のウエハの処理時間）＋３０秒（二つのウエハを結合する時間）である。加圧加熱工程Ｐｒ４の処理時間は、図８Ａ（ａ）に示す表のように各ジョブで異なる。冷却工程Ｐｒ５の処理時間は、各ジョブ共通で，６００秒である。抜き取り検査工程Ｐｒ６の処理時間は、各ジョブ共通で、３００秒である。分離工程Ｐｒ７の処理時間は各ジョブ共通で、６０秒である。ただし、サンプルパス最適化で使う乱数系列は１０個である，すなわちＮ＝１０である。乱数系列の生成において不良率は１０％とする。
【００５０】
図８Ａ（ｂ）、図８Ｂ（ｃ）、図８Ｂ（ｄ）に示す表にそれぞれジョブの番号順のスケジュール、タブーサーチのみによるスケジュール、サンプルパス最適化＋タブーサーチによるスケジュールを示す。得られたスケジュールのメイクスパンはそれぞれ
●  ジョブの番号順：２５８９０秒
●  タブーサーチのみ：２４９００秒
●  サンプルパス最適化＋タブーサーチ：２４１８０秒
である。
【００５１】
計算時間は，単純なタブーサーチで３秒程度、サンプルパス最適化＋タブーサーチで３０秒程度である。実験には市販のパソコンを用いた。表の１列目のｉはジョブが固定工程Ｐｒ３で処理される順番を表し、２列目のσｉはその順番で処理されるジョブを表し、３列目のｘｉはそのジョブが先に検査されるか否かを表している。３列目ｘｉは先に検査すれば１、そうでなければ０である。１列目から３列目までは問題の解を表している。４列目以降は各工程での各ジョブの開始時刻と終了時刻とを表している。各ジョブの開始時刻と終了時刻とは３列目までの解と故障があるか否かによって自動的に決まる。表で「−」と表示しているところは、先の検査の結果で故障が見つかり、それ以降の処理をしないことを表している。
【００５２】
評価に使った乱数系列の生成において不良率は１０％とした。これはサンプルパス最適化で使った乱数系列の生成に使った不良率と同じである。評価に使った乱数系列（故障するか否か）そのものは、サンプルパス最適化で使った乱数系列とは異なるものである。これは、サンプルパス最適化で使った乱数系列を評価でも使うと、サンプルパス最適化に有利な評価になってしまうためである。
【００５３】
サンプルパス最適化とタブーサーチなどのヒューリスティックを組み合わせることで，ヒューリスティック単体では対応しづらい確率的入力にも対応できる。サンプルパス最適化と組み合わせるヒューリスティクスとしてタブーサーチを選んだのは、タブーサーチはほかのヒューリスティクスに比べ、短い時間でよい解を出すという特徴があるからである。本実施例では、解くべき問題のサイズが比較的小さくかつ高速な求解が要求されるためタブーサーチが適切である。サンプルパス最適化とタブーサーチとを組み合わせた特徴は、成功率（又は不良率）を考えたことにある。本実施例は生産途中で不良品がでるという確率的なシステムである。不良の発生は一般的な確定的な事象でないため、サンプルパス最適化が必要となる．具体的にはサンプルパス最適化により確定的な問題にして解決している。
【図面の簡単な説明】
【００５４】
【図１】複数のチャンバを持つクラスタツール１００である。
【図２】主制御部９０の主な構成を示すものである。
【図３】クラスタツール１００の各工程の処理順序を図示したものである。（実施例１）
【図４】成功率が変動する場合においてのシミュレーション部９３のフローチャートである。
【図５】抜き取り検査工程Ｐｒ６を含むクラスタツール１００の各工程の処理順序を図示したものである。（実施例２）
【図６】タブーサーチのアルゴリズムを示したフローチャートである。
【図７】入力データの一例である。
【図８Ａ】（ａ）は、加圧加熱工程Ｐｒ４の処理時間を示した表である。  （ｂ）は、ジョブの番号順にスケジュールを行った場合にかかるメイクスパンである。
【図８Ｂ】（ｃ）は、タブーサーチのみによるスケジュールを行った場合にかかるメイクスパンである。  （ｄ）は、サンプルパス最適化＋タブーサーチによるスケジュールを行った場合にかかるメイクスパンである。
【符号の説明】
【００５５】
９０  …  制御装置
９１  …  成功率設定部
９２  …  処理工程設定部
９３  …  シミュレーション部
９４  …  処理工程監視部
９５  …  クラスタツール制御部
１００  …  クラスタツール
Ｐｒ０  …  第１ウエハのプリアライメントの工程
Ｐｒ１  …  第２ウエハのプリアライメントの工程
Ｐｒ２  …  位置合わせする工程
Ｐｒ３  …  固定工程
Ｐｒ４  …  加圧加熱工程
Ｐｒ５  …  冷却工程
Ｐｒ６  …  抜き取り検査工程
Ｐｒ７  …  分離工程
【図１】
2009158736.tif 000024
【図２】
2009158736.tif 000025
【図３】
2009158736.tif 000026
【図４】
2009158736.tif 000027
【図５】
2009158736.tif 000028
【図６】
2009158736.tif 000029
【図７】
2009158736.tif 000030
【図８Ａ】
2009158736.tif 000031
【図８Ｂ】
2009158736.tif 000032