JPH06215087A - コンピュータ制御部品装着機の構成最適化方法 - Google Patents

Abstract

(57)【要約】 【目的】 コンピュータ制御部品装着機に対する任意の
タスクの高品質構成を生ぜしめる方法を提供せんとする
ものである。 【構成】 多重ポートキャリアを集群化するコンピュー
タ制御部品装着機の構成を最適化するに当たり、該部品
装着機はキャリア用サポートと、複数の把持装置と、前
記多重ポートキャリアを集群化するに要する部品を支承
する複数の番号を付されたフィーダと、選択されたフィ
ーダから選択された部品をピックアップするとともにこ
れら部品を多数のチャージの１つに従ってキャリアの選
択された位置に搭載する把持装置を作動させる手段とを
具え、各チャージによって群としてピックアップされ、
かつ、搭載された特定組みの部品を表わし、且つキャリ
アを集群化するに必要なチャージのリストにより機器の
作動を制御し得るチャージマップを構成する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は素子載置機を処理して性
能を高める方法、特にコンピュータ制御部品装着機の構
成最適化方法に関するものである。

【０００２】

【従来の技術】既知の電子素子搭載機はプリント配線板
（以下ＰＣＢと称する）に素子をロードするために代表
的に用いて素子をＰＣＢ板トレースに半田付けするよう
にしたものである。本発明はＰＣＢ技術に限定されるも
のではない。（チップ部品自動装着機・搭載機）

【０００３】この種の代表的な機器はＰＣＢを支承する
プラットホームを具え、これに隣接して複数の素子フィ
ーダを設ける。構成素子はテープまたはスティックある
いはバルクフィーダのリールに設ける。Ｘ−Ｙ面におい
てＰＣＢに平行に且つＺ軸に沿ってＰＣＢに直角に移動
自在のヘッドはその底部に１つ以上の部品ホルダを有
し、このホルダはピペットを含み、内部にコンピュータ
制御された吸引により保持出力を提供する。能動ピペッ
トにはグリッパを固着する。これらグリッパは代表的に
はある大きさの部品を単に把持するだけである。

【０００４】

【発明が解決しようとする課題】生産スループットはＰ
ＣＢをロードし、またはポピュレートする時間を短縮す
ることによって改善する。単一ピペットを有する単一ヘ
ッドを用いる場合にはプラットホームの周りに部品を配
置して、フィーダから１部分をピックアップしてコンピ
ュータ制御によりＰＣＢ上の正しい箇所に載置するため
にヘッドを動かす距離を最小にする問題を解決する。一
回に１部分のみをピックアップして正しい箇所に載置す
るも、機器の構成上既知のように、部品を最適にまたは
ほ最適にレイアウトすることは困難であり、従って通常
手動操作または比較的簡単な慣例のプログラムによって
行うようにしている。とう

【０００５】市販されている機器は複数のピペットを用
いて各ヘッドの移動中複数の部品をピックアップして正
しい箇所に配置するようにしている。従って部品を適当
なフィーダに割当ててピペットに対し機器に制御プログ
ラムの仕様としての“レイアウト”および“チャージマ
ップ”として把持する問題が含まれるようになる。この
組合せの相違点は特に現在の機器が28ピペット、112 ビ
ンまたは部品フィーダを有し、部品を把持し得る複数の
グリッパはその大きさが８〜44ｍｍの範囲内で変化す
る。また、追加の配列ステップを必要とする大きな部品
および隣接するフィーダをシャドウし、従って仕様し得
ない１つのフィーダの大きな部品のような他の制約も考
慮する必要がある。

【０００６】試行錯誤に基づく手動操作による解決は時
間を費やし、構成ファウンドが最適であるかどうかを判
定するのが困難である。ある機器に対してはある制限さ
れたコンピュータアシスタントが有効であるが、この問
題に対するある程度良好な構成を提供し得る良好なコン
ピュータ制御アルゴリズムは誰も開発していない。

【０００７】本発明の目的は上述した種類の機器に対す
る任意のタスクの高品質構成を生ぜしめる方法を提供せ
んとするにある。

【０００８】

【課題を解決するための手段】本発明は多重ポートキャ
リアを集群化するコンピュータ制御部品装着機の構成を
最適化するに当たり、該部品装着機はキャリア用サポー
トと、複数の把持装置と、前記多重ポートキャリアを集
群化するに要する部品を支承する複数の番号を付された
フィーダと、選択されたフィーダから選択された部品を
ピックアップするとともにこれら部品を多数のチャージ
の１つに従ってキャリアの選択された位置に搭載する把
持装置を作動させる手段とを具え、各チャージによって
群としてピックアップされ、かつ、搭載された特定組み
の部品を表わし、且つキャリアを集群化するに必要なチ
ャージのリストにより機器の作動を制御し得るチャージ
マップを構成するようにしたコンピュータ制御部品装着
機の構成を最適化する方法において、 （ａ）所定組みの部品および部品位置を有する所定のプ
リント配線板を集群化するために機器の操作を制御する
チャージ−マップを発生する手段を制御する１組のパラ
メータを各々が表わす染色体ストリングの初期集団を発
生するステップと； （ｂ）搭載すべき部品のリストおよび機器の構成を制御
するパラメータを表わす所定の染色体ストリングを供給
する際に前記構成を発生し、且つ前記機器を有するキャ
リアを所定の構成に集群化する装着時間を計算し得るチ
ャージマップ発生機を設けるステップと； （ｃ）遺伝的アルゴリズムを用いて前の染色体ストリン
グから搭載時間を最小にする機器構成を決める問題に対
する可能な解を表わす新たな染色体ストリングを発生す
るステップと； （ｄ）この新たな染色体ストリングをチャージマップ発
生機に供給することによりステップ（ｃ）で発生した新
たな染色体ストリングを評価するステップと； （ｅ）染色体ストリングの改善を行う際特定数の染色体
が発生し且つ評価されるまで、または染色体集団が収斂
されるまで前のストリングを新たな染色体ストリングに
置換するステップ（ｃ）および（ｄ）を繰返すステップ
と； （ｆ）最良の染色体ストリングが所望の機器構成を表わ
すものとして見いだされる際これを出力するステップと
を具えることを特徴とする。

【０００９】

【作用】本発明の１態様によれば、いわゆる遺伝的アル
ゴリズムが機器構成問題に対するほぼ最適な解決を提供
することができる。

【００１０】さらに本発明の他の態様によれば、かかる
アルゴリズムを共通に使用しない特定の技術を用いるこ
とによって更なる改善を得ることができる。特に、遺伝
的アルゴリズムによって、親の染色体ストリング間の近
親交配を除去し、遺伝的アルゴリズムを、親の染色体ス
トリング間の近親交配を除去し、親の染色体ストリング
の対に対する交差の特定の強力な形態を適用し、親の染
色体ストリングおよび子の染色体ストリングの双方を最
適に含む存続を含み、発生した解が限定数の繰返し後に
収斂される際にのみ集団突然変異を適用し得るようにす
る。

【００１１】また、本発明は上述した所に従って構成さ
れた構成部品載置機器に関するものである。

【００１２】

【実施例】図面につき本発明の実施例を説明する。本発
明は立体的に逐次移動し得且つ複数のフィーダから供給
される部品を通常同時にピックアップしてコンピュータ
制御の下で１つ以上のボードに搭載する１つ以上のヘッ
ド上に複数の部品把持装置を有する任意の載置機に適用
することができる。一般に本発明方法は、部品把持装置
の数を３以上とするクラスの機器によれば、手動操作に
対し迅速または優秀である。本発明は２つの市販されて
いる載置機に対し説明するが、この種の任意の機器に一
般に適用するとともに当業者が容易に適用し得るもので
ある。本発明で詳細に説明する２つの機器はフィリップ
ス モジュラー コンポーネント プレイスメント マ
シン モデル ＭＣＭ−VII およびＦＣＭである。

【００１３】フィリップス ＭＣＭ−VII モジュラー
コンポーネント プレイスメントマシンは電子装置のサ
ーフェイス マウント アセンブリ用の機器である。Ｍ
ＣＭ−VII は１ユニットとして全て移動する可動ヘッド
に装着された28個の部品を有する。これらピペットは１
組のフィーダから28部品までを同時に把持してこれをプ
リント回路板上に載置する。機器の中央部にはプリント
回路板を適正位置に移動させるコンベアを設ける。この
コンベアの各側部には部品マガジン（テープ）を載置す
る１行のスロットまたはフィーダを設ける。即ち、コン
ベアの各側部には最大で56個のビン（28×２）を設け
る。ここに云う“最大”とは、各フィーダの幅が（種々
の大きさの部品に対し）変化し得るが、全スロット間隔
は固定されているものとする。全ての部品が小型である
場合にのみ、最大数のビンを用いることができる。部品
マガジンは少数の標準幅：８,12,16,24,36および44ｍｍ
とする。市販されている多数の種々の部品をこれらが嵌
合される際にグリッパの種類によって群別されるパッケ
ージの種類のファミリ内に組入れることができる。

【００１４】２８個のピペットはヘッドのＸ軸に沿って
単一行に均等に離間して配置する。これらピペットはＺ
軸方向にのみ移動し得るようにする。ヘッドはＸ軸およ
びＹ軸方向に移動させることができる。部品の搭載は順
次または同時に行うことができる。多重グリッパを単一
ヘッドに装着する際には同時搭載によって１つ以上の回
路板を回路キャリアに設けるかまたは１つ以上の回路を
特定の回路板に設ける必要がある。例えば、１つの回路
板がある場合には部品の対状同時載置を確実に行うこと
ができる。

【００１５】小さな部品寸法（８および12ｍｍ）のもの
をピックアップするグリッパによって部品を同時に整列
させることができる。大きな部品は整列させる必要があ
る。コンベアの各側部には14個の整列ネストを設ける。
これらネストは適宜離間して偶数番目または奇数番目の
ピックアップによって把持された大きな部品を同時によ
って整列させ得るようにする。

【００１６】図１ＡはＭＣＭ機10の斜視図であり、図１
ＢはＭＣＭ機10の平面図である。このＭＣＭ機10は図示
の２つのＰＣＢ９を有するＰＣＢコンベア12を中央部で
支持する機器基部11を具える。ヘッド13にはこれから下
方に懸垂配置されたピックアップ14（便宜上12個のみを
示す）を設ける。ピックアップ14のあるものには種々の
寸法のグリッパ15を設ける。コンピュータ制御および吸
引装置は図示しない。ビン18はコンベア12の反対側に図
示のように設ける（便宜上６個のみを示す）。整列ネス
ト19は数箇所に示す。図の中央部にＸ，ＹおよびＺ方向
を矢印で示す。

【００１７】ＭＣＭ機を含む機器の分類に対する構成問
題を以下に概説する。各々に対し幅、グリッパの種類お
よびｘ−ｙ座標を特定した部品リストを有する１つ以上
の回路板を設けるものとすると、タスクは部品をビンに
対しおよびグリッパをピペットに対し割当て且つ何れの
部品がピックアップされ、且つともに載置されるかを特
定して全ての部品を最小時間で回路板に載置し得るよう
にする。この時間は３つのファクタ：即ち、ヘッドが部
品を同時にピックアップする回数、ヘッドが整列ネスト
をビジットする必要のある回数および部品を載置するた
めにヘッドを移動させる必要のある回数に主として依存
する。単一回路板の場合には後者のファクタは部品の総
数に等しくなるが、数個の回路板の場合にはこのファク
タは同時載置により減少させることができる。

