JP2004006962A - 部品実装順序最適化方法、その装置及びその記録媒体 - Google Patents

Abstract

【要　約】
　【課　題】　電子部品をプリント配線基板に実装する部品実装装置において、より短い実装時間を実現するために、部品実装装置の部品カセット群における各部品カセットの配列順序を最適化することが必要である。
　【解決手段】１つのタスクグループにおいて、ランダムに選択した２つの実装点を入れ替えた場合の総実装時間が小さくなるならば、それら２つの実装点を入れ替える。このような入れ替え操作を繰り返して行う。
　【選択図】　　　　図２２

Description

　本発明は、部品実装装置によって電子部品をプリント配線基板等の基板に実装するときの最適な順序を決定する方法等に関し、特に、複数の部品を吸着して基板に装着する作業ヘッドを備える部品実装装置を対象とする部品実装順序の最適化方法、その装置及びその記録媒体に関する。

　電子部品をプリント配線基板等の基板に実装する部品実装装置では、より短いタクト（実装時間）を実現するために、対象部品の実装順序について、最適化が行われる。具体的には、部品実装装置が装備する部品カセット群における各部品カセットの配列順序を最適化しておく必要がある。

　そのための従来の技術として、例えば、特開平０５−１０４３６４号公報に開示された部品装着順序最適化方法がある。この方法では、（１）部品カセット群を、その部品に適用される装着スピ−ドによってグル−プ分けし、同一グループ内の部品カセットを、２個ずつ組み合わせたときの装着点数の和が均等化されるように、同一基板に対する装着点数の多いものと少ないものを適宜組み合わせてペア群を構成し、（２）このカセットグル−プを装着スピード順に配置し、かつ、同一グル−プ内においては前記ペア毎に並べることによって、カセットの配列順序を決定し、（３）その後に、部品の装着順序のみをパラメータとして最適化処理を行う。

　これによって、カセット配列順序と部品の装着順序という２つのパラメータによる複雑な最適化が回避され、単一のパラメータによる短時間での最適化が実現される、というものである。
特開平０５−１０４３６４号公報

　しかしながら、このような従来の最適化方法は、作業ヘッドの吸着率（作業ヘッドによる部品の吸着→移動→装着という一連の繰り返し動作における１回の動作において吸着される部品の個数の最大個数に対する比率）が考慮されていないために、複数（例えば、１０個）の部品を吸着して基板に装着していく高機能な作業ヘッドを備える部品実装装置に適用することができないという問題がある。

　特に、最近の携帯電話機やノートパソコン等の電子機器の急激な需要の増大に伴い、複数の部品を一括で吸着して基板に装着していく生産性の高い作業ヘッドを備える部品実装装置が開発されており、そのような高機能な部品実装装置に対応した新たな部品実装順序の最適化方法が望まれている。

　そこで、本発明は、かかる問題点に鑑みてなされたものであり、複数の部品を吸着して基板に装着する作業ヘッドを備える部品実装装置を対象とする部品実装順序の最適化方法、その装置及び部品実装装置を提供することを目的とする。

　上記目的を達成するために、本発明に係る部品実装順序最適化方法は、部品を収納した部品カセットの並びから、最大ｎ個の部品を吸着することが可能な作業ヘッドで部品群を吸着し、ＸＹロボットにより前記作業ヘッドを移動させ基板に実装していく実装装置を対象とし、コンピュータの実行により部品の実装順序を最適化する方法であって、作業ヘッドによる部品の吸着・移動・装着という一連の動作の繰り返しにおける１回分の一連動作によって実装される部品群をタスクとした場合に、同時吸着可能な部品カセットの並びに対応する複数のタスクの並びからタスクグループを構成する部品について、最適化の対象となる全ての部品の取り得る実装順序それぞれを１つの状態とした場合の初期状態を第１状態として生成する初期化ステップと、前記タスクグループを構成する部品について、ランダムに選択した実装点を入れ替えることにより、前記第１状態を第２状態に変更する状態変更ステップと、前記第２状態に対応する実装順序に従って前記実装装置が全ての部品を実装することができ、かつ、それら全ての部品の実装に要する時間が第１状態における時間よりも小さいか否か判断する判断ステップと、前記実装装置が全ての部品を実装することができ、かつ、前記時間が第１状態における時間よりも小さいと判断された場合に、前記第２状態を新たな第１状態として、前記状態変更ステップ及び前記判断ステップを繰り返させて第１状態を更新していくことにより、部品の実装順序を最適化していく繰り返し制御ステップと、　を含むことを特徴とする。

　また、前記状態変更ステップでは、予め定められた複数の種類の変更方法からランダムに選択した１つの方法を採用して、前記第１状態を変更することを特徴とする。

　また、前記状態変更ステップで選択され得る複数の変更方法には、２つのタスクそれぞれに属する同一の部品種の部品それぞれを入れ替える方法が含まれることを特徴とする。

　また、最適の対象となる全ての部品は、一定範囲の高さの部品の集まりを一つの部品グループとする複数の部品グループに分類され、前記状態は、前記複数の部品グループそれぞれについて、前記部品カセットの並びに配置するときの優先順序パラメータと、同一種類の部品の集まりを１つの部品種とした場合における同一部品グループに属する部品種の並びを示す部品種順序パラメータとを含む中間言語によって表現されていることを特徴とする。

　また、前記状態変更ステップで選択され得る複数の変更方法には、前記複数の部品グループから２つの部品グループをランダムに選択し、それら部品グループの優先順位パラメータを入れ替える方法が含まれることを特徴とする
　また、前記状態変更ステップで選択され得る複数の変更方法には、同一の部品グループに属する複数の部品種から２つの部品種をランダムに選択し、それら部品種の部品種順序パラメータを入れ替える方法が含まれることを特徴とする。

　また、前記状態変更ステップでは、対象となる全ての状態を複数のグループに分類した場合における前記第２状態が属するグループが、前記複数のグループそれぞれについて等しい確立となるように、前記第２状態を生成することを特徴とする。

　また、上述の方法を実現する部品実装順序最適化装置及びその記録媒体を特徴とする。

　さらに、部品を収納した部品カセットの並びから、最大ｎ個の部品を吸着することが可能な作業ヘッドで部品群を吸着し、ＸＹロボットにより前記作業ヘッドを移動させ基板に実装していく実装装置を対象とし、コンピュータの実行により部品の実装順序を最適化する方法であって、最適化の対象となる全ての部品を、部品の高さに基づいて、小部品グループと汎用部品グループとに分類する分類ステップと、前記小部品グループに属する部品に対して、前記作業ヘッドによる部品の同時吸着が最大限できるようにする第１のアルゴリズムを用いて実装順序の最適化を行うステップと、前記汎用部品グループに属する部品に対して、取り得る実装順序の１つである状態を変化させながら最適な実装順序を導き出す第２のアルゴリズムを用いて実装順序の最適化を行うステップとを含むことを特徴とする

　本発明に係る部品実装順序最適化方法は、部品を収納した部品カセットの並びから、最大ｎ個の部品を吸着し、基板に実装していく作業ヘッドを備える実装装置を対象とし、コンピュータを用いて部品の実装順序を最適化する方法であって、最適化の対象となる全ての部品について、とり得る実装順序それぞれを１つの状態とした場合の初期状態を第１状態として生成する初期化ステップと、第１状態を暫定的に変更することにより、第２状態を生成する状態変更ステップと、生成された第２状態に対応する実装順序に従って前記実装装置が全ての部品を実装することができ、かつ、それら全ての部品の実装に要する時間が第１状態における時間よりも小さいか否かを判断する判断ステップと、前記実装装置が全ての部品を実装することができ、かつ、前記時間が第１状態における時間よりも小さいと判断された場合に、前記第２状態を新たな第１状態として、前記状態変更ステップ及び前記判断ステップを繰り返させて第１状態を更新していくことにより、部品の実装順序を最適化していく繰り返し制御ステップとを含むことを特徴し、前記状態変更ステップでは、予め定められた複数の種類の変更方法からランダムに選択した１つの方法を採用して、前記第１の状態を変更する。

　これによって、ランダムに選択された複数の方法による状態の探索が行われるので、局所的には最適であるが大局的には最適でない状態が最適状態として探索されてしまう危険性が少なくなる。

　ここで、最適化の対象となる全ての部品は、一定範囲の高さの部品の集まりを１つの部品グループとする複数の部品グループに分類され、前記状態は、前記複数の部品グループそれぞれについて、前記部品カセットの並びに配置するときの優先順序を示す優先順序パラメータと、同一種類の部品の集まりを１つの部品種とした場合における同一部品グループに属する部品種の並びを示す部品種順序パラメータとを含む中間言語によって表現されていてもよい。

　これによって、膨大な数の状態は、部品グループを単位とするパラメータと部品グループを構成する部品種を単位とするパラメータによる階層化されたパラメータによって特定されるので、それらパラメータを変更することによって容易に他の状態を得ることができ、偏りのない探索が行われる。

　また、前記状態変更ステップでは、対象となる全ての状態を複数のグループに分類した場合における前記第２状態が属するグループが、前記複数のグループそれぞれについて等しい確率となるように、前記第２状態を生成してもよい。

