(57)【要約】要約書なし。【特許請求の範囲】
【請求項１】
アセンブリのための部品を配置するのに使用される１つまたはそれ以上の部品配置装置を有する生産ラインの設定を決定することに使用される方法であって、所定の部品配置装置のタイプのための少なくとも１つの装置最適化モジュールを持つモジュール最適化装置を使用して上記設定が決定され、上記少なくとも１つの装置最適化モジュールが上記モジュール最適化装置に関連しており、上記方法が：
上記モジュール最適化装置と異質の部品配置装置タイプと関連した少なくとも１つの異質最適化モジュールのための出力値を見積もるステップ；および
上記生産ラインの設定を決定するために上記モジュール最適化装置において上記見積もられた出力値を使用するステップ；
を含むことを特徴とする方法。
【請求項２】
上記少なくとも１つの装置最適化モジュールがＦＣＭ装置タイプ用のＦＣＭモジュールを含むことを特徴とする請求項１に記載の方法。
【請求項３】
上記少なくとも１つの装置最適化モジュールがＡＣＭ装置タイプ用のＡＣＭモジュールを含むことを特徴とする請求項１に記載の方法。
【請求項４】
上記異質最適化モジュールの呼び出しを定期的に行い、当該呼び出しの内の所定の１つに関して、上記異質最適化モジュールによって発生させられた出力値であり結果として起こる出力値を上記見積もられた出力値と比較するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項５】
上記異質最適化モジュールが、複数の所定の間隔の各々の間に１回呼び出されることを特徴とする請求項４に記載の方法。
【請求項６】
上記モジュール最適化装置の遺伝子アルゴリズムの再始動に少なくとも部分的に基づいて、上記異質最適化モジュールが、呼び出されることを特徴とする請求項４に記載の方法。
【請求項７】
上記最適化装置の上記遺伝子アルゴリズムの再始動が起こる度に、新たなベスト個体が前の再始動以来見つけられている場合には、上記異質最適化モジュールが呼び出されることを特徴とする請求項６に記載の方法。
【請求項８】
上記モジュール最適化装置の遺伝子アルゴリズムの新たな子孫であって生き残る個体群に入りそうな当該子孫に出会う度に、上記異質最適化モジュールが呼び出されること特徴とする請求項４に記載の方法。
【請求項９】
上記モジュール最適化装置の遺伝子アルゴリズムにおいて潜在的な新しいベスト個体に出会う度に、上記異質最適化モジュールが呼び出されることを特徴とする請求項４に記載の方法。
【請求項１０】
上記異質最適化モジュールが呼び出された時、もし対応する見積もられた値に対する実際の出力値が改善された結果を与えると決定されたならば、引き続いて起こる見積もられた出力値の発生に関連したエラーを減らすために、上記対応する見積もられた出力値を発生させるのに使用された見積もり部の少なくとも１つのパラメータが変更されることを特徴とする請求項４に記載の方法。
【請求項１１】
上記見積もられた出力値が、上記異質の装置タイプの部品配置装置による１つまたはそれ以上の所定の部品の配置に関連した見積もられたサイクル時間を含むことを特徴とする請求項１に記載の方法。
【請求項１２】
上記見積もられた出力値を発生させる見積もり部を、上記異質最適化装置に対して１回またはそれ以上の回数の呼び出しを行うことによって、較正するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項１３】
部品の所定のセットを使用して上記異質最適化モジュールが、１回またはそれ以上の回数呼び出されることを特徴とする請求項１２に記載の方法。
【請求項１４】
上記異質最適化モジュールが、部品の所定のセットの各部品に関して少なくとも１回呼び出されることを特徴とする請求項１２に記載の方法。
【請求項１５】
アセンブリのための部品を配置するのに使用される１つまたはそれ以上の部品配置装置を含む生産ラインの設定を決定する装置であって、所定の部品配置装置タイプのための少なくとも１つの装置最適化モジュールを有するモジュール最適化装置を使用して上記設定が決定され、上記少なくとも１つの最適化モジュールが上記モジュール最適化装置に関連しており、上記装置が：
上記生産ラインの少なくとも一部の特徴を示す情報を記憶するメモリ；および
上記メモリに接続されたプロセッサであり、上記モジュール最適化装置に対して異質の部品配置装置タイプに関連した少なくとも１つの異質最適化モジュールに関する出力値を見積もり、上記生産ラインの上記設定を決定するために上記モジュール最適化装置において上記見積もられた出力値を使用するように動作する当該プロセッサ；
を含むことを特徴とする装置。
【請求項１６】
上記異質最適化モジュールの定期的な呼び出しを行い、上記呼び出しの所定の１つに関して上記異質最適化モジュールによって発生させられた出力値であり結果として起こる出力値を上記見積もられた出力値と比較し、もし必要ならば、引き続いて起こる見積もられた出力値の発生に関連したエラーを減らすために、上記見積もられた出力値を発生させるために使用された見積もり部の少なくとも１つのパラメータを変更するようにさらに動作することを特徴とする請求項１５に記載の装置。
【請求項１７】
アセンブリのための部品を配置するのに使用される１つまたはそれ以上の部品配置装置を含む生産ラインの設定を決定するモジュール最適化装置であって：
所定の部品配置装置タイプに関する少なくとも１つの装置最適化モジュール；および
上記モジュール最適化装置に対して異質の部品配置装置タイプに関連した少なくとも１つの異質最適化モジュールに関する出力値を見積もるように動作する見積もり部；
を含み、
上記生産ラインの上記設定を決定することにおいて、上記モジュール最適化装置が上記見積もられた出力値を使用する
ことを特徴とする上記モジュール最適化装置。
【請求項１８】
上記異質最適化モジュールの呼び出しを定期的に行い、上記呼び出しの内の所定の１つに関して、上記異質最適化モジュールによって発生させられた出力値であり結果として起こる出力値を、上記見積もられた出力値と比較し、必要な場合には、引き続いて起こる見積もられた出力値の発生に関連したエラーを減らすために、上記見積もられた出力値を発生させるのに使用された見積もり部の少なくとも１つのパラメータを変更するように動作する請求項１７に記載のモジュール最適化装置。
【請求項１９】
アセンブリのための部品を配置するのに使用される１つまたはそれ以上の部品配置装置を含む生産ラインの設定を決定することにおいて使用される１つまたはそれ以上のソフトウェアプログラムを記憶する機械読み取り可能媒体を含む製造物品であって、所定の部品配置装置タイプに関する少なくとも１つの装置最適化モジュールを有するモジュール最適化装置を使用して上記設定が決定され、上記少なくとも１つの装置最適化モジュールが上記モジュール最適化装置に関連しており、上記１つまたはそれ以上のプログラムは、実行されると：
上記モジュール最適化装置に対して異質の部品配置装置タイプに関連した少なくとも１つの異質最適化モジュールに関する出力値を見積もるステップ；
上記生産ラインの上記設定を決定するために上記モジュール最適化装置において上記見積もられた出力値を使用するステップ；
を行うこと特徴とする製造物品。
【請求項２０】
上記１つまたはそれ以上のプログラムは、実行されると、上記異質最適化モジュールの呼び出しを定期的に行って、上記呼び出しの所定の１つに関して、上記異質最適化モジュールによって発生させられた出力であり結果として起こる出力値を、上記見積もられた出力値と比較し、必要な場合には、引き続いて起こる見積もられた出力値に関連したエラーを減らすために、上記見積もられた出力値を発生させるのに使用された見積もり部の少なくとも１つのパラメータ値を変更するようにさらに動作することを特徴とする請求項１９に記載の製造物品。
【発明の詳細な説明】
【０００１】
（発明の属する技術分野）
本発明は、米国特許出願第０９／２８６，０２６号に記載された発明に関する。この特許出願の出願日は１９９９年４月５日であり、その発明者はラリー，ジェー，イーシャルマンとジェー，デビット，シャファー（Ｌａｒｒｙ Ｊ． Ｅｓｈｅｌｍａｎ ａｎｄ Ｊ． Ｄａｖｉｄ Ｓｃｈａｆｆｅｒ）であり、発明の名称は「選択配置装置のラインを最適化する方法」である。また、本願の譲受人とこの米国特許出願の譲受人は同一であり、この米国特許出願は本願に組み込まれた。
【０００２】
本発明は、一般的に、表面据付装置（ｓｕｒｆａｃｅ ｍｏｕｎｔ ｄｅｖｉｃｅｓ（ＳＭＤｓ））とプリントされた回路基盤へ配置される他の部品とのアセンブリにおいて使用されるいわゆる選択配置装置（ｐｉｃｋ ａｎｄ ｐｌａｃｅ ｍａｃｈｉｎｅｓ）のような部品配置装置に関し、特にそのような装置を設定・構成することにおいて使用される最適化装置に関する。
【０００３】
（従来の技術および発明が解決しようとする課題）
選択配置装置と他のタイプの部品配置装置の最適化の公知の技術は、１９９５年２月１４日に発行された米国特許第５，３９０，２８３号に記載されている。この米国特許の発明者はラリー，ジェー，イーシャルマンとジェー，デビット，シャファー（Ｌａｒｒｙ Ｊ． Ｅｓｈｅｌｍａｎ ａｎｄ Ｊ． Ｄａｖｉｄ Ｓｃｈａｆｆｅｒ）であり、発明の名称は「選択配置装置の設定を最適化する方法」。また、この最適化の公知の技術は、１９９９年１月２６日に発行された米国特許第５，８６４，８３３号にも記載されており、この特許の発明者はジェー，デビット，シャファーとミューラリ，マニ（Ｍｕｒａｌｉ Ｍａｎｉ）であり、発明の名称は「レイアウトと選択配置装置のフローラインのチャージマップを最適化する装置」である。さらに、この最適化の公知の技術は、１９９９年６月１日に発行された米国特許第５，９０９，６７４号にも記載されており、この特許の発明者はジェー，デビット，シャファーとミューラリ，マニであり、発明の名称は「レイアウトと選択配置装置のフローラインのチャージマップを最適化する方法」である。これらの特許のすべての譲受人が本願の譲受人と同一であり、これらの特許のすべてが本願に組み込まれた。
【０００４】
上述の文献に記載された技術によってかなり進歩したにもかかわらず、部品配置装置のラインの最適化においてさらなる改善が必要とされる。部品配置装置のための既存のモジュール最適化装置では、所定の生産ラインに追加されるどんな新たな装置に関しても、新たな最適化モジュールの開発が要求される。新たな装置のタイプの多くは既に自身の最適化装置を有しているかもしれないが、そのような最適化装置はしばしばモジュール最適化装置での使用には適していない。より特定した例として、新たな装置の最適化装置は非遺伝子アルゴリズムに基づいた最適化装置であり、非常にゆっくり動作するので遺伝子アルゴリズム（ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ（ＧＡ））に基づいたモジュール最適化装置に一般的であるように何千回も呼び出すことができない。遺伝子アルゴリズムに基づいたモジュール最適化装置は例えば、上述の米国特許出願第０９／２８６，０２６号に記載されている。それ故、異質の最適化装置のモジュールを効果的な方法で学習し使用することが可能なモジュール最適化装置の必要性が存在する。
【０００５】
（課題を解決するための手段）
本発明は、部品配置装置の最適化のための改善された技術を提供する。本発明の１つの態様によると、効果的な方法で異質最適化装置モジュールを使用するようにモジュール最適化装置が構成される。
【０００６】
より詳しくは、１つまたはそれ以上の部品配置装置を含む生産ラインの設定・構成（ｃｏｎｆｉｇｕｒａｔｉｏｎ）を決定することにおいて使用されるモジュール最適化装置は、このモジュール最適化装置に対して異質である部品配置装置タイプに関連した異質最適化装置モジュールを使用するように構成される。異質最適化装置モジュールは、（異質でない）モジュール最適化装置の特定の必要条件に従って出力の発生を行えないという点で異質（ｆｏｒｅｉｇｎ）である。しかしながら、モジュール最適化装置は適合見積もり部を有しており、この適合見積もり部は異質最適化装置モジュールに関する配置サイクル時間の長さのような出力値を見積もる。見積もられた出力値は生産ラインの設定を決定することにおいて使用されてよい。
【０００７】
本発明の別の態様によると、モジュール最適化装置は異質最適化装置モジュールの呼び出しを定期的に行い、これらの呼び出しの内の所定の１つに関して、異質最適化装置モジュールによって発生させられた出力であり結果として起こる出力値を、適合見積もり部によって発生させられた対応する見積もり出力値と比較する。もし異質最適化装置モジュールの所定の１つの呼び出しに関して対応する見積もられた値に対する実際の出力値が改善された結果を与えると判断されたならば、引き続いて起こる見積もり出力値の発生に関連したエラーを減らすために、見積もり部の１つまたはそれ以上のパラメータが変更される。
【０００８】
本発明のさらなる態様によると、モジュール最適化装置の遺伝子アルゴリズム（ＧＡ）の再始動に少なくとも部分的に基づいて、異質最適化装置モジュールが呼び出されてよい。例えば、ＧＡの再始動がある度に、前の再始動後に（以前の再始動以来）新たなベスト個体が見つけらいる場合には、異質最適化装置モジュールが呼び出されてよい。代わりに、異質最適化装置モジュールは他の基準に基づいて呼び出されてもよい。例えば、生き残る個体群に入りそうなＧＡの新たな子孫に出会う度に、異質最適化装置モジュールが呼び出されてよい。または、ＧＡにおいて潜在的にベスト個体であるものに出会う度に、異質最適化装置モジュールが呼び出されてもよい。
【０００９】
有益にも、本発明によって、その特定の稼動時間必要条件に従って異質最適化装置モジュールの十分な最適化が単に断続的に行われる。時間が経過すると、適合見積もり部は異質最適化装置モジュールの動作について学習を行い、このように出力のより正確な予測部となる。
【００１０】
本発明は、１つまたはそれ以上の異質最適化装置モジュールの使用を容易にするために、部品配置装置のモジュール最適化装置を構成する技術を提供する。ここで使われる「異質」という単語は、所定のモジュール最適化装置の特定の必要条件に従って出力を発生させることができない最適化装置モジュールに言及する。例えば、遺伝子アルゴリズム（ＧＡ）に基づいたモジュール最適化装置において、異質最適化装置モジュールは、ＧＡに基づいた最適化装置の稼動時間必要条件を超える稼働時間必要条件を持つ最適化装置モジュールであってよい。この場合には、異質最適化装置はＧＡに基づかない最適化装置モジュールであってよいが、これに限定される必要はない。
【００１１】
（発明の実施の形態）
本発明は、例示的な生産ライン、部品配置装置、モジュール最適化装置といった要素と関連して説明される。しかしながら、これらの要素は単に例示的なものであって本発明の範囲を限定するように意図されていない。当業者は、本発明によって提供される特徴がこれらのまたは他の要素の多くの他の構成によって実施可能であることに気づくであろう。
Ｉ  例示的な生産ライン
図１は本発明に従ったモジュール最適化装置を使用して設定されてよい生産ラインを簡潔に表した図である。生産ラインは、第一部品配置装置１とコンベヤー２と第二部品配置装置３を含んでいる。プリントされた回路基盤（ＰＣＢｓ）または他の部品据え付け支持構造がコンベヤー２上の生産ラインの装置１と３を通過する。１つまたはそれ以上の部品配置装置１と３は、例えば、高速部品据え付け装置（ＦＣＭ）または高度部品据え付け装置（ＡＣＭ）または所定のモジュール最適化装置の必要条件に従って出力を発生できない最適化モジュールを有する異質の装置であってよい。これらの高速部品据え付け装置（ＦＣＭ）と高度部品据え付け装置（ＡＣＭ）のタイプは、当該技術で知られており、上述の米国特許第５，３９０，２８３号、第５，８６４，８３３号、第５，９０９，６７４号と上述の米国特許出願第０９／２８６，０２６号に詳しく記載されている。
【００１２】
添付の図面は２つの装置しか有していない生産ラインを示しているが、本発明は３つ以上の装置を有する生産ラインにも適用可能である。また、所定の生産ラインの装置は、多数の異なる装置のタイプの各々に関して１つまたはそれ以上の装置を含んでいてよい。例えば、以下で説明される本発明の例示的な実施形態は、１つまたはそれ以上のＦＣＭ装置と１つまたはそれ以上のＡＣＭ装置と少なくとも１つの異質装置を有する生産ラインを最適化するように構成される。この異質装置は、例えば、ＧＡに基づいたモジュール最適化装置の必要条件・要求に従って出力を発生できない最適化モジュールを有する装置である。
ＩＩ  例示的なモジュール最適化装置
本発明の例示的な実施形態に従ったモジュール最適化装置の例が、図２、３に関連させて説明される。この例示的なモジュール最適化装置は、上述の米国特許出願第０９／２８６，０２６号に詳しく記載されているモジュール最適化装置と同一または類似したものであるが、本発明に従った異質最適化モジュール学習特徴を含むように修正される。しかしながら、本発明は、異質な最適化モジュールを学習する能力を実施することが望ましい部品配置装置のためのモジュール最適化装置のどんなタイプのものに対してもより一般的に適用可能である。
【００１３】
図２は、本発明が実施されてよい例示的なモジュール最適化装置（ｍｏｄｕｌａｒ ｏｐｔｉｍｉｚｅｒ）の概略的な図である。上述したように、この最適化装置は図１の部品配置装置１と３を含む生産ラインを最適化するのに使用されてよい。また、この最適化装置は、図３と関連させてより詳しく説明される異質最適化装置学習特徴を含むように本発明に従って構成されてよい。モジュール最適化装置は、遺伝的アルゴリズム（ＧＡ）１０１を実施するプロセッサ１１０と、発見的レイアウト発生部（ＨＬＧ（ｈｅｕｒｉｓｔｉｃ  ｌａｙｏｕｔ  ｇｅｎｅｒａｔｏｒ）１０２を含む。プロセッサ１１０内で、ＧＡ１０１は繰り返してＨＬＧ１０２と相互に作用しあう。プロセッサ１１０は装置１と３の内部にあってもよいし、外部にあってもよい。
【００１４】
ＧＡ１０１は図示されない染色体のひも（ｃｈｒｏｍｏｓｏｍｅ ｓｔｒｉｎｇｓ）の個体群（ｐｏｐｕｌａｔｉｏｎ）を維持する。染色体のひものある長さのもの１２０は、初期ステップにおいてＨＬＧ１０２によってＧＡ１０１に供給される。このある長さのもの１２０に反応して、ＧＡ１０１はひもの第一個体群を作成する。後の反復・繰り返しにおいて、ＧＡ１０１は変更・突然変異（ｍｕｔａｔｉｏｎ）および／または交差（ｃｒｏｓｓｏｖｅｒ）を特定のタイプのＧＡ１０１に従って適用する。上述の米国特許のように、ＣＨＣはＧＡの好ましいタイプであるが、他のタイプも同様に使用されてよい。その後、ＧＡ１０１は染色体のひもをコントロールパラメータ１０３としてＨＬＧ１０２に供給する。
【００１５】
ＨＬＧは、製造されるべき製品を定義するファイル１０５と、ライン構成１０６と、装置セットアップ／仕様１０７と相互作用する。ファイル１０５とライン構成１０６と装置セットアップ／仕様１０７は、メモリ装置１１１内に保存される。ＨＬＧ１０２は染色体のひもに関連した適合尺度・長さ・寸法（ｍｅａｓｕｒｅｓ ｏｆ ｆｉｔｎｅｓｓ）をＧＡ１０１に供給する。これらの尺度は、サイクル時間（ｃｙｃｌｅ ｔｉｍｅｓ）または他のタイプのコストの相関的要素であってよい。ＧＡ１０１は、後の反復においてこれらの適合尺度を使用する。
【００１６】
図２に示されたサイクルは、終了の特定の基準が達せられるまで繰り返される。
【００１７】
図３は、本発明の例示的な実施形態に従ったＨＬＧ１０２のより詳しい図である。図示されているようなＨＬＧ１０２は、部品分配モジュール・部品分配装置モジュール（ｐａｒｔ ｓｐｌｉｔｔｅｒ ｍｏｄｕｌｅ）２０２と、ＦＣＭモジュール２０３と、ＡＣＭモジュール２０５を含んでいる。部品分配モジュール２０２とＦＣＭモジュール２０３とＡＣＭモジュール２０５は、上述の米国出願第０９／２８６，０２６に記載されている方法と実質的に同じ方法で動作する。図１の生産ラインにおける２つの装置１と３は、説明のために、それぞれＦＣＭ装置とＡＣＭ装置に対応していると仮定する。
【００１８】
さらに、生産ラインは少なくとも１つの追加装置を含むように修正されることを仮定する。この追加装置は図２のモジュール最適化装置の必要条件に従って出力を発生させることができない最適化モジュールと関連している点でこの追加装置は異質装置である。例えば、異質装置はフィリップス（Ｐｈｉｌｉｐｓ）ＴＯＰＡＺ部品配置装置として当該技術において知られている装置であってよい。そのような装置は、比較的長い稼動時間条件（ｌｏｎｇ  ｒｕｎ  ｒｅｑｕｉｒｅｍｅｎｔｓ）を持つＧＡに基づかない当該装置に関連した最適化装置を有し、このように図２と３の例示的なＧＡに基づいたモジュール最適化装置における直接的な実施に一般的には適していない。
【００１９】
本発明に従うと、ＨＬＧ１０２は異質最適化モジュール２１５と対応した適合見積もり部２１６を含む。この異質最適化モジュール２１５は、生産ラインに追加された異質装置の上述した最適化モジュールを表している。適合見積もり部２１６は、異質最適化モジュール２１５の出力の見積もりを発生させる。見積もり部２１６は、見積もったものを異質最適化モジュール２１５の実際の出力と比較し、その後、異質最適化モジュールの動作についてのこれらの比較から学んだものに基づいて先の（未来の）見積もりを適合・適応・順応させるという点で適合性・順応性がある。
【００２０】
ＨＬＧ１０２はＧＡ１０１から染色体のひも２０８を受ける。１つのひもだけが図示されているが、ＨＬＧ１０２は一般的にＧＡによって発生させられた各ひもに基づいて動作する。染色体のひも２０８の第一部分２０９は、パーツ・部品（ｐａｒｔｓ）が、例示的な生産ラインの装置の間で、即ち、ＦＣＭ装置とＡＣＭ装置と上述の追加異質装置の間でどのように分配されられるべきかを制御するパラメータを表している。染色体のひも２０８の第二部分２１０は、第一装置１（この例では、ＦＣＭ装置と仮定する）のレイアウトを制御するパラメータを表している。染色体のひも２０８の第二部分２１１は、第二装置３（この例では、ＡＣＭ装置と仮定する）のレイアウトを制御するパラメータを表している。装置の各々に使用される遺伝子（ｇｅｎｅｓ）を含めて１つまたはそれ以上の染色体のひも２０８の部分があってよい。ここで概略的に図示されている染色体のひもは、かなり小さな量のビット（ｂｉｔｓ）を持っている。しかしながら、実際の染色体のひもは一般的にずっと長く、例えば、１００から４０００ビットを持っている。また、図３に示されている染色体の部分２０９、２１０、２１１の順番は選択的なものである。これらの部分のどんな順番を用いても同じ機能の達成が可能である。２つの特定の装置のタイプ、即ち、ＦＣＭ装置とＡＣＭ装置のタイプと追加異質装置のタイプの観点でこの例が示されているが、当業者は、他の数の装置と他の数のタイプの装置を持つ生産ラインにモジュール最適化装置を適用することが可能である。
【００２１】
ＨＬＧ１０２内において、分配モジュール２０２は最初に染色体のひも２０８の第一部分２０９の制御のもとで動作して装置１と装置３と追加異質装置の間におけるパーツの割り当てを発生させる。その後、２つのモジュール２０３と２０５は、それぞれ装置１と３のためのレイアウトを発生させる。モジュール２０３と２０５は上述の米国特許第５，３９０，２８３号、第５，８６４，８３３号、第５，９０９，６７４号に記載された方法で動作する。例えば、これらのモジュールは、米国特許第５，３９０，２８３号に記載されているように別々のＨＬＧモジュールとして動作してよいしまたは米国特許第５，８６４，８３３号に記載されているように特定のタイプの装置に対して対応するラインタイプのモジュールであってもよい。いくつかの装置が同じタイプの装置でありさえすれば、モジュール２０３と２０５の各々は、これらのいくつかの装置のラインを実際に最適化することが可能である。
【００２２】
本発明に従うと、見積もり部２１６は、図２に示されたループの各繰り返しに関して実際には完全な最適化を実行せずに、異質最適化モジュール２１５によって発生させられるであろうレイアウトに関する見積もりを発生させる。特に、もし異質装置のタイプによって実行されるべき特定のサブタスクが異質最適化モジュール２１５に与えられたのならば、異質最適化モジュール２１５によって戻されるであろう値を見積もるように見積もり部２１６が設計される。見積もり部２１６は好ましくはサブタスクに反応する。上述のように見積もり部２１６は適合見積もり部であり、自分自身で適合・適応・調整を行うように構成される。所定間隔であるが代表的には見積もり部２１６が呼び出される頻度よりもずっと少ない頻度で、完全に・十分に異質な最適化モジュール２１５が特定のサブタスクによって呼び出される。これらの所定の間隔は、以下でより詳しく説明されるように、ＣＨＣ  ＧＡ１０１の再始動に一致してよい。最適化モジュール２１５の完全な・十分な最適化は、自身の特定の動作時間必要条件に従ってこのように単に断続的に実行される。異質最適化モジュール２１５によって戻された値は、同じサブタスクのための見積もりと比較され、見積もり部２１６はエラーを減らすように調整される。時間の経過によって、見積もり部は異質最適化モジュールの動作についての学習を行い、異質最適化モジュールのより正確な予測を行う。モジュール２０３、２０５、２１６がレイアウトを発生させた後、モジュール最適化装置のそれぞれのモジュール２０４、２０６、２１８はそれらのレイアウトに適合するサイクル時間の長さを決定する。モジュール２０４、２０６、２１８は上述の米国特許第５，３９０，２８３号、第５，８６４，８３３号、第５，９０９，６７４号に記載されているように構成されてもよい。その後、要素２０７は、全体のラインに関する最大サイクル時間をモジュール２０４、２０６、２１８によって発生させられた部品サイクル時間から決定する。この例は３つだけの部品配置装置、即ち、ＦＣＭ装置とＡＣＭ装置と異質装置を含んでいるが、モジュール最適化装置を、より多くの装置と異なるタイプの装置、例えば、多数の異なるタイプの異質装置を含むように同様に拡張させてもよい。全体の染色体は追加された異質装置ではない装置の各々に関して再設計される必要がないので、上述のモジュール最適化装置のモジュラリティー（ｍｏｄｕｌａｒｉｔｙ）は新たな異質装置でないタイプの装置の追加に特によく適合させられる。新たな染色体部分だけが、新たな異質装置でないタイプの装置のために追加される必要がある。本発明に従うと、適合見積もり部と異質最適化モジュールが、生産ラインに追加された異質タイプの装置の各々のためにモジュール最適化装置に追加されてよい。しかしながら、見積もりにおける不確実性やノイズの量は、所定の実施において動作する異質最適化装置の数とともに一般的に増加する。例えば、２つの異なる動作異質最適化装置を持つ実施形態は、１つだけの動作異質最適化装置を持つ実施形態よりも確実性が劣る出力を発生させることが予想される。
【００２３】
ＨＬＧ１０２において、モジュールのどれも新たな異質装置でないタイプの装置の追加によって修正される必要がない。代わりに、モジュール２０３から２０６に類似した新たなモジュールを、異質装置でない追加の装置のために図の最下部に追加することが可能である。上述したように、異質タイプの装置の各々は、対応する適合見積もり部と、モジュール最適化装置の異質最適化モジュールを有してよい。
【００２４】
なお、装置の内の１つが修正された場合には、モジュールと、その装置に関係する染色体部分だけが修正される必要がある。
【００２５】
要素２０７は、ＧＡ１０１に適合する長さとしての最大サイクル時間を出力して、その処理の次のステップへと繰り返しが実行される。
【００２６】
ＧＡ１０１とＨＬＧ１０２の間の繰り返しが妥当な解に収束する場合には、モジュール２０３、２０５と異質最適化モジュール２１５は、それぞれ装置１、３と追加異質装置で使用される最終的なレイアウトを出力することが可能である。
【００２７】
この特定の例示的なモジュール最適化装置の基礎となるサーチアルゴリズム（ｓｅａｒｃｈ  ａｌｇｏｒｉｔｈｍ）は、ＣＨＣ，即ち、フィリップスエレクトロニックノースアメリカコーポレーション（Ｐｈｉｌｉｐｓ  Ｅｌｅｃｔｒｏｎｉｃ  Ｎｏｒｔｈ  Ａｍｅｒｉｃａ  Ｃｏｒｐ．）によって開発されたＧＡの特定のバージョンである。ＣＨＣの追加的詳細は、上述の米国特許第５，３９０，２８３号、第５，８６４，８３３号、第５，９０９，６７４号に述べられている。また、ＣＨＣの追加的詳細は、本明細書に組み込まれた１９９１年、カリフォルニア、サンマテオ、モーガン  カフマン、ジー  ローリン（Ｇ． Ｒａｗｌｉｎｇｓ ｅｄ．， Ｍｏｒｇａｎ Ｋａｕｆｍａｎｎ， Ｓａｎ Ｍａｔｅｏ， ＣＡ）の遺伝子アルゴリズムの財団におけるエル  ジェー  イーシャルマン（Ｌ．Ｊ．Ｅｓｈｅｌｍａｎ）の「ＣＨＣ適合アルゴリズム：従来的でない遺伝子再結合時のセーフサーチの仕方」に述べられている。ＣＨＣの重要な特徴は、再始動であり、ダイバージェンス・発散（ｄｉｖｅｒｇｅｎｃｅ）とも呼ばれる。すべてのＧＡのように、ＣＨＣは試験的な解（ｔｒｉａｌ ｓｏｌｕｔｉｏｎｓ）の個体群を維持し、新たな試験的な解を発生させるためにこれらの解（ｓｏｌｕｔｉｏｎｓ）を使用する。ベスト解（ｂｅｓｔ ｓｏｌｕｔｉｏｎｓ）が選択され、ワースト解（ｗｏｒｓｔ ｓｏｌｕｔｉｏｎｓ）と置き換えられる。新たな解を発生させて適合するものを選択する各サイクルをジェネレーション・発生と呼ぶ。時間の経過に伴って、個体群が非常に似た解に収束する。これが起こると、ＣＨＣが再始動を行う。これまでに見つけられたベスト解の変形となる個々の解の新たな個体群を作成するテンプレート（ｔｅｍｐｌａｔｅ）としてこのベスト解が使用される。その後、処理が続けられる。それ故、ＧＡ１０１としてのＣＨＣを使用することによってよい解を検索・サーチする処理において、再始動が繰り返される。
【００２８】
上述のモジュール最適化装置における試験的な解は、ＨＬＧ１０２を制御する所定のセットのパラメータである。上述のように、ＨＬＧは所定のＰＣＢまたは他のアセンブリ構造のための部品配置装置の所定の構成・設定（ｃｏｎｆｉｇｕｒａｔｉｏｎ）に関するレイアウトを発生させる。その後、ＨＬＧに非常によい解を発生させることを可能にするであろう１セットのパラメータをＧＡが探す・サーチする。
【００２９】
適合見積もり部２１６は、実質的に異質タイプの装置のために、ＨＬＧの代わりに使用され、見積もりを調整するために、単に断続的に、例えば、上述のＣＨＣの再始動の度に、対応する異質最適化モジュール２１５が呼び出される。ＨＬＧ１０２の一部が図３に示されているが、適合見積もり部２１６と異質最適化モジュール２１５をＨＬＧ１０２の一部として見る必要はない。代わりに、要素２１５と２１６を図２のモジュール最適化装置において独立型要素として見たり、ＧＡ１０１とＨＬＧ１０２にわたって配分したり、または、上述の方法でモジュール最適化装置とともに動作するように構成することも可能である。
【００３０】
パーツ間で差異が生じないように、即ち、各パーツを同じ重さであるとして扱い、どの追加パーツも同じコスト増加を得るように、上述の例示的な実施形態の見積もり部２１６が構成されてよい。上述のＴＯＰＡＺタイプの装置での使用のためのこのタイプの見積もりルーチンの例は、以下で説明される。他の実施形態では、異なるパーツ間でのコスト増加や重さに関して差異を導入することによって、または他の情報を追加することによって、パーツ間において差異が生じるように見積もり部が構成されてよい。追加情報によってより正確な見積もりが得られることが予期される。
ＩＩＩ  異質最適化モジュール２１５と見積もり部２１６に対する呼び出し
適切な異質最適化モジュール２１５と見積もり部２１６の呼び出しは、一般的に、上述のＣＨＣに対して多くの修正を要求するであろう。特に、ＣＨＣの確認ルーチンｖｅｒｉｆｙ＿ｅｓｔｉｍａｔｅ０が再始動ルーチンの始めに呼び出されるように再始動ルーチンｃｈｃ＿ｄｉｖｅｒｇｅ＿ｉｎｉｔが修正されてよい。このルーチンｖｅｒｉｆｙ＿ｅｓｔｉｍａｔｅ０は、モジュール最適化装置が動作異質最適化モジュールを含んでいるかどうかを知るためにチェックを行う。もしそうであるならば（例えば、ｎ＿ｔｏｐａｚ＞０であるならば）、ｖｅｒｉｆｙ＿ｅｓｔｉｍａｔｅ０ルーチンは、ｖｅｒｉｆｙ＿ｅｓｔｉｍａｔｅ＿ｆｌａｇセットとこれまでに染色体として見つけられたベスト個体とともにＧＡ１０１の見積もりルーチン（ｅｖａｌ）を呼び出す。
ｖｅｒｉｆｙ＿ｅｓｔｉｍａｔｅ＿ｆｌａｇが設定された場合には、見積もりルーチンは、見積もり部２１６の代わりに、異質最適化モジュール、例えば、異質最適化モジュール２１５を呼び出す。その後、見積もりルーチンによって戻された値はベスト個体の染色体に保存された古い値と比較される。新しい値がよりよい場合には、ｓａｖｅ＿ａｃｔｕａｌ＿ｂｅｓｔ＿ｃｈｒｍルーチンが呼び出される。または、ｒｅｓｔｏｒｅ＿ａｃｔｕａｌ＿ｂｅｓｔ＿ｃｈｒｍルーチンが呼び出される。ｓａｖｅ＿ａｃｔｕａｌ＿ｂｅｓｔ＿ｃｈｒｍルーチンは、新たな（実際の）性能値をベスト個体の染色体に写し、（ａｃｔｕａｌ＿ｂｅｓｔ染色体データ構成が次の再始動において失われないようにするために）この個体をａｃｔｕａｌ＿ｂｅｓｔ染色体データ構成に写し、見積もり因数を更新する。見積もり因数は、適合見積もり部２１６のパラメータの１つのタイプの例であり、見積もられた出力値を発生させる時に使用される。
【００３１】
ｒｅｓｔｏｒｅ＿ａｃｔｕａｌ＿ｂｅｓｔ＿ｃｈｒｍルーチンが、ａｃｔｕａｌ＿ｂｅｓｔ染色体をｂｅｓｔ＿ｉｎｄｉｖｉｄｕａｌデータ構成に写すことによって、このよりよい個体が再始動を引き起こすのに使用される。
【００３２】
上述のＴＯＰＡＺ装置に対する異質最適化モジュールの出力を見積もる見積もり部２１６において使用される例示的な見積もりルーチンは、ＴＯＰＡＺ装置に置かれるパーツの数（ｎ＿ｐａｒｔｓ）に５００（５００ミリ秒のパーツ配置時間に対応している）を掛け、９０００（９秒のならし稼動時間（ｒｕｎ−ｉｎ ｔｉｍｅ）に対応している）を加え、その後、最初はゼロまたは１のような特定の値に設定されてよいＴＯＰＡＺ見積もり因数を掛ける。本発明によると、異質最適化モジュールが呼び出される度に、初期見積もり因数がそれに続いて調整されることによって、（５００＊ｎ＿ｐａｒｔｓ）＋９０００）＊ｅｓｔ＿ｆａｃｔｏｒが異質最適化モジュールによって戻された実際の時間に等しくなる。
上述の修正は、従来のダイバージェンスとＣＨＣの見積もりプログラムで実施されてよい。当業者は、直接的な・普通の方法で上述のルーチンを実施することができる。当業者は、既存のモジュール最適化装置が追加装置のタイプを扱えるようにこのモジュール最適化装置を構成するなどのために、他のソフトウェアの変更が必要であることに気がつくであろう。そのような変更は、特定の実施に依存し、直接的な・普通の方法でも実行可能である。
【００３３】
上述のように例示的な実施形態での異質最適化モジュール２１５はＣＨＣ  ＧＡ１０１の再始動時に呼び出されたが、多くの代わりの取り決めが可能である。一般的に、異質最適化モジュールに対する呼び出しは、サーチ・探索における適切な時機で起こるべきである。次のものを含むが、異質最適化モジュールを呼び出すいくつかの適切な時機がある。
（１）個体群に入りそうな、即ち、生き残りそうな新たな子孫（ｏｆｆｓｐｒｉｎｇ）に出会う度に異質最適化モジュールを呼び出す。
（２）潜在的な新たなベスト個体に出会う度に異質最適化モジュールを呼び出す。
（３）再始動が起こる度に、この前の（つい最近の）再始動後に（再始動以来）新たなベストが見つかっている場合には、異質最適化モジュールを呼び出す。
【００３４】
代表的な受け入れ率（生き残る新たな個体の割合）が約１０％から２０％であるとすると、最初の選択肢は非常に費用が高くなりそうである。個体が受け入れられるかどうかの決定は見積もられた値に基づいているので、この数字が示すよりもコストは高くなりそうである。これらのいくつかの新たな個体は、一旦完全に見積もられると、受け入れられないことになる。このことは、完全な見積もりの回数を簡単に倍化させる。
新たな個体の数はかなり少なく、特定の適用に依存して、およそ１０から２０のオーダーから１００から２００のオーダーの範囲にわたる。しかしながら、新たなベスト個体のいくつかの内の多くは、完全に見積もられたとき、本当は新たなベストなものではないとすると、これらの数は少なくとも２倍になりそうである。完全な見積もりにかかる時間が１分より短い場合には、このアプローチは実用的である。完全な見積もりにかかる時間が数分より長い場合には、唯一の実用的なアプローチは上で与えられた三番目のアプローチ（（３）のアプローチ）であるかもしれない。再始動の回数はノイズのために増加させなければならないが、再始動の回数はたいてい１０より少ない。再始動の回数が２倍になり異質最適化装置の各々の呼び出しが例えば３０分かかる場合には、最適化装置の稼動時間に１０時間が追加される。また、新たなベストであるもののほとんどが最初の収束において、即ち、最初の再始動の前に起こる。それで、すべての新たなベストであるものに関する異質最適化装置モジュールの呼び出しは、最初の探索・サーチを重大に遅らせることになり、このように受け入れ可能な解を見つけるのにかかる時間を長引かせる。受け入れ可能な解が見つかった時はいつでもユーザーが探索・サーチを停止することができるようにすることが目的である場合には、異質最適化装置に対するより多くの呼び出しを行うよりもよい解決方法は、受け入れ可能でありそうな解が見つかった時はいつでもユーザーが異質最適化装置モジュールに対する呼び出しを引き起こせる（ｉｎｉｔｉａｔｅ）ようにすることである。この呼び出しは見積もりを調整する。もし調整された値がユーザーにとって受け入れ可能あるならば、探索が停止させられる。
【００３５】
上で与えられた一番目のアプローチによって正確さを高められたということをシミュレーションは示している。しかしながら、一番目のアプローチはコストがかかる。一方、二番目のアプローチは正確さを大いに改善しないのでコストの上昇に値しないかもしれない。
【００３６】
しかしながら、最初の再始動の後に、二番目のアプローチを使用する混合アプローチが可能である。これによって、異質最適化装置モジュールに対する呼び出しの回数が大いに削減される。
【００３７】
もちろん他の多くの他の代わりの方法・アプローチがある。例えば、見積もり部を調整するために最適化処理の始めに異質最適化装置モジュールがより頻繁に呼び出されてよい。たとえ解がこれまでに見つかったベスト解であったとしても、もし異質最適化装置が実際には劣っている解に関して呼び出されるならば、これはそれほど有益ではない。なぜなら、これらの解は初期においてはベストであっても最終的には劣った解であるというようにまぎらわしいものであるからである。収束を早めてこのように異質最適化装置モジュールをより早く呼び出すために、より小さな個体群を使用するという別の方法・アプローチを実行してよい。
【００３８】
異質最適化装置モジュールが呼び出される度に、もし実際のサイクル時間が見積もられたサイクル時間よりもよいならば、新たな見積もり因数が計算される。これは、再始動時に問題を引き起こさない。なぜなら、実際のサイクル時間の計算が行われたメンバーである個体群の内のベストメンバー（ｂｅｓｔ ｍｅｍｂｅｒ）だけが保持されているからである。しかしながら、他の点に関しては、個体群の多くの他のメンバーは、古い見積もり因数に基づいた適合値（サイクル時間）を持っている。有効な比較が行えるようにこれらの値は再度計算される必要がある。最終的な適合値は、各装置に関するサイクル時間の内の最大のサイクル時間であり、これらの値の内の１つが変わっているかもしれないので、新たな最大値が得られるようにこれらの値を保存するかまたはこれらの値を再度計算する必要があるかもしれない。
ＩＶ  初期見積もりの較正
上述のように、適合見積もり部２１６は１つまたはそれ以上の見積もり因数を使用して見積もられた出力値を発生させる。これらの因数はここでは重みとも呼ばれる。
【００３９】
適合見積もり部２１６に使用される重みの初期の１セットがあまり正確でない場合には、最初の再始動における結果はあまり正確でないであろう。一つの可能な解決方法は見積もり部のために初期重みのよりよいセットを決定するためにパーツの選ばれたセットを使用して異質最適化装置モジュールを少ない回数呼び出すことである。例えば、０個のパーツ、４個のパーツ、８個のパーツ、１６個のパーツおよび２０個のパーツを使用して異質最適化装置モジュール２１５を呼び出すことが可能である。その後、これらの数の各々に基づいてよりよい見積もり部の初期重みの選択が可能である。
例えば、ＴＯＰＡＺ装置のピペットモジュール（ｐｉｐｅｔｔｅ  ｍｏｄｕｌｅｓ（ＰＭｓ））の数のような自然数の境界に基づいてパーツの数を選択することが可能である。この装置は代表的に８つのピペットモジュールを有している。バランスのとれた負荷（ｌｏａｄ）を得るために異質最適化装置モジュールを使用していくつのパーツを置く必要があるかの見積もりに基づいてより多くのパーツ（上の例では２０のパーツ）を選択することが可能である。上述の米国特許第５，３９０，２８３号に記載されているようにＦＣＭ装置とＡＣＭ装置のタイプのためのｐｐ＿ｔｉｍｅ＿ｌｏｗｅｒ情報を使用することによってこの見積もりを得ることが可能である。
代わりに、異質最適化装置モジュールを各パーツに関して１回呼び出すことが可能である。上述のｐｐ＿ｔｉｍｅ＿ｌｏｗｅｒ情報の代わりに戻された値を使用することが可能である。これによって、異質最適化モジュールがパーツ間において異なることが可能であり、このようにより正確な見積もりを行うことが可能である。パーツのいくつかのセットに関しての異質最適化装置に対する呼び出しとともに、この情報を初期見積もりを較正するために使用することができる。
Ｖ  装置タイプにわたるパーツの分離
図３のパーツ分離モジュール２０２は、所定の生産ラインの異なる装置のタイプの間でパーツを分離する役割を持つ。このモジュールは主に異なるタイプのパーツを異なるタイプの装置に割り当てる（パーツ分配処理）が、特に１つのパーツタイプのパーツが多数ある場合には、１つのパーツタイプのパーツを異なるタイプの装置にわたって分離させる（パーツタイプ分配処理）必要があるかもしれない。
【００４０】
それ故、装置のタイプにわたる分離はたいていパーツタイプレベルにおけるパーツ分離処理である。しかしながら、１つのパーツタイプが代表的に選択されて、これに関して上述のパーツタイプ分離処理がパーツレベルにおいて起こる。この分離されるパーツタイプのパーツは各装置タイプに関する相対的有益さに基づいて分類される。これは、ＦＣＭ装置とＡＣＭ装置のｐｐ＿ｔｉｍｅ＿ｌｏｗｅｒ値の比率を比較することによって、ＦＣＭ装置とＡＣＭ装置に関して実行されてよい。上述のＴＯＰＡＺ異質装置タイプのための利用可能な対応する情報が存在しないので、上述の米国特許第５，３９０，２８３号に記載されているようなｙ距離（ｙ−ｄｉｓｔａｎｃｅ）の値を代わりに使用してよい。しかしながら、このアプローチは、異なる質、即ち、ｙ距離と見積もられた時間に基づいて比率を計算することに関わり、不確実になるかもしれない。多くの実用的な適用において、パーツタイプ分離処理は大きな役割を果たさないので、パーツをどのように配列するかについてはあまり大きな違いとならない。
【００４１】
別の問題は、３つ以上の装置が存在する場合には、２つ以上のパーツタイプを分離するべきかどうかという問題である。分離に関してパーツタイプを選ぶ１つの基準は、パーツの数である。しかしながら、パーツのタイプの数が少なくて、１つのパーツタイプが他のパーツタイプよりもずっと多くのパーツを持っている場合には、パーツタイプ分離処理は価値を持つ。分離のためのパーツタイプを選択する上述の基準は、一般的に受け入れ可能である。分離パーツタイプに関してパーツを配列する可能な他の技術は以下のようなものである。相対的なｐｐ＿ｔｉｍｅ＿ｌｏｗｅｒ比率に基づいてパーツを分類する代わりに、パーツは上述のｙ距離値に基づいて分類されてよい。これは完全に十分な解ではないかもしれないが、３つ以上の装置タイプに関しては一般的であり、これによって染色体はいくつかのコントロールを行うことが可能である。すべての場合において、改善された性能を得ることはできないかもしれない。
【００４２】
電子的メモリ、磁気的メモリ、光学的メモリまたは機械読み取り可能媒体の他のタイプのものに保存された１つまたはそれ以上のソフトウェアプログラムの形式で本発明を部分的に実施することが可能である。例えば、上述したようなモジュール最適化装置の様々なモジュールが、メモリ１１１に保存されたソフトウェアで実施され、プロセッサ１１０によって実行されることが可能である。
【００４３】
本発明の上述した実施形態は、単に例示的なものとして意図されている。例えば、本発明は他のタイプのモジュール最適化装置において使用されることが可能であり、様々な異なる配列・配置と様々なタイプの部品配置装置を持つ生産ラインに適用可能である。これらのまたは多くの他の実施形態が、本発明の特許請求の範囲から逸脱せずに当業者によって実施可能である。
【図面の簡単な説明】
【図１】
本発明に従った異質モジュール学習特徴を有するモジュール最適化装置を使用して設定されてよい２つの部品配置装置を含む生産ラインの例を示す簡潔にした図である。
【図２】
本発明に従った異質最適化装置モジュール学習特徴を有する例示的なモジュール最適化装置の概略的な図である。
【図３】
図２のモジュール最適化装置の発見的レイアウト発生部のより詳しい概略図であり、本発明の例示的な実施形態に従った異質最適化装置モジュールとこれと対応する見積もり部を示している。
【図２】
2004517401.tif 000002
【図３】
2004517401.tif 000003
【国際公開パンフレット】
2004517401.tif 000004
2004517401.tif 000005
2004517401.tif 000006
2004517401.tif 000007
2004517401.tif 000008
2004517401.tif 000009
2004517401.tif 000010
2004517401.tif 000011
2004517401.tif 000012
2004517401.tif 000013
2004517401.tif 000014
2004517401.tif 000015
2004517401.tif 000016
2004517401.tif 000017
2004517401.tif 000018
2004517401.tif 000019
2004517401.tif 000020
2004517401.tif 000021
2004517401.tif 000022
2004517401.tif 000023
【国際公開パンフレット（コレクトバージョン）】
2004517401.tif 000024
2004517401.tif 000025
2004517401.tif 000026
【国際公開パンフレット（コレクトバージョン）】
2004517401.tif 000027