【００１８】構成問題の解はチャージ−マップと称され
る。チャージは特定の部品を有する１ピックアップおよ
び載置サイクルである。従って、チャージ−マップは回
路板を完全に集群化する特定のチャージリストである。
チャージ−マップを形成するためには、グリッパの種類
をピペットに割当てるとともに部品をビンに割当て、且
つ全ての部品をチャージに群別する必要がある。

【００１９】チャージ−マップを有効とするために、種
々の制約を満足する必要がある。先ず第一に、１つのビ
ンに大部分を割当てることにより隣接のビンが用いられ
るのを防止し、この効果をシャドウと称する。第２に、
正しいグリッパの種類を構成部品のピックアップに用い
る必要があり、従ってあるビンからのみ部品をピックア
ップすることができる。最後に、全てのピペットがポテ
ンシャル回路板位置に到達し得るとは限らず、従って何
れのピペットを用いて特定の部品を載置するかを決める
際に、かかる到達度を考慮する必要がある。

【００２０】本発明は、部品のリストを載置させる際に
載置機に対しほぼ最適のチャージ−マップを発生させる
方法である。この方法はコンピュータプログラムで実行
する。部品リストによって載置すべき各部品に対し
（ａ）独特の部品番号、（ｂ）部品の種類、（ｃ）グリ
ッパの種類および（ｄ）その位置（機器に対するｘおよ
びｙ座標）および載置配向を特定する。

【００２１】本発明は３つの主項目、即ち、ＨＬＧ：発
見的レイアウト（チャージ−マップ）発生器；ＣＨＣ：
ＨＬＧを制御するパラメータを探索する適応探索アルゴ
リズム；およびＣＨＣにより探索されたパラメータ範囲
を決める発見的プロセッサを具える。ＣＨＣによってパ
ラメータ値、即ち、試験パラメータ組の形状の試験解を
発生し、ＨＬＧによって（所定組の部品および載置座標
に対し）これら試験解を解釈しまたは使用してチャージ
−マップを発生し、各チャージ−マップの利点の目安
（解の実行にかかる時間の推測）をＣＨＣに戻すように
する。

【００２２】発見的チャージ−マップ発生器（ＨＬＧ）
によって１組の入力パラメータによりその特性を変更し
得る構成問題を解決する。ＨＬＧはチャージ−マップを
発生するために階層アプローチをとる。先ず第１に、こ
の方法によってグリッパをピペットに割当て、且つ何れ
のビンが何れのグリッパに関連するかを決めるようにす
る。次いで，これにより部品をビンに割当て且つ部品が
チャージに群別される手段を決めるようにする。

【００２３】グリッパの割当てステージ中、ＨＬＧによ
って先ず最初全部のグリッパの種類を巡回し、各グリッ
パの種類に最高所望度のグリッパをピックアップする所
望度の目安を割当てることによりグリッパの種類を選択
する。ここに云う“所望度”とはターゲットされたスロ
ットに関しグリッパの利点を表わす数を意味するものと
する。従って、ピペット全体を巡回して各ピペットに、
最高所望度のピペットにグリッパの種類を割当てるよう
に選択されたグリッパの種類に対する所望度を割当てる
ようにする。４つの関連するビンのうちの１つ以上をピ
ペットに割当てるようにする。

【００２４】部品の割当てステージ中、ＨＬＧによって
先ず最初各グリッパの種類に対しその構成素子の種類に
対するテープ（部品マガジン）の数を決め、従って任意
のテープにおける任意の部品の数を最小に保持する。次
いで、テープをビンに割当てて構成素子の座標が到達可
能となり、チャージの数を最小とし、かつ部品の多重載
置の数を最大とし得るようにする。

【００２５】パラメータ探索アルゴリズムは局部最小値
によって容易にトラップしてはならず、もっともらしい
解を含むように探索スペースの領域に探索限定し得るよ
うにする必要がある。以下に説明する遺伝的アルゴリズ
ム（ＧＡ）は次の特性のうちの２つを有する。本発明の
構成アルゴリズムではＧＡおよびＣＨＣの変形をパラメ
ータ探索アルゴリズムとして用いる。発見的プリプロセ
ッサによって部品リストを試験するとともにパラメータ
のあるものに対する妥当な範囲を決めるようにする。

【００２６】ある問題に対する本発明の方法は次のステ
ップから成る： １．部品リストを含む機器読取り可能なファイルを形成
する。 ２．ＨＬＧ入力パラメータ組のフォーマットを決める機
器読取り可能なファイルを形成するプリプロセッサを実
行する。 ３．ＣＨＣおよびＨＬＧを含み短い実行時間のチャージ
−マップを見いだす問題ソルバを実行する。ＣＨＣによ
って高性能組に対する旋回探索のシミュレーションにお
ける染色体としてパラメータ組を処理する。ＨＬＧによ
って各々１つの“フィットネス”を評価する。

【００２７】ＣＨＣの作動は次に示す論文、即ちモーガ
ン カウフマンによって刊行され、ジョージ ローリン
によって編集された“ファンデーション オブ ジェネ
チック アルゴリズム”サン マテオ，カルフォルニア
（１９９１）に掲載された発明者の１人（エシェルマ
ン）による論文に詳細に説明されている。この論文のタ
イトルは“The CHC Adative Search Algorithm: How to
have Safe Search WhenEngaging in Nontraditional G
enetic Recombination" である。

【００２８】遺伝的アルゴリズム（ＧＡ）は集団遺伝学
から要約された機構に基づく“汎用探索方法”である。
この遺伝的アルゴリズムＧＡは集団と称される１組の試
験的解を含んでいる。この遺伝的アルゴリズムは遺伝的
組換が後続する“最適選定のサバイバル”によって順次
の集団を発生する世代と称されるサイクルにおいて作動
する。この試験的解は２進文字記号組で通常符号化され
た染色体と称されるストリングとして表わされる。ＧＡ
に基づく理論は汎用最適度の達成は保証しないが、ほぼ
最適の利点は探索中に習得された情報が得られることで
ある。

【００２９】クラスとしてのＧＡは構成問題に適用し得
るが、ある変化を加えることによってその可能性を改善
し、“高品質の解”を得ることができる。この点は以下
の一層詳細な記載から理解される。

【００３０】伝統的なＧＡの概要は以下の非疑似符号が
現われることである。

【００３１】ここに云う“伝統的ＧＡ”とは以下を推定
するＧＡを意味するものである。 （１）（固定の大きさＭ）の集団P(0)の初期化が任意。 （２）交配選択（select＿m ）は良好な実行構成の選択
方向にバイアス。 （３）置換選択（select＿r ）は均一（非バイアス）で
あり、代表的には旧集団P(t-1)全体をP(t-1)から発生し
た子C(t)と置換 （４）再結合オペレータは１又は２ポイントクロスオー
バの何れかである。 （５）低い割合の突然変異を再結合ステージに用いて集
団ダイバーシティを保持する。

【００３２】ＣＨＣは以下の点（２）−（５）で伝統的
ＧＡとは相違する。 （２）このＣＨＣは交配選択よりも置換選択によって駆
動する：即ち、良好な実行構成によるバイアスは交配選
択よりも置換選択に発生する。 （３）同様の再結合固体に対する交配選択中新たなバイ
アスを導入する。 （４）１または２ポイントクロスオーバでなくＣＨＣに
よって用いられる再結合オペレータはクロスオーバの高
度の崩壊形態である。 （５）突然変異は再結合ステージでは行われない。むし
ろ、収束が検出される場合にはいつも部分集団任意性に
よって分散が再導入される。

【００３３】（２）最優良選択に関してはＣＨＣによっ
て“強調による生殖”の代わりに“最適合のサバイバ
ル”を用いる。一層正確には、生殖選択中、親の集団P
(t-1)の良好な実行部材に関する生殖候補C(t)の選択を
バイアスする代わりに、P(t-1)の各部材をC(t)にコピー
し、かつ生殖に対して任意に対合する。換言すれば、構
成の順序が入換えられる点を除いてC(t)はP(t-1)と同一
である。また、サバイバル選択中、旧親の集団Ｐ(t-1)
の代わりに子の集団C(t)を用いてP(t)を形成することに
より新たに発生した子はサバイバル用の親の集団P(t-1)
の部材と競合し、即ち、競合は交雑世代となる。特に、
P(t-1)およびC ′(t) の部材は適合に従って合併されか
つランク付けされるとともにP(t)は合併集団の最良のＭ
部材を選択することによって発生する。ここにＭは集団
の大きさである。P(t-1)の部材およびC(t)の部材が同一
の適合性を有する場合にはP(t-1)の部材が一層高いラン
ク付けとなる。合併された親および子の最良にランク付
けされた部材を保持するこの手順によって最優良選択を
集群化する。その理由はさらに見られる最良のＭ固体が
常時サバイバルされるからである。

【００３４】（３）近親相姦を防止する項目に対して、
良好な概要の瞬時の指数関数的成長はこれが早期の収束
を導く場合には小さな値となる。親間で異なるビットの
半分をクロスオーバするのが好適である。これにより早
期の収束の危険を低減する。各世代で最も最近の子孫を
起源先祖の１つと交配する場合（毎回同様に）でもlog₂
ｈ世代をとって起源先祖への（１ビット内の）収束を行
う。ここにｈは起源の親間のハミング距離である。ま
た、２ポイントクロスオーバの場合には、２つの子の各
々が（ハミング距離により測定して）その最も近い親か
ら１ビット乃至ストリングＬの長さの１／２の範囲だけ
相違する。これがため、先祖の１ビット内に収束するに
要する最長時間はlog₂ｈ世代となり、その最短のものが
１世代である。子は離れた先祖の１つと繰返し交配すべ
きでないが、良好な個体が多くの子孫を有するため、個
体は近い血族の１つと交配することが有り得る。これが
多くの対立遺伝子を共有する個体の乗換えをもたらす限
り再結合を経る調査が急激に退化する。異なるビット
（以下ＨＵＸと称する）の半分の任意の乗換えがこの処
理を緩慢とする乗換え操作を用いるも、数個の差異を有
する個体が対合となる場合がある。１つまたは２つの子
がこの交配を生き残る場合にはかかる事象が次の世代に
発生することが大いに有り得るようになる。

【００３５】ＣＨＣには収束箇所を緩慢とする追加の機
構、即ち、近親相姦の防止を補助する機構を設ける。生
殖ステップ中、親の集団の各部材は置換および交配対合
を行うことなく任意に選択することができる。しかし、
交配前、潜在親間のハミング距離を計算するとともにこ
の距離（その親から期待された子のハミング距離）の半
分が異なるスレシホルド以上とならない場合にはこれら
は交配されず、子の集団から除去されるようになる。
（差のスレシホルドは実行の開始時にＬ／４、即ち、２
つの任意に発生したストリング間の期待されたハミング
距離の半分に設定する。）これがため、代表的には集団
の１部分のみを交配して任意の世代に新たな子を発生さ
せるようにする。（潜在交配が行われないため、または
子の何れもが親の集団の最悪の部材よりも良好であるた
めに）子が親の集団に受け入れられない場合には差のス
レシホルドを減少させることができる。これがため、一
層発散する潜在親のみを交配するが、差のスレシホルド
により要求される発散は集団自然収束として自動的に減
少する。各世代の生存者の数は探索中著しく一定とな
る。その理由はＣＨＣが困難な交配過程を有する場合に
異なるスレシホルドが平均ハミング距離よりも迅速に降
下して多くの個体が評価されるようになる。ＣＨＣがこ
れを容易に見いだして生存の子を生ぜしめる場合には異
なるスレシホルドが緩慢な速度で降下するとともに交配
の回数が減少する。