　これによって、タクトｖｓ状態の分布におけるグルーバルミニマムが最適解として確実に探索され得る。

　以下、本発明の実施の形態について図面を用いて詳細に説明する。

　図１は、本発明に係る電子部品実装システム１０全体の構成を示す外観図である。この電子部品実装システム１０は、上流から下流に向けて回路基板２０を送りながら電子部品を実装していく生産ラインを構成する複数の部品実装装置１００、２００と、生産の開始等にあたり、各種データベースに基づいて必要な電子部品の実装順序を最適化し、得られたＮＣデータを実装装置１００、２００にダウンロードして設定・制御する部品実装順序最適化装置３００とからなる。

　部品実装装置１００は、同時かつ独立して、又は、お互いが協調して（又は、交互動作にて）部品実装を行う２つの実装ユニット（第１実装ユニット１１０及び第２実装ユニット１２０）を備える。各実装ユニット１１０（１２０）は、テーピング部品を収納する最大４８個の部品カセット１１４の配列からなる２つの部品供給部１１５ａ及びｂと、それら部品カセット１１４から最大１０個の部品を同時吸着し基板に装着することができる１０個の吸着ノズルを有する作業ヘッド１１２（１０ノズルヘッド）と、その作業ヘッド１１２を移動させるＸＹロボット１１３と、作業ヘッド１１２に吸着された部品の吸着状態を検査するための認識カメラ１１６と、トレイ部品を供給するトレイ供給部１１７等を備える。

　図２は、部品実装装置１００の主要な構成を示す平面図である。シャトルコンベヤ１１８は、トレイ供給部１１７から取り出された部品を載せて、作業ヘッド１１２による吸着可能な所定位置まで運搬するための移動テーブルである。ノズルステーション１１９は、各種形状の部品種に対応するための交換用ノズルが置かれるテーブルである。

　各実装ユニット１１０（又は１２０）を構成する２つの部品供給部１１５ａ及びｂは、それぞれ、認識カメラ１１６を挟んで左右に配置されている。したがって、部品供給部１１５ａ又は１１５ｂにおいて部品を吸着した作業ヘッド１１２は、認識カメラ１１６を通過した後に、基板の実装点に移動し、吸着した全ての部品を順次装着していく動作を繰り返す。

　ここで、作業ヘッド１１２による部品の吸着・移動・装着という一連の動作の繰り返しにおける１回分の動作（吸着・移動・装着）、又は、そのような１回分の動作によって実装される部品群）を「タスク」と呼ぶ。例えば、１０ノズルヘッド１１２によれば、１個のタスクによって実装される部品の最大数は１０となる。

　図３は、作業ヘッド１１２と部品カセット１１４の外観及び位置関係を示す図である。この作業ヘッド１１２は、最大１０個の吸着ノズル１１２ａ〜１１２ｂ１０を装着することが可能であり、このときには、１０個の部品カセット１１４それぞれから部品を一括吸着することができる。

　なお、１つの部品カセット１１４には１つの部品種（テーピング部品）だけが装填される。また、部品供給部１１５ａ及びｂにおける部品カセット１１４の位置又は並びを「Ｚ軸」又は「Ｚ軸上の位置」と呼び、部品供給部１１５ａの最左端を「１」とする連続番号等が用いられる。したがって、テーピング部品についての部品種の実装順序を決定することは、各部品種（又は、それら部品を収納した部品カセット１１４）のＺ軸を決定することに等しい。

　図４は、図１に示された部品実装順序最適化装置３００の構成を示す機能ブロック図である。この部品実装順序最適化装置３００は、生産ラインを構成する各設備の仕様等に基づく各種制約の下で、対象となる基板の部品実装におけるラインタクト（サブ設備ごとのタクトの最大値）を最小化するように、部品実装用ＣＡＤ装置等から与えられた全ての部品を対象として、各サブ設備で実装すべき部品及び各サブ設備における部品の実装順序を決定し、最適なＮＣデータを生成するコンピュータ装置であり、表示部３０２、入力部３０３、入出力制御部３０１、部品グループ生成部３０４、ラインバランス最適化部３０５、状態最適化部３０６、データベース記憶部３０７及び通信Ｉ／Ｆ部３０８から構成される。

　入出力制御部３０１は、各構成要素３０２〜３０８を制御することによって、本部品実装順序最適化装置３００による部品実装順序の最適化条件（レベル、要求精度、最適化処理の最大許容時間等）についての操作者からの指示を取得したり、その条件に合致した最適化処理を選択し開始させたり、最適化の結果を操作者に提示したり、最終的なＮＣデータを部品実装装置１００、２００にダウンロードさせたりする。

　表示部３０２はＣＲＴやＬＣＤ等であり、入力部３０３はキーボードやマウス等であり、これらは、入出力制御部３０１による制御の下で、本部品実装順序最適化装置３００と操作者とが対話する等のために用いられる。通信Ｉ／Ｆ部３０８は、ＬＡＮアダプタ等であり、本部品実装順序最適化装置３００と部品実装装置１００、２００との通信に用いられる。

　データベース記憶部３０７は、この部品実装順序最適化装置３００による最適化処理に用いられるモデリングデータ（実装点データ３０７ａ、パーツライブラリ３０７ｂ及び実装装置情報３０７ｃ）を予め記憶している。

　図５〜図７は、それぞれ、実装点データ３０７ａ、パーツライブラリ３０７ｂ及び実装装置情報３０７ｃの例を示す。

　実装点データ３０７ａは、実装の対象となる全ての部品の実装点を示す情報の集まりである。図５に示されるように、１つの実装点ｐiは、部品種ｃi、Ｘ座標ｘi、Ｙ座標ｙi、制御データφiからなる。ここで、「部品種」は、図６に示されるパーツライブラリ３０７ｂにおける部品名に相当し、「Ｘ座標」及び「Ｙ座標」は、実装点の座標（基板上の特定位置を示す座標）であり、「制御データ」は、その部品の実装に関する制約情報（使用可能な吸着ノズルのタイプ、作業ヘッド１１２の最高移動速度等）である。なお、最終的に求めるべきＮＣデータとは、ラインタクトが最小となるような実装点の並びである。

　パーツライブラリ３０７ｂは、部品実装装置１００、２００が扱うことができる全ての部品種それぞれについての固有の情報を集めたライブラリであり、図６に示されるように、部品種ごとの部品サイズ、タクト（一定条件下における部品種に固有のタクト）、その他の制約情報（使用可能な吸着ノズルのタイプ、認識カメラ１１６による認識方式、作業ヘッド１１２の最高速度比等）からなる。なお、本図には、参考として、各部品種の外観も併せて示されている。

　実装装置情報３０７ｃは、生産ラインを構成する全てのサブ設備（独立して部品実装を実行する装置単位で、実装ユニット又は部品実装装置）ごとの装置構成や制約を示す情報であり、図７に示されるように、作業ヘッドのタイプ等に関するヘッド情報、作業ヘッドに装着され得る吸着ノズルのタイプ等に関するノズル情報、部品カセット１１４の最大数等に関するカセット情報、トレイ供給部１１７が収納しているトレイの段数等に関するトレイ情報等からなる。

　部品グループ生成部３０４は、データベース記憶部３０７に格納された実装点データ３０７ａによって特定される全ての実装部品を、部品厚みの点から、図８（ａ）に示されるような９つの部品グループＧ[1]〜Ｇ[9]に分類する。具体的には、実装点データ３０７ａが示す全ての部品種を参照することで、図８（ｂ）に示されるような、同一部品種ごとの員数を示す部品表を作成し、パーツライブラリ３０７ｂにおける部品サイズを参照することで、全ての部品種それぞれを９つの部品グループＧ[1]〜Ｇ[9]のいずれかに対応づける。そして、その分類結果（各部品グループに属する部品種及び員数等）をラインバランス最適化部３０５に通知する。

　ラインバランス最適化部３０５は、部品グループ生成部３０４から通知された部品グループの情報に基づいて、部品厚みの薄い部品グループから順に実装することを遵守しつつ、ラインタクトが最小となるように、ラインバランスを最適化（サブ設備ごとのタクトを平準化）する。そのために、状態最適化部３０６と連携しながら動作する３つの機能モジュール（第１ＬＢＭ部３０５ａ、第２ＬＢＭ部３０５ｂ及び第３ＬＢＭ部３０５ｃ）を有する。

　なお、部品厚みの薄い部品グループを優先して実装することとしているのは、基板に部品を装着する際の作業ヘッド１１２の移動を円滑にさせ、実装の品質を高めるためである。

　第１ＬＢＭ部３０５ａは、部品グループ生成部３０４から通知された９つの部品グループをタスクグループの単位で各サブ設備でのタクトがほぼ等しくなるようにラフに振り分ける。つまり、粗い調整によるラインバランスの最適化を行う。ここで、「タスクグループ」とは、タスクの集まりをいい、最適化のために部品の実装順序を入れ替えることが可能な部品群の範囲と一致する。

