(57)【要約】１台以上のコンポーネント配置機械を含む生産ラインの構造を決定する際に使用するモジュラー最適化装置は、先行制約に対処するように構成される。先行制約は、Ａ  Ｂ  ＭＴの形式でも構わない。Ａ  Ｂ  ＭＴは、部品Ａと部品Ｂの両方を機械タイプＭＴによって配置する場合に、配置部品Ａが部品Ｂよりも先に指定された組立ボードに配置されなければならない、ということを定める。所定の先行制約の組は、少なくとも、１種類のコンポーネント配置機械タイプだけに当てはまる第１の制約クラスと、２種類以上のコンポーネント配置機械タイプに当てはまる第２の制約クラスと、を含む。制約の種々のクラスへの割り当ては、どの部品がどの機械タイプに割り当てられるかに関するモジュラー最適化装置の部品スプリッタモジュールの決定に基づいている。所定の機械タイプと関連付けられた第１の制約クラス中の各制約は、モジュラー最適化装置の対応した機械モジュールで取り扱われる。第２の制約クラスは、モジュラー最適化装置の部品スプリッタモジュールで取り扱われる。部品スプリッタ・モジュールの出力は、機械モジュールへ供給され、構造を決定する際に使用される情報を生成するため、機械モジュールで処理される。
2004518192.tif 000002
【特許請求の範囲】
【請求項１】
組立用のコンポーネントを配置するため使用される１台以上のコンポーネント配置装置が設けられた生産ラインの構造を決定するため使用される方法であって、
一つのコンポーネント配置機械タイプだけに当てはまる少なくとも第１の制約のクラスと、二つ以上のコンポーネント配置機械タイプに当てはまる第２の制約のクラスと、を含む先行制約の組を決定する手順と、
各々が一つの機械タイプに対応する複数の機械モジュールを含むモジュラー最適化装置の対応した一つの機械モジュールにおいて所定の機械タイプと関連した第１の制約のクラスの各制約を処理する手順と、
モジュラー最適化装置において一つ以上の機械モジュールへの入力を提供する部品スプリッタ・モジュールによって第２の制約のクラスを処理する手順と、
を有し、
機械モジュールの出力は構造を決定するため使用される情報を提供する、
方法。
【請求項２】
先行制約の組の少なくとも部分集合は、部品Ａと部品Ｂの両方の部品を機械タイプＭＴを用いて配置しなければならない場合に、部品Ａが部品Ｂよりも先に指定された基板に配置されなければならないことを規定するＡ  Ｂ  ＭＴの形式の先行制約を含む、請求項１記載の方法。
【請求項３】
先行制約の組の第１の先行制約のクラスと第２の先行制約のクラスへの分割は、少なくとも部分的には、モジュラー最適化装置の部品スプリッタ・モジュールで行われる、請求項１記載の方法。
【請求項４】
所定の先行制約と関連付けられた２個の部品が二つの別個の機械タイプに割り当てられた場合、部品スプリッタ・モジュールはその割当が実施可能であるかどうかを判定する、請求項１記載の方法。
【請求項５】
複数の機械モジュールは、少なくともＦＣＭモジュールとＡＣＭモジュールとを含む、請求項１記載の方法。
【請求項６】
部品Ａと部品Ｂの両方の部品を機械タイプＭＴを用いて配置しなければならない場合に、部品Ａが部品Ｂよりも先に指定された基板に配置されなければならないことを規定するＡ  Ｂ  ＭＴの形式の所定の先行制約に対し、部品スプリッタ・モジュールは、
部品Ａと部品ＢのどちらもタイプＭＴの機械に割り当てることがなく、この場合に、制約を無視することができる割当と、
部品Ａと部品Ｂの両方をタイプＭＴの機械に割り当て、制約は第１の制約クラスに含まれ、機械タイプＭＴに対応した機械モジュールによって取り扱われる割当と、
部品Ａと部品Ｂのうちの一方をある機械タイプに割り当て、もう一方の部品を別の機械タイプに割り当て、制約は第２の制約クラスに含まれ、部品スプリッタ・モジュールによって取り扱われる割当と、
のうちのいずれかの割り当てを行う、
請求項３記載の方法。
【請求項７】
先行制約の組を決定する手順は、静的制約カウントと動的制約カウントを含むデータ構造を利用し、
静的制約カウントは、先行制約ファイルの読み出しに基づいて決定され、
動的制約カウントは、特定の部品の特定の機械タイプへの割り当てに関するスプリッタ・モジュールの決定に従う累積的な基準で決定される、
請求項１記載の方法。
【請求項８】
モジュラー最適化装置のうちの所定の一つの機械モジュールは、先行制約に従う部品と共に使用する複数のバケットの中から一つのバケットを選択することが予め割り当てられた部品と関連付けられた制約に違反する場合、低レベルのデザイアビリティが当該バケットに割り当てられる、
請求項１記載の方法。
【請求項９】
機械タイプのうちの所定の一つの機械タイプは、先行制約に従う部品に関するバケット・デザイアビリティが、先行制約の総累積数に対する事前先行制約の総累積数の比の関数として計算されるように構成されている、請求項１記載の方法。
【請求項１０】
機械タイプのうちの所定の一つの機械タイプは、部品が先行制約の総累積数に基づいて常に最初に保持されるように構成されている、請求項１記載の方法。
【請求項１１】
組立用のコンポーネントを配置するため使用される１台以上のコンポーネント配置装置が設けられた生産ラインの構造を決定するシステムであって、
生産ラインの少なくとも一部分の特性を示す情報を記憶するメモリと、
メモリに接続され、部品スプリッタ・モジュール、及び、各々が別個のコンポーネント配置装置タイプと関連付けられた複数の種々の機械モジュールを有するモジュラー最適化装置の少なくとも一部を実現するように動作するプロセッサと、
を有し、
モジュラー最適化装置は、
一つのコンポーネント配置機械タイプだけに当てはまる少なくとも第１の制約のクラスと、二つ以上のコンポーネント配置機械タイプに当てはまる第２の制約のクラスと、を含む先行制約の組を決定し、
対応した一つの機械モジュールにおいて所定の機械タイプと関連した第１の制約のクラスの各制約を処理し、
一つ以上の機械モジュールへの入力を提供する部品スプリッタ・モジュールにおいて第２の制約のクラスを処理し、
機械モジュールの出力は構造を決定するため使用される情報を提供する、
システム。
【請求項１２】
先行制約の組の第１の先行制約のクラスと第２の先行制約のクラスへの分割は、少なくとも部分的には、モジュラー最適化装置の部品スプリッタ・モジュールで行われる、請求項１１記載のシステム。
【請求項１３】
部品Ａと部品Ｂの両方の部品を機械タイプＭＴを用いて配置しなければならない場合に、部品Ａが部品Ｂよりも先に指定された基板に配置されなければならないことを規定するＡ  Ｂ  ＭＴの形式の所定の先行制約に対し、部品スプリッタ・モジュールは、
部品Ａと部品ＢのどちらもタイプＭＴの機械に割り当てることがなく、この場合に、制約を無視することができる割当と、
部品Ａと部品Ｂの両方をタイプＭＴの機械に割り当て、制約は第１の制約クラスに含まれ、機械タイプＭＴに対応した機械モジュールによって取り扱われる割当と、
部品Ａと部品Ｂのうちの一方をある機械タイプに割り当て、もう一方の部品を別の機械タイプに割り当て、制約は第２の制約クラスに含まれ、部品スプリッタ・モジュールによって取り扱われる割当と、
のうちのいずれかの割り当てを行う、
請求項１２記載のシステム。
【請求項１４】
組立用のコンポーネントを配置するため使用される１台以上のコンポーネント配置装置が設けられた生産ラインの構造を決定するモジュラー最適化装置であって、
部品スプリッタ・モジュールと、
各々が別個のコンポーネント配置装置タイプに関連付けられた複数の種々の機械モジュールと、
を有し、
当該モジュラー最適化装置は、
一つのコンポーネント配置機械タイプだけに当てはまる少なくとも第１の制約のクラスと、二つ以上のコンポーネント配置機械タイプに当てはまる第２の制約のクラスと、を含む先行制約の組を決定し、
対応した一つの機械モジュールにおいて所定の機械タイプと関連した第１の制約のクラスの各制約を処理し、
一つ以上の機械モジュールへの入力を提供する部品スプリッタ・モジュールにおいて第２の制約のクラスを処理し、
機械モジュールの出力は構造を決定するため使用される情報を提供する、
モジュラー最適化装置。
【請求項１５】
先行制約の組の第１の先行制約のクラスと第２の先行制約のクラスへの分割は、少なくとも部分的には、当該モジュラー最適化装置の部品スプリッタ・モジュールで行われる、請求項１４記載のモジュラー最適化装置。
【請求項１６】
部品Ａと部品Ｂの両方の部品を機械タイプＭＴを用いて配置しなければならない場合に、部品Ａが部品Ｂよりも先に指定された基板に配置されなければならないことを規定するＡ  Ｂ  ＭＴの形式の所定の先行制約に対し、部品スプリッタ・モジュールは、
部品Ａと部品ＢのどちらもタイプＭＴの機械に割り当てることがなく、この場合に、制約を無視することができる割当と、
部品Ａと部品Ｂの両方をタイプＭＴの機械に割り当て、制約は第１の制約クラスに含まれ、機械タイプＭＴに対応した機械モジュールによって取り扱われる割当と、
部品Ａと部品Ｂのうちの一方をある機械タイプに割り当て、もう一方の部品を別の機械タイプに割り当て、制約は第２の制約クラスに含まれ、部品スプリッタ・モジュールによって取り扱われる割当と、
のうちのいずれかの割り当てを行う、
請求項１５記載のモジュラー最適化装置。
【請求項１７】
組立用のコンポーネントを配置するため使用される１台以上のコンポーネント配置装置が設けられた生産ラインの構造を決定するため使用される一つ以上のソフトウェア・プログラムを記憶した機械読取可能な記録媒体であって、
上記ソフトウェア・プログラムは、
一つのコンポーネント配置機械タイプだけに当てはまる少なくとも第１の制約のクラスと、二つ以上のコンポーネント配置機械タイプに当てはまる第２の制約のクラスと、を含む先行制約の組を決定する機能と、
各々が一つの機械タイプに対応する複数の機械モジュールを含むモジュラー最適化装置の対応した一つの機械モジュールにおいて所定の機械タイプと関連した第１の制約のクラスの各制約を処理する機能と、
モジュラー最適化装置において一つ以上の機械モジュールへの入力を提供する部品スプリッタ・モジュールによって第２の制約のクラスを処理する機能と、
機械モジュールの出力が構造を決定するため使用される情報を提供する機能と、
を実現させるためのプログラムである、
記録媒体。
【請求項１８】
先行制約の組の第１の先行制約のクラスと第２の先行制約のクラスへの分割は、少なくとも部分的には、モジュラー最適化装置の部品スプリッタ・モジュールで行われる、請求項１７記載の記録媒体。
【請求項１９】
部品Ａと部品Ｂの両方の部品を機械タイプＭＴを用いて配置しなければならない場合に、部品Ａが部品Ｂよりも先に指定された基板に配置されなければならないことを規定するＡ  Ｂ  ＭＴの形式の所定の先行制約に対し、部品スプリッタ・モジュールは、
部品Ａと部品ＢのどちらもタイプＭＴの機械に割り当てることがなく、この場合に、制約を無視することができる割当と、
部品Ａと部品Ｂの両方をタイプＭＴの機械に割り当て、制約は第１の制約クラスに含まれ、機械タイプＭＴに対応した機械モジュールによって取り扱われる割当と、
部品Ａと部品Ｂのうちの一方をある機械タイプに割り当て、もう一方の部品を別の機械タイプに割り当て、制約は第２の制約クラスに含まれ、部品スプリッタ・モジュールによって取り扱われる割当と、
のうちのいずれかの割り当てを行う、
請求項１８記載の記録媒体。
【発明の詳細な説明】
【０００１】
本発明は、１９９９年４月５日に、発明者Ｌａｒｒｙ Ｊ． ＥｓｈｅｌｍａｎとＪ． Ｄａｖｉｄ Ｓｃｈａｆｆｅｒの名前で出願され、本願と同一出願人に譲渡され、参考のため引用される発明の名称が”Ｍｅｔｈｏｄ ｆｏｒ Ｏｐｔｉｍｉｚｉｎｇ ａ Ｌｉｎｅ ｏｆ Ｐｉｃｋ ａｎｄ Ｐｌａｃｅ Ｍａｃｈｉｎｅｓ”である米国特許出願第０９／２８６，０２６号明細書に記載された発明に関連する。
【０００２】
本発明は、一般的に、表面実装装置（ＳＭＤ）及びその他のコンポーネントをプリント基板（ＰＣＢ）上に組み立てる際に使用される、いわゆる「ピック・アンド・プレース」機械のようなコンポーネント配置機械に係り、特に、このような機械を構成する際に使用する最適化装置に関する。
【０００３】
ピック・アンド・プレース機械及びその他のタイプのコンポーネント配置機械を最適化する従来の技術は、発明者Ｌａｒｒｙ Ｊ． ＥｓｈｅｌｍａｎとＪ． Ｄａｖｉｄ Ｓｃｈａｆｆｅｒの名前で１９９５年２月１４日に発行された、発明の名称が”Ｍｅｔｈｏｄ ｆｏｒ Ｏｐｔｉｍｉｚｉｎｇ ｔｈｅ Ｃｏｎｆｉｇｕｒａｔｉｏｎ ｏｆ ａ Ｐｉｃｋ ａｎｄ Ｐｌａｃｅ Ｍａｃｈｉｎｅ”である米国特許第５，３９０，２８３号明細書と、発明者Ｊ． Ｄａｖｉｄ ＳｃｈａｆｆｅｒとＭｕｒａｌｉ Ｍａｎｉの名前で１９９９年１月２６日に発行された、発明の名称が”Ａｐｐａｒａｔｕｓ ｆｏｒ Ｏｐｔｉｍｉｚｉｎｇ ｔｈｅ Ｌａｙｏｕｔ ａｎｄ Ｃｈａｒｇｅ Ｍａｐｓ ｏｆ ａ Ｆｌｏｗｌｉｎｅ ｏｆ Ｐｉｃｋ ａｎｄ Ｐｌａｃｅ Ｍａｃｈｉｎｅｓ”である米国特許第５，８６４，８３３号と、発明者Ｊ． Ｄａｖｉｄ ＳｃｈａｆｆｅｒとＭｕｒａｌｉ Ｍａｎｉの名前で１９９９年６月１日に発行された、発明の名称が”Ｍｅｔｈｏｄ ｏｆ Ｏｐｔｉｍｉｚｉｎｇ ｔｈｅ Ｌａｙｏｕｔ ａｎｄ Ｃｈａｒｇｅ Ｍａｐｓ ｏｆ ａ Ｆｌｏｗｌｉｎｅ ｏｆ Ｐｉｃｋ ａｎｄ Ｐｌａｃｅ Ｍａｃｈｉｎｅｓ”である米国特許第５，９０９，６７４号と、に記載されている。これらの文献は、本願と同一出願人に譲渡され、参考のためここに引用されている。
【０００４】
上記の文献に記載された技術によって著しい進歩が得られたにもかかわらず、コンポーネント配置機械の最適化には更なる改良が必要である。例えば、既存のコンポーネント配置機械の最適化装置は、任意の数の先行制約、即ち、一方の部品が別の部品の前にその機械によって配置されなければならないことを定める制約を取り扱えるようにするため簡単に構成することができない。このような制約は、コンポーネント及び基板寸法の縮小化と関連した厳しい公差要件の結果として、徐々に重要になり始めている。したがって、任意の個数の先行制約を効率的に取り扱うことができるモジュラー最適化装置が必要とされていることは明白である。
【０００５】
本発明は、コンポーネント配置機械を最適化する改良された技術を提供する。本発明の一局面によれば、コンポーネント配置機械用のモジュラー最適化装置は、多数の先行制約を効率的な方式で取り扱うことができるように構成される。
【０００６】
より詳細には、本発明に従って構成されたモジュラー最適化装置は、１台以上のコンポーネント配置機械を含む生産ラインの構造を決定するため使用される。先行制約は、Ａ  Ｂ  ＭＴの形式でもよい。この形式は、部品Ａと部品Ｂの両方の部品を機械タイプＭＴを用いて配置しなければならない場合、部品Ａが部品Ｂよりも先に指定されたプリント基板（ＰＣＢ）若しくはその他のタイプの組立構造体に配置されなければならないことを規定する。所定の先行制約の組は、少なくとも、１種類のコンポーネント配置機械タイプだけに当てはまる第１の制約クラスと、２種類以上のコンポーネント配置機械タイプに当てはまる第２の制約クラスと、を含む。制約の種々のクラスへの割り当ては、どの部品がどの機械タイプに割り当てられるかに関するモジュラー最適化装置の部品スプリッタモジュールの決定に基づいている。先行制約の組の第１の先行制約クラスと第２の先行制約クラスへの分割は、少なくとも、モジュラー最適化装置の部品スプリッタ・モジュール内で部分的に行われる。
【０００７】
所定の機械タイプと関連付けられた第１の制約クラス中の各制約は、モジュラー最適化装置の対応した機械モジュールで取り扱われる。例えば、高速コンポーネント実装（ＦＣＭ）機械だけに関連付けられた制約は、モジュラー最適化装置のＦＣＭモジュールで取り扱われ、最新式コンポーネント実装（ＡＣＭ）機械だけに関連付けられた制約は、モジュラー最適化装置のＡＣＭモジュールで取り扱われる。第２の制約クラスは、モジュラー最適化装置の部品スプリッタモジュールで取り扱われる。その結果として、所定の先行制約と関連付けられた２個の部品が２種類の機械タイプに割り当てられた場合、スプリッタモジュールは、割り当てが実施可能であるかどうかを判定する。部品スプリッタ・モジュールの出力は、機械モジュールへ供給され、生産ラインの構造を決定する際に使用される情報を生成するため、機械モジュールで処理される。
【０００８】
本発明の別の局面によれば、形式Ａ  Ｂ  ＭＴの所定の先行制約に対し、部品スプリッタモジュールは、（ｉ）〜（ｉｉｉ）のいずれかの割り当てを行う。
（ｉ）部品Ａと部品ＢのどちらもタイプＭＴの機械に割り当てない。この場合、制約は無視することができる。
（ｉｉ）部品Ａと部品Ｂの両方をタイプＭＴの機械に割り当てる。制約は第１の制約クラスに含まれ、機械タイプＭＴに対応した機械モジュールによって取り扱われる。
（ｉｉｉ）部品Ａと部品Ｂのうちの一方をある機械タイプに割り当て、もう一方の部品を別の機械タイプに割り当てる。制約は第２の制約クラスに含まれ、部品スプリッタモジュールによって取り扱われる。
【０００９】
本発明の更なる局面によれば、先行制約の処理は、静的制約カウントと動的制約カウントを含むデータ構造を利用する。静的制約カウントは、一般的に、先行制約ファイルの読み出しに基づいて決定される。動的制約カウントは、一般的に、特定の部品の特定の機械タイプへの割り当てに関するスプリッタ・モジュールの決定に従う累積的な基準で決定される。
【００１０】
本発明は、先行制約を取り扱うためコンポーネント配置機械最適化装置を構成する技術を提供する。本発明は、例示的な生産ライン、コンポーネント配置装置及びモジュラー最適化装置の構成要素と共に説明される。しかし、これらの構成要素は、例示の目的のためだけに示されているものであり、本発明の範囲を限定することを意図していない。当業者には明白であるように、本発明によって提供される先行制約取扱機能は、これらの構成要素及びその他の構成要素の様々な別の配置を使用して実施され得る。
【００１１】
１．  生産ラインとコンポーネント配置機械の例
図１には、本発明によるモジュラー最適化装置を使用して構成される生産ラインの略図が示されている。生産ラインは、第１のコンポーネント配置機械１と、コンベヤ２と、第２のコンポーネント配置機械３と、を含む。プリント基板又はその他のコンポーネント取り付け用サポート構造体は、コンベヤ２上でラインの機械１及び３を通過する。コンポーネント配置機械１及び３の一方又は両方は、例えば、高速コンポーネント実装（ＦＣＭ）機械、又は、最新式コンポーネント実装（ＡＣＭ）機械であり、これらの機械は、技術的に公知であり、上記の米国特許第５，３９０，２８３号、第５，８６４，８３３号、及び、第５，９０９，６７４号と、上記の米国特許出願第０９／２８６，０２６号に記載されている。
【００１２】
同図には、１本のライン上に２台の機械が示されているが、本発明は、３台以上の機械を含む生産ライン、並びに、１台の機械だけを含む生産ラインにも適用可能である。その上、所定の生産ラインの機械には、多種類の機械タイプの各々について１台以上の機械が含まれる場合がある。
【００１３】
図２及び３は、図１の生産ライン内の一方若しくは両方の機械に使用されるＦＣＭ機械をより詳細に示す図である。より具体的に説明すると、図２には、１６台のピック・アンド・プレース若しくはピペット・モジュール（ＰＭ）を含むＦＣＭ機械の一例の平面図が示されている。図３には、ＰＭのうちの一台の斜視図が示されている。図示されたＦＣＭ機械は、本例の場合には、一連の１６台の独立したＰＭ６２の下でＰＣＢ６１の列を運ぶ搬送システム６０を含む。搬送システム６０は、（割り出しステップと呼ばれるステップで）次第に前進する。そのステップ間で、ＰＣＢはある期間だけ静止し、その期間中にＰＭは部品タイプを配置する。各ＰＭ６２は、（図２に示されるように機械の正面側に）対応した送り台６３を有する。この送り台６３には、様々なコンポーネント・フィーダー・タイプ６４（例えば、テープ、スティック、ばら積みフィーダーなど）を取り付けることができる。更に、各ＰＭ６２には幅があり、その幅の一部は、到達可能ゾーンにある。本例の場合、各ＰＭ６２の幅は１２０ｍｍであり、そのうちの８０ｍｍが到達可能ゾーンである。しかし、これらの寸法は簡単に変更できる。ＰＭ同士の干渉は許されない。
【００１４】
フィーダーは、送り台６３上の到達可能ゾーンに設置される。この目的のため、フィーダーは、フィーダー・スロットを通して、指定された間隔で取り付けられる。図２に示された例では、６個のフィーダー・スロットが示されている。搬送システム６０は、左から右へ移動する。新しいＰＣＢは、左端でコンベヤベルト若しくは可動機構に載ってＦＣＭへ入り、完成したＰＣＢは右端から送り出される。各ＰＭ６２は、ｘ方向（左から右）、ｙ方向（前から後）、ｚ方向（上下）、及び、φ方向（ｚ回りの回転）に独立した制御部を備えた一つの可動配置ヘッド６６を含む。各制御部は、様々な加速度と最大速度を設定できるので、ピック位置からプレース位置までの移動時間は、ｘ方向、ｙ方向及びφ方向の時間のうちの最大値である。ｚ方向の移動は、ピック動作とプレース動作に対して固定の遅延時間として考慮される。
【００１５】
各ＰＭ６２は、部品をピックアップ（捕捉）するための特定のノズル、正確な機械的アライメント用のφ方向配置ユニット、及び／又は、アライメント・オフセットを計算するためのビジョンシステムが取り付けられる。ノズルとφ方向配置ユニットの組み合わせは、グリッパと呼ばれ、ある寸法制限、形状制限、及び／又は、重量制限の範囲内で部品を配置することができる。各部品には、その部品専用の特定のグリッパタイプを設けてもよく、或いは、システムソフトウェアは、多数の代替的なグリッパの中から適切なグリッパを選択するように構成してもよい。
【００１６】
ＦＣＭの場合、最適化タスクは、配置されるべき各部品のｘ、ｙ及びφの位置を規定する部品リストと、対応したグリッパ、若しくは、代替的なグリッパとフィーダータイプのリストとが与えられ、ＦＣＭ機械のラインの仕様（機械の台数、各機械のＰＭの台数）が与えられるならば、本例では、ＰＣＢにすべての部品を載せるための所要時間を最小限に抑えるレイアウトとチャージ・マップ（ｃｈａｒｇｅ ｍａｐ）の組を生成する。これは、サイクルタイムの最小化と呼ばれる。その他の評価尺度をサイクルタイム評価尺度に代えて、或いは、加えて使用してもよい。例えば、セットアップ時間及び／又は切替時間を最小化すること、又は、最小サイクルタイムを達成することは、同時にフィーダー台数を最小限に抑えることになる。最適化は、ＦＣＭユーザが、使用される特定のタイプのグリッパ台数、及び／又は、特定の部品タイプを送るフィーダー台数に関する上限を予め指定できるようでなければならない。更に、ＦＣＭユーザは、特定のＰＭに割り当てられる特定のグリッパを自由に予め指定し、特定のフィーダー・スロットが特定の部品タイプを搬送しなければならないことを自由に予め指定できる必要がある。一部のＰＭ及び一部のフィーダー・スロットは、使用しないように予め指定される場合もある。
【００１７】
図２及び３に示された例示的なＦＣＭに関するより詳細な説明は、上記の米国特許第５，３９０，２８３号、第５，８６４，８３３号及び第５，９０９，６７４号に記載されている。
【００１８】
２．  モジュラー最適化装置の例
次に、図４及び５を参照して、本発明の解説のための実施例によるモジュラー最適化装置の一例を説明する。この最適化装置の一例は、上記の米国特許出願第０９／２８６，０２６号に詳述されているモジュラー最適化装置と類似しているが、本発明による先行制約取扱機能を組み込むように変更されている。しかし、本発明の技術は、より一般的に、先行制約を取り扱う機能を導入することが望ましいコンポーネント配置機械用の任意のタイプのモジュラー最適化装置に適用可能である。
【００１９】
図４は、本発明が実施されるモジュラー最適化装置の一例の略構成図である。図４に示されるような最適化装置は、実際には、汎用最適化装置であり、モジュラー型であってもなくてもよい。しかし、汎用最適化装置は、図５に示されるように構成された要素を含む場合には、モジュラー型である。従って、以下の説明では、図４の最適化装置をモジュラー最適化装置と呼ぶ。勿論、これは、一例に過ぎず、本発明は、他のタイプのモジュラー最適化装置を使用して実施することが可能である。
【００２０】
上述の通り、図４のモジュラー最適化装置は、図１のコンポーネント配置機械１、３を最適化するため使用され、本発明に従って、先行制約取扱機能を組み入れるように構成されている。モジュラー最適化装置は、遺伝的アルゴリズム（ＧＡ）１０１とヒューリスティック（発見的）レイアウト・ジェネレータ（ＨＬＧ）１０２とを実施するプロセッサ１１０を含む。プロセッサ１１０内において、遺伝的アルゴリズム１０１は、ヒューリスティック・レイアウト・ジェネレータ１０２と反復的に相互作用する。プロセッサ１１０は、機械１と３の内部に設けても外部に設けても構わない。
【００２１】
遺伝的アルゴリズム１０１は、図示されていないが、染色体ストリングの集団を保持する。染色体ストリングの長さ１２０は、初期化ステップ中に、ヒューリスティック・レイアウト・ジェネレータ１０２によって遺伝的アルゴリズム１０１へ供給される。この長さに応答して、遺伝的アルゴリズム１０１は、第１のストリング集団を生成する。その後の反復で、遺伝的アルゴリズム１０１は、遺伝的アルゴリズム１０１の特定のタイプに応じて、突然変異と交叉のうちの少なくとも一方を適用する。上記の米国特許に記載されているように、ＣＨＣは好ましいタイプである。しかし、他のタイプも同じように使用される。遺伝的アルゴリズム１０１は、制御パラメータ１０３として染色体ストリングをヒューリスティック・レイアウト・ジェネレータ１０２へ供給する。
【００２２】
ヒューリスティック・レイアウト・ジェネレータ１０２は、製造されるべき製品１０５、ライン構造（コンフィギュレーション）１０６、機械セットアップ及び仕様１０７を定義するファイルと相互に作用する。これらのすべては記憶装置１１１に保存されている。ヒューリスティック・レイアウト・ジェネレータ１０２は、染色体ストリング１０３と関連した適応度の指標を遺伝的アルゴリズム１０１に供給する。これらの指標は、上述のサイクルタイムのようなコスト関数である。遺伝的アルゴリズム１０１は、これらの適応度の指標を後の反復の際に使用する。
【００２３】
図４に例示されたサイクルは、定められた終了規準に達するまで繰り返される。
【００２４】
図５は、初期化終了後におけるヒューリスティック・レイアウト・ジェネレータ１０２の動作を詳細に説明する図である。同図に示されるようにヒューリスティック・レイアウト・ジェネレータ１０２は、部品スプリッタ・モジュール２０２と、ＦＣＭモジュール２０３と、ＡＣＭモジュール２０５とを含む。本例では、図１の機械１はＦＣＭ機械であり、機械３はＡＣＭ機械である場合を考える。ＦＣＭ機械にはＦＣＭモジュールが付随し、ＡＣＭ機械にはＡＣＭモジュールが付随する。
【００２５】
本発明によれば、部品スプリッタ・モジュール２０２は、先行制約の組２１５を利用できる。これらの制約は、図４の記憶装置１１１に記憶されている一つ以上の先行ファイルの形式でもよい。次に詳述するように、部品スプリッタ・モジュールは、所定の生産ラインに対する適切な構造を決定する際にその動作と関連して、このようなファイルにアクセスするか、又は、このようなファイルを供給される。
【００２６】
遺伝的アルゴリズム（ＧＡ）１０１から、ヒューリスティック・レイアウト・ジェネレータ１０２は、染色体ストリング２０８を受け取る。同図には、一つの染色体ストリングしか示されていないが、実際には、ヒューリスティック・レイアウト・ジェネレータは、遺伝的アルゴリズムによって生成された個々のストリングに基づいて動作する。染色体ストリング２０８の第１部分２０９は、部品が機械１と機械３の間でどのように分割されるかを制御するパラメータを表現する。染色体ストリング２０８の第２部分２１０は、第１の機械１のレイアウトを制御するパラメータを表現する。第１の機械１は、図２及び３に関して既に説明したように、ＦＣＭ機械であると仮定する。染色体ストリング２０８の第３部分２１１は、第２の機械３のレイアウトを制御するパラメータを表現する。第２の機械３は、上述のようにＡＣＭ機械であると仮定する。染色体ストリング２０８には一つ以上の他の部分があり、機械毎に使用される遺伝子が含まれている。染色体ストリングは、かなり少数のビットを有するように概略的に示されている。事実上、実際の染色体ストリングは、一般的にはもっと長く、例えば、１００乃至４０００ビットになる。更に、図５に示されているような染色体部分２０９、２１０及び２１１の順序は、自由に選択できる。同じ機能は、任意の順序の同じセグメントによって実現され得る。
【００２７】
本例は、二つの特定の機械タイプ、即ち、ＦＣＭ機械とＡＣＭ機械に関する例であるが、モジュラー最適化装置は、当業者によって、台数とタイプが異なる機械を含むラインにも同等に適用される。
【００２８】
ヒューリスティック・レイアウト・ジェネレータ１０２内では、最初に、スプリッタ・モジュール２０２が、機械１と機械３の間の部品割り付けを行うため染色体ストリング２０８の第１部分２０９の制御下で動作する。次に、モジュール２０３は機械１用のレイアウトを生成し、モジュール２０５は機械３用のレイアウトを生成する。モジュール２０３及び２０５は、上記の米国特許第５，３９０，２８３号、第５，８６４，８３３号、及び、第５，９０９，６７４号に記載された方式で動作する。例えば、これらのモジュールは、米国特許第５，３９０，２８３号に記載されているように別個のヒューリスティック・レイアウト・ジェネレータ・モジュールとして動作し、或いは、米国特許第５，８６４，８３３号に記載されているように、特定のタイプの機械を取り扱うことを目的としたライン型モジュールでもよい。本例には、１台のＦＣＭ機械と１台のＡＣＭ機械しか含まれていないが、各モジュール２０３及び２０５は、機械が同一タイプである限り、数台の機械のラインを実際に最適化することが可能である。
【００２９】
モジュール２０３と２０５の一方若しくは両方によって実行されるタスクの例を以下に列挙する。
タスク１：グリッパをＰＭ（又は、ＡＣＭ上のツール（若しくはノズル）交換ユニット）に割り当てる。
タスク２：送り台をピペット・モジュール（又は、ＡＣＭ用の棒状支柱）に割り当てる。
タスク３：フィーダータイプを送り台スロット（又は、トレイ置き台のトレイ及びパレット）に割り当てる。
タスク４：部品タイプをピック位置に割り当てる。
タスク５：個別の部品を特定のＰＭ割り出しステップ（ＦＣＭ）に割り当てるか、部品をチャージ（ＡＣＭ）に割り当てる。
タスク６：各割り出しステップ（ＦＣＭ）中に個別の部品の配置に順番を付ける。
タスク７：ＢＶＭ（ボード・ビジョン・モジュール）が存在する場合、ＢＶＭ画像化に順番を付ける。
【００３０】
モジュール２０３及び２０５がレイアウトを作成した後、モジュール最適化装置のモジュール２０４及び２０６は、これらのレイアウトに対するサイクルタイムの適応度指標を決定する。モジュール２０４及び２０６は、上記の米国特許第５，３９０，２８３号、第５，８６４，８３３号、及び、第５，９０９，６７４号に記載されているように構成される。次に、構成要素２０７は、モジュール２０４及び２０６によって生成されたコンポーネント・サイクル時間からライン全体の最大サイクル時間を決定する。本例には、２台のコンポーネント配置機械だけが含まれるが、モジュラー最適化装置は、より多くの台数の機械、並びに、種々のタイプの機械に対しても同じように拡張することができる。
【００３１】
上記のモジュラー最適化装置のモジュール方式は、新しい機械タイプの追加に特に巧く適合する。なぜならば、機械が追加されても、その度に染色体全体を再設計する必要がないからである。新しい機械タイプが追加された場合、新しいセグメントを追加するだけでよい。
【００３２】
ヒューリスティック・レイアウト・ジェネレータ１０２において、新しい機械タイプを追加したときに変更する必要のあるモジュールは存在しない。その代わり、モジュール２０３乃至２０６に類似した新しいモジュールが追加された機械のために図５の下方に追加される。
【００３３】
更に、１台の機械が変更された場合、その機械に関連したモジュールと染色体位置だけを変更すればよい。
【００３４】
構成要素２０７は、適応度の指標を遺伝的アルゴリズム１０１へ出力し、遺伝的アルゴリズム２０７は次のステップを繰り返す。この出力は、３個の位置を有するコストベクトルの形式でも構わない。ここで、
ｃｏｓｔ［０］は、失敗コードであり、ライン内の任意の機械タイプで生じる最高コードであり、このコードは、
０＝失敗なし
１＝ある機械タイプモジュールにおけるレイアウト失敗
の２個の値のうちの一方をとる。
ｃｏｓｔ［１］は、生産ラインにおける最低速機械に対するサイクルタイムであり、ｃｏｓｔ［０］＝１である場合、ｃｏｓｔ［１］は配置できない部品個数である。
ｃｏｓｔ［２］は、使用されるピック位置の総数である。
【００３５】
この３部分コストベクトルは、遺伝的アルゴリズムによって階層的に使用される。即ち、２個の染色体を比較したときに、より優れている染色体はコストの低い方の染色体であり、ここで、比較は、レベル０から始まり、均衡している場合に限り、次のレベルへ進む。任意の機械タイプモジュール２０３、２０５からの実行不可能なレイアウトのｃｏｓｔ［０］は、１である。両方の染色体が実行不可能なレイアウトを生じた場合、配置されない部品数の少ない方の染色体が優れている。両方の染色体が実行可能な解決手法を提示する場合、サイクルタイムのｃｏｓｔ［１］が比較され、両方が一致する場合、ピック位置の個数（必要なフィーダーの台数に略一致する）が均衡を破るために使用される。３種類のすべてのスコアが等しい場合、染色体は同等に適応していると考えられる。この仕組みによって、遺伝的アルゴリズム１０１は、実行可能な解を見つけることが困難な非常に難しい問題の解法を進展させ、サイクルタイムが一致する場合に、必要なハードウェアが少なくなる解を優先することができる。
【００３６】
遺伝的アルゴリズム１０１とヒューリスティック・レイアウト・ジェネレータ１０２の間の反復が合理的な解へ収束するように思われるとき、モジュール２０３及びモジュール２０５は、機械１及び機械３で使用される最終的なレイアウトを出力できる。
【００３７】
既に説明したように、本発明の解説のための実施例は、先行制約取扱機能を上述の例示的なモジュラー最適化装置に組み込む。以下で詳述するように、この機能の例示的なモジュラー最適化装置への組み込みは、部品スプリッタ・モジュール２０２と、ＦＣＭモジュール２０３と、ＡＣＭモジュール２０５の変更によって実現される。
【００３８】
３．  先行制約フォーマット
本発明の解説のための実施例において、先行制約は、上記のタイプのモジュラー最適化装置への入力として、以下のフォーマット：
Ａ  Ｂ  ＭＴ
を使用して規定される。このフォーマットは、部品Ａと部品Ｂの両方の部品が機械タイプＭＴによって配置される場合に、部品Ａが部品Ｂよりも先に指定されたプリント基板（ＰＣＢ）に配置されなければならないことを規定する。このような制約は、例えば、プリント基板上の部品Ａと部品Ｂが接近し、コンポーネント配置機械の精度に固有の限界がある場合に生ずる。上記のように表現された先行制約は、部品Ａと部品Ｂのいずれもが機械タイプＭＴによって配置されない状況に関しては何も規定していないことに注意すべきである。これらの部品が他の機械タイプについても制約されている場合、付加的な制約を規定しなければならない。解説のための実施例は、任意の個数の先行制約が規定されるように構成されている。これらの制約は、解説のための実施例では、ｐｒｅｃｅｄｅｎｃｅ．ｈｌｇと呼ばれる先行制約ファイルから最適化装置によって読み出される。このような一つ以上のファイルは、図５の部品スプリッタ・モジュール２０２によって利用される先行制約の組２１５に存在する。ｐｒｅｃｅｄｅｎｃｅ．ｈｌｇファイルの例は以下の通りである。
先行制約数＝２２
”１” １ ”２” １ Ｆ
”２” １ ”３” １ Ｆ
”３” １ ”４” １ Ｆ
”１” １ ”３” １ Ｆ
”１” １ ”４” １ Ｆ
”４” １ ”６” １ Ｆ
”４” １ ”７” １ Ｆ
”４” １ ”８” １ Ｆ
”４” １ ”９” １ Ｆ
”４” １ ”１０” １ Ｆ
”４” １ ”１１” １ Ｆ
”４” １ ”１２” １ Ｆ
”４” １ ”１３” １ Ｆ
”４” １ ”１４” １ Ｆ
”４” １ ”１５” １ Ｆ
”４” １ ”１６” １ Ｆ
”１６” １ ”２２” １ Ｆ
”２２” １ ”２３” １ Ｆ
”２３” １ ”２５” １ Ｆ
”２５” １ ”２６” １ Ｆ
”２６” １ ”２７” １ Ｆ
”２７” １ ”２８” １ Ｆ
【００３９】
上記の例で使用されるファイルフォーマットにおいて、各部品は、（引用符で囲まれた）項目コードと、回路番号とによって指定される。本例における機械タイプＦは、ＦＣＭ機械を表す。所定の先行ファイルにおける機械タイプ指定は、最適化装置に既知の機械タイプに限定される。
【００４０】
本発明の不可欠な構成要件ではないが、最適化装置は、衝突若しくはその他のエラーに関して先行ファイルをチェックする入力ルーチンを含み得る。このようなエラーは、先行ファイル内のサイクルによって明らかにされる。先行制約は推移的である。即ち、「＜」が先行関係を表す場合、「Ａ＜Ｂ  かつ  Ｂ＜Ｃ  ならば、Ａ＜Ｃ  である」が成り立ち、先行制約の組は、循環（サイクル）を内包すべきではない有向グラフであるとみなすことができる。グラフ内の循環を検出する技術では多数のアルゴリズムが公知である。このようなアルゴリズムのより具体的な例は、トポロジカル・アルゴリズムとして技術的に知られているタイプのアルゴリズムである。
【００４１】
先行制約を充足するように構成されたモジュラー最適化装置は、一般的に、生産ラインにおける機械の実際の（物理的な）順序を知る必要がある。上記の米国特許出願第０９／２８６，０２６号に記載されているような上述の例示的なモジュラー最適化装置は、一般的に、生産ラインにおける機械タイプを記述する一定の順序を定義する。この一定の順序は、（もしあるとすれば）ＦＣＭの後に（もしあるとすれば）ＡＣＭが続き、ｐａｒａｎｓ．ｈｌｇファイルという名前のファイルに規定される。解説のための実施例では、この順序は、物理的な順序であると仮定される。更に、機械タイプは、生産ライン内で混ざり合わないことを仮定する。即ち、あるタイプのすべての機械は一つにまとめられ、別のタイプのすべての機械がその後に続き、以下同様に続く。しかし、これらの仮定、並びに、説明中でなされるその他の仮定は、解説だけのための仮定であり、本発明の必須要件ではないことに注意する必要がある。
【００４２】
４．  一般的なアプローチ
解説のための実施例において、本発明は、上述のような先行制約を取り扱うモジュラー最適化装置を構成するための一般的なアプローチを提供する。この一般的なアプローチは、任意の数の種々の機械タイプに拡張可能であるが、実施例では、上記のＦＣＭ機械タイプ及びＡＣＭ機械タイプを使用して解説される。
【００４３】
一般的なアプローチによれば、先行制約は、通常、二つのクラスに分割される。第１のクラスは、１台の機械タイプだけに当てはまる先行制約を含む。これらの制約は、特定の機械タイプと関連した最適化装置モジュールによって取り扱われる。例えば、図４及び５を参照して説明した最適化装置では、ＦＣＭ装置に当てはまる先行制約は、ＦＣＭモジュール２０３によって取り扱われる。第２のクラスは、２台以上の機械タイプにかかわる先行制約を含む。これらの制約は、モジュラー最適化装置の部品スプリッタ・モジュールによって取り扱われる。この部品スプリッタ・モジュールは、以下では、簡単に「スプリッタ」のように呼ばれる。このようなモジュールの一例は、図５に関して説明した部品スプリッタ・モジュール２０２である。
【００４４】
各制約の表現が唯一の機械タイプだけを規定するとしても、スプリッタが所定の制約の二つの部分を別々の機械タイプに割り当てるならば、スプリッタは、割り当てが実行可能であることを保証する責任を担う。したがって、一般的に、制約が「機械タイプ内」の制約であるか、又は、「機械タイプ間」の制約であるかを判定することは、スプリッタの動作に依存するので、単純に制約のリストを読み出すだけではなし得ない。
【００４５】
次に、モジュール最適化装置の要素の間での制約取扱の責任分担の一例を説明する。上記の制約フォーマットを使用し、機械タイプＭＴ＝Ｆ（即ち、Ａ  Ｂ  Ｆという形式の制約）を規定することにより、以下のＰ１〜Ｐ３の３通りの可能性を確認することができる。
Ｐ１：スプリッタは、ＡとＢのいずれもＦＣＭ機械タイプに割り当てない。この場合、制約は無視することができる。
Ｐ２：スプリッタは、ＡとＢの両方をＦＣＭ機械タイプに割り当てる。この場合、制約はＦＣＭモジュールが責任を担う。
Ｐ３：スプリッタは、一方の部品をＦＣＭ機械タイプに割り当て、もう一方の部品を他の機械タイプに割り当てる。この場合、スプリッタは、分割が制約を満たすことを保証する責任を担う。機械モジュールは安全に制約を無視することができる。勿論、スプリッタは、ライン内の機械タイプの物理的順序を知ることが必要である。
【００４６】
５．  先行制約ブックキーピング
ブックキーピング処理は、本発明の技術に従って先行制約の取扱と共に利用される。このブックキーピング処理は、後述のＰＡＲＴ（部品）データ構造及びＢＵＣＫＥＴ（バケット）データ構造を含む多数のデータ構造を使用する。
【００４７】
５．１  部品データ構造
ブックキーピング処理は、上記のｐｒｅｃｅｄｅｎｃｅ．ｈｌｇファイルを読み込み、対応した制約を一つ以上の影響を受ける部品データ構造に格納することによって始まる。所定の部品に対する部品データ構造には、以下の要素：
ＰＡＲＴ＿ＰＲＥＣＥＤＥＮＣＥ＿ＩＴＭＥＳ ＊＊ｐｒｅｃ； ／＊部品が先行制約に関係する場合に限り必要になる項目＊／
が含まれる。
【００４８】
この要素は、機械タイプ毎に１要素を含む配列へのポインタである。所定の部品に対する先行情報を保持するための部品データ構造の要素の例を以下に記載する。
2004518192.tif 000003
2004518192.tif 000004
【００４９】
上記のデータ構造では、静的制約カウント（ｎ＿ｔｏｔａｌ＿ｃｏｎｓｔｒａｉｎｔｓ， ｎ＿ｐｒｅ＿ｃｏｎｓｔｒａｉｎｔｓ， ｎ＿ｐｏｓｔ＿ｃｏｎｓｔｒａｉｎｔｓ）と動的カウント（ｎ＿ｔｏｔａｌ＿ｃｕｍ＿ｃｏｎｓｔｒａｉｎｔｓ， ｎ＿ｐｒｅ＿ｃｕｍ＿ｃｏｎｓｔｒａｉｎｔｓ， ｎ＿ｐｏｓｔ＿ｃｕｍ＿ｃｏｎｓｔｒａｉｎｔｓ）との間に多数の相違が存在する。一つの相違は、ｐｒｅｃｅｄｅｎｃｅ．ｈｌｇファイルが読み込まれたときに、静的カウントと、その対応した部品インデックスのリスト（＊ｐｒｅ＿ｐａｒｔ＿ｉｎｄｅｘｅｓ， ＊ｐｏｓｔ＿ｐａｒｔ＿ｉｎｄｅｘｅｓ）が記入されることである。これらの静的カウントは、所定の部品が関係するすべての制約を含み、通常、決して変更されない。静的カウントは、動的カウントを計算するための制約情報のリポジトリである。動的カウントは、スプリッタが決定を行うたびに更新される可能性がある。なぜならば、スプリッタが決定を行った後、一部の制約は所定の機械タイプに当てはまらない場合があるからである。別の相違は、カウント名中の”＿ｃｕｍ”標示によって示されるように、動的カウントが累積されることである。その結果として、先行制約の推移性は再帰的に考慮される。その理由は、部品に対するバケットのデザイアビリティ（望ましさ）を決定するときに、累積されたカウントが使用されるからである。例えば、二つの先行制約”Ａ  Ｂ  Ｆ”と”Ｂ  Ｃ  Ｆ”が与えられた場合、静的カウントと動的カウントは、
Ａ：ｎ＿ｔｏｔａｌ＝１ ｎ＿ｐｒｅ＝０ ｎ＿ｐｏｓｔ＝１ ｎ＿ｔｏｔａｌ＿ｃｕｍ２ ｎ＿ｐｒｅ＿ｃｕｍ＝０ ｎ＿ｐｏｓｔ＿ｃｕｍ＝２
Ｂ：ｎ＿ｔｏｔａｌ＝２ ｎ＿ｐｒｅ＝１ ｎ＿ｐｏｓｔ＝１ ｎ＿ｔｏｔａｌ＿ｃｕｍ２ ｎ＿ｐｒｅ＿ｃｕｍ＝１ ｎ＿ｐｏｓｔ＿ｃｕｍ＝１
Ａ：ｎ＿ｔｏｔａｌ＝１ ｎ＿ｐｒｅ＝１ ｎ＿ｐｏｓｔ＝０ ｎ＿ｔｏｔａｌ＿ｃｕｍ２ ｎ＿ｐｒｅ＿ｃｕｍ＝２ ｎ＿ｐｏｓｔ＿ｃｕｍ＝０
となるであろう。
【００５０】
部品Ａの静的制約は一つだけであり、この静的制約は部品Ｂが部品Ａの後でなければならないことを規定するが、部品Ａは、２個の累積された制約を含む。なぜならば、部品Ｂと部品Ｃの両方が最終的に部品Ａの後に続かなければならないからである。
【００５１】
動的カウントは、上記のルーチンｓｕｍ＿ｐｒｅｃｅｄｅｎｃｅ＿ｃｏｎｓｔｒａｉｎｔｓ＿ｗｉｔｈｉｎ＿ｍｔ（）を使用して計算される。このルーチンは、最適化装置がＦＣＭ機械だけを取り扱う場合に、ルーチンｏｎｅ＿ｔｉｍｅ（）から呼び出される。最適化装置が多数の機械タイプを取り扱う場合には、動的カウント計算がワンタイムコードで実行されるとき、及び、動的カウント計算が染色体毎に改めて呼び出されなければならないときを決定するため、適当なロジックが簡単な方法で追加される。ルーチンｓｕｍ＿ｐｒｅｃｅｄｅｎｃｅ＿ｃｏｎｓｔｒａｉｎｔｓ＿ｗｉｔｈｉｎ＿ｍｔ（）は、先行制約の連鎖を辿るとき、データ要素再帰フラグをセットし、リセットする。このフラグは、同じ部品が多重にカウントされることを防止する。
【００５２】
５．２  バックアップデータ構造
本発明は、上記の米国特許第５，３９０，２８３号に記載されているようなバケットの概念を利用する。ヒューリスティック・レイアウト・ジェネレータ１０２は、割り出しステップ毎に各ＰＭに対してバケットを定義するように構成される。バケットは、部品が中に配置される容器であり、生産ラインを構成する際にバランスが維持されるべき容器である。本発明の解説のための実施例では、既存のバケットデータ構造、例えば、ＦＣＭ＿ＢＵＣＫＥＴ＿ＩＴＥＭＳデータ構造が、「ストライプ」、即ち、プリント基板上の指定された幅の目的の配置領域の配列と平行な一時的なシーケンス要素ｔｅｍｐ＿ｓｅｑを組み込むために構成される。この要素は、所定のプリント基板上のストライプがＰＭによってアクセスされる一時的なシーケンスを示す整数を保持するため使用される。これらの整数を決定するためのロジックは、ルーチンｆｃｍ＿ｓｅｔｕｐ＿ｂｕｃｋｅｔｓ（）に組み込まれる。このルーチンｆｃｍ＿ｓｅｔｕｐ＿ｂｕｃｋｅｔｓ（）は、好ましくは、
（１）２枚以上のプリント基板が任意の割り出しステップでＰＭからアクセスされる状況と、
（２）小さい割り出しステップが、２ステップ以上の割り出しステップの間にＰＭからアクセスできるように一部のストライプを残す状況と、
を取り扱う。
【００５３】
上記のルーチンｆｃｍ＿ｓｅｔｕｐ＿ｂｕｃｋｅｔｓ（）は、あらゆるＰＭが、少なくとも一つの割り出しステップの間に、ストライプ０と表される第１のストライプを見つけることを仮定している。尚、この仮定は、遺伝的アルゴリズムが割り出しステッピングの仕組みによって制御される場合、破られるかもしれない。例えば、このような配置では、ストライプ０への厳密な依存性は緩和され、処理は、下位のストライプ番号が現れたときに、そのストライプ番号に基づいてトリガーされるように一般化され得る。このルーチンは、更に、多数のプリント基板が割り出しステップ中にＰＭからアクセスできるとき、各ストライプ中に１回だけアクセス可能であると仮定する。例えば、ＰＭが４本のストライプを含む３枚のプリント基板にアクセス可能である場合を考える。この状況は、
プリント基板        ３  ３  ２  ２  ２  ２  １  １
ストライプ          １  ０  ３  ２  １  ０  ３  ２
アクセス可能性      否  否  否  否  可  可  可  可
のように表される。
【００５４】
この状況では、（右から左へ読むと）プリント基板１のストライプ２及び３の後にプリント基板２のストライプ０乃至３が続き、その後にプリント基板３のストライプ１と２が続く。右側から４番目までのストライプだけがアクセス可能であると考えられ、所定のストライプに向けられた部品をどのプリント基板が受け入れるかに関して曖昧さはない。
【００５５】
上記のルーチンｆｃｍ＿ｓｅｔｕｐ＿ｂｕｃｋｅｔｓ（）を例示的なプリント基板に適用すると次のようになる。これは、適当なトレースレベルが指定されたときに、トレースファイル、例えば、ｔｒａｃｅ．ｈｌｇに現れる表示の一部として見ることができる。
2004518192.tif 000005
【００５６】
本例のプリント基板は、２４０ｍｍのピッチと、６本の４０ｍｍ幅ストライプとによって構成され、割り出しステッピング処理は、８０ｍｍずつの３ステップを含む。偶数番目のＰＭは、割り出しステップ０でプリント基板の前縁（ストライプ０）から始まるストライプのペアを表す簡単なパターンを有することが分かる。括弧付きで示された一時的なシーケンスも０，１，２のように簡単である。しかし、奇数番目のＰＭは、割り出しステップ１においてストライプ０を見つけ、先行のプリント基板の最後のストライプ（５）と共にそのストライプ０が見える。そのため、一時的シーケンスは、ステップ１で０から始まるが、このシーケンス番号はストライプ０だけに付けられる。シーケンス１及び２は、それぞれ、ステップ２及び０でアクセスできるストライプに適用され、４番目のシーケンス、例えば、シーケンス［３］は、次にステップ１へ戻り、ストライプ５に対して必要になる。上記の一時的シーケンスをサポートするため構成されたＦＣＭモジュール２０３のルーチンａｓｓｉｎｇ＿ｐａｒｔｓ（）は、所定のＰＭに割り当てられた２個の部品が適当なシーケンスに置かれているかどうかを判定することができる。
【００５７】
６．  先行制約を取り扱うためのＦＣＭモジュール構成
本発明によれば、図４及び５を参照して説明した例示的なモジュラー最適化装置のＦＣＭモジュール２０３は、上記の先行制約の取扱を容易に行えるように構成される。一例として、ＦＣＭモジュール２０３の従来のルーチンａｓｓｉｇｎ＿ｐａｒｔｓ（）は、先行制約違反検出と、バケット・デザイアビリティ判定と、新部品ソーティング技術を組み込むように修正される。次に、これらの各修正について説明する。
【００５８】
６．１  制約違反検出
上述のようにＦＣＭモジュール２０３のルーチンａｓｓｉｇｎ＿ｐａｒｔｓ（）は、先行制約の違反をチェックするように構成される。このようなチェックは、上記のルーチンｃｈｏｏｓｅ＿ｂｕｃｋｅｔ＿ｆｃｍ（）に組み込んでもよい。より詳細には、考えられる各バケットが調べられたとき、配置される部品が先行制約に関係するならば、このバケットを選択することが既に割り当てられた他の部品に関する制約に違反するかどうかを判定するためにチェックが行われる。違反する場合、このバケットには、望ましさ（デザイアビリティ）として、
ｄｅｓｉｒａｂｉｌｉｔｙ＝ＶＥＲＹ＿ＵＮＤＥＳＩＲＡＢＬＥ
が与えられ、その結果として、このバケットは決して選択されない。勿論、的確なバケットが見つからない場合もあるが、その場合には、部品は割り当てられず、結果として、実行不可能なセットアップになる。
【００５９】
制約違反のチェックは、他の「事前（ｐｒｅ）」制約部品がＰＭよりも先に割り当てられている場合には、違反が起こり得ない、ということを前提としている。このチェックは、「事後（ｐｏｓｔ）」制約部品及び後のＰＭという類似した前提を含む。部品がＰＭ［ｉ］によって配置される前に、部品がＰＭ［ｉ＋１］によって配置されることは、技術的に起こり得る。なぜならば、すべてのＰＭは所定の割り出しステップの間に同時に動作するからである。この状況において興味のある問題は、このような２個の部品が、ＰＭ［ｉ］によって配置された部品がＰＭ［ｉ＋１］に関する部品の後に配置されたと考えられる、という先行制約に含まれ得るかどうか、という点である。このことは起こり得ないように思われる。なぜならば、ＰＭ間のギャップよりも分離された２個の部品が先行制約に関与することを要求するからである。制約された部品ペアの連鎖がＰＭ間の間隔で広がることは考えられるが、このような状況では、連鎖の両端の部品が同じ割り出しステップ中に２個の隣接したＰＭに割り当てられるとは考えられない。上記の制約違反のチェックは、実際のアプリケーションでは安全であると考えられる。尚、このチェックは、解説のための例であり、上記の前提が当てはまらないようなその他のチェックを使用しても構わない。
【００６０】
このチェックは、２個の制約された部品が同じＰＭに割り当てられる状況を取り扱うことを目的としている。この状況では、両方の部品を同じ割り出しステップに割り当てることが許可される。なぜならば、先行関係は、配置順序を入れ替えることによって常に達成されるからである。部品が別の割り出しステップに割り当てられたとき、関係したストライプは違反を検出するために調べられる。一時的シーケンスも上述の方法で調べられる。
【００６１】
６．２  バケット・デザイアビリティ
先行制約に関連していない部品は、ゆっくりとした時間に基づくバケット・デザイアビリティを使用する。部品が先行制約に関与し、当該バケットがいずれの制約にも違反していない場合、そのバケット・デザイアビリティは、
ｂｕｃｋｅｔ＿ｄｅｓｉｒａｂｉｌｉｔｙ＝ｎ＿ｆｃｍ＿ＰＭｓ−ａｂｓ（ＰＭ＿ｉ−ＰＭ＿ｊ）
にしたがって計算される。式中、ｎ＿ｆｃｍ＿ＰＭｓは、ＦＣＭライン内のＰＭの台数を表し、ＰＭ＿ｉは、当該バケットのＰＭを表し、ＰＭ＿ｊは、部品に対する「理想的な」ＰＭを表す。ＰＭ＿ｊは、
ＰＭ＿ｊ＝（ｎ＿ｆｃｓ＿ＰＭｓ−１）＊ｎ＿ｐｒｅ＿ｃｕｍ＿ｃｏｎｓｔｒａｉｎｔｓ（ｉ）／ｎ＿ｔｏｔａｌ＿ｃｕｍ＿ｃｏｎｓｔｒａｉｎｔｓ（ｉ）
として計算される。
【００６２】
図６は、上記のバケット・デザイアビリティ関数が、例示的な１６台のＰＭ  ＦＣＭ機械の場合に、理想的なＰＭのＰＭ＿ｊの３通りの値、即ち、ＰＭ＿ｊ＝０， ８， １６に対して、ＰＭの台数と共に変化する様子を示すグラフである。
【００６３】
このバケット・デザイアビリティ関数は、特に、多数の部品が制約されているときには、過度に融通が利かないことに注意する必要がある。しかし、その性能は、制約された部品タイプ毎に遺伝子を作成することによって実質的により柔軟にすることができる。この遺伝子は、ＰＭ＿ｊの公称位置からのシフトをコード化したものに相当し、即ち、使用されるＰＭ＿ｊの値は、公称ＰＭ＿ｊと遺伝子値の合計である。かくして、１台のＦＣＭに対し３ビット、２台のＦＣＭに対し４ビットが使用され、以下同様である。これにより、ＦＣＭラインのＰＭの台数の半分までの遺伝子制御型シフトが可能になる。部品タイプに事後制約がない場合、その公称ＰＭ＿ｊは、ラインの端にあるので、遺伝子は、左へのシフトだけをコード化する。同様に、事前制約がない場合、右へのシフトだけがコード化される。事前制約と事後制約の両方がある場合、シフト範囲は、おおよそ左半分と右半分である。尚、ＰＭ＿ｊは、ＦＣＭのＰＭの正当な範囲外へシフトされることはないことに注意する必要がある。
【００６４】
６．３  部品ソーティング
本発明の解説のための実施例は、部品に対して以下のソーティング処理を使用する。先行制約が存在する場合、部品は、最初に、ｎ＿ｔｏｔａｌ＿ｃｕｍ＿ｃｏｎｓｔｒａｉｎｔｓによってソートされ、次に、通常のモジュラー最適化装置と同じように染色体によって指示された深江Ｔ期名ソーティング処理が行われる。このアプローチは、最大のフレキシビリティの時点でのバケットにおける最初のショットを、最も制約された部品に与える。殆どのアプリケーションでは、先行制約を用いて部品数を最小限に抑えるか、又は、制限することが望ましい。なぜならば、制約違反を回避することによりバランスが悪くなるからである。制約された部品よりも制約されていない部品の方が多数存在する場合、制約されていない部品は、通常の緩やかなデザイアビリティを使用して追加されるときに、バランスを改良する。
【００６５】
６．４  部品順序付け
ルーチンｓｅｑｕｅｎｃｅ＿ｐａｒｔｓ＿ｉｎ＿ｂｕｃｋｅｔ（）は、各割り出しステップでＰＭによって配置された部品の最終的な順序付けを行う。上記の米国特許第５，３９０，２８３号に記載されているように、このようなルーチンの一つの考えられる実施形態は、最大のｐｐ＿ｔｉｍｅの部品を最初に並べ、次に大きいｐｐ＿ｔｉｍｅの部品を最後に並べ、それらの間で、部品は、スロット／ピックによってソートされる。最初の部品及び最後の部品は、ＰＭヘッドの動きと、搬送システムの動きの間の重なり合いを最大限にするためこのようにして選択される。これらの２個の部品の間で、ヘッドは、割り出しステップのパリティに応じて、左から右へ、或いは、右から左へ通過する。即ち、ヘッドは、最初に一方向へ移動し、次に、ステップ毎に交互に反対方向へ移動する。
【００６６】
本発明によれば、この通常のルーチンは、バケット内の部品に適用される（もしあれば）先行制約を考慮するため、上記の実施形態から変更される。ローカルデータ構造であるｂｕｃｋｅｔ＿ｐａｒｔ＿ｇｒｏｕｐは、これらのローカル先行制約が見つかった場合、或いは、見つかったときに、これらの先行制約を把握するため、要素を組み込むように構成され、ルーチンは、制約を見つけ出し、カウントするロジックを収容するように変更される。このような状況で使用される用語「ローカル」は、同じバケット内の部品を参照する。
【００６７】
最大のｐｐ＿ｔｉｍｅを含む部品を見つけるロジックは、この部品にはこの部品よりも先に配置されなければならない他のローカル部品がないこと、即ち、この部品には事前制約がないということを保証するため変更された。バケット内のすべての部品が相互に制約されているとしても、バケット内事前制約の無い部品が必ず１個存在する。同様の変更が、２番目に大きいｐｐ＿ｔｉｍｅを有する部品を見つけるロジックに対して行われる。この変更は、事後制約の無いことを保証する。すべての部品が従来の方法でソートされた後、先行制約が違反されていないことを保証する新しい演算が適用される。この新しい演算は、最初に、最初の配置位置に対して考えられている部品がバケット内事前制約の無い部品であり、最後の配置位置に置かれる部品は事後制約の無い部品であることを保証する。最初の配置位置と最後の配置位置の間の部品は、従来の方法でソートされた後、あらゆる制約違反を訂正するバブル・ソートを用いて最終的に一掃される。
【００６８】
７．  ＦＣＭモジュールに対する更なる変更
解説のための実施例におけるモジュラー最適化装置のＦＣＭモジュール２０３に対して行われるその他の変更には、グリッパ・デザイアビリティと、ルーチンａｓｓｉｇｎ＿ｇｒｉｐｐｅｒｓに対する変更が含まれる。従来のこれらの要素は、上記の米国特許第５，３９０，２８３号に記載されている。
【００６９】
グリッパ・デザイアビリティの場合、先行制約を守る可能性を反映した新しい要因が付け加えられる。これは、スプリッタに関して後述される要因と類似しているが、グリッパレベルで適用される（即ち、グリッパが操作できる部品よりも前に配置されるべき部品の個数を指定する。）。スプリッタで使用される要因と同様に、この要因は、事後制約を含む多数の部品に関するグリッパに対しＦＣＭラインの正面側のＰＭを優先する傾向があり、事前制約を含む多数の部品に関するグリッパに対しＦＣＭラインの背面側のＰＭを優先する傾向がある。事前制約と事後制約が略同数のグリッパは、ラインの中ほどのＰＭを優先する。制約のある部品と殆ど関連付けられていないグリッパは、非常に大きい自由度がある。
【００７０】
ルーチンａｓｓｉｇｎ＿ｇｒｉｐｐｅｒは、最初に、先行制約のあるグリッパを割り当て、制約のないグリッパを後で割り当てるために残しておくように構成されるべきである。このようなルーチンａｓｓｉｇｎ＿ｇｒｉｐｐｅｒｓは、以下の３フェーズを含み、即ち、（１）先行制約のあるグリッパに対する実施可能性を獲得するために最初に割り当て、（２）先行制約の無いグリッパに対する実施可能性を獲得するために次に割り当て、（３）指定されたバランス用の目標を達成するため最終的に割り当てる。
【００７１】
グリッパレベルにおけるカウントｎ＿ｐｒｅ＿ｃｏｎｓｔｒａｉｎｔｓとｎ＿ｐｏｓｔ＿ｃｏｎｓｔｒａｉｎｔｓが略一致するときには、上記のアプローチのようにすべてのグリッパを中間に向けて置くよりも、ラインの正面側に一部のグリッパを割り当て、背面側に別のグリッパを割り当てる方が好ましい。一般に、ルーチンａｓｓｉｇｎ＿ｇｒｉｐｐｅｒｓの変更を始めるかどうかの判定は、グリッパの割り当てが先行制約を充足する際に問題を生ずるという観察に基づいて行われるべきである。
【００７２】
上記のグリッパ・デザイアビリティに対する変更は、以下のようにテストされる。最初に、制約は、対象としているグリッパによって操作できない別の部品によって制約された部品だけを考慮しているグリッパ毎に集計される。換言すると、同じグリッパによって操作可能な２個の部品に関連した制約は考慮されない。次に、先行要因重み（ビット値０、１、２及び３に対して、それぞれ、０、２、４及び６）をコード化した遺伝子（２ビット）がグリッパ毎に生成される。ＧＤ［ｉ］が上述のように（即ち、事前割当と割り付けステッピングを考慮し、先行制約を考慮せずに）計算されたＰＭ［ｉ］に対するグリッパ・デザイアビリティであると仮定し、ＧＤ＿ＲがすべてのＦＣＭ  ＰＭのこれらの値の範囲（即ち、最小値から最大値）であると仮定する。ＰＤ［ｉ］は、グリッパの事前制約及び総制約を使用した点を除くと、上述の部品バケット・デザイアビリティと全く同様に計算されたグリッパのＰＭ［ｉ］に対する先行デザイアビリティであるとする。Ｇは、このグリッパの遺伝子によって与えられる先行要因重みであるとする。ＰＭ［ｉ］に対して実際に使用されるグリッパ・デザイアビリティ（ｕｓｅｄ＿ＧＤ［ｉ］）は、
ｕｓｅｄ＿ＧＤ［ｉ］＝ＧＤ［ｉ］＋ＧＤ＿Ｒ＊ＰＤ［ｉ］＊Ｇ
として計算される。
【００７３】
図７には、上記の遺伝子の値０、２、４及び６の各々を使用して、１６台のＰＭを含むＦＣＭ機械と一つの事前制約だけを関係するグリッパに対する使用グリッパ・デザイアビリティｕｓｅｄ＿ＧＤ［ｉ］のグラフの組が示されている。本例では、ＰＤ［ｉ］はＰＭ［０］に対する０から、ＰＭ［１５］に対する１５／１６まで増加する。
【００７４】
８．  部品スプリッタ・モジュールの変更
解説のための実施例において、部品スプリッタ・モジュール２０２は、上述の汎用アプローチと共に記述された処理機能を含む。本発明に従って先行制約の取扱を容易に行うため、少なくとも二つの付加的な変更が部品スプリッタ・モジュールに対して行われる。これらの各変更は、後で詳述される。
【００７５】
上記の変更のうちの第１の変更は、先行制約を守る分割を優先する傾向が得られるようにｐａｒｔ＿ｔｙｐｅ−ｓｐｌｉｔｔｉｎｇ（部品タイプ分割）ロジックを変更する。この変更には、機械タイプ毎に別の要因をｐａｒｔ＿ｔｙｐｅグループ（ｐｔｙｐｅ＿ｇｒｏｕｐ）ソートに追加することが含まれる。新しい要因は、そのｐｔｙｐｅ＿ｇｒｏｕｐ内のある部品よりも先に配置しなければならない部品の数（即ち、先行制約の数）によって部品タイプをソートする。この要因は、生産ラインの最初と最後で機械タイプに対し逆の形式で取り扱われるべきである。
【００７６】
次に、第１の変更のより詳細な例を説明する。本例のアプローチは、ＦＣＭモジュール２０３に関して既に説明したアプローチと類似しているが、事前制約及び事後制約の数のカウントに依存するのではなく、このような制約の連鎖の最大長さに依存する。
【００７７】
本例のアプローチによれば、部品スプリッタ・モジュールは、機械タイプの各ｐｔｙｐｅ＿ｇｒｏｕｐへの割り当てを偏らせ、ｐｔｙｐｅ＿ｇｒｏｕｐ内の部品タイプを順序付けること（或いは、部品が機械タイプの間で分割されている単一の部品タイプからなる特殊なｐｔｙｐｅ＿ｇｒｏｕｐ内の部品の順序付け）により、事前先行制約及び事後先行制約を取り扱うように構成される。
【００７８】
各ｐｔｙｐｅ＿ｇｒｏｕｐは、典型的に、デフォルト機械タイプが割り当てられる。デフォルト機械タイプは、一般的に、染色体決定され。即ち、機械タイプの順番（ｍｔｙｐｅ＿ｏｒｄｅｒ）で列挙された最初の機械タイプである。しかし、多数の部品タイプが存在し、染色体決定高速デフォルト・ヒューリスティック（ｆａｓｔ＿ｄｅｆａｕｌｔ＿ｈｅｕｒｉｓｔｉｃ）がオンにされている場合（この場合に、デフォルトは最高速の機械タイプにセットされる）、又は、半分よりも多数の部品タイプがある機械タイプに予め割り当てられている場合（この場合には、この機械タイプが選択される）のいずれかの場合に、デフォルト機械タイプは書き換え可能である。事前先行制約及び事後先行制約を取り扱うため、染色体決定されたデフォルト機械タイプを書き換えるために、付加的な条件が加えられる。
【００７９】
所定のｐｔｙｐｅ＿ｇｒｏｕｐ内の殆どの部品タイプは、対応したデフォルト機械タイプで終わるが、一部の部品タイプは、他の機械タイプ上で配置のため選択され得る。これらの部品タイプは、リストの上方の部品タイプ選択する方向のバイアスを用いて、部品タイプのｐｔｙｐｅ＿ｇｒｏｕｐのリストから選択される。（部品タイプの）ソートリストは、ｐｔｙｐｅ＿ｇｒｏｕｐの機械タイプ毎に保持される。部品タイプは、部品タイプ当たりの部品数と、対象とする機械タイプに予め割り当てられているかどうかとに応じて格納される。事前先行制約及び事後先行制約によって部品タイプの割り当てに偏りを設けることができるように、付加的なソート順序条件を付け加えてもよい。
【００８０】
上述の通り、ＦＣＭモジュールは、部品毎に事前先行制約及び事後先行制約のカウントを利用する。ＦＣＭモジュールは、制約を通る方法をつなぐ再帰的ルーチンによってこれらの制約をカウントする。更に、見つけられた制約の個数ではなく、連鎖の長さの方が部品スプリッタ・モジュールにより関連している。したがって、部品スプリッタ・モジュールは、部品毎に（及び部品タイプ毎に）、最長事前制約連鎖と最長事後制約連鎖を決定する。部品タイプの連鎖は、（特殊なスプリットｐｔｙｐｅ＿ｇｒｏｕｐを除いて）最も関連性のある連鎖であるが、以下では、より簡単な部品の連鎖から説明を始める。
【００８１】
連鎖の決定の仕方を説明するため例を用いる。この例では、以下の標識付けの慣例を使用する。部品タイプは、大文字、例えば、Ａ、Ｂ、Ｃなどによって特定される。部品は、部品が属する部品タイプを示す大文字と、大文字の後に続く数字を用いて、例えば、Ａ１、Ａ２、Ｂ１、Ｂ２などのように識別される。
【００８２】
一つの複雑な問題をここで指摘しておく必要がある。制約は機械タイプを用いて詳述される。かくして、部品Ａ５と部品Ｂ３がＦＣＭ上で制約されている場合、Ａ５  Ｂ３  Ｆのような制約が存在する。しかし、これらの部品がＡＣＭによっても配置可能であるならば、ＡＣＭに対して類似した制約：Ａ５  Ｂ３  Ａが存在する。衝突の無い限り、例えば、異なる機械タイプに対して逆の順序が無い限り、一般に、制約の合併を使用するべきである。換言すると、機械タイプは、連鎖を計算するときに無視され、（異なる機械タイプに対する）重複したレコードは一つのレコードとして取り扱われる。衝突は、例えば、衝突用の先行ファイルをチェックする入力ルーチンを使用して、上述のように検出され対処される。
【００８３】
部品の連鎖を解説する例に戻ると、部品Ｃ１は部品Ｂ３の後に配置されるべきであり、部品Ｂ３は部品Ａ５の後に配置去れるべきである場合、部品Ａ５は、少なくとも長さ２の事後連鎖：Ａ５−＞Ｂ３−＞Ｃ１をもつ。部品Ｃ２は部品Ｂ３の後に配置され、部品Ｄ４は部品Ｃ２の後に配置されなければならない場合、Ａ５は、少なくとも長さ３の事後連鎖：Ａ５−＞Ｂ３−＞Ｃ２−＞Ｄ４をもつ。制約が１個しかない場合、以下の事前連鎖長さ及び事後連鎖長さ（括弧内）は各部品に割り当てられる。
Ａ５（０，３）−３
Ｂ３（１，２）−１
Ｃ１（２，０）２
Ｃ２（２，１）１
Ｄ４（３，０）３
最終列は、正味の連鎖長さを表し、即ち、事前連鎖長さと事後連鎖長さの差を表す。
【００８４】
部品タイプ連鎖は、同様にして決定され、屡々、最大連鎖長さのその部品タイプの部品の連鎖の長さと一致する。例えば、上記例では、部品タイプＣは、連鎖のある２個の部品を含み、Ｃ２は最大長の連鎖を有する。よって、部品タイプＣの最大事前連鎖及び最大事後連鎖は、２及び１である。しかし、部品タイプＤが部品Ｅ１に対する事前制約である部品Ｄ１を含む場合を考える。部品Ｄ１は、部品Ｃ２の連鎖のメンバーではないが、部品タイプＣ’のメンバーであろう。各部品タイプ（上記の特殊なスプリット部品タイプを除く）は一つの機械タイプに割り当てられるので、部品タイプの連鎖は、一般に、部品タイプのすべての部品について計算されるべきである。別の例は、この点を明瞭にするために役立つ。部品Ｇ１が部品Ｈ１の前に配置され、部品Ｈ２が部品Ｉ２の前に配置され、部品Ｉ２が部品Ｊ３の前に配置されるべき場合を考える。このとき、部品に対する事前連鎖及び事後連鎖は、以下の通りである。
Ｇ１（０，１）−１
Ｈ１（１，０）１
Ｈ２（０，２）−２
Ｊ２（１，１）０
Ｊ３（２，０）２
【００８５】
部品タイプに対する事前連鎖及び事後連鎖は以下の通りである。
Ｇ（０，３）−３
Ｈ（１，２）−１
Ｉ（２，１）１
Ｊ（３，０）３
【００８６】
連鎖長さを使用するのではなく、ＦＣＭに使用された方法と同様の方法で事前コネクション及び事後コネクションの数を使用してもよい。しかし、部品タイプの場合にコネクションとしての考慮は、連鎖長さの場合と同じように行われる。例えば、二つの部品タイプのある部品が接続されている限り、これらの部品タイプは接続されていると考えられる。所定のアプリケーションで使用するために最も適当な具体的なアプローチは、当業者には明らかであるように、一般的に、アプリケーション固有要因の多様さに依存する。
【００８７】
尚、正味の総連鎖長さは、一般的に、ｐｔｙｐｅ＿ｇｒｏｕｐ毎に計算されるべきである。これは、ｐｔｙｐｅ＿ｇｒｏｕｐ内の部品タイプの正味の部品タイプ連鎖のすべてを合計することによって（或いは、特殊なスプリットｐｔｙｐｅ＿ｇｒｏｕｐの場合には、正味の部品タイプ連鎖のすべてを合計することにより）行われ得る。しかし、正が負を打ち消し、ゼロサムが得られる場合と、制約が無く、ゼロサムが得られる場合とを区別することも可能である。前者の場合、ゼロサムのｐｔｙｐｅ＿ｇｒｏｕｐは、ラインの中程へ向かい、一方、後者の場合、ｐｔｙｐｅ＿ｇｒｏｕｐは（少なくともこの規準に基づいて）どちらへ進んでも構わない。
【００８８】
上記の連鎖情報は、次のように使用される。ｐｔａｙｐｅ＿ｇｒｏｕｐの正味の総連鎖長さは、染色体決定デフォルト機械タイプが書き換えられるべきであるかどうかを判定するため使用される。その値が大きい負の数である場合、デフォルト機械タイプは、ラインの先頭の機械タイプでもよい。その値が大きい正の数である場合、デフォルト機械タイプはラインの最後の機械タイプでもよい。大きさが等価的である大きい正の数及び大きい負の数によって表現された単一の固定閾値は、簡単な方法で経験的に決定される。或いは、固定の単一の閾値ではなく、染色体に基づいて多数の閾値を決定してもよい。例えば、３種類の閾値と、閾値を使用しない４番目の値とを決定する２ビットの遺伝子が存在する。各閾値は、正と負の両方の値に使用される。
【００８９】
染色体決定されたデフォルト機械タイプ、即ち、部品タイプの数と、事前割当と、先行制約とを書き換えるときを決定する多数の規準は、重要性の順番に並べられるべきである。一般的に、事前割当規準は、部品タイプ数規準よりも優先し、先行制約規準は事前割当規準よりも優先すべきである。或いは、後の二つの規準は、サイズ（例えば、事前割当の個数、又は、正味の連鎖のサイズ）に関して変化するので、規準の相対的なサイズに基づくデフォルト順序付けが使用される。例えば、部品タイプの３分の２以上が特定の機械タイプに事前割当されている場合、これは、連鎖サイズの絶対値が指定された閾値、例えば、５よりも小さいならば、異なる機械タイプを示す正味のネットサイズよりも優位になる。或いは、染色体のビットは、競合が存在する場合にどちらの規準を優先すべきかを決定するため使用される。
【００９０】
次に、連鎖情報がｐｔｙｐｅ＿ｇｒｏｕｐｓ内の部品タイプを順序付けるため使用される方法を説明する。ここでも、適切な情報は正味の連鎖長さであるが、本例では、部品タイプに関する情報であるとする。一般的に、大きい負の値をとる部品タイプは、ラインの前の方にある機械タイプに対するリストの始めに置かれるべきであり、ラインの後ろの方にある機械タイプに対してはその逆が成り立つ。
【００９１】
上記の特別のスプリットｐｔｙｐｅ＿ｇｒｏｕｐの場合、順序付けは部品の正味の連鎖長さに基づいていることに注意する必要がある。
【００９２】
また、部品タイプを順序付けするとき、衝突規準を統合することが重要である。正味の連鎖長さの他に、部品数の規準と事前割当の規準がある。先行制約は、一般的に、部品数よりも重要な規準であるので、最初のソート規準とすべきである。しかし、正味の連鎖長さをバンドに分類し、バンド内で部品数に基づいてソートし、最後に、事前割当規準に基づいてソートすることも有効である。例えば、−２未満の正味の連鎖、−２乃至２の正味の連鎖、２よりも大きい正味の連鎖の三つのバンドがある。
【００９３】
代替案として、ソートリストを機械タイプから分離し、その代わりに、幾つかのソートリストを保持し、染色体に使用するリストを決定させる。この代替案の潜在的な問題点は、部品タイプ割当順序が固定のソートリストと対応しなくなり、その意味が染色体によってどのソートリストが選択されたかに応じて変ることである。このため、遺伝的アルゴリズムは、使用すべきリストを見出すことが困難になり、例えば、不安定化する。しかし、この問題は、ソートリスト内の部品タイプを実際にソートする代わりに、ソートされたインデックスのリストを保持することによって解決することができる。同じリストは、ｐｔｙｐｅ＿ｇｒｏｕｐの部品タイプインデックス（ｐｔｙｐｅ＿ｉｎｄｅｘ）値及び部品タイプ割当（ｐｔｙｐｅ＿ａｓｓｉｇｎ）値を索引に掲載するために使用できる。
【００９４】
この点を明らかにするために一例を説明する。ｐｔｙｐｅ＿ｇｒｏｕｐ［０］を構成する部品タイプインデックスが７、１１、１３、２０及び２２であり、これらのインデックスがｐｔｙｐｅ＿ｇｒｏｕｐ［０］．ｐｔｙｐｅ＿ｉｎｄｅｘ［ｍｔ］に格納される場合を考える。ソート順が異なる機械タイプ毎にインデックスの別個のリストを準備するのではなく、インデックスのリストを一つ準備する。次に、別々のソート順のリストを準備する。部品タイプは、既に部品番号の昇順になっているとする。昇順の部品のソート順インデックスは、０、１、２、３、４であり、降順の部品のソート順インデックスは、４、３、２、１、０である。他のソーティング法のための他のソート順インデックスも存在し得る。これらのソート順インデックスは、ｐｔｙｐｅ＿ｇｒｏｕｐ ｐｔｙｐｅ＿ｉｎｄｅｘとｐｔｙｐｅ＿ｇｒｏｕｐ ｐｔｙｐｅ＿ａｓｓｉｇｎの両方のビットに索引を付けるため使用される。かくして、ｐｔｙｐｅ＿ａｓｓｉｇｎビットは、すべてのソート順に対して同じ意味がある。一般的に、逆のソート順を保持する意味はなく、現在実行されていることを行い、リストの反対側から開始することだけが必要である。
【００９５】
更なる規準は、特殊なスプリットｐｔｙｐｅ＿ｇｒｏｕｐである部品タイプを選択するため追加される。この付加的な規準は、例えば、先行制約を伴う非常に多数の部品を、事前と事後の間でかなり均等に分割する基準である。再度、最も重要な規準、部品数、若しくは、先行制約を含む部品数を決定する必要がある。上述のバンド方式は、この決定を促進するために使用される。この場合、最初に、部品数を固定し、次に、最上位のバンド内で連鎖に基づいて選択を行う。連鎖のある部品数と、これらの連鎖が事前先行制約と事後先行制約（例えば、正味の負か正味の正）の間で均等にバランスがとれているかどうかと、の間には、どちらを優先するかというトレードオフが残っている。しかし、このトレードオフは、アプリオリ（先験的）に解決することは困難である。したがって、トレードオフを実施する簡単な方法を採用し、必要に応じて、より複雑な規則を追加することによって、或いは、染色体コントロールを追加することによってその方式を変更する方が好ましい。
【００９６】
部品スプリッタ・モジュール２０２に対する上述の２番目の変更は、スプリッタが先行制約を守れなかったときを示すコードを組み込むように拡張することである。この変更は、従来のフェイル・コード処理に、制約違反をチェックし、分割が実施不可能であることが分かった場合に新しいコードを返すロジックと共に新しいコードを付与することによって実施される。両方ともに実行不可能であるとき、染色体のペアの間のつながりを切断するために使用可能なサイクル・タイム・フィールドに値が返されるべきである。このような値は、少なくとも部分的には、違反された先行制約の個数の指標に依存する。
【００９７】
上記のフェイル・コード方式の代替案として、（機械タイプ間で）先行制約違反を含む部品は特殊なルーチンによって判定され、これらの部品はヒューリスティック・レイアウト・ジェネレータ・モジュール２０３及び２０５へ送信された部品のリストから削除される。しかし、フェイル・コードは、これらの部品を配置されない部品として含む。かくして、失敗した解（配置されない部品）の適応度を評価するため使用される同じペナルティー機構が、失敗した先行制約を考慮するため採用される。
【００９８】
９．  ＡＣＭモジュールの変更
本発明による先行制約の取扱を容易に行うため、図４及び５に関して説明した例示的なモジュラー最適化装置のＡＣＭモジュール２０５に対して多数の変更がなされる。解説のための実施例では、この変更には、部品の挿入時に制約違反をチェックする従来のチャージ・マップ挿入アルゴリズムの変更が含まれる。殆どの場合に違反を回避することは可能である。なぜならば、新しい部品だけを含む新しいチャージを常に作成することができるからである。これは、ノズル交換に大きなコストを生じ、おそらく、多数の１部品チャージのために大きなコストを招くが、（ＦＣＭの場合に説明したように）制約された部品が最初に配置された場合、後続の部品は、１部品チャージの損失を補う。このことが不可能であるのは、２個の部品が常に２部品チャージに分類され、新しい部品を一方の部品の前、かつ、他方の部品の後に配置しなければならない場合だけである。このような状況は、２部品チャージを解体し、新しい部品を２部品のうちの一方と共に配置するか、又は、３部品チャージのストリングを作成することによって対処される。この処理は、コスト高であるとしても、常に、実行可能なチャージ・マップを生成する。最悪のコスト影響の一部を改良することができるルーチンを作成することが望ましい。
【００９９】
有利的には、本発明の技術に従って先行制約を取り扱うように構成されたモジュラー最適化装置は、殆どのアプリケーションにおいて、対応した制約の無い実施形態に対して最小限のペナルティーしか生じない性能を提供する。制約のある実施形態によって要求される余分な遺伝子は、探索空間を非常に拡大することが可能であり、制約の無い実施形態よりも制約のある実施形態に対する解を獲得することの方が一般的には実質的に難しくは無い。場合によっては、制約の無い実施形態よりも制約のある実施形態に対してより優れた解を見つけることが可能である。
【０１００】
本発明は、少なくとも一部分では、電子式、磁気式、若しくは、光学式メモリ、又は、その他のタイプの機械読取可能な媒体に記憶された一つ以上のソフトウェア・プログラムの形式で実現することができる。例えば、上述のモジュラー最適化装置の種々のモジュールは、メモリ１１１に記憶されたソフトウェアの形式で実現され、プロセッサ１１０によって実行される。
【０１０１】
上記の本発明の実施例は、例示として説明するためだけのものである。例えば、本発明は、他のタイプのモジュラー最適化装置で使用することが可能であり、多種多様な配置とコンポーネント配置機械のタイプを含む生産ラインに適用可能である。特許請求の範囲に記載された事項に包含されるこれらの実施例及びその他の実施例は、当業者に理解できるであろう。
【図面の簡単な説明】
【図１】
本発明による先行制約取扱機能を備えたモジュラー最適化装置を使用して構成された２台のコンポーネント配置機械を含む生産ラインの一例を示す略図である。
【図２】
本発明と共に利用される高速コンポーネント実装（ＦＣＭ）型コンポーネント配置装置の一例の平面図である。
【図３】
図２のＦＣＭ機械の一つのパイプライン・モジュール（ＰＭ）の斜視図である。
【図４】
本発明による先行制約取扱機能を備えたモジュラー最適化装置の一例の略構成図である。
【図５】
図４のモジュラー最適化装置の発見的レイアウト発生器（ＨＬＧ）部のより詳細な構成図である。
【図６】
本発明の一実施例においてバケット・デザイアビリティをＰＭ数の関数として表したグラフである。
【図７】
本発明の一実施例においてグリッパ・デザイアビリティを種々の遺伝子に対するＰＭ数の関数として表したグラフである。
【図４】
2004518192.tif 000006
【図５】
2004518192.tif 000007
【図６】
2004518192.tif 000008
【図７】
2004518192.tif 000009
【国際公開パンフレット】
2004518192.tif 000010
2004518192.tif 000011
2004518192.tif 000012
2004518192.tif 000013
2004518192.tif 000014
2004518192.tif 000015
2004518192.tif 000016
2004518192.tif 000017
2004518192.tif 000018
2004518192.tif 000019
2004518192.tif 000020
2004518192.tif 000021
2004518192.tif 000022
2004518192.tif 000023
2004518192.tif 000024
2004518192.tif 000025
2004518192.tif 000026
2004518192.tif 000027
2004518192.tif 000028
2004518192.tif 000029
2004518192.tif 000030
2004518192.tif 000031
2004518192.tif 000032
2004518192.tif 000033
2004518192.tif 000034
2004518192.tif 000035
2004518192.tif 000036
2004518192.tif 000037
2004518192.tif 000038
2004518192.tif 000039
2004518192.tif 000040
2004518192.tif 000041
2004518192.tif 000042
2004518192.tif 000043
2004518192.tif 000044
2004518192.tif 000045
2004518192.tif 000046
2004518192.tif 000047
2004518192.tif 000048
2004518192.tif 000049
【国際公開パンフレット（コレクトバージョン）】
2004518192.tif 000050
【国際調査報告】
2004518192.tif 000051
2004518192.tif 000052
2004518192.tif 000053