【００３６】均一な乗換えに対し、ＧＡはオペレータと
なり、これにより生殖再結合を提供し且つ計画の保存は
簡単ではない。これが有効再結合および計画間の交換で
ある。例えば単一の異なるビットを常時乗換える再結合
オペレータによって最小に分断されるも新たな個体を発
生するがこれは極めて有効ではない。この交換は乗換え
を経てプリザーブされる最小数の計画に対する下記の公
式から明らかである（即ち、親が全ての座で相補とな
る）： ２^X ＋２^(L-X) （１） ここにＬはストリングの長さであり、ｘはビット乗換え
の数である。プリザーブすべき保証された計画の数は、
オペレータが再結合を行わない場合、即ち、ｘ＝０また
はＬの場合に最大となる。また、プリザーブすべき保証
された計画の数は、ｘ＝Ｌ／２の場合に最小となる。こ
れがため、計画が興味深い場合にはｘを小さくするのが
好適である。

【００３７】さらに、再結合後の直感的なアイデアは、
２つの良好な親からの特徴を組合せることにより一層良
好な子を発生することができる。双方の親から高い値の
計画をコピーする場合にはこれらを同一の子に同時に具
体化する。第１の親からコピーを行うビットを多くすれ
ばするほどコピーする計画が多くなり、従って一層高い
値の計画を分裂なくコピーする必要がある。また、第１
の親からコピーするビットを多くすればするほど第２の
親からコピーし得るビットが多くなり、従って第２の親
から高い値の計画を分裂する可能性を増大する。これが
ため、ビットの半分（良好には異なるビットの半分）を
乗換える乗換えオペレータは価値のある計画を主として
組合せるようになる。その理由は最大数の計画が各親か
ら組合さるからである。

【００３８】均一の乗換えＵＸによってセグメントより
もビットを交換する。ＣＨＣによって用いられる実際の
再結合オペレータはＨＵＸであり、均一の乗換えの変
形、ＨＵＸは交換すべきビットが置換なく任意に選択さ
れる非整合対立遺伝子の半分を正確に乗換える。このＨ
ＵＸによって子が常時その２つの親から最大ハミング距
離であることを保証する。ＨＵＸの分断の他側は、これ
により子で結合された各親から１つ宛、２つの良好な計
画の機会を最大とする。その理由は各親からの材料の半
分を選択する。さらに、同一次数の全ての計画は分断さ
れたかまたは保持された等しい機会を有する。

【００３９】（５）再出発に関し、発散構体の数、（例
えば50）を保持するに充分に大きい集団の大きさに従っ
てＨＵＸおよび近親相姦防止の使用によってＣＨＣを作
動させて早期の収束を遅延させ、従って何らの突然変異
なくこれを良好に実行する。しかし、場所が早期に収束
しないこれらの種々の機構は保証されない。従ってある
種類の突然変異が必要になる。

【００４０】しかし、突然変異の影響は伝統的なＧＡよ
りもＣＨＣにおいてより少ない。ＣＨＣが保持分散にお
いて既に極めて良好であるため、突然変異は探索におい
て僅かだけ早期となる。また、探索の後期において集団
がほぼ収束されている場合には、最も精鋭された選択と
組合わされた突然変異は再導入分散における影響は殆ど
ない。従ってかかる突然変異は集団における最悪の個体
よりも良好な個体を実際に発生し、従って極めて少ない
個体が集団に受容されるようになる。ＣＨＣに対し親の
集団を各世代に置換することにより伝統的なＧＡによっ
て新たな変化が絶えず導入されることを確実にする。

【００４１】このインパスからのＣＨＣの手段は集団が
収束された場合または探索が沈滞する（即ち、差のスレ
シホルドが低下して零値となるとともに何らの生存者な
く数世代が存在する）場合には突然変異が導入されるよ
うになる。特に、再生−再結合サイクルによってその端
末状態が達成される場合には集団が再び開始され、且つ
上記サイクルが繰返されるようになる。しかし、再初期
化は部分的となるだけである。新たな集団を発生するテ
ンプレートとして今までに見いだされた最良の個体を用
いることにより集団を再初期化する。置換なく任意に選
択されたテンプレートのビットの固定部分（例えば、35
％）を反転することにより各新たな個体が発生する。最
良の個体の１つを新たな集団に不変のまま加えるように
する。これがため、確実に次の探索により前の探索より
も悪い解に収束し得ないようにする。遺伝的探索が追従
する再初期化または激動突然変異より成るこの外部ルー
プはその終端条件が満足される（固定数の再初期化に到
達するか、または保持された構体よりも任意の良好な構
体を見いだすことを繰返し失敗する）まで繰返されるよ
うになる。

【００４２】上述した概念のあるものを図面につきさに
説明する。図３は本発明方法を説明するためのデータフ
ローチャート図である。ＣＨＣのようにラベルされたブ
ロック30は本発明による遺伝的アルゴリズムを有するプ
ログラムを表わし、ＨＬＧとしてラベルされたブロック
31は双方ともコンピュータ32の制御のもとで発見的レイ
アウト発生器を有するプログラムを表わす。問題29は各
部品に要求されるグリッパのタイプおよびフィーダのタ
イプとともにＨＬＧ31に部品リストの形態で入力され、
各部品の座標をＰＣＢに特定する。ＨＬＧプログラムの
個別に示されないプリプロセッサ部分は処理の始端で１
回実行するとともに許容し得るパラメータ範囲を表わす
染色体プロフィールを機器読出し可能形態で発生する。
ＣＨＣによって、ＨＬＧを用いて完全な機械構造を決め
ると云うパラメータを各々が表わす染色体の初期組（集
団）発生する。染色体は任意の形態をとりうるため、便
宜上これを１および０のビットストリング（図４に35で
示す）の形態とする。このビットストリング35は充分な
長さとして逐次群のビットはＨＬＧにより明らかに用い
て特定の機器構成を生ぜしめることができる。ＭＣＭ機
器に対してはあるＰＣＢで１ビットストリングは140 ビ
ットであった。ＣＨＣによって染色体をプログラムのＨ
ＬＧ評価部分に通過せしめ、これにより染色体から特定
のレイアウトを発生せしめるとともに染色体に対する性
能指数、この場合には置換またはサイクル時間を発生せ
しめるようにする。次いで、性能指数をＣＨＣプログラ
ムに逆通過せしめ、これによりこの情報を用いて新たな
染色体を生ぜしめるようにする。今までに最適であった
レイアウトが生じる場合にはこれをファイルに出力す
る。古い染色体から新たな染色体を発生し、且つこれら
染色体を、レイアウトを発生し性能指数をＣＨＣに戻す
ようにしたこのＣＨＣの処理は、（この収束は集団の最
悪の解が最良の解と同様となる場合）固定数の染色体が
発生して評価されるか、または染色体の集団が固定回数
収束され且つ分散する。

【００４３】最良の適合の生存者の遺伝的概観は図５お
よび図６に示すフローチャートに示し、ここに図５は図
６の簡単化されたものである。染色体の初期集団40は染
色体の種々の箇所における種々のビット値に相当する染
色体および個体の特徴を表わす４つの不機嫌な／しかめ
面をした顔の各々を有するものとして頂部に示す。図６
において６行の隣接する白黒の正方形は１を表わす黒い
正方形および０を表わす白い正方形を有する染色体を示
す。図５は４つの集団の大きさを表わし、図６が６つの
集団の大きさを表わしているが、代表的な集団の大きさ
は50である。

【００４４】染色体のスコアまたは性能指数を図５にお
いては各顔の下側に示すとともに図６においては各染色
体の端部に示す。図５において、最高のスコアは最良の
性能を示し、従ってアルゴリズムの目的はこれらスコア
を最大とする必要のあることである。図６において、最
低のスコアは任意であり、従ってアルゴリズムの目的は
これらスコアを最小とすることである。

【００４５】図５および図６の双方において、左側には
親の組を示し、右側にはこれら親から発生した子を示
す。各ラベル付きのボックスは順次の時間ステップを示
す。図中40は親の染色体の初期集団を示す。次のステッ
プ41において、左側（図５の顔および図６の行）の親は
任意の順序ではあるが空の右側の区分をそのまま占めて
任意対の組合せを形成する。図６に示すが図５には示さ
ない次のステップ42A では、殆ど同一の個体の対が組合
さるのを防止する。ステップ42A に示すように、最後の
組合せの対は除去される（近親相姦防止）。次のステッ
プ42では、個体対の特徴を再結合して（オペレータの称
する乗換を経て交換して）新たな子を形成し、各新たな
子の染色体をＨＬＧに供給し且つ同様の顔の下側でボッ
クスの行の右側に示される性能指数を受けるようにす
る。次のステップ43では、親および子の集団を結合して
最悪の個体を除去して残存する個体の数を親の集団の大
きさに等しくする。図５は選択される８つの顔のうちの
最良の４つを示す。図６は選択される８つの顔のうちの
最良の６つを示す、即ち、親の側の２行を廃棄し子の側
の２つの最良の行と置換する。テスト44は更新された親
の集団の最悪および最良の部材のスコアを比較すること
により収束が生じるか否かを決める。

【００４６】収束が生じない場合には処理は新たな親と
して作用する４つまたは６つの染色体の最良に選択され
た集団で他の繰返しを経て実行する。収束が生じる場合
には集団の染色体の１つを除いた全てが部分的に任意抽
出する（突然変異する）とともにこの処理を継続する。
固定数の染色体が発生して評価される場合には、または
固定数の収束が生じる場合にはかかる処理を停止する。

【００４７】前述したように、ＣＨＣアルゴリズムは次
に示す４つの顕著な点において慣例のＧＡとは相違す
る。・伝統的なＧＡよりも乗換の一層分裂された形態の
ものを用いる。 ・選択は強調付き再現よりもむしろ最適生存に起因す
る。 ・近親相姦交配を防止して乗換の方法を一層強力にす
る。 ・突然変異を適用して集団が収束されたときのみ処理を
再び開始する。 第１の相違を図７に示し、これにより左側の標準ＧＡの
相違と右側のＣＨＣの相違とを比較する。

【００４８】ステップ50および50A において、双方のア
ルゴリズムは左側の４つの顔により表わされる初期の親
の染色体の同一の集団により開始する。伝統的なＧＡで
は次のステップにおいてステップ51に示すような良好な
親のコピーを多数且つ悪い親のコピーを少数形成する。
ステップ51では２つのコピーを第３のしかめ面の顔で形
成し、第２のしかめ面の顔のコピーは存在しない。ま
た、ＣＨＣではステップ50A に示すように１つのコピー
を各親で形成する。ＧＡでは右側の子の全部をステップ
53に示すように左側の親の全部と置換するが、ＣＨＣで
は良好な子をステップ53A に示すように最悪の親と置換
する。

【００４９】本発明の重要な要部は、染色体ストリング
のビット、またはビットの組によって表わされ、機器の
作動を制御するレイアウトおよびチャージマップを発生
する手段を案内または制御するとともに一般に機器に依
存するパラメータである。機器のＭＣＭタイプに対し
て、染色体ビットと、最上またはほぼ最上の機器レイア
ウトに到達する必要度とにより表わされるパラメータを
決めるために次のルールを選択する。これらルールは次
の通りである。 （ａｉ）割当てグリッパの種類の優先度および各グリッ
パの種類に理想的に関連するフィーダの数を制御するパ
ラメータ； （ａii）優先度を次の基準、即ち、到達度制限、適合の
剛性および多重搭載機会に割当てることによりグリッパ
の種類に対するピペット位置の割当てを制御するパラメ
ータ； （aiii）グリッパの種類当たりに割当てられたピペット
位置当たりのフィーダの初期数を特定することによりフ
ィーダを割当てる手段を制御し、且つ（昇順または降順
の）何れの順序でフィーダが割当てられるかを制御する
パラメータ； （ａiv）部品を剛固にパッケージする手段を制御するこ
とによりフィーダ位置全体に亘り部品を配分する手段を
制御するパラメータ；および （ａｖ）部品の種類が割当てられる順序（昇順または降
順）を制御することにより何れの部品を何れのフィーダ
に割当てるかを制御するパラメータ。