　第２ＬＢＭ部３０５ｂは、第１ＬＢＭ部３０５ａによってラフに振り分けられた各サブ設備ごとのタスクグループをサブ設備間で移動させることによりラインタクトを最小化する。つまり、細かい調整によるラインバランスの最適化を行う。

　第３ＬＢＭ部３０５ｃは、第２ＬＢＭ部３０５ｂにより最適化された状態（タスクグループの振り分け）に対して、部品種を単位として、第２ＬＢＭ部３０５ｂと同様の手順でラインバランスの最適化を行う。

　状態最適化部３０６は、部品グループ生成部３０４で生成された９個の部品グループそれぞれについて、各部品グループを構成するタスクグループを決定したり、決定したタスクグループごとの最適状態（各部品種のＺ軸、各部品種における部品（実装点）の実装順序を決定するものであり、小部品（ここでは、部品グループＧ[1]〜Ｇ[5]に属する部品）を対象として最適化を行う小部品最適化部３０６ａと、汎用部品（部品グループＧ[6]〜Ｇ[9]に属する部品）を対象として最適化を行う汎用部品最適化部３０６ｂと、それら小部品最適化部３０６ａおよび汎用部品最適化部３０６ｂにおける最適化に共通する計算処理を実行する最適化エンジン部３０６ｃとから構成される。なお、「状態」とは、対象となっている部品又は部品種がとり得る実装順序における個々をいう。

　なお、小部品最適化部３０６ａは、簡易で高速処理に向いたアルゴリズムを用いてタスクグループを決定したり状態の最適化を行い、一方、汎用部品最適化部３０６ｂは、緻密でインテリジェントなアルゴリズムを用いて状態の最適化を行う。これは、一般に、携帯電話機等の基板に実装される小部品の総数は、汎用部品に比べて極めて多い（例えば、９：１の比率）ことが分かっているので、それぞれに対応したアルゴリズムを用いて最適化を行うことで、より短時間で、より最適な解を求めるためである。

　最適化エンジン部３０６ｃは、小部品最適化部３０６ａ及び汎用部品最適化部３０６ｂから与えられたパラメータに基づいて、ヒューリスティックであるが確定的なアルゴリズム（山登り法）に基づく最適化計算と、確率的ではあるがグローバルに最適解を探索するアルゴリズム（マルチカノニカル法）に基づく最適化計算を実行する。

　次に、以上のように構成された部品実装順序最適化装置３００のラインバランス最適化部３０５及び状態最適化部３０６の動作を詳細に説明する。

　図９は、ラインバランス最適化部３０５の第１ＬＢＭ部３０５ａによるタスクグループのサブ設備への振り分け処理の様子を示す図である。

　第１ＬＢＭ部３０５ａは、部品厚みの薄い部品グループが先となるように全てのタスクグループを一列に並べ、その並びに対して、先頭から順に、サブ設備ごとのタクトが以下の式で示される値θに近くなるように、各タスクグループを上流のサブ設備から順に振り分けていく。

　θ＝（全部品グループを対象とした総タクト）／サブ設備の総数Ｎ
　なお、「全部品グループを対象とした総タクト」は、実装点データ３０７ａ及びパーツライブラリ３０７ｂを参照することにより特定され、「サブ設備の総数Ｎ」は、実装装置情報３０７ｃを参照することにより特定される。

　図１０は、第２ＬＢＭ部３０５ｂによるラインバランスの最適化（タスクグループの移動）の様子を示す図であり、図１０（ａ）は、最適化前におけるタクト分布（各サブ設備へのタスクグループの振り分け状態）を示し、図１０（ｂ）は、最適化によるタスクグループの移動の様子を示し、図１０（ｃ）は、最適化後におけるタクト分布を示す。

　ここで、本図に示されるタクト分布において、縦軸は、タクトの大きさを示し、横軸は、生産ラインを構成する全てのサブ設備（ここでは６台）の並び（上流から下流に向けた並び）を示し、タスクグループは、そのタクトを高さとするブロック「ＴＧｎ−ｍ」として示されている。ｎは、そのタスクグループが属する部品グループの番号１〜９を示し、ｍは、同一の部品グループに属するタスクグループを区別する番号である。

　なお、各サブ設備は、振り分けられた複数のタスクグループに対して、部品厚みの薄い部品グループに属するものを先に実装する。ただし、同一の部品グループに属する複数のタスクグループに対しては、その順序の制約を受けないものとする。例えば、サブ設備［３］は、ＴＧ３−３→ＴＧ３−１→ＴＧ３−２の順で実装してもよい。

　図１１は、図１０（ａ）〜（ｃ）に示された第２ＬＢＭ部３０５ｂによるラインバランスの最適化手順を示すフローチャートである。

　第２ＬＢＭ部３０５ｂは、まず、第１ＬＢＭ部３０５ａが生成した図１０（ａ）に示される初期状態（タスクグループの振り分け）に対して、サブ設備ごとのタクトが最大であるサブ設備［Ｓmax］と最小であるサブ設備［Ｓmin］を特定する（ステップＳ５００）。例えば、Ｓmax＝５、Ｓmin＝２と特定する。

　そして、サブ設備［Ｓmax］のタクトをラインタクトＬＴとして記憶する（ステップＳ５０１）。例えば、ＬＴ＝サブ設備［５］として記憶する。

　次に、サブ設備［Ｓmin］からサブ設備［Ｓmax−１］までのサブ設備［ｉ］について順に、隣接する２つのサブ設備間で、移動可能なタスクグループを移動させていく（ステップＳ５０２〜Ｓ５０７）。

　つまり、サブ設備［ｉ＋１］からサブ設備［ｉ］に、一つタスクグループを仮移動し（ステップＳ５０３）、それでもなお、サブ設備［ｉ］のタクトがラインタクトＬＴよりも小さいか否かを確認する（ステップＳ５０４）。

　その結果、小さいことを確認できた場合にだけ、そのタスクグループを実際に移動させる（ステップＳ５０５）。つまり、サブ設備［ｉ］及びサブ設備［ｉ＋１］のタクトを更新する。例えば、タスクグループＴＧ３−１をサブ設備［３］からサブ設備［２］に移動させる。なお、移動させる候補となるタスクグループは、部品厚みの薄い部品グループに属するものを優先して選択するものとする。

　このようなタスクグループの移動を、サブ設備［Ｓmin］からサブ設備［Ｓmax−１］について順に繰り返し終えると（ステップＳ５０２〜Ｓ５０６）、最後に、サブ設備［Ｓmax］のタクトが減少したか否か、つまり、サブ設備［Ｓmax］からサブ設備［Ｓmax−１］に１つ以上のタスクグループが移動されたか否かを判断する（ステップＳ５０７）。

　その結果、減少している場合には、まだ最適化の余地が残されていると判断し、再び、同様の最適化（ステップＳ５００〜Ｓ５０７）を繰り返し、そうでない場合には、これ以上の最適化は困難であると判断し、終了する（ステップＳ５０７）。

　なお、移動可能なタスクグループが複数個存在する場合には、移動対象の選択について自由度があるので、計算時間の許される範囲で、移動させるタスクグループの組合せを各種試みることとする。

　このようにして、最小タクトのサブ設備と最大タクトのサブ設備間において、タスクグループの移動を順次試みることで、最大タクト（ラインタクト）の減少化、つまり、ラインバランスの最適化が実現される。

　以上の最適化が完了すると、次に、第３ＬＢＭ部３０５ｃは、第２ＬＢＭ部３０５ｂにより最適化された状態（タスクグループの振り分け）に対して、部品種を単位として、第２ＬＢＭ部３０５ｂと同様の手順でラインバランスの最適化を行う。

　つまり、第２ＬＢＭ部３０５ｂは、タスクグループを単位として、隣接するサブ設備間を移動させたが（ステップＳ５０３、Ｓ５０５）、第３ＬＢＭ部３０５ｃは、タスクグループに代えて、各タスクグループを構成する部品種を単位として、サブ設備間を移動させる。したがって、２つのサブ設備間でのタクトの増減の刻みは、第２ＬＢＭ部３０５ｂによる場合よりも小さくなり、よりきめ細かい最適化が行われる。これによって、ラインタクトＬＴがさらに減少され得る。

　図１２は、状態最適化部３０６の小部品最適化部３０６ａによる小部品の実装順序最適化の概略手順を示すフローチャートであり、２つの大きなステップからなる。

　小部品最適化部３０６ａは、まず、全ての実装部品を対象として、テトリスダイヤグラムを生成する（ステップＳ５２０）。これは、部品種を単位とした配列、即ち、部品カセット１１４の並び（Ｚ軸）を決定することに相当する。

　ここで、「テトリスダイヤグラム」とは、図１３に示されるような２次元のダイヤグラムであり、縦軸を作業ヘッドによる部品の吸着順とし、横軸を部品カセット１１４（部品種）の配列（Ｚ軸）とし、実装の対象となる個々の部品（実装点）を単位矩形（正方形又は長方形）で配置した図のことである。