【００５０】チャージマップ発生器ＨＬＧによって以下
に示すステップおよびパラメータを用いてチャージマッ
プを発生するアルゴリズムを有するプログラムを実行す
る。ここ“チャージマップ発生器”および“発見的レイ
アウト発生器”の双方はアルゴリズムＨＬＧを参照する
ために用いる。その理由はアルゴリズムによってレイア
ウトおよびチャージマップの双方を発生させるからであ
る。 （ｉ）全てのフィーダスロットが割当てられるまで； ・パラメータ（ａｉ）に基づきグリッパの種類ｇｔを選
択し、 ・パラメータ（aii)に基づきグリッパの種類ｇｔに対す
るピペット位置ppを選択し、・ピペット位置ppが得られ
る場合にはパラメータ（aiii）に基づきピペット位置pp
により到達し得るフィーダを割当て、他に(else)既に割
当てられたピペットｇｔに対する未使用フィーダを割当
て； （ii）割当てられた各グリッパの種類に対し、 ・パラメータ（ａiv）に基づき多くのフィーダを各部品
の種類に割当てを手段を決め、・パラメータ（av）に基
づき部品を特定のフィーダに割当てる。

【００５１】ＣＨＣアルゴリズムによって発生した染色
体はこれらを順次ＨＬＧに供給することによりテスト
し、且つ評価される。新たな染色体ストリングは、特定
数の染色体が発生し且つテストされ、その結果、代表的
な数がほぼ10,000乃至100,000個の染色体の範囲にある
高品質の構成となるか、または集団が特定回数収束され
て代表的な数がほぼ５乃至10の範囲にある期待された同
様の結果となるまで、一連の繰返しで発生し且つテスト
されるようになる。

【００５２】上述したタイプの置換機器に対する構成問
題を解決する修正ＧＡを用いることはＭＣＭタイプの機
器に限定されるものではない。他の機器に対しては、特
に機器に依存する統率パラメータにおいてアルゴリズム
にある変形を与える必要があるが、その原理はそのまま
である。これはモデルＦＣＭフィリップス型構成素子搭
載機に対して以下に説明する詳細な例から明らかであ
る。

【００５３】ＦＣＭ機はその平面図を図８に示し、斜視
図を図９に示す。このＦＣＭ機は移送システム60を具
え、これにより一連の16個までの独立したピックアップ
アンド プレース モジュール（ＰＭ）62の下側で一
連のプリント回路板（ＰＣＢ）61を支持する。移送シス
テム60はステップ（インデックスステップ）状に進行
し、これらステップ間でＰＣＢが瞬時的に停止するがＰ
Ｍはある構成素子を搭載している。各ＰＭは（図８に示
すように機器の全面に）フィーダバー63を有し、これに
種々の構成素子フィーダタイプ64（可変幅のテープまた
はスチック、またはバルクフィーダ）を固着する。各Ｐ
Ｍ62を120mm 幅とし、そのうちの80mmをその到達可能区
域とする。ＰＭ間には物理的障壁を設けるため、ＰＭ間
に干渉が生じることはない。これらフィーダはフィーダ
バー63上の到達可能区域内に搭載する必要があり、この
目的のために６つの孔を16mm間隔で穿孔し、これら孔に
フィーダを固着する。これらの孔の位置はフィーダスロ
ットと称し、０〜５の番号を（図８の左から右に示すよ
うに）付す。新たなＰＣＢをＦＣＭの左端に挿入し完成
されたＰＣＢを右端から取出す。各ＰＭ62にはｘ（左
右）、ｙ（前後）、ｚ（上／下）およびｐｈｉ（軸ｚを
中心とする回転）方向に独立してサーボ制御される単一
の可動ヘッド66を設ける。これらサーボ制御は種々の加
速度および最大速度を有し、従ってピックアップから載
置位置までの移送時間はｘ，ｙおよびｐｈｉ時間の最大
値である。ｚ方向の移動はピックアップに対するおよび
載置に対する固定遅延で計算される。各ヘッドは部品を
ピックアップする特定の真空ノズルおよび正確な機械的
な整列を行うチャックに固着することができる。このノ
ズルおよびチャックの組合せをグリッパと称し、（部
品）を搭載すべき各構成素子を特定のグリッパタイプに
設計することができる。

【００５４】最適化タスクは搭載すべき部品およびグリ
ッパ並びにフィーダタイプのｘ，ｙおよびｐｈｉ位置を
特定する部品リストを与え、且つＦＣＭ機のラインの仕
様（機器の数およびＰＭの数）を与え、全ての部品を有
するＰＣＢを集群化するに要する時間（サイクル時間）
を最小にするレイアウトおよびチャージマップを発生し
得るようにする。さらに、ＦＣＭユーザは使用される特
定のタイプのグリッパの数および／または特定の部品の
タイプを送給するフィーダの数の上限を前置することに
より解を抑制し得るようにして最適化を行う必要があ
る。これらは特定のグリッパを特定のＰＭに割当てると
ともにとともにスロットが特定の部品タイプを送給する
必要のあることを前以て特定することが必要となる。あ
るＰＭおよびあるスロットを使用しないように前以て特
定することもできる。上述した最適化タスクは単一ボー
ド問題と称される。さらに、最適化によってファミリ−
オブ−ボード問題を処理する必要がある。ＰＣＢのファ
ミリは、これら部品の同一の外部寸法および剪断最大限
度を有する数個の密に関連するボード（ファミリーオブ
ボード部材）を具える。ある部品はファミリーオブボー
ド部材の１つ以上のものに対して独特のものとする。フ
ァミリ−オブ−ボード問題の最適化ゴールはファミリ部
材を所定のように混合するサイクル時間を最小にする必
要があり、ここで全てのファミリ部材に対する解は同一
のレイアウトを共有する（即ち、製造ラインはグリッパ
対ピペットまたは部品対フィーダの任意の割当てを変更
することなく１つのファミリ部材から他のファミリ部材
に切換えることができる）。

【００５５】移送システムのインデックスステップ間の
動きは表１に示すように前置特定する。インデックスス
テップの動きの和はピッチに等しくする必要がある。１
つのＰＣＢのピッチはコンベア上の順次のＰＣＢ間の距
離であり、移送システムの簡便さのためには、全てのボ
ードは表１にリストアップされた選択対象から１つのピ
ッチを割当てるようにする。移送システムによって新た
なＰＣＢをピックアップし、インデックスステップの列
記された数を進行し、次いで左端に戻り、ここで他のボ
ードをピックアップする。処理に際し全てのボードをピ
ックアップし、これらが右端に送出されるまでインデッ
クスステップのサイクルで同一に進行せしめるようにす
る。例えば、全部で80個のピッチボードは各ステップで
ＰＭ間の距離を120mm 進行する。小型のボードは単一Ｐ
Ｍの到達可能区域内に完全に適合するため、新たなボー
ドは各１ステップサイクルピックアップされるようにな
る。他方の端部では480 個のピッチボードはＰＭも下側
で各ＰＣＢを通過させるために６つのインデックスステ
ップをとる。

【００５６】

【表１】 Ｅは可視検査操作（ＥＶＡ）がこのステップで発生する
ことを意味する。Ｆは第１の部品がこのステップに載置
されていることを意味する。

【００５７】この時点で既知のフィーダタイプを表２に
リストアップする。各フィーダタイプ（Ｔ＝テープ，Ｓ
＝スティック，Ｂ＝バルク）に対して、表２は寸法（フ
ィーダバー孔に整列された中心ラインの左側および右
側）、独特の部品タイプをピックアップし得る位置の番
号および（フィーダバー孔に対し載置された）ピック位
置のｘおよびｙ座標をリストアップする。寸法はμｍで
ある。

【００５８】

【表２】

【００５９】要約するに、一般のアプローチでは、問題
を解決するために対話処理ＧＡおよびＨＬＧを用い、Ｈ
ＬＧはその特性を変呼応し得る多くの埋設パラメータを
有する。ＨＬＧは単一アルゴリズムよりもむしろアルゴ
リズムファミリであると考えることができる。遺伝的ア
ルゴリズム（ＧＡ）は展開アプローチを用いるこれら同
調パラメータの良好な組を位置するタスクを有する。各
染色体によってＨＬＧパラメータの完全な組を特定す
る。ＨＬＧに対する各呼によって所定のＦＣＭ最適化タ
スクを解決することを試みる。この試みから生じるサイ
クル時間を染色体の“フィットネス”として処理する。
染色体の任意の集団から出発し、ＧＡは最良に適合した
部材のサバイバルを優先的に行い、その遺伝子（ＨＬＧ
パラメータ）を乗換えて遺伝子の新たな組合せを形成す
る処理によって最良適合部材から子（テストすべき新た
な染色体）を生ぜしめるようにして新たな染色体の世代
を循環する。

【００６０】一般にＧＡの仕事を一層詳細に知るために
は、ゴールドバーグ著“Genetic Algorithms in Searc
h,Optomization, and Machine Learning ”Addison Wes
ley,Reading, MA,1989年，およびリファレンス エシェ
ルマン ペーパー オン ザＣＨＣ，モディファイドＧ
Ａを参照されたい。

【００６１】ＨＬＧのタスクはＦＣＭレイアウト問題に
対する完全に実現可能な解をこれが可能である場合に生
ぜしめることである。成功の場合には、ＧＡに戻り解に
対するサイクル時間を見いだす。失敗の場合には、数値
を戻し、如何にして容易な解を充分に見いだす手段を反
映することを発見的に決めるようにする。この発見的な
値を適宜選定して全ての容易な解が全ての難解な解より
も低い（良好な）スコアを有し、且つこれら難解な解の
うちでは容易なスコアに近いスコアが良好である。

【００６２】ＨＬＧにより用いられる有効な概念はバケ
ットの概念である。各インデックスステップには各ＰＭ
に対し規定されたバケットが存在する。これらバケット
は平衡アルゴリズムにより用いられるリセプタクルであ
り、この中に部品を載置し、そのうえで平衡を保持す
る。図１０は理想的な概念を示す。同一のインデックス
ステップ（図１０の列）の全てのバケットは同一の心拍
時間：最も緩やかなＰＭの実行時間を共有する。全機器
／ラインのサイクル時間は全てのインデックスステップ
に対する心拍の和によって近似されるようになる。真実
のサイクル時間は移送システムの動きおよびピック位置
間のヘッドの動きを考慮する必要があるが、移送運動に
対し同時に発生するヘッドの動き時間を検出することが
できる。ＨＬＧは以下に示す５つのステップより構成さ
れる。 ステップ１．ＰＭに対しグリッパを割当てる。 ステップ２．ＰＭフィーダスロットに対しフィーダのタ
イプを割当てる。 ステップ３．バケットに対し部品を割当てる。 ステップ４．各ＰＭにおけるフィーダ間で部品タイプを
変更する。 ステップ５．各バケットに載置される部品を順序付けす
る。

【００６３】各ステップによって発見的測定および近接
性能測定を用いる染色体のパラメータにより案内し得る
取消不可能な決定を行う（ステップ１〜３）。ステップ
１および２は各交互の載置の“必要性(desirability)”
の発見的測定を用いる。ステップ３は部品をバケットに
割当てて良好な時間平衡を保持するように試みる際に各
部品に対し“ピックアップ−載置時間”（pp＿time）を
用いる。部品のピックアップ位置およびそのピックアッ
プ順序が次のステップまで決まらない場合にはpp＿time
を推定する必要がある。ＨＬＧによって各部品に対する
２つの推定：pp＿time＿lower およびpp＿time＿actua
l；を保持する。pp＿time＿lower はフィーダバー（ｙ
＝０）から載置位置（y = part＿y ）を経て戻る循環時
間（ピックアップおよび載置遅延を含む）である。この
値はｙまたはｐｈｉサーボをにより掛かる時間の最大値
である。ｘサーボの行程はピックアップ位置が選択され
るまで決めることはできない。一旦ピックアップ位置が
決まると（ステップ４）、pp＿time＿actualはｘサーボ
の循環時間およびpp＿time＿lower の最大値となる。

【００６４】各染色体のフィットネスとしてＨＬＧによ
りＧＡに戻るサイクル時間は移送システムに対する移動
時間、その最終順序の順次のピックアップおよびボード
を移動させながらＰＭを移動させるＦＣＭを達成し得る
平行を含む真実のサイクルシステムである。

【００６５】次の区分は各ステップの作動を概説する。 ステップ１．ＰＭに対しグリッパを割当てる。

【００６６】このステップに対する疑似コードを以下に
示す（Ｈ１およびＨ２は以下に説明する発見的測定） assign＿pipette() if (グリッパの番号 = 1) このグリッパを全てのＰＭに割当てる グリッパを前置割当することなくＰＭの番号を計算する （ＰＭが割当てられた儘である) ため 各グリッパの必要性（Ｈ１）を計算する。 最も必要なグリッパに対しては割当てられていない各ＰＭの必要性（Ｈ ２）を計算する。 最も必要なグリッパを最も必要なＰＭに割当てる。

【００６７】発見的Ｈ１は各グリッパタイプ（重みおよ
びグリッパ基準ビット）に対する染色体からの２つのパ
ラメータと、解決される問題および特定されたライン
（ＰＭの最大および最小数）に依存する２つの予備計算
された定数とを用いる。minimum ＿PMは各グリッパを用
いる部品に必要な各フィーダタイプによってカバーされ
るフィーダスロットの数を考慮することによって推定す
る。この計算はある程度保存され、従って必要な真の最
小値はより高くなる（即ち、minimum ＿PMが割当てられ
る場合に、実現可能な解を生ずることは保証できな
い）。target＿PMは各グリッパタイプが必要とするtota
l pp＿timeの一部分を推定することによって計算する。
maximum ＿PMはユーザによって設定された限度である
か、またはＰＭから全ての他のグリッパは必要とする最
小値の総数とする。これらの定数およびvariable PM ＿
assignedを用いて各グリッパの必要性(H1)を次に示すよ
うに計算する： diff(g) = target＿PM(g) - PM＿assigned(g)

【００６８】

【数１】

【００６９】染色体における（必要性に関係を切断する
ために用いられる）重みおよびグリッパ参照ビットを操
作することによりＣＨＣはＰＭに対するグリッパの割当
ての広い変化を生じ得るようにする。

【００７０】発見的Ｈ２は各ＰＭにおける各グリッパに
対する予備計算された必要性および各グリッパに対する
染色体のreference ＿bit を含む。この必要性は、部品
が既知であり且つ任意の予備割当てを含むＦＣＭライン
を規定すると直ちに一回の計算を行う。グリッパ−ＰＭ
必要性は、グリッパがその部品をそのＰＭに載置する必
要があると云う機会を表わす。これは各インデックスス
テップにおける各スロットで確実に載置し得る各部品に
対し増大する係数値である。斯様に確実に載置し得るよ
うにするためには、適宜のフィーダタイプを前置割当て
を行うかまたはスロットをなくするようにする必要があ
る。さらに、部品のｘ位置はインデックスステップでア
クセス可能とする必要がある。この必要性は40mmボード
の移動が生じる際に何れのｘ位置が２つの順次のインデ
ックスステップで露出されるかに関しＰＭ間に度々生じ
る差に反映する。

【００７１】reference ＿bit によって同一の必要性を
有するラインにおいて最初または最後のＰＭによる関係
を解決する。これがため、染色体によって特定のグリッ
パがラインの始端または終端から載置されることを記述
することができる。

【００７２】ステップ２．ＰＭフィーダスロットに対し
フィーダのタイプを割当てる。

【００７３】このステップに対する疑似コードを以下に
示す。グリッパをアルゴリズムのこの点におけるＰＭに
載置されているため、各グリッパによって独立のフィー
ダ割当ての選択を有するＰＭの独立の組を特定する。 assign feeder＿types() for （各グリッパ） while （同一のフィーダタイプが確実な必要性を有するとともにあるス ロットもいまだ有効である） 各フィーダタイプの必要性を計算する（Ｈ３） for 最も所望のフィーダタイプ、各有効なスロットの必要性を計算する （Ｈ４） 最も所望のフィーダタイプを最も所望のスロットに載置する 不足高＝達成し得ない所望のピックアップ位置を計算する return（shortfall ）

【００７４】発見的Ｈ３は各グリッパタイプに必要な各
フィーダタイプに対し染色体からのパラメータを（重
み，wt(g,f))用いる。必要性の計算はピックアップ位置
に基づくものである。多くのフィーダタイプは４つのバ
ルクフィーダを除いてフィーダ当たり１つのピックアッ
プ位置を有する。各グリッパタイプ（ｇ）に必要な各フ
ィーダタイプ（ｆ）に対し２つの定数:min＿picks(g,f)
=部品タイプの数(g,f)、max ＿picks(g,f) =部品の数
(g,f) ：を計算する。実現可能な解を可能とするために
個別のフィーダを各部品タイプに対し必要とするが、各
タイプの部品の場合よりも一層多くのフィーダを割当て
る理由はない。これらの定数およびvariablepicks＿ass
igned(g,f) を用いることにより、各フィーダタイプの
必要性を次のように計算する。

【００７５】

【数２】

【００７６】染色体で重みを操作することにより、ＣＨ
ＣはＨＬＧと相俟ってスロットへのフィーダタイプの割
当ての広い変化を生ぜしめるようにする。