　なお、この図１３には、４ノズルヘッドを対象としたテトリスダイヤグラムが示されており、最大４個の単位矩形が横に繋がったものが実装（吸着・移動・装着）の１回分（つまり、タスク）に相当し、丸で囲まれた一繋がりのタスクの集合がタスクグループに相当する。したがって、本図には、合計３つの独立したタスクグループが示されている。

　このようなテトリスダイヤグラムの生成は、作業ヘッドができるだけ多くの部品を同時吸着することができるように、部品種の相対的な配列を決定する作業にに相当し、言い換えると、全ての部品種を、互いに独立した複数の配列グループ（タスクグループ）に分割することに相当する。

　次に、小部品最適化部３０６ａは、図１２に示されるように、上記ステップＳ５２０で決定されたタスクグループ（配列が固定化された部品種群）ごとに、その総タクトが小さくなるように、各部品種を構成する部品の装着順序を決定する（ステップＳ５２１）。これは、同一の部品カセット１１４から取り出した（吸着した）部品であっても、どの実装点に装着するかによって、同一タスクにおける直前の実装点からの距離が異なるので、装着時における作業ヘッド１１２の移動距離（実装時間）を短縮化することに相当する。

　以下、上述の２つのステップＳ５２０、Ｓ５２１における詳細な処理内容を説明する。
（１）テトリスダイヤグラムの生成（ステップＳ５２０）
　小部品最適化部３０６ａは、許容される処理時間や操作者による指定等に基づいて、以下の２種類のアルゴリズムの一つを採用する。
（１−１）タスクグループ生成法
　この方法は、一定範囲内（吸着ノズル数の２倍以下）の個数の部品種からなるタスクグループの生成を繰り返していく手法であり、基本的には、以下の２つの大きなステップ（第１及び第２ステップ）からなる。なお、図１４は、これら第１及び第２ステップを説明するための図であり、図１４（ａ）は、対象となる部品を員数の多い部品種の順に並べた（ソートした）部品ヒストグラムであり、図１４（ｂ）は、これら第１及び第２ステップによって生成されるテトリスダイヤグラムである。

　［第１ステップ］
　このステップでは、１つのタスクグループを生成する前半処理、つまり、員数の多い部品種の順に右方向（Ｚ軸方向）に部品ヒストグラムを並べる。具体的には、
　(i)まだ配置されていない部品種の中で員数が最大の部品種（１番部品種）をＺ軸上に置く。

　(ii)その右隣に２番目の員数の部品種（２番部品種）を置く。

　(iii)２番部品種の右隣に３番目の員数の部品種（３番部品種）を置く。

　(iv)以下、これを作業ヘッドの吸着ノズル数Ｌ（ここでは「４」）まで繰り返す。

　この結果、図１４（ａ）の部品ヒストグラムから４つの部品種４００が取り出され、図１４（ｂ）に示される箇所４００に配置される。

　［第２ステップ］
　このステップでは、前半処理で生成されたダイヤグラムに対して、同時吸着数がＬに満たないタスクの同時吸着数がＬとなるように、左方向に部品ヒストグラムを配置していく。具体的には、
　(i)１番部品種の員数からＬ番部品種の員数を引く。

　(ii)得られた員数差以下であって、その員数差に最も近い員数を持つ部品種（Ｌ＋１番部品種）を１番部品種の左隣に置く。

　(iii)２番部品種から（Ｌ−１）番部品種の員数を引く。

　(iv)その員数差以下であって、その員数に最も近い員数を持つ部品種を（Ｌ＋１）部品種の左隣に置く。

　(v)以下、これを（Ｌ−１）回繰り返す。

　この結果、図１４（ａ）の部品ヒストグラムにおける２つの部品種４０１ａ及び４０１ｂが取り出され、図１４（ｂ）に示される箇所４０１に配置される。これによって、部品種４００及び部品種４０１からなる１つのタスクダイヤグラムが完成する。これによって、これら６種の部品種からなるタスクグループについて、相対的なＺ軸が決定されたことになる。

　以上の第１及び第２ステップによるタスクグループの生成を、対象の部品種が無くなるまで繰り返す。

　ここで、もし、上記第２ステップの条件を満たす未配置の部品種が無くなってしまった場合には、上記第１及び第２ステップに代えて、以下の３つのステップ（第３〜第５ステップ）を実行する。図１５は、これら第３〜第５ステップを説明するための図であり、図１５（ａ）は、部品ヒストグラムのうち未配置の部分（実線で囲まれた部分）を示し、図１５（ｂ）は、これら第３〜第５ステップによって生成されるテトリスダイヤグラムを示す。

　［第３ステップ］
　このステップでは、未配置の部品ヒストグラムを整形して部分ヒストグラムを生成する。具体的には、
　(i)まだ配置されていない部品種の員数の最小値を求める。

　(ii)まだ配置されていない部品種それぞれの員数から（最小値−１）を引く。

　このような減算処理の結果、未配置の部品ヒストグラムにおける員数は、図１５（ａ）における太い実線で囲まれた部分ヒストグラムとなり、以下、この部分ヒストグラムにおける員数を用いて、以下の第４及び第５ステップを進める。

　［第４ステップ］
　このステップは、上述の第１ステップに相当する。具体的には、
　(i)まだ配置されていない部品種の中で員数最大の部品種（１番部品種）をＺ軸上に置く。

　(ii)その右隣に２番目の員数の部品種（２番部品種）を置く。

　(iii)２番部品種の右隣に３番目の員数の部品種（３番部品種）を置く。

　(iv)以下、これを作業ヘッドの吸着ノズル数Ｌ（ここでは「３」）まで繰り返す。

　この結果、図１５（ａ）の部品ヒストグラムから３つの部品種４１０が取り出され、図１５（ｂ）に示される箇所４１０に配置される。

　［第５ステップ］
　このステップは、上述の第２ステップに相当する。具体的には、
　(i)１番部品種の員数から、（Ｌ番部品種の員数−１）の値を引く。

　(ii)その員数差以下であって、その員数差に最も近い員数を持つ部品種（Ｌ＋１部品種）を１番部品種の左隣に置く。

　(iii)（Ｌ＋１）番部品種からＬ番部品種の員数を引く。

　(iv)その員数差以下であって、その員数差に最も近い部品種を（Ｌ＋１）番部品種の左隣に置く。

　(v)以下、これをＬ回繰り返す。

　この結果、図１５（ａ）の部品ヒストグラムにおける３つの部品種４１１が取り出され、図１５（ｂ）に示される箇所４１１に配置される。これによって、部品種４１０及び部品種４１１からなる１つのタスクダイヤグラムが完成する。これによって、上記第１及び第２ステップで取り残された部品種、つまり、員数の差が小さい部品種についても、同時吸着が可能なタスクの集まりからなるタスクグループが生成され、それらの部品種について相対的なＺ軸が決定されたことになる。
（１−２）刈り上げ法
　この方法は、員数の多い部品種の順に並べた部品ヒストグラムをそのままＺ軸に配置することを基本とし、最大個数（Ｌ個）の部品を同時吸着することができない箇所についてだけ、上述のタスクダイヤグラム生成法を適用する手法であり、以下の２つの大きなステップ（第１及び第２ステップ）からなる。

　［第１ステップ］
　このステップでは、部品ヒストグラムから、Ｌ個の部品並びからなるタスクを取り出することを繰り返す（刈り上げていく）。

　図１６及び図１７は、刈り上げ法における第１ステップを説明するための図であり、図１６は、実装の対象となる全ての部品を員数の多い部品種の順に並べた部品ヒストグラムであり、図１７は、図１６の部品ヒストグラムから、Ｌ個（ここでは、１０個）の部品並び（最大個数の部品を同時吸着した場合のタスク）の単位で部品を取っていく（刈り上げていく）様子を示す図である。

　刈り上げにおいては、員数の少ない部品種が先に無くなるように、つまり、部品ヒストグラムにおける右端の部品種から部品が無くなっていくように、Ｌ個の部品並び（〇、△及び×のいずれかを含む１０個の矩形並び）を取り除いていく。これを、Ｌ個の部品並びの単位で取る除くことができなくなるまで繰り返す。

　［第２ステップ］
　このステップでは、上述の刈り上げ後における残り部品からなる部品ヒストグラムに対して、上述のタスクグループ生成法に準じたダイヤグラムを生成する。

　図１８及び図１９は、刈り上げ法における第２ステップを説明するための図であり、図１８は、第１ステップでの刈り上げ後に残された部品を対象として、員数の多い順に再構築された部品ヒストグラムであり、図１９は、再構築された部品ヒストグラムに対して、上述のタスクグループ生成法に準じたダイヤグラムの生成を行っている様子を示す図である。なお、再構築された部品ダイヤグラムの幅（部品種の数）は、上記第１ステップの処理内容より、必ず、（Ｌ−１）以下となる。

　この第２ステップでは、具体的には、以下の処理を行う。

　(i)刈り上げ後に残った部品について、図１８に示された部品ヒストグラムを生成するとともに、合計員数（ここでは、１００個）を算出する。

　(ii)算出した合計員数をＬ（ここでは、１０）で割り、得られた値（ここでは、１０）をタスク数とするテトリスダイヤグラムの作成を目指す。