【００７７】発見的Ｈ４は既に載置されている他のフィ
ーダタイプを有する各フィーダタイプに対する“タイト
ネス- オブ- フィット- 測定”と、各ＰＭの物理的境界
とを計算する。space ＿left(f,p,s) とは、これがＰＭ
のスロットｓに載置されている場合にはフィーダタイプ
ｆの左端とその最も近隣のフィーダタイプの右端（左壁
またはその左端に最も近いフィーダ）との間の自由スペ
ースである。space ＿right(f,p,s ）はアナログ的に規
定する。必要性は次に示すように計算する。 desirability(f,p,s) ＝max ｛space ＿left(f,p,s), space ＿right(f,p,s)｝ （４）

【００７８】この発見的ＨはＰＭ内で共にフィーダを剛
固にパックする効果を有すると同時にこれらフィーダを
ＰＭ間で拡散する傾向にあり、従ってＰＭを横切って
“ピックアップ＿載置”を後に平行にする機会を最小に
する。ステップ３が実効部品を割当てる際に全ての割当
てられたフィーダが実際に用いられることは定かではな
い。

【００７９】ステップ３．バケットに対し部品を割当て
る。

【００８０】このアルゴリズムはＨＬＧの心臓を考察す
ることができる。これは全てのインデックスステップ中
全てのＰＭの遊び時間を最小にするためにバケット間に
ワークロードされたピックアップ−載置を分配し得るよ
うにする。２つの前のステップ中に行われた割当てのフ
レームワーク内で作動し、且つ部品（または部品群）の
分類されたリストとともに作動する。ソフトウエアによ
ってかかる群または個体の部品載置のオプションを提供
する。１つの群はそのボード位置の全てが同一ストライ
プ内にある同一タイプの全ての部品をもって構成する。
ストライプは図１１に示すようにプリント回路板の40mm
垂直スライスとする。アルゴリズムは常時部品群で作動
する。ユーザがオプションを選択して部品を個別に載置
する場合には、これは簡単に１部品群を構成する。バケ
ット割当てに対する部品（群）の分類は染色体における
８ビットによって制御する。最初の４ビットは次表３に
示される分類順序の表にインデックスとして解読され
る。残りの４ビットは各分類欄に対し順序：ｐｐｔ，ｓ
ｔ，ｐｔ，ｇｔの昇順（１）または降順（２）として分
類順序をフラグをたてる。

【００８１】

【表３】 ここにppt = pp＿time st =ストライプ pt =部品タイプ gt =グリッパタイプ

【００８２】このステップに対する疑似コードを以下に
示す。 level() while （分類されたリストから載置するための他の部品が存在する） 全ての可能なバケットを見いだし（Ｃ１） if 適当なバケットが存在しない （載置するために残存する部品群）を戻し バケットを選択する（Ｈ５） 選択されたバケットに部品群を載置する （零）に戻す。 “可能”とすべきバケットに対する条件（Ｃ１）は次の
通りである。 ・割当てられたグリッパタイプは整合する必要がある ・ＰＭの下側の２つのストライプのうちの１つを整合す
る必要がある ・適当なフィーダタイプは利用可能とする必要がある
（右側の部品タイプに自由にまたは既に割当てられ
た）。

【００８３】最良のバケットの選択は染色体で少し制御
された簡単なアルゴリズムによって行う。通常の発見的
測定は最も緩慢な時間を有するバケットを選択し、ここ
に緩慢な時間はバケットのインデックスステップに対す
る現在の心拍時間（即ち、最も緩慢なＰＭに対する総合
pp＿time）と既にこのバケット内にある全ての部品に対
する総合pp＿timeとの間のpp＿time差である。pp＿time
＿低下をここで使用する。その理由は使用すべきピック
アップ位置の決定がアルゴリズムの次のステップで行わ
れるからである。（各部品群に対し１つの）染色体から
のバケット＿選択＿ビットによって適当なフィーダタイ
プに既に割当てられたフィーダを有するバケットの選択
を有利に優先する。これにより208 個の可能な分類順序
の各々に対し最良−適合−フィーダ−戦略および適合−
保存−戦略の複雑な組合せとしてレベラーを作動せしめ
るようにする。（例えば、ただ１つのグリッパタイプの
みが存在する場合には）ある問題に対しては分類順序の
あるものが冗長されるようになる。

【００８４】ステップ４．各ＰＭにおけるフィーダ間で
部品タイプを変更する。

【００８５】このアルゴリズムは特性を変更するための
染色体の制御がないと云う点で固定される。これは簡単
に各ＰＭを順次訪問し、且つ折衷フィーダ間で部品タイ
プを交換し得るようにする。この交換のゴールは、部品
のpp＿timeがそのピックアップ位置のためｘサーボ制限
される場合に生ずる推定pp＿time＿lower にの矛盾を最
小とする試みが必要とする。このｘサーボペナルティ
（pp＿time＿lower が増大する量）は、これが可能な折
衷ピックアップ位置の各々において載置される場合には
“危険区域”（以下参照）における各部品に対し計算さ
れるようになる。このｘサーボペナルティは全てのイン
デックスステップに対し加算するとともにこの和を得ら
れる任意のスラック時間により減少する。発生するペナ
ルティが零の場合には交換は行われない。さもなくば、
零コスト交換が見いだされるかまたは交換回数のあらか
じめ設定された制限に到達するまで交換を組織的に試み
るようにする。現在この制限は720 （６！＝720 ）。こ
の値によって、単一ＰＭ（11! ＝39916800）に11個のピ
ックアップ位置が存在し得るバルクフィーダを除き全て
のフィーダタイプに対し最適な交換が見いだされること
を保証する。データに対する経験は、許可された720 個
の交換の僅かな部分を試みながらこのアルゴリズムが常
時零コスト解をレポートすると云うことを示唆する。

【００８６】危険区域はフィーダバーに近いプリント回
路板の領域であり、ここでｘサーボの行程時間がｙサー
ボまたはｐｈｉサーボの行程時間よりも大きいと云うこ
とが可能となる。この領域を図１２に示す。ｙ＝65mmの
水平ラインは、これ以上ではｘサーボの最悪のケース
（80mmを移動）がｐｈｉサーボに対する最悪のケースよ
りも悪くならないと云う限度を表わす。２つの傾斜ライ
ンは（ピックアップ位置０および５からの）ｙサーボ行
程がｘサーボ行程に等しくなる焦点を表わす。プリント
回路板の位置がこれら領域上にある部品はこれらがピッ
クアップされるピックアップ位置にかかわらずｘサーボ
制約とならない。この領域内の部品のみを交換アルゴリ
ズムに関連させるようにする必要がある。

【００８７】ステップ５．各バケットに載置される部品
を順序付けする。

【００８８】このアルゴリズムも特性を変更するための
染色体の制御がないと云う点で固定される。これは各バ
ケットを順にビジットし且つそのピックアップ位置の順
序：奇数番目のインデックスステップに対しては左から
右におよび偶数番目インデックスステップに対しては右
から左の順序で載置すべき部品を分類する。これがた
め、各ステップで部品を載置するＰＭはフィーダバーを
横切って先ず最初左に、次いで右に交互にスィープされ
るようになる。

【００８９】図１３は、ＧＡおよびＨＬＧ間の内部通信
が示されず、外部ファイルが示される点を除き図３に示
す所と同様である。

【００９０】ファイルを出力する。

【００９１】fcm.bestファイルは前のbestよりも良好な
新たな解を見いだす際の探索中上書きされるようにな
る。このファイルは各々が他の観念の解を記述する一連
の“パラグラフ”で構成される。第１のパラグラフは部
品リストファイルに設けられたＰＣＢ情報を要約する。
その一例を以下に示す。

【００９２】TITLE:PCB-3 ピッチ = 360000 ｎ＿part = 910 ｎ＿part＿types = 45 ｎ＿gripper ＿types = 4 グリッパタイプ１は３つのピペットモジュール（最小）
を要求する26部品タイプ有する グリッパタイプ２は２つのピペットモジュール（最小）
を要求する７部品タイプ有する グリッパタイプ３は１つのピペットモジュール（最小）
を要求する７部品タイプ有する グリッパタイプ４は１つのピペットモジュール（最小）
を要求する５部品タイプ有する フィーダタイプＢ32は33部品タイプを有する フィーダタイプＴ８は12部品タイプを有する

【００９３】第２パラグラフは以下に示すようにfcm.pa
ramsファイルの情報をエコーする。 LINE: ラインのＦＣＭ機器は１ ラインの総合ピペットモジュールは16 使用するピペットモジュールは16 MACHINE:FCM 0 16ピペットモジュール付き PM 0 グリッパFREEは６スロットを有する PM 1 グリッパFREEは６スロットを有する PM 2 グリッパFREEは６スロットを有する PM 3 グリッパFREEは６スロットを有する PM 4 グリッパFREEは６スロットを有する PM 5 グリッパFREEは６スロットを有する PM 6 グリッパFREEは６スロットを有する PM 7 グリッパFREEは６スロットを有する PM 8 グリッパFREEは６スロットを有する PM 9 グリッパFREEは６スロットを有する PM 10 グリッパFREEは６スロットを有する PM 11 グリッパFREEは６スロットを有する PM 12 グリッパFREEは６スロットを有する PM 13 グリッパFREEは６スロットを有する PM 14 グリッパFREEは６スロットを有する PM 15 グリッパFREEは６スロットを有する 戦略：部品を個別に載置する

【００９４】FEEDER SUMMARYパラグラフはＰＭに対する
グリッパ、スロットに対するフィーダタイプ、ピックア
ップ位置に対する部品タイプのそれぞれ割当てを記述す
る。かかるパラグラフの部品を以下に示す。フィーダタ
イプは割当てられ、従って実際に使用されない（PM 0
スロット 5 参照）。また、隣接のスロットのフィーダ
がスロット位置に実際に延在する場合にのみ１つのスロ
ットが“ブロック”されることも記載されている。スロ
ットはFREEがラベルされているが、隣接のフィーダが近
くにきて干渉なくフィーダが載置されなくなる場合には
“有効にブロック”されるようになる。

【００９５】 FEEDER SUMMARY FCM 0 PM 0 gripper：４ slot 0 feeder type ：T ８ part ＿type 12 slot 1 feeder type ：T ８ part ＿type 22 slot 2 feeder type ：T ８ part ＿type 20 slot 3 feeder type ：T ８ part ＿type 13 slot 4 feeder type ：T ８ part ＿type 21 slot 5 feeder type ：T ８ part ＿type FREE FCM 0 PM 1 gripper：１ slot 0 feeder type ：B32 pick 0 part ＿type FREE pick 1 part ＿type 6 pick 2 part ＿type 5 pick 3 part ＿type 39 slot 1 blocked slot 2 feeder type:B32 pick 0 part ＿type 44 pick 1 part ＿type 1 pick 2 part ＿type 4 pick 3 part ＿type 31 slot 3 blocked slot 4 feeder type:B32 pick 0 part ＿type 38 pick 1 part ＿type 43 pick 2 part ＿type 32 pick 3 part ＿type 7 slot 5 blocked

【００９６】次のパラグラフは解の各インデックスステ
ップ中実際に載置された部品を記述する。かかるパラグ
ラフの始端を以下に示す。先ず最初、インデックスステ
ップはEVA が発生するステップ（可視検査）をマークす
る“Ｅ”および新たなボードに部品を最初に載置するス
テップをPM 0 でマークする“Ｆ”とともに記述する。
この下にボードのストライプを示す各バケットをリスト
アップし、これにより心拍時間（移送システムの動きを
無効にするpp＿time推定）、バケットに載置されたすべ
ての部品に対し推定されたpp＿timeの和、およびslack
＿時間（心拍−pp＿time）を“示す”。すべての時間は
ｍｓとする。次いで載置された部品の部品番号をこれら
が載置された順番にリストアップする。各部品番号の後
に３つの記号が括弧［abc ］内に現れ、ここにａはスロ
ット、ｂは取上げられるピックアップ位置、ｃはpp＿ti
meがｘサーボ、ｙサーボまたはphi サーボにより制約さ
れるか否かに依存する“ｘ”，“ｙ”および“ｐ”をそ
れぞれ示す。交互のインデックスステップのスロットは
ＨＬＧのステップ５に対する簡単な発見的測定を反映し
て左側から右側、および右側から左側に交互に配列する
ことは勿論である（§４参照）。

【００９７】 インデックス ステップ 0 1 2 3 4 寸法（mm）: 40 80 80 80 80 FCM 0 : PM 0 E F ストライプ: 5,6 7,8 0,1 2,3 4,5 心 拍: 9561 8471 12582 14127 12177 pp＿time: 7784 3494 8205 13267 8952 slack ＿time: 1778 4977 4377 860 3225 部品: 868 00y 910 10y 862 00y 894 40y 866 00y 部品: 908 10y 909 10x 861 00y 896 40y 865 00x 部品: 888 20y 869 00x 901 10y 893 40p 867 00y 部品: 890 20y 870 00y 902 10p 895 40x 906 10y 部品: 889 20p 882 20y 873 30p 905 10x 部品: 880 30y 881 20p 876 30p 907 10p 部品: 879 30x 872 30y 874 30y 887 20p 部品: 900 40y 871 30p 875 30y 878 30y 部品: 899 40x 892 40y 884 20y 877 30p 部品: 891 40p 886 20y 898 40y 部品: 883 20x 897 40p 部品: 885 20p 部品: 904 10y 部品: 903 10x 部品: 863 00x 部品: 864 00y

【００９８】以下に示す最終パラグラフによって問題に
対する２つの低い制約推定と真のサイクル時間（移送シ
ステムの動きを含む）とを与える。第１の（強制されな
い）低い制約（ULB ）は簡単に云って使用されるＰＭの
数によって分割される各部品に対するpp＿time＿lower
の和となる。これは、全ての部品がｙサーボ制約または
phi サーボ制約であり、ＰＭがslack ＿timeを何ら有さ
ない場合に生じる（移送の動きは無視する）真の低い制
約である。第２の（強制された）低い制約（CLB ）は真
の低い制約ではない。その理由はこれが提案された解に
おけるＰＭに対するグリッパの割当てに依存するからで
ある。これは、割当てられたＰＭの吸うにより除算され
た各グリッパタイプの全ての部品に対するpp＿time＿lo
wer の和の（グリッパタイプ間の）最大値である。この
低下制約の品質を評価するために、ある要約統計を各グ
リッパタイプに対し：即ち、必要なmin ＿PM（推定）、
実際に割当てられたＰＭの数およびＰＭの最適数に対し
与えるようにする。後者の性能は非現実的な理想であり
通常整数でもない。これは各グリッパタイプに対しワー
クロードされた等平均値（pp＿time sums)であるＰＭの
数である。assigned＿PMがこれらの数に近い場合にはＣ
ＬＢは良好なものとなる。真のサイクル時間はこれがＣ
ＬＢ以上となる量（％）である。この性能しばしば最適
のギャップと称される。最後にＧＡは経験およびこの解
が見いだされた試行を記録する。

【００９９】LOWER BOUND PICK & TIME(グリッパタイプ
割当て及び移送無視): 51200 ms LOWER BOUND PICK & TIME(グリッパタイプ割当て考慮及
び移送無視): 55745 msG T: 1 min＿PM 3 assigned ＿PM 10 opt ＿PM 10.5 GT: 2 min ＿PM 2 assigned ＿PM 2 opt＿PM 2.2 GT: 3 min ＿PM 1 assigned ＿PM 3 opt＿PM 2.5 GT: 4 min ＿PM 1 assigned ＿PM 1 opt＿PM 0.8 TOTAL PICK & PLACE TIME(移送を含む): 57607 ms 低い制約以上の％ = 3.340210 経験0 試行46128 で見いだされたkost = 57607

【０１００】要約するに、ＦＣＭ機に対しＨＬＧを制御
する染色体ストリングに表わされる複数のパラメータは
次の通りである。・グリッパ−ピペット判定を行う順序
に影響を及ぼす各グリッパタイプに対する重み：・（等
しい所望のグリッパ−ピペット判定間の関係を破断す
る）関係グリッパタイプに対するピペット基準ビット：
・フィーダスロットに対するフィーダタイプに関する判
定の順序に影響を及ぼす各グリッパタイプの各フィーダ
タイプに対する重み：・ＰＣＢ素子をバケットに割当て
る際にこれらを考慮する順序に影響を及ぼす分類パラメ
ータ：および・バケットの選択に影響を及ぼす各部品に
対する基準ビット。

【０１０１】ＭＣＭ機のパラメータに対する基本的類似
性は明らかであり、双方の機器に対しては次のように概
説することができる。 １．各グリッパタイプに対し重みを割当てる。 ２．ピペットの数を各グリッパタイプに割当てり優先権
を割当てる。 ３．各グリッパタイプに対し各フィーダタイプの優先権
を割当てる。 ４．部品タイプを各フィーダタイプに割当てる手段を制
御する順序を決める。

【０１０２】好適な染色体を構成して多重ヘッド、多重
ピペット、多重グリッパタイプおよび多重フィーダを有
するこれら汎用タイプの搭載機の構成を表わす場合に
は、これら同一のパラメータは組込む必要がある。

【０１０３】こらの記述を完成させるために、本発明の
プログラムに対する疑似コードのある他の例を以下に示
す。

【０１０４】 procedure select begin Ｐ(t-1) 〜Ｃ(t) の全ての部材を任意順序にコピー; end 。 procedure select begin Ｐ(t-1) の最悪の部材をＣ′(t) の最良の部材と置換することによりＰ(t) からＰ(t-1) を形成 until Ｃ′(t) の残存部材がＰ(t-1) の任意の残存部材よりも何ら良好でな くなる end 。

【０１０５】

【０１０６】

【０１０７】 ＨＬＧによってＭＣＭ機に対するパラメータを制御 ・・・・・・・・・・・ グリッパタイプ当たりのピペットおよびフィーダのターゲットされた番号： P ＿num ＿pipettes＿targeted gt グリッパタイプ当たりのピペットの番号 P ＿num ＿feeders ＿targeted gt グリッパタイプ当たりのフィーダの番号 P ＿num ＿feeders ＿per ＿pipette gt グリッパタイプに対するピペット当た りのフィーダの番号 部品を割当てる手段を制御する各グリッパタイプに対しフラグ付けする。 P ＿use ＿all ＿feeders gt 得られるフィーダの全部を用いるかどうか P ＿packing ＿criterion gt 到達可能度又は番号が部品をパッケージする 主規準であるかどうか

【０１０８】 グリッパタイプを選択する重み P ＿gripper ＿type＿wt gt 各グリッパタイプの優先度 P ＿gripper ＿type＿feeder＿wt gt フィーダの取得度の重要性 ピペットを選択する重み P ＿reachability＿wt 到達可能度の重要性 P ＿fit ＿wt フィットのタイトネスの重要性 P ＿multi ＿wt 多重度の重要性( 一般に) P ＿multi ＿wt1 可能性多重度の重要性 P ＿multi ＿wt2 相手方グリッパタイプの多重度をブロックしない重 要性 付帯パラメータ P ＿first ＿pip 割当てるべき第１ピペット, グリッパ P ＿low ＿lfu 低( 第1)又は高( 第4)論理フィードユニットで開始する 大きな部品にフィーダを割当てるかどうか P ＿single＿align チャージに対し多くとも１つの整列で確実とするか

【０１０９】 ＭＣＭ機のためのＨＬＧアルゴリズム ・・・・・・・・・・・・・・ メイン グリッパをピペットに割当てると共にフィーダを割当てる。 構成素子をピペットに割当てると共にチャージに集群化する。 assign＿grippers do untilブレーク for 各グリッパタイプ(gt) グリッパタイプ(gt)の必要度を決める if 確実な必要度のグリッパタイプが存在しない ブレークを行う else 最高の必要度を有するグリッパタイプを選択 if グリッパタイプ(gt)の選択が第１グリッパタイプである パラメータP ＿first ＿pip によって示されるピペットを選択 else for 各ピペット(pip) desirability＿of＿pipette(gt,pip) を決定 if 確実な必要度を有するあるピペットが存在する 最高の必要度を有するピペットを選択 選択されたグリッパタイプを選択されたピペットに割当て フィーダをP ＿num ＿feeders ＿per ＿pipette gt およびP ＿low ＿lfu によって示されるように割当てる else for 同一のグリッパタイプおよび得られるフィーダを有する各ピペット desirable ＿of＿next＿available ＿feeder(gt,pip)を決定 if 確実な必要度のグリッパタイプが存在しない ブレークを行うか else 最高の必要度を有するグリッパタイプを選択しフィーダを割当てる

【０１１０】 desirability＿of＿gripper ＿type(gt) if num＿feeders ＿available ＞ 0 desirability = P ＿gripper ＿type＿wt gt + (P ＿gripper ＿type＿feeder＿wt* P ＿num ＿feeders ＿targeted gt / num ＿feeders ＿available) else desirability ( 必要度)= 0.0 if num＿pipettes＿assigned gt ＞ = P＿num ＿pipettes＿targeted gt desirability * = 0.1 desirability＿of＿pipette(gt,pip) if pipが既にグリッパを割当てている desirability = 0.0 else if 部品が整列を必要とし且つpip をも番号付けする P ＿single＿align desirability = 0.0 else desirability = P ＿multi ＿wt * desire ＿multi(gt,pip) + P ＿reachability＿wt * desire ＿reachability + P ＿fit ＿wt * desire ＿fit

【０１１１】 desire＿multi ＿(gt,pip) if n＿boards＞ 1 多重位置に用い得るpip の同胞を試験; num ＿actual＿multi = 同一のgtを有する同胞ピペットの計数 num ＿potential ＿multi = gtを有する同胞ピペットの計数 num ＿rivals =異なるgtを有する同胞ピペットの計数 num ＿rivals＿blocked = 多重位置のpip を用いる異なるgtを有する同胞 ピペットの計数 desirability = num＿actual＿multi + P＿multi ＿wt1 * num ＿potential ＿multi + P＿multi ＿wt2 * (num＿rivals - num＿rivals＿blocked) /(num＿boards - 1) else desirability = 1.0;

【０１１２】 desire＿reach(gt,pip) if ピペットがgtの任意の構成素子のボード位置に到達し得ない desirability = 0 else desirability =同一のグリッパタイプ/27 の最も近い隣人に対するnum ＿ pipettes desire＿fit(gt,pip) desirability = 1 -｜num ＿feeders ＿available ＿to＿pipette ＿ P＿num ＿feeders ＿per ＿pipette gt ｜/4 desirability＿of＿next＿available＿feeder(gt,pip) desirability = 0.5 * num ＿feeders ＿allocated gt＿of＿1st ＿neighbor / P＿num ＿feeders ＿targeted gt ＿of＿1st ＿neighbor + 0.5 * num＿feeders ＿allocated gt＿of＿2nd ＿neighbor / P ＿num ＿feeders ＿targeted gt ＿of＿2nd ＿neighbor

【０１１３】 assign＿components for 各グリッパタイプ(gt) group ＿components(gt) onto tapes assign＿tapes(gt) to feeders group ＿components(gt) テープ(gt)の各構成素子に割当てるべきテープの数を決定 so that テープの任意の構成素子の最も大きな数を最小に保持し、 且つ if P＿use ＿all ＿feeders gt so that 全ての割当てられたfeeders を用いる。 assign＿tapes(gt) if num＿boards＞ 1 do while ボードによって集群化された部品および適当に離間された有効 なフィーダを有する未割当テープが存在する 最も大きな数の構成素子を有するテープの組を割当てる do while 未割当テープおよび有効なフィーダが存在する if P＿packing ＿criterion gt が0 reachability( 最も少ない数のピペットが座標に到達し得る) に対しその構成素子が最も制約されるテープを割当て else if P ＿packing ＿criterion gt が 1 最大数の構成素子を有するテープを割当てる

【０１１４】

【０１１５】本発明は上述した例にのみ限定されるもの
ではなく要旨を限定しない範囲内で種々の変形または変
更が可能である。

【図面の簡単な説明】

【図１】モデルＭＣＭ部品載置機の斜視図である。

【図２】モデルＭＣＭ部品載置機の平面図である。

【図３】本発明方法を実施するシステムのデータフロー
チャート図である。である。

【図４】本発明方法に有効な染色体ストリングの１例を
示す説明図である。

【図５】本発明に使用する変形染色体アルゴリズムＣＨ
Ｃの操作を説明するフローチャート図である。

【図６】本発明に使用する変形染色体アルゴリズムＣＨ
Ｃの操作を説明するフローチャート図である。

【図７】標準遺伝的アルゴリズムの操作と、本発明に使
用する変形アルゴリズムの操作とを比較するフローチャ
ート図である。

【図８】１６個のピペットモジュールを有するモデルＦ
ＣＭ機を示す頂面図である。

【図９】本発明方法を使用し得るモデルＦＣＭ機の１つ
のピペットモジュールを示す斜視図である。

【図１０】ＦＣＭ機のアルゴリズムに使用するある概念
を示す説明図である。

【図１１】ＦＣＭ機のアルゴリズムに使用するある概念
を示す説明図である。

【図１２】ＦＣＭ機のアルゴリズムに使用するある概念
を示す説明図である。

【図１３】ＦＣＭプログラムに使用する入出力ファイル
を示すブロック図である。

【符号の説明】

9 PCB 10 MCM 機 11 機器基台 12 PCB コンベア 13 ヘッド 14 ピペット 15 グリッパ 18 ビン 19 整列ネスト 29 問題 30 CHC 31 HLG 32 コンピュータ 35 バイストリング 60 移送システム 61 PCB 62 PM 63 フィーダバー 64 フィーダタイプ 66 可動ヘッド

───────────────────────────────────────────────────── フロントページの続き (72)発明者 ジェイ デビッド シャッファー アメリカ合衆国 ニューヨーク州 12590 ワッピンガース フォールス エッジヒ ル ドライブ 101

Claims (10)

【特許請求の範囲】
1. 【請求項１】 多重ポートキャリアを集群化するコンピ
   ュータ制御部品装着機の構成を最適化するに当たり、該
   部品装着機はキャリア用サポートと、複数の把持装置
   と、前記多重ポートキャリアを集群化するに要する部品
   を支承する複数の番号を付されたフィーダと、選択され
   たフィーダから選択された部品をピックアップするとと
   もにこれら部品を多数のチャージの１つに従ってキャリ
   アの選択された位置に搭載する把持装置を作動させる手
   段とを具え、各チャージによって群としてピックアップ
   され、かつ、搭載された特定組みの部品を表わし、且つ
   キャリアを集群化するに必要なチャージのリストにより
   機器の作動を制御し得るチャージマップを構成するよう
   にしたコンピュータ制御部品装着機の構成を最適化する
   方法において、 （ａ）所定組みの部品および部品位置を有する所定のプ
   リント配線板を集群化するために機器の操作を制御する
   チャージマップを発生する手段を制御する１組のパラメ
   ータを各々が表わす染色体ストリングの初期集団を発生
   するステップと； （ｂ）搭載すべき部品のリストおよび機器の構成を制御
   するパラメータを表わす所定の染色体ストリングを供給
   する際に前記構成を発生し、且つ前記機器を有するキャ
   リアを所定の構成に集群化する装着時間を計算し得るチ
   ャージマップ発生機を設けるステップと； （ｃ）遺伝的アルゴリズムを用いて前の染色体ストリン
   グから搭載時間を最小にする機器構成を決める問題に対
   する可能な解を表わす新たな染色体ストリングを発生す
   るステップと； （ｄ）この新たな染色体ストリングをチャージマップ発
   生機に供給することによりステップ（ｃ）で発生した新
   たな染色体ストリングを評価するステップと； （ｅ）染色体ストリングの改善を行う際特定数の染色体
   が発生し且つ評価されるまで、または染色体集団が収斂
   されるまで前のストリングを新たな染色体ストリングに
   置換するステップ（ｃ）および（ｄ）を繰返すステップ
   と； （ｆ）最良の染色体ストリングが所望の機器構成を表わ
   すものとして見いだされる際これを出力するステップと
   を具えることを特徴とするコンピュータ制御部品装着機
   の構成最適化方法。