　(iii)そのために、図１９に示されるように、得られたタスク数（１０）よりも大きな員数を持つ部品種について、その超過分の員数（又は、超過部分の員数を分割したもの）だけ切り取り、部品ヒストグラムの左側に補完して置いていく。

　図２０は、以上の第１及び第２ステップによる刈り上げ法によってＺ軸が決定された部品種についてのテトリスダイヤグラムである。この図に示されるように、全ての部品は、最大個数（１０個）の部品が同時吸着されるタスクだけから構成され、最大の同時吸着率で効率よく実装され得る。

　図２１は、図２０に示されたテトリスダイヤグラムに対応する（Ｚ軸を変化させない再構築した）部品ヒストグラムである。

　このヒストグラムから分かるように、刈り上げ法によれば、員数の多い部品種が左位置に配列されるという傾向が維持される。このことは、刈り上げ法が、作業ヘッド１１２の移動軌跡（右側の部品供給部１１５ｂに対しては、部品を吸着した後に、必ず、部品供給部１１５ｂの左端に置かれた２次元カメラの前を通過すること）を考慮した（総移動距離を小さくする、即ち、総タクトを小さくする）部品配置の決定方法であることを意味する。

　なお、左側の部品供給部１１５ａに対しては、上述の処理において、Ｚ軸方向に対称な処理を施せばよい。つまり、員数の小さい順に部品種を並べた後に、同様の手順でタスクを刈り上げていくことで、ダイヤグラムを生成すればよい。
（２）各部品種を構成する部品の装着順序の最適化（ステップＳ５２１）
　このステップでは、小部品最適化部３０６ａは、許容される処理時間や操作者による指定等に基づいて、以下の２種類のアルゴリズムの一つ以上を採用する。
（２−１）ランダム選択法
　この方法は、１つのタスクグループにおいて、ランダムに選択した２つの実装点を入れ替えた場合の総タクトが小さくなるならば、それら２つの実装点を入れ替える、という処理を繰り返す手法である。

　図２２は、ランダム選択法による部品の装着順序の最適化の手順を示すフローチャートであり、図２３は、ランダム選択法によって２つの実装点が入れ替えられる様子を示すである。

　まず、小部品最適化部３０６ａは、初期状態での総タクトを算出する（ステップＳ５３０）。なお、ここでの状態は、１つのタスクグループを構成する全ての部品（実装点）について実装順序が一定のパターンに定められた状態である。したがって、一つの状態に対する総タクトは、データベース記憶部３０７に記憶された情報３０７ａ〜ｃから一義的に決定される。

　次に、それら全ての実装点の中からランダムに２つを選択し（ステップＳ５３１）、選択した２つの実装点の順序を入れ替えた場合の総タクト（仮タクト）を算出する（ステップＳ５３２）。図２３には、実装点Ｂ２とＢ４とが入れ替えられた場合の状態例が示されている。

　そして、いま算出された仮タクトが、直前の状態におけるタクトよりも小さいか否か判断する（ステップＳ５３３）。

　その結果、小さい場合には、それら２つの実装点の入れ替えを実施する（ステップＳ５３４）。つまり、現在の状態と総タクトについて、それら実装点を入れ替えた場合のものに更新して記憶する。そして、その時点での終了条件（その状態でのタクトが操作者によって予め指定された目標タクトよりも小さいか、又は、一定の処理時間に達した等）を満たすか否か判断し（ステップＳ５３５）、満たす場合に処理を終了する。

　一方、２つの実装点の入れ替えによってもタクトが小さくならない場合（ステップＳ５３３でＮｏ）、及び、終了条件を満たさない場合（ステップＳ５３５でＮｏ）には、終了条件が満たされるまで、再び、同様の処理を繰り返す（ステップＳ５３１〜Ｓ５３３〜Ｓ５３５）。このようにして、ランダム選択法により、費やした実行時間に応じて、タスクグループごとのタクトが小さくなり、部品実装順序が最適化され。
（２−２）交差解消法
　この方法は、入れ替える２つの実装点をランダムに選択するのではなく、一定の基準、即ち、タスクごとの実装点を直線で接続して得られる折れ線（パス）どうしの交差があればそれを解消するという基準を満たす実装点を選択して入れ替える手法である。

　図２４は、５個の実装点からなる３つのタスクについて、交差解消法により部品の装着順序を最適化する様子を示す図であり、図２４（ａ）は、折れ線の交差が解消される前の装着順序（タスクごとの折れ線の分布）を示し、図２４（ｂ）は、折れ線の交差が解消された後の装着順序を示す。なお、同一部品種の実装点は、同一模様の丸印で示されている。

　まず、小部品最適化部３０６ａは、データベース記憶部３０７の実装点データ３０７ａ等を参照することによって、初期状態における全ての交差を特定する。ただし、ここでの交差は、同一タスクに属する連続して装着する２つの実装点を結ぶ線分と、他のタスクに属する同様の線分との交差であって、それら線分の両端の実装点に用いられる部品の部品種がそれら線分同士で同一であるものに限られる。

　次に、特定した全ての交差について、順次、交差を解消するように線分の接続を変更する。なお、解消の前後において、各線分の両端に位置する部品の部品種は変更されないので、この線分の接続変更は一義的に定まり、かつ、その接続変更によって各タスクを構成する部品種の並びが変化することはない。

　このような交差解消法によって、タスク間における作業ヘッド１１２の無駄な移動が解消される。つまり、一つの部品を装着した後に移動すべき実装点は、作業ヘッド１１２の移動に伴う無駄なタクトの増加が抑えられた部品の実装順序が決定される。
（２−３）戻り軌跡法
　この方法は、１つのタスクグループにおいて、１つのタスクの部品装着を完了した後に、次のタスクの部品を吸着するために移動する作業ヘッド１１２の戻り軌跡に着目し、そのタスクグループを構成するタスクの並び（タスク単位での順序）を最適化する手法である。

　図２５は、戻り軌跡法によりタスクの順序を最適化する手順を説明するための図である。ここには、Ｚ軸における部品供給部１１５ａ及びｂそれぞれに１０個のタスクが配置されている場合における基板と部品供給部間を行き来する作業ヘッド１１２の移動軌跡（実装経路）が矢印線で示されている。

　ここで、丸印は、作業ヘッド１１２の代表的な位置を示す。つまり、基板上の丸印は、１つのタスクにおいて最後の部品を装着し終えた直後の作業ヘッド１１２の位置（最終実装点）を示し、Ｚ軸における丸印は、２０個のタスクそれぞれにおいて最初に部品を吸着するときの作業ヘッド１１２の位置（吸着パターン）を示す。なお、丸印に付された数値は、各吸着パターン（タスク）を区別する番号である。

　［第１ステップ］
　このステップでは、以下のルールに従って、実装経路を描く。

　(i)各タスクの最終実装点から最短距離にある吸着パターンに戻る、つまり、戻り軌跡を最小にする。

　(ii)１番吸着パターンを始点にして実装経路を順次描いていく。なお、１つの吸着パターンは１つのタスクに相当するので、その吸着パターンに対応する最終実装点は一義的に特定される。図２５では、１→５→１４→２→８→３→１７→１２→１６→１の順で吸着パターンと最終実装点とを接続する実装経路が描かれる。

　(iii)最初の吸着パターン（１番吸着パターン）に戻ったら、それを最短巡回部分経路１とする。

　(iv)次に、これまで見つかった最短巡回部分経路に含まれない吸着パターンを探す。図２５では、４番吸着パターンが見つけられる。

　(v)上記(ii)に戻り、未だ使用されていない吸着パターンが無くなるまで、繰り返す。図２５では、５つの最短巡回部分経路が描かれている。

　このような第１ステップにより、特定の吸着パターンから開始した場合における、作業ヘッド１１２の戻り軌跡が最短となるような吸着パターンの順序、即ち、タスクの順序が決定されたことになる。

　［第２ステップ］
　次に、第１ステップで描かれた全ての最短巡回部分経路それぞれにおいて、どの吸着パターンから開始すればよいかを特定する。具体的には、１つの最短巡回部分経路に属する全ての部品の実装を終えてから次の最短巡回部分経路を開始するのに移動させる作業ヘッド１１２の戻り軌跡が最短となるように、各最短巡回部分経路における最初の吸着パターン及びそれら最短巡回部分経路の順序を決定する。

　これによって、１つのタスクグループを構成する全てのタスクを対象として、タスク間における作業ヘッド１１２の戻り軌跡が短くなるように、タスクの実行順序が決定されたことになる。

　なお、図２５は、２０個の吸着パターンが異なる位置となるタスクグループにおける実装経路であったが、図２６に示されるように、同一位置の複数の吸着パターンが含まれるタスクグループについても同様の最適化をすることができる。このときには、同一位置の吸着パターンに対応する最終実装点の選択において自由度があるので、複数の選択パターンに対応するタスクグループの総タクトを算出し、それらの中からタクトが最小となる最終実装点を選択し、最短巡回部分経路を作成すればよい。

　以上のように、ランダム選択法及び交差解消法によって、タスクの形を変えずに、(i)タスク内の実装順序の最適化、及び、(ii)全タスクを考慮した実装順序の最適化が行われ、一方、戻り軌跡法によって、全てのタスクがフィックスされた後に（つまり、各タスクのメンバが決まった状態で）、タスクの順序についての最適化が行われる。

　図２７（ａ）は、汎用部品最適化部３０６ｂによる汎用部品の実装順序を最適化する際の手順を示すフローチャートであり、図２７（ｂ）は、その最適化による最適解の探索アプローチを説明するための図（とり得る全ての状態それぞれのタクトを示す図）である。なお、フローチャートにおいて、「ＨＣ法」は山登り法を意味し、「ＭＣ法」はマルチカノニカル法を意味する。

　図２７（ａ）に示されるように、汎用部品最適化部３０６ｂは、部品グループＧ[6]〜Ｇ[9]に属する全ての部品（汎用部品）を対象として、初期状態Ｘを生成した後に（ステップＳ５５０）、初期状態Ｘに対して、山登り法による最適化を最適化エンジン部３０６ｃに実行させることによって、最適状態Ｘoptを求めた後に（ステップＳ５５１）、初期状態Ｘに対して、マルチカノニカル法による最適化を最適化エンジン部３０６ｃに実行させることによって、上記ステップＳ５５１で求められた最適状態Ｘoptを更新し（ステップＳ５５２）、最後に、更新された最適状態Ｘoptに対して、再び、山登り法による最適化を最適化エンジン部３０６ｃに実行させることによって、上記ステップＳ５５２で得られた最適状態Ｘoptを更新する（ステップＳ５５３）。

　このように、局所的な最適解を確実に求める山登り法による最適化（ステップＳ５５１、Ｓ５５３）の途中過程に、グローバルな始点で最適解を探索するマルチカノニカル法による最適化（ステップＳ５５２）が挿入されているので、局所的には最適状態であるがグローバル的には最適状態でない状態（図２７（ｂ）に示される状態1)等）の探索で終わってしまうことが回避され、グローバルな最適状態（図２７（ｂ）に示される状態5)）が求められる。

　図２８は、図２７（ａ）に示された山登り法による最適化（ステップＳ５５１、Ｓ５５３）の詳細な手順を示すフローチャートである。つまり、初期状態Ｘや終了条件等についての通知を受けた最適化エンジン部３０６ｃは、その初期状態Ｘを生成した後に（ステップＳ５６０）、外部ループ終了条件が満たされるまで（ステップＳ５６１）、内部ループを繰り返す（ステップＳ５６２〜Ｓ５６８）。ここで、外部ループ終了条件とは、それ以上の最適解が存在しないことを確認するための条件であり、例えば、状態変化を起こす全ての種類のパラメータを変化させた（探索した）こと等であり、内部ループ終了条件とは、１つの種類のパラメータについて、一定範囲の変化をさせた（探索した）こと等である。

　内部ループにおいて、最適化エンジン部３０６ｃは、まず、後述する９種類の状態変更から汎用部品最適化部３０６ｂが選択した１つを用いて、状態候補Ｘtmpを生成し（ステップＳ５６３、Ｓ５６４）、その候補状態Ｘtmpが、後述するフィージビリティ（実現可能性）を有し（ステップＳ５６５）、かつ、その候補状態Xtmpのタクトが直前の状態のタクトよりも小さい場合に（ステップＳ５６６、Ｓ５６７）、それら状態とタクトを更新する（ステップＳ６８）。

　これによって、局所的に最適な状態が確定的に得られる。

　図２９は、図２７（ａ）に示されたマルチカノニカル法による最適化（ステップＳ５５２）の詳細な手順を示すフローチャートである。本図において、ビン番号は、例えば、図２７（ｂ）に示された横軸（とり得る状態の全て）をＮ個に均等分割して得られる各区間（ビン）を示す番号であり、ヒストグラムＨ[i]は、ビン番号ｉのビンに属する候補状態Ｘtmpが選択され（ステップＳ５７６、Ｓ５７７）、その候補状態Ｘtmpが実現可能性を有し（ステップＳ５７８）、かつ、エントロピーを減少させる状態であると判断された（ステップＳ５７９〜Ｓ５８１）総回数を記憶する変数である。

　本図に示されたフローチャートと図２８に示された山登り法によるものとを比較して分かるように、状態Ｘをベースに状態候補Ｘtmpを生成し、それを受理するかどうかを決定するという一連の処理を繰り返す点で、これらの処理は共通する。異なる点は、受理決定の方法であり、図２８に示された山登り法では、状態候補Ｘtmpのタクトの方が状態Ｘよりも小さい場合に（確定的に）受理しているのに対し、図２９に示されたマルチカノニカル法では、タクトにおけるエントロピーを参照して状態候補Ｘtmpを確率的に受理していることである（ステップＳ５８０〜Ｓ５８２）。

　ここで、図２８及び図２９に示されたフローチャートにおける９種類の状態変更と実現可能性の詳細を説明するために、まず、汎用部品最適化部３０６ｂが用いている中間表現について説明する。汎用部品最適化部３０６ｂは、最適化を容易にするために、Ｚ軸配列の中間表現として以下の３種類を導入し、それらの表現を用いて状態を記憶したり、最適化エンジン部３０６ｃに指示したりする。

　(i)Ｇorder[i](i=1,...,L)
　入力されたＬ個の部品グループ（タスクグループＴＧ[i](i=1,...,L)をＺ軸に配置する際の優先順序を指定する変数であり、優先順序番号１〜Ｌを値にとる。ｉ！＝ｊの場合、Ｇorder[i]！＝Ｇorder［ｊ］となる。

　(ii)block[i](i=1,...,L)
　タスクグループＴＧ[i](i=1,...,L)を左・右のＺブロック（部品供給部１１５ａ及びｂ）のどちらに配置するかを指定する変数であり、"左"又は"右"のシンボル値をとる。

　(iii)Ｃorder[i][j](i=1,...,L, j=1,...,M[i])
　タスクグループＴＧ[i](i=1,...,L)に属する部品種ｊ(=1,...,M[i])のＺ軸における配置順序を指定する数であり、順序番号１〜Ｍ[i]を値にとる。ｊ！＝ｋの場合、Ｃorder[i][j]！＝Ｃorder[i][k]である。なお、Ｃorder[i][j]＜Ｃorder[i][k]の場合、「部品種ｊのＺ番号＜部品種ｋのＺ番号」なる関係を持っている。

　図３０（ａ）は、汎用部品最適化部３０６ｂが用いている中間表現の具体例を示し、図３０（ｂ）〜（ｅ）は、図３０（ａ）に示された中間表現の意味（Ｚ軸配列への変換）を示す図である。図３０（ａ）に示された中間表現が示すＺ軸配列は、具体的には、以下の変換を経ることによって特定される。

　まず、Ｇorder[i]＝１、つまり、Ｚ軸配列決定において最優先するタスクグループＴＧ[2]を配置する（図３０（ｂ））。このＴＧ[2]は、block[2]＝"右"であるため、右Ｚブロックのカメラ（認識カメラ１１６）寄り左詰で配置される。その際、ＴＧ[2]に属している計Ｍ[i=2]＝６つの部品種ｊ(i=1,...,6)を収納している部品カセット１１４は、Ｃorder[i=2][j]の若いものが左になるように、右Ｚブロックのカメラ寄り左詰で配置される。

　次に、Ｇorder[i]＝２であるＴＧ[4]を配置する（図３０（ｃ））。block[4]＝"左"であるため、左Ｚブロックのカメラ寄り右詰で配置される。その際、計Ｍ[i=4]＝３つの部品種ｊ(i=1,...,3)を収納している部品カセット１１４は、Ｃorder[i=2][j]の若いものが左になるように、カメラ寄り右詰で配置される。

　同様に、Ｇorder[i]＝３であるＴＧ[3]、Ｇorder[i]＝４であるＴＧ[1]の順で配置すればよい（図３０（ｄ）、(e)）。

　次に、汎用部品最適化部３０６ｂによる選択（図２８におけるステップＳ５６４、図２９におけるステップＳ５７７）の対象となる９種類の状態変更を示す。以下の通りである。
（１）同一汎用部品グループの２実装点をランダムに選択し、それらのタスク番号とヘッド番号（作業ヘッド１１２における吸着ノズル１１２ａ〜１１２ｂの位置）をスワップする。
（２）同一タスク内の２実装点をランダムに選択し、それらの実装順序をスワップする。
（３）２タスクグループ（２汎用部品グループ）をランダムに選択し、それらのＧorderをスワップする。
（４）１タスクグループ（１汎用部品グループ）をランダムに選択し、そのblockの値（"左"又は"右"）を変更する。
（５）同一タスクグループの２部品種をランダムに選択し、それらのＣorderをスワップする。
（６）同一タスクグループにおいて、連続したＣorder部分区間をランダムに選択し、シフトする。
（７）同一タスクグループにおいて、連続したＣorder部分区間をランダムに選択し、対応する部品種が実装点の平均Ｘ座標値に従ってＺ軸に配置されるようにＣorderを変更する。
（８）１タスクをランダムに選択し、当該タスクの実装点のＺ番号に基づいてヘッド番号を変更する。
（９）シャトル運用可能なトレイ部品の運用モード（ダイレクトモード、シャトルモード）をランダムに変更する。