2. 【請求項２】 ステップ（ｆ）で出力された最良の染色
   体ストリングに従って機器を構成し、且つ、機器を誘う
   させて最後の繰返しステップ後、ステップ（ｂ）で発生
   したチャージマップに従ってキャリアを集群化するよう
   にしたことを特徴とする請求項１に記載のコンピュータ
   制御部品装着機の構成最適化方法。
3. 【請求項３】 前記ステップ（ａ）は染色体ストリング
   で表わされる次のパラメータ： （ａｉ）割当てグリッパの種類の優先度および各グリッ
   パの種類に理想的に関連するフィーダの数を制御するパ
   ラメータ； （ａii）優先度を次の基準、即ち、到達度制限、適合の
   剛性および多重搭載機会に割当てることによりグリッパ
   の種類に対するピペット位置の割当てを制御するパラメ
   ータ； （aiii）グリッパの種類当たりに割当てられたピペット
   位置当たりのフィーダの初期数を特定することによりフ
   ィーダを割当てる手段を制御し、且つ何れの順序でフィ
   ーダが割当てられるかを制御するパラメータ； （ａiv）部品を剛固にパッケージする手段または割当て
   を実行する手段を制御することによりフィーダ位置全体
   に亘り部品を配分する手段を制御するパラメータ；およ
   び （ａｖ）部品の種類が割当てられる順序を制御すること
   により何れの部品を何れのフィーダに割当てるかを制御
   するパラメータ；を用いるようにしたことを特徴とする
   請求項１に記載のコンピュータ制御部品装着機の構成最
   適化方法。
4. 【請求項４】 各グリッパ装置はピペットおよびこれに
   装着されたグリッパを含み、ステップ（ｂ）のチャージ
   発生機は次のステップ： （ｉ）全てのフィーダスロットが割当てられるまで； ・パラメータ（ａｉ）に基づきグリッパの種類ｇｔを選
   択し、 ・パラメータ（aii ）に基づきグリッパの種類ｇｔに対
   するピペット位置ppを選択し、・ピペット位置ppが得ら
   れる場合にはパラメータ（aiii）に基づきピペット位置
   ppにより到達し得るフィーダを割当て、他に（else）既
   に割当てられたピペットｇｔに対する未使用フィーダを
   割当て； （ii）割当てられた各グリッパの種類に対し、 ・パラメータ（ａiv）に基づき多くのフィーダを各部品
   の種類に割当てを手段を決め、・パラメータ（av）に基
   づき部品を特定のフィーダに割当てる、を用いてチャー
   ジマップを発生するようにしたことを特徴とする請求項
   ３に記載のコンピュータ制御部品装着機の構成最適化方
   法。
5. 【請求項５】 ステップ（ｃ）で用いられる遺伝的アル
   ゴリズムを、親の染色体ストリング間の近親交配を除去
   し、親の染色体ストリングの対に対する交差を適用し、
   親の染色体ストリングおよび子の染色体ストリングの双
   方を最適に含む存続を含み、発生した解が限定数の繰返
   し後に収斂される際にのみ集団突然変異を適用する遺伝
   的アルゴリズムとしたことを特徴とする請求項１に記載
   のコンピュータ制御部品装着機の構成最適化方法。
6. 【請求項６】 各把持装置はピペットおよびこれに装着
   されたグリッパを含み、且つ染色体によって少なくとも
   次のパラメータ：グリッパ−ピペット判定を行う順序に
   影響を及ぼす各々のグリッパの種類に対する重み； １
   つ以上のピペットが等しく必要となる際にグリッパ−ピ
   ペット判定に影響を及ぼす各々のグリッパの種類に対す
   るピペット基準ビット；フィーダスロットに対しフィー
   ダの種類に関する判定順序に影響を及ぼす各グリッパの
   種類に対する各フィーダの種類に関する重み；ＰＣＢ構
   成素子をフィーダスロットおよびインデックスステップ
   に割当てる際にこれら素子を考慮する順序に影響を及ぼ
   す分類パラメータ；およびフィーダ箇所およびインデッ
   クスステップの選定に影響を及ぼす各部品に対する基準
   ビット；を表わすことを特徴とする請求項１に記載のコ
   ンピュータ制御部品装着機の構成最適化方法。
7. 【請求項７】 多重ポートキャリアを集群化するコンピ
   ュータ制御部品装着機の構成を最適化するに当たり、該
   部品装着機はキャリア用サポートと、複数の番号を付さ
   れた６以上のピペットと、種々の異なる大きさまたは形
   状の部品用の各々が関連するピペットに装着された複数
   の番号付きピペットと、前記多重ポートキャリアを集群
   化するに要する部品を支承する複数の番号付されたフィ
   ーダと、選択されたフィーダから選択された部品をその
   関連するグリッパと相俟ってピックアップするとともに
   これら部品を、機器に記憶された複数のチャージの１つ
   に、従ってキャリアの選択された位置に搭載する把持装
   置を作動させる手段とを具え、各チャージによって群と
   してピックアップされた特定組みの部品を表わし、且つ
   キャリアを集群化するに必要なチャージのリストにより
   機器の作動を制御し得るチャージマップを構成するよう
   にしたコンピュータ制御部品装着機の構成を最適化する
   方法において、 （ａ）所定組みの部品および部品位置を有する所定のプ
   リント配線板を集群化するために機器の操作を制御する
   チャーマップを発生する手段を制御する１組のパラメー
   タを各々が表わす染色体ストリングの初期集団を発生す
   るステップを具え；染色体ストリングの１ビットまたは
   ビット組は少なくとも次に示すパラメータ、 （ｉ）割当てグリッパの種類の優先度および各グリッパ
   の種類に理想的に関連するフィーダの数を制御するパラ
   メータ； （ii）優先度を次の基準、即ち、到達度制限、適合の剛
   性および多重搭載機会に割当てることによりグリッパの
   種類に対するピペット位置の割当てを制御するパラメー
   タ； （iii) グリッパの種類当たりに割当てられたピペット
   位置当たりのフィーダの初期数を特定することによりフ
   ィーダを割当てる手段を制御し、且つ何れの順序でフィ
   ーダが割当てられるかを制御するパラメータ； （iv）部品を剛固にパッケージする手段または割当てを
   実行する手段を制御することによりフィーダ位置全体に
   亘り部品を配分する手段を制御するパラメータ；および （ｖ）部品の種類が割当てられる順序を制御することに
   より何れの部品を何れのフィーダに割当てるかを制御す
   るパラメータ；を表わし； （ｂ）搭載すべき部品のリストおよび機器の構成を制御
   するパラメータを表わす所定の染色体ストリングを供給
   する際に前記構成を発生し、且つ前記機器を有するキャ
   リアを所定の構成に集群化する装着時間を計算し得るチ
   ャージマップ発生機を設けるステップを具え、前記チャ
   ージマップ発生機は次のステップ； （ｉ）全てのフィーダスロットが割当てられるまで； ・パラメータ（ａｉ）に基づきグリッパの種類ｇｔを選
   択し、 ・パラメータ（aii)に基づきグリッパの種類ｇｔに対す
   るピペット位置ppを選択し、・ピペット位置ppが得られ
   る場合にはパラメータ（aiii）に基づきピペット位置pp
   により到達し得るフィーダを割当て、他に既に割当てら
   れたピペットｇｔに対する未使用フィーダを割当て； （ii）割当てられた各グリッパの種類に対し、 ・パラメータ（ａiv）に基づき多くのフィーダを各部品
   の種類に割当てを手段を決め、・パラメータ（av）に基
   づき部品を特定のフィーダに割当てる、を用いてチャー
   ジマップを発生するようにしたことを特徴とするコンピ
   ュータ制御部品装着機の構成最適化方法。
8. 【請求項８】 多重ポートキャリアを集群化するコンピ
   ュータ制御部品装着機の構成を最適化するに当たり、該
   部品装着機は１組のキャリア用サポートと、複数の番号
   を付された６以上のピペットと、種々の異なる大きさま
   たは形状の部品用の各々が関連するピペットに装着され
   た複数の番号付きピペットと、前記多重ポートキャリア
   を集群化するに要する部品を支承する複数の番号付され
   たフィーダと、ピペットを動かして選択されたフィーダ
   から選択された部品をその関連するグリッパと相俟って
   ピックアップするとともにこれら部品を、機器に記憶さ
   れた複数のチャージの１つに従ってキャリアの選択され
   た位置に搭載するピペット作動手段とを具え、各チャー
   ジは、適宜に組のキャリアがピペットの到達可能な区域
   である際の時間間隔中ピックアップされ且つ搭載された
   特定組みの部品を表わし、且つキャリアを集群化するに
   必要なチャージのリストにより機器の作動を制御し得る
   チャージマップを構成するようにしたコンピュータ制御
   部品装着機の構成を最適化する方法において、 （ａ）各々が複数のビットまたはビット組により表わさ
   れ、且つ発見的レイアウト発生器を制御する複数のパラ
   メータを表わす染色体ストリングの集団を発生するステ
   ップを具え、 この染色体ストリングは少なくとも次のパラメータ；グ
   リッパ−ピペット判定を行う順序に影響を及ぼす各々の
   グリッパの種類に対する重み；１つ以上のピペットが等
   しく必要となる際にグリッパ−ピペット判定に影響を及
   ぼす各々のグリッパの種類に対するピペット基準ビッ
   ト；フィーダスロットに対しフィーダの種類に関する判
   定順序に影響を及ぼす各グリッパの種類に対する各フィ
   ーダの種類に関する重み；キャリア構成素子をフィーダ
   スロットおよびインデックスステップに割当てる際にこ
   れら素子を考慮する順序に影響を及ぼす分類パラメー
   タ；およびフィーダ箇所およびインデックスステップの
   選定に影響を及ぼす各部品に対する基準ビット；を少な
   くとも表わし；この染色体ストリングは所定のキャリア
   を集群化する１つの完全な機器構成を表わし；さらに （ｂ）所定の機器の構成を表わす所定の染色体ストリン
   グを供給する際に完全なレイアウトおよびチャージリス
   トを計算し、この計算から前記機器を有するキャリアを
   所定の構成に集群化する装着時間を計算し得る発見的レ
   イアウト発生器を設けるステップと； （ｃ）遺伝的アルゴリズム，ＣＨＣ，を用いて搭載時間
   を最小にする機器構成を決める問題に対する可能な解を
   表わす新たな染色体ストリングを発生し、且つ親の染色
   体における前記ビットあるものを交差し、親の染色体ス
   トリング間の近親交配を除去し、親の染色体ストリング
   および子の染色体ストリングの双方を最適に含む存続を
   含み、発生した解が限定数の繰返し後に収斂される際に
   のみ集団突然変異を適用することにより前記遺伝的アル
   ゴリズムによって前にテストされた親の解から新たな子
   の解を発生するステップと； （ｄ）許容し得る短い時間にキャリアを集群化する機器
   構成を表わす染色体ストリングを発生するまでステップ
   （ｂ）および（ｃ）を繰返すステップと；を具えること
   を特徴とするコンピュータ制御部品装着機の構成最適化
   方法。
9. 【請求項９】 前記ステップ（ａ）のパラメータはグリ
   ッパ−ピペット判定の順序に影響を及ぼす各グリッパに
   割当てるべきピペットのターゲット番号を含むことを特
   徴とする請求項８に記載のコンピュータ制御部品装着機
   の構成最適化方法。
10. 【請求項１０】 請求項１〜９の何れかの項に記載のコ
    ンピュータ制御部品装着機の構成最適化方法に従って構
    成された部品装着機。