　ここで、「トレイ部品の運用モード」とは、トレイ供給部１１７が内蔵するエレベータ（複数の段を持つ）を用いてトレイ部品を供給する（作業ヘッド１１２が吸着できる位置まで移動させて置く）ときの方式であり、「ダイレクトモード」は、部品が載せられた１つのトレイごと直接差し出す方式であり、「シャトルモード」は、シャトルコンベヤ１１８を用いた往復移動によって複数のトレイから取り出して集めた複数の部品を１列に並べて差し出す方式である。これらの運用モードについての各種情報は、実装装置情報３０７ｃに含まれており、必要な部品を所定位置に移動させるのに要する時間等に影響を与える。

　また、汎用部品最適化部３０６ｂによる実現可能性のチェック（図２８におけるステップＳ５６５、図２９におけるステップＳ５７８）については、以下の５つのチェック項目が同時に満たされている場合にのみ、状態Ｘtmpが可能解とみなされる。
（１）各タスクにおいて、ダイレクトモードの実装点のＺ番号が同じ段であること。つまり、ダイレクトモードでは、一つの段に置かれたトレイ部品だけが同時に供給され得ることを考慮する。
（２）各タスクにおいて、吸着時の部品点間に干渉がないこと。つまり、隣接して吸着される２つの部品の形状によっては、部品どうしが接触してしまうので、それを回避することを考慮する。
（３）各タスクにおいて、実装点が吸着可能であること（実装点のヘッド番号とＺ番号との組が適切であること）。つまり、作業ヘッド１１２に装着された吸着ノズルのいずれもが、９６個の部品カセット１１４のいずれの位置にも移動できる（部品を吸着できる）とは限らないことを考慮する。
（４）各タスクにおいて、実装点が装着可能であること（実装点のヘッド番号と座標値との組が適切であること）。作業ヘッド１１２を構成する全ての吸着ノズルが基板上のあらゆる箇所に移動できるとは限らないことを考慮する。
（５）全タスクグループの全タスクの吸着ノズルパターンが実現可能なようにノズルステーション１１９における吸着ノズルの配列を決定できること。つまり、ノズルステーション１１９に配置しておくことができる交換用の吸着ノズルの配置位置や数等に制限があることを考慮する。

　（６）作業ヘッド１１２とＺ軸上の部品とが同一ピッチで並んでいること。つまり、作業ヘッド１１２が同時吸着できるような部品（又は、部品カセット）がＺ軸に配置されていることを確認する。

　以上のように、汎用部品最適化部３０６ｂは、ローカルな（局所的な）最適化だけでなく、確率的な探索を混ぜた最適化を行っているので（図２７（ａ）におけるステップＳ５５０〜Ｓ５５３）、ローカルミニマムが最適解として算出されてしまう不具合が回避される。

　以上、本発明に係る部品実装順序最適化装置について、実施の形態に基づいて説明したが、本発明は、この実施の形態に限定されない。

　例えば、部品実装順序最適化装置３００は、具体的な構成を備える部品実装装置１００、２００それぞれにダウンロードするための最適なＮＣデータを生成するために用いられたが、このような用途だけでなく、生産性に関する要求仕様を満たすために必要とされる生産ラインの構成を決定するために用いることができるのは言うまでもない。生産対象となる基板の実装点データとモデリングした仮想的な電子部品実装システムの実装装置情報等とを部品実装順序最適化装置３００に与え、得られた最適状態（ラインタクト）が要求仕様を満たすか否か判断すればよい。

　具体的には、この部品実装順序最適化装置３００を、(i)実装装置の設計として、例えば、作業ヘッドのノズル数を４ノズルヘッド→１０ノズルヘッド→８ノズルヘッドを変えてみたり、ノズルピッチを２１．５ｍｍ→２２ｍと変えてみたり、部品カセットのピッチ（Z軸ピッチ）を変えてみたり、認識カメラの位置を変えてみたりすることで、最も効率のよい（生産性の高い）ヘッド等を決定するのに用いたり、(ii)複数の生産ラインのうち、どの生産ライン（又は、実装装置）で対象の基板を生産すべきかの決定に用いたり、(iii)実装装置の販売や営業用のツールとして、いかなるオプション（部品カセットやノズルの本数や種類）を装備すれば、いかなる生産性（時間あたり何枚の基板を生産することができるか）が確保されるかの計算に用いたりすることができる。　また、本実施の形態では、部品実装順序最適化装置３００は、部品実装装置１００、２００とは独立した装置であったが、これら部品実装装置１００、２００に内蔵されていてもよい。

　また、本実施の形態では、状態最適化部３０６は、部品グループＧ[1]〜Ｇ[5]に属する小部品と部品グループＧ[6]〜Ｇ[9]に属する汎用部品それぞれに対して、異なる探索アプローチによる最適化を行ったが、本発明は、このような分類やアプローチに限られない。
例えば、各部品グループに属する員数やコンピュータの計算能力等に応じて、小部品の実装順序の決定に対して、山登り法とマルチカノニカル法とを混在させた手法を適用したり、汎用部品の実装順序の決定に対して、タスクグループ生成法、刈り上げ法、ランダム選択法、交差解消法及び戻り軌跡法を適用してもよい。

　また、本実施の形態における交差解消法では、２つのタスクそれぞれの部品の実装点を接続する折れ線（パス）どうしの交差を解消するように実装順序を入れ替えてみてタクトが小さくなるか否かで実装順序の最適化を行ったが、交差していないパスどうしを入れ替えてみてもよい。交差していないタスクのパスを入れ替えることでタクトが短縮化されることもあり得るからである。

　本発明の部品実装順序最適化方法はプリント基板に電子部品を実装する実装機に用いて有用である。

本発明に係る電子部品実装システム全体の構成を示す外観図である。 部品実装装置の主要な構成を示す平面図である。 部品実装装置の作業ヘッドと部品カセットの外観及び位置関係を示す図である。 部品実装順序最適化装置の構成を示す機能ブロック図である。 データベース部に格納された実装点データ及びＮＣデータのデータ構造を示す図である。 データベース部に格納されたパーツライブラリの例を示す図である。 データベース部に格納された実装装置情報の例を示す図である。 （ａ）は、部品グループ生成部が生成する部品グループを説明するための図であり、（ｂ）は、部品グループ生成部による部品グループの生成過程で作成される部品表の例を示す図である。 ラインバランス最適化部の第１ＬＢＭ部によるタスクグループのサブ設備への振り分け処理の様子を示す図である。 （ａ）は、ラインバランス最適化部の第２ＬＢＭ部によるラインバランスの最適化前におけるタクト分布を示し、（ｂ）は、最適化によるタスクグループの移動の様子を示し、（ｃ）は、最適化後におけるタクト分布を示す。 ラインバランス最適化部の第２ＬＢＭ部によるラインバランスの最適化手順を示すフローチャートである。 状態最適化部の小部品最適化部ａによる小部品の実装順序最適化の概略手順を示すフローチャートである。 テトリスダイヤグラムを説明するための図である。 （ａ）は、タスクグループ生成法によるテトリスダイヤグラムの生成の対象となる部品の部品ヒストグラムであり、（ｂ）は、（ａ）に示された部品ヒストグラムから生成されるテトリスダイヤグラムである。 （ａ）は、部品ヒストグラムにおける未配置部分を示し、（ｂ）は、（ａ）に示された部品ヒストグラムの未配置部分から生成されるテトリスダイヤグラムを示す。 刈り上げ法によるテトリスダイヤグラムの生成の対象となる部品の部品ヒストグラムである。 図１６に示された部品ヒストグラムから、１０個の部品並びの単位で部品を取っていく（刈り上げていく）様子を示す図である。 図１７に示された刈り上げ後に残された部品を対象とする部品ヒストグラムである。 図１８に示された部品ヒストグラムに対して、タスクグループ生成法に準じたダイヤグラムの生成を行っている様子を示す図である。 刈り上げ法によってＺ軸が決定された部品種についてのテトリスダイヤグラムである。 図２０に示されたテトリスダイヤグラムに対応する（Ｚ軸を変化させない再構築した）部品ヒストグラムである。 ランダム選択法による部品の装着順序の最適化の手順を示すフローチャートである。 ランダム選択法によって２つの実装点が入れ替えられる様子を示すである。 交差解消法により部品の装着順序を最適化する様子を示す図であり、（ａ）は、折れ線の交差が解消される前の装着順序を示し、（ｂ）は、折れ線の交差が解消された後の装着順序を示す。 戻り軌跡法によりタスクの順序を最適化する際に生成される作業ヘッドの移動軌跡（実装経路）を示す図である。 同一位置の複数の吸着パターンが含まれる場合における戻り軌跡法で生成される作業ヘッドの移動軌跡を示す図である。 （ａ）は、汎用部品最適化部による汎用部品の実装順序を最適化する際の手順を示すフローチャートであり、（ｂ）は、その最適化による最適解の探索アプローチを説明するための状態vsタクトの関係を示す図である。 図２７（ａ）に示された山登り法による最適化（ステップＳ５５１、Ｓ５５３）の詳細な手順を示すフローチャートである。 図２７（ａ）に示されたマルチカノニカル法による最適化（ステップＳ５５２）の詳細な手順を示すフローチャートである。 （ａ）は、汎用部品最適化部が用いている中間表現の具体例を示し、（ｂ）〜（ｅ）は、に示された中間表現の意味（Ｚ軸配列への変換）を示す図である。

符号の説明

　　　１０　　電子部品実装システム
　　　２０　　回路基板
　　１００　　部品実装装置
　　１１０、１２０　　実装ユニット
　　１１２　　作業ヘッド
　　１１２ａ〜１１２ｂ　吸着ノズル
　　１１３　　ＸＹロボット
　　１１４　　部品カセット
　　１１５ａ、ｂ　部品供給部
　　１１６　　認識カメラ
　　１１７　　トレイ供給部
　　１１８　　シャトルコンベヤ
　　１１９　　ノズルステーション
　　３００　　部品実装順序最適化装置
　　３０１　　入出力制御部
　　３０２　　表示部
　　３０３　　入力部
　　３０４　　部品グループ生成部
　　３０５　　ラインバランス最適化部
　　３０５ａ　ＬＢＭ部
　　３０５ｂ　ＬＢＭ部
　　３０５ｃ　ＬＢＭ部
　　３０６　　状態最適化部
　　３０６ａ　小部品最適化部
　　３０６ｂ　汎用部品最適化部
　　３０６ｃ　最適化エンジン部
　　３０７　　データベース記憶部
　　３０７ａ　実装点データ
　　３０７ｂ　パーツライブラリ
　　３０７ｃ　実装装置情報
　　３０８　　通信Ｉ／Ｆ部

Claims (10)

1. 部品を収納した部品カセットの並びから、最大ｎ個の部品を吸着することが可能な作業ヘッドで部品群を吸着し、ＸＹロボットにより前記作業ヘッドを移動させ基板に実装していく実装装置を対象とし、コンピュータの実行により部品の実装順序を最適化する方法であって、
   　作業ヘッドによる部品の吸着・移動・装着という一連の動作の繰り返しにおける１回分の一連動作によって実装される部品群をタスクとした場合に、同時吸着可能な部品カセットの並びに対応する複数のタスクの並びからタスクグループを構成する部品について、最適化の対象となる全ての部品の取り得る実装順序それぞれを１つの状態とした場合の初期状態を第１状態として生成する初期化ステップと、
   　前記タスクグループを構成する部品について、ランダムに選択した実装点を入れ替えることにより、前記第１状態を第２状態に変更する状態変更ステップと、
   　前記第２状態に対応する実装順序に従って前記実装装置が全ての部品を実装することができ、かつ、それら全ての部品の実装に要する時間が第１状態における時間よりも小さいか否か判断する判断ステップと、
   　前記実装装置が全ての部品を実装することができ、かつ、前記時間が第１状態における時間よりも小さいと判断された場合に、前記第２状態を新たな第１状態として、前記状態変更ステップ及び前記判断ステップを繰り返させて第１状態を更新していくことにより、部品の実装順序を最適化していく繰り返し制御ステップと、
   　を含むことを特徴とする部品実装順序最適化方法。
2. 前記状態変更ステップでは、予め定められた複数の種類の変更方法からランダムに選択した１つの方法を採用して、前記第１状態を変更する
   　ことを特徴とする請求項１記載の部品実装順序最適化方法。
3. 前記状態変更ステップで選択され得る複数の変更方法には、２つのタスクそれぞれに属する同一の部品種の部品それぞれを入れ替える方法が含まれる
   　ことを特徴とする請求項２記載の部品実装順序最適化方法。
4. 最適の対象となる全ての部品は、一定範囲の高さの部品の集まりを一つの部品グループとする複数の部品グループに分類され、
   　前記状態は、前記複数の部品グループそれぞれについて、前記部品カセットの並びに配置するときの優先順序パラメータと、同一種類の部品の集まりを１つの部品種とした場合における同一部品グループに属する部品種の並びを示す部品種順序パラメータとを含む中間言語によって表現されている
   　ことを特徴とする請求項２記載の部品実装順序最適化方法。
5. 前記状態変更ステップで選択され得る複数の変更方法には、前記複数の部品グループから２つの部品グループをランダムに選択し、それら部品グループの優先順位パラメータを入れ替える方法が含まれる
   　ことを特徴とする請求項４記載の部品実装順序最適化方法。
6. 前記状態変更ステップで選択され得る複数の変更方法には、同一の部品グループに属する複数の部品種から２つの部品種をランダムに選択し、それら部品種の部品種順序パラメータを入れ替える方法が含まれる
   　ことを特徴とする請求項４記載の部品実装順序最適化方法。
7. 前記状態変更ステップでは、対象となる全ての状態を複数のグループに分類した場合における前記第２状態が属するグループが、前記複数のグループそれぞれについて等しい確立となるように、前記第２状態を生成する
   　ことを特徴とする請求項１記載の部品実装順序最適化方法。
8. 部品を収納した部品カセットの並びから、最大ｎ個の部品を吸着することが可能な作業ヘッドで部品群を吸着し、ＸＹロボットにより前記作業ヘッドを移動させ基板に実装していく実装装置を対象とし、コンピュータの実行により部品の実装順序を最適化する装置であって、
   　作業ヘッドによる部品の吸着・移動・装着という一連の動作の繰り返しにおける１回分の一連動作によって実装される部品群をタスクとした場合に、同時吸着可能な部品カセットの並びに対応する複数のタスクの並びからタスクグループを構成する部品について、最適化の対象となる全ての部品の取り得る実装順序それぞれを１つの状態とした場合の初期状態を第１状態として生成する初期化手段と、
   　前記タスクグループを構成する部品について、ランダムに選択した実装点を入れ替えることにより、前記第１状態を第２状態に変更する状態変更手段と、
   　前記第２状態に対応する実装順序に従って前記実装装置が全ての部品を実装することができ、かつ、それら全ての部品の実装に要する時間が第１状態における時間よりも小さいか否か判断する判断手段と、
   　前記実装装置が全ての部品を実装することができ、かつ、前記時間が第１状態における時間よりも小さいと判断された場合に、前記第２状態を新たな第１状態として、前記状態変更手段による第２状態の生成及び前記判断手段による判断を繰り返させて第１状態を更新していくことにより、部品の実装順序を最適化していく繰り返し制御手段と、
   　を備えることを特徴とする部品実装順序最適化装置。
9. 部品を収納した部品カセットの並びから、最大ｎ個の部品を吸着することが可能な作業ヘッドで部品群を吸着し、ＸＹロボットにより前記作業ヘッドを移動させ基板に実装していく実装装置を対象とし、コンピュータに部品の実行順序の最適化を実行させるためのプログラムを記録したコンピュータ読取可能な記録媒体であって、
   　作業ヘッドによる部品の吸着・移動・装着という一連の動作の繰り返しにおける１回分の一連動作によって実装される部品群をタスクとした場合に、同時吸着可能な部品カセットの並びに対応する複数のタスクの並びからタスクグループを構成する部品について、最適化の対象となる全ての部品の取り得る実装順序それぞれを１つの状態とした場合の初期状態を第１状態として生成する初期化ステップと、
   　前記タスクグループを構成する部品について、ランダムに選択した実装点を入れ替えることにより、前記第１状態を第２状態に変更する状態変更ステップと、
   　前記第２状態に対応する実装順序に従って前記実装装置が全ての部品を実装することができ、かつ、それら全ての部品の実装に要する時間が第１状態における時間よりも小さいか否か判断する判断ステップと、
   　前記実装装置が全ての部品を実装することができ、かつ、前記時間が第１状態における時間よりも小さいと判断された場合に、前記第２状態を新たな第１状態として、前記状態変更ステップ及び前記判断ステップを繰り返させて第１状態を更新していくことにより、部品の実装順序を最適化していく繰り返し制御ステップと、
   　をコンピュータに実行させるためのプログラムを記録した記録媒体。
10. 部品を収納した部品カセットの並びから、最大ｎ個の部品を吸着することが可能な作業ヘッドで部品群を吸着し、ＸＹロボットにより前記作業ヘッドを移動させ基板に実装していく実装装置を対象とし、コンピュータの実行により部品の実装順序を最適化する方法であって、
    　最適化の対象となる全ての部品を、部品の高さに基づいて、小部品グループと汎用部品グループとに分類する分類ステップと、
    　前記小部品グループに属する部品に対して、前記作業ヘッドによる部品の同時吸着が最大限できるようにする第１のアルゴリズムを用いて実装順序の最適化を行うステップと、
    　前記汎用部品グループに属する部品に対して、取り得る実装順序の１つである状態を変化させながら最適な実装順序を導き出す第２のアルゴリズムを用いて実装順序の最適化を行うステップと
    　を含むことを特徴とする部品実装順序最適化方法。

Images