(57)【要約】【課題】  現実的な時間内で最適な部品実装順序を決定することができる部品実装順序決定方法を提供する。【解決手段】  演算制御部は、実装点情報配列および変換テーブルに基づいて、タクトテーブルを作成する（Ｓ４）。ダミー点から各実装点までの実装時間は、任意の実装点間の実装時間よりも大きい値とする。また、基板マークとダミー点とのとの間の実装時間は、任意の実装点間の実装時間よりも小さい値とする。演算制御部は、実装点情報配列に基づいて初期巡回路を作成する（Ｓ６）。演算制御部は、求められた初期巡回路における総実装時間を求める（Ｓ８）。演算制御部は、ループカウンタｉを０に設定する（Ｓ１０）。演算制御部は、巡回路に対して巡回セールスマン問題の２−ＯＰＴ法を適用させ、実装順序の入れ替えを試み（Ｓ１２）、総実装時間が最小となるような巡回路を求める（ループＡ）。【選択図】      図１２
2006173318.tif 000002
【特許請求の範囲】
【請求項１】
基板に複数の部品を実装する部品実装機における部品の実装順序を決定する方法であって、
複数の部品実装点および所定点の任意の２点間について、当該２点間の距離または当該２点間のうちの一方の点へ部品を実装してから他方の点へ部品を実装するまでに必要な時間を当該２点間のコストと定義し、
どの部品実装点との間のコストでも、複数の部品実装点および所定点のうちのどの２点間のコストよりも大きく、かつ所定点との間のコストが、複数の部品実装点および所定点のうちのどの２点間のコストより小さいものであるダミー点を定義し、
前記複数の部品実装点の位置情報と、前記複数の部品実装点、前記所定点および前記ダミー点に関する前記コストとを取得する部品実装点情報取得ステップと、
前記基板上の所定点、前記ダミー点および前記複数の部品実装点について、コストの和が最小となるような各点を通る巡回路を、巡回セールスマン問題を用いて算出する巡回路算出ステップと、
前記巡回路に基づいて、前記部品の実装順序を決定する実装順序決定ステップと
を含むことを特徴とする部品実装順序決定方法。
【請求項２】
前記部品実装機は、部品を吸着し、基板上に実装する実装ヘッドと、前記実装ヘッドに部品を供給する部品供給部とを備え、
前記ある部品実装点から他の部品実装点へのコストは、部品実装点間の移動に必要な時間、前記実装ヘッドが部品を吸着してから実装するまでの時間、および前記実装ヘッドへの前記部品供給部からの部品供給に必要な時間のうちの少なくとも１つに基づいて定められる
ことを特徴とする請求項１に記載の部品実装順序決定方法。
【請求項３】
前記実装ヘッドは、所定の軸周りに回転しながら部品を吸着し、基板上に実装するロータリーヘッドであり、
前記部品実装機は、さらに、前記基板を載置し、前記基板上の部品実装点と前記ロータリーヘッドの部品実装位置とが一致するように自身が移動するテーブルを備え、
前記ある部品実装点から他の部品実装点へのコストは、部品実装点間のテーブルの移動に必要な時間、前記ロータリーヘッドが部品を吸着してから実装するまでの時間および前記ロータリーヘッドへの前記部品供給部からの部品供給に必要な時間のうちの少なくとも１つに基づいて定められる
ことを特徴とする請求項２に記載の部品実装順序決定方法。
【請求項４】
前記基板上の所定点からある部品実装点へのコストまたはある部品実装点から前記基板上の所定点へのコストは、部品実装点間のテーブルの移動に必要な時間または前記ロータリーヘッドが部品を吸着してから実装するまでの時間に基づいて定められる
ことを特徴とする請求項３に記載の部品実装順序決定方法。
【請求項５】
前記ロータリーヘッドが部品を吸着してから実装するまでの時間には、前記ロータリーヘッドが部品を吸着してから部品の実装位置に移動するまでの回転時間を含めない
ことを特徴とする請求項３または４に記載の部品実装順序決定方法。
【請求項６】
さらに、前記基板上の所定点、前記ダミー点および前記複数の部品実装点のうちの任意の２点間のコストを算出するコスト算出ステップを含み、
前記巡回路算出ステップでは、前記コスト算出ステップで算出されたコストを用いて、前記基板上の所定点、前記ダミー点および前記複数の部品実装点について、コストの和が最小となるような各点を通る巡回路を、巡回セールスマン問題を用いて算出する
ことを特徴とする請求項１〜５のいずれか１項に記載の部品実装順序決定方法。
【請求項７】
前記コスト算出ステップでは、第１の点から第２の点へのコストと第２の点から第１の点へのコストとが等しいとみなし、任意の２点間のコストを算出する
ことを特徴とする請求項６に記載の部品実装順序決定方法。
【請求項８】
前記所定点は、前記基板上に設けられた基板位置決めのための基板マークのうち、最後に認識される基板マークである
ことを特徴とする請求項１〜７のいずれか１項に記載の部品実装順序決定方法。
【請求項９】
前記所定点は、前記複数の部品実装点のうち、予め定められた最初に部品が実装される部品実装点である
ことを特徴とする請求項１〜７のいずれか１項に記載の部品実装順序決定方法。
【請求項１０】
前記ダミー点は前記所定点と同一点である
ことを特徴とする請求項１〜９のいずれか１項に記載の部品実装順序決定方法。
【請求項１１】
基板に複数の部品を実装する部品実装機における部品の実装順序を決定する装置であって、
複数の部品実装点および所定点の任意の２点間について、当該２点間の距離または当該２点間のうちの一方の点へ部品を実装してから他方の点へ部品を実装するまでに必要な時間を当該２点間のコストと定義し、
どの部品実装点との間のコストでも、複数の部品実装点および所定点のうちのどの２点間のコストよりも大きく、かつ所定点との間のコストが、複数の部品実装点および所定点のうちのどの２点間のコストより小さいものであるダミー点を定義し、
前記複数の部品実装点の位置情報と、前記複数の部品実装点、前記所定点および前記ダミー点に関する前記コストとを取得する部品実装点情報取得手段と、
前記基板上の所定点、前記ダミー点および前記複数の部品実装点について、コストの和が最小となるような各点を通る巡回路を、巡回セールスマン問題を用いて算出する巡回路算出手段と、
前記巡回路に基づいて、前記部品の実装順序を決定する実装順序決定手段と
を備えることを特徴とする部品実装順序決定装置。
【請求項１２】
基板に部品を実装する部品実装機であって、
請求項１〜１０のいずれか１項に記載の部品実装順序決定方法により決定された前記部品の実装順序に従い、前記基板に前記部品を実装する
ことを特徴とする部品実装機。
【請求項１３】
請求項１〜１０のいずれか１項に記載の部品実装順序決定方法に含まれるステップをコンピュータに実行させる
ことを特徴とするプログラム。
【請求項１４】
請求項１３に記載のプログラムを記録した
ことを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、基板上に部品を実装する部品実装機における部品実装順序決定方法に関する。
【背景技術】
【０００２】
部品実装機による基板上への部品実装においては、その部品実装に先立って、部品の実装順序を決定しなければならない。部品実装順序決定方法では、１枚の基板上へ部品の実装を開始してからすべての部品を実装し終えるまでの時間を最小にすることを目的として部品の実装順序を決定する。しかし、考えられる部品実装順序をすべて生成し、最適な部品実装順序を求める総当り法では、部品の実装点数が多くなればなるほど、最適な部品実装順序を決定するための処理時間が増大し、現実的な時間で最適な部品実装順序を決定するのが困難である。
【０００３】
このため、現実的な時間で最適な部品実装順序を決定する方法として、貪欲法を用いた方法が提案されている（たとえば、特許文献１参照。）。
【特許文献１】特開平７−１７６８９１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、貪欲法を用いた部品実装順序決定方法では、コスト（たとえば、部品実装点間の距離）が最小な部品実装点を順次選択していき、部品実装順序を決定していく。このため、部品実装開始時には部品実装点間の移動距離が小さくなるような実装順序になっている反面、部品実装終了に近づくにつれ、部品実装点間の移動距離が大きくなる、実装点間の移動の乱れ（無駄な動作）が発生してしまうという問題があり、必ずしも最適な実装順序が求められないという問題がある。
【０００５】
本発明は、上述の課題を解決するためになされたものであり、現実的な時間内で最適な部品実装順序を決定することができる部品実装順序決定方法を提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記目的を達成するために、本発明に係る部品実装順序決定方法は、基板に複数の部品を実装する部品実装機における部品の実装順序を決定する方法であって、複数の部品実装点および所定点の任意の２点間について、当該２点間の距離または当該２点間のうちの一方の点へ部品を実装してから他方の点へ部品を実装するまでに必要な時間を当該２点間のコストと定義し、どの部品実装点との間のコストでも、複数の部品実装点および所定点のうちのどの２点間のコストよりも大きく、かつ所定点との間のコストが、複数の部品実装点および所定点のうちのどの２点間のコストより小さいものであるダミー点を定義し、前記複数の部品実装点の位置情報と、前記複数の部品実装点、前記所定点および前記ダミー点に関する前記コストとを取得する部品実装点情報取得ステップと、前記基板上の所定点、前記ダミー点および前記複数の部品実装点について、コストの和が最小となるような各点を通る巡回路を、巡回セールスマン問題を用いて算出する巡回路算出ステップと、前記巡回路に基づいて、前記部品の実装順序を決定する実装順序決定ステップとを含むことを特徴とする。
【０００７】
巡回セールスマン問題を部品実装順序の決定に用いている。このため、貪欲法により部品実装順序を決定した際に生じる部品実装終了に近づくにつれ実装点間の移動の乱れ（無駄な動作）が発生してしまうという問題が解消され、最適な実装順序を求めることができる。また、巡回セールスマン問題は現実的な処理時間で厳密解の近似解を求めることができる。なお、ダミー点を上述のように定義することにより、ダミー点と所定点とが必ず接続されるような巡回路が生成される。このため、所定点をスタート点とする閉じた巡回路を生成することが可能となる。なお、予め部品実装順序を貪欲法で求めておき、上述した無駄な動作を改善するために、巡回セールスマン問題を適用させ、最適な部品実装順序を求めるようにしてもよい。
【０００８】
また、上述の部品実装順序決定方法は、さらに、前記基板上の所定点、前記ダミー点および前記複数の部品実装点のうちの任意の２点間のコストを算出するコスト算出ステップを含み、前記巡回路算出ステップでは、前記コスト算出ステップで算出されたコストを用いて、前記基板上の所定点、前記ダミー点および前記複数の部品実装点について、コストの和が最小となるような各点を通る巡回路を、巡回セールスマン問題を用いて算出するようにしてもよい。また、前記コスト算出ステップでは、第１の点から第２の点へのコストと第２の点から第１の点へのコストとが等しいとみなし、任意の２点間のコストを算出するようにしてもよい。
【０００９】
第１の点から第２の点へのコストと第２の点から第１の点へのコストとを等しいとみなすことにより、コストの計算時間を半分に短縮することができる。
【００１０】
なお、本発明は、このような特徴的なステップを備える部品実装順序決定方法として実現することができるだけでなく、部品実装順序決定方法に含まれる特徴的なステップを手段とする部品実装順序決定装置として実現したり、部品実装順序決定方法に含まれる特徴的なステップをコンピュータに実行させるプログラムとして実現したりすることもできる。そして、そのようなプログラムは、ＣＤ−ＲＯＭ（Compact Disc-Read Only Memory）等の記録媒体やインターネット等の通信ネットワークを介して流通させることができるのは言うまでもない。
【発明の効果】
【００１１】
現実的な時間内で最適な部品実装順序を決定することができる部品実装順序決定方法を提供することができる。
【発明を実施するための最良の形態】
【００１２】
本発明の実施の形態に係る部品実装システムについて説明する。
図１は、本発明の実施の形態に係る部品実装システムの外観図である。
【００１３】
部品実装システムは、基板上への部品の実装順序を決定するとともに、決定された実装順序に従って、基板上に部品を実装するシステムであり、部品実装機１０と、部品実装順序決定装置３００とを備えている。
【００１４】
部品実装機１０は、電子機器を構成するプリント基板上に複数種類の部品を高速に装着する実装装置であり、部品を吸着、搬送、装着するロータリーヘッド１００と、多種類の部品をロータリーヘッド１００に供給する部品供給部１１と、載置したプリント基板を水平面方向に移動させるＸＹテーブル１５とを備えている。
【００１５】
図２は、部品供給部とロータリーヘッドとの位置関係を示す概略図である。
ロータリーヘッド１００は、図２の上部に示すように、部品をプリント基板上に装着する装着手段としての装着ヘッド１０３を１８個備えている。またこの装着ヘッド１０３は、高さ方向には移動することなく回転する回転基台１０１に高さ方向に移動自在に取り付けられ、部品を真空吸着により保持することのできる吸着ノズル（図示せず）を６本備えている。
【００１６】
部品供給部１１は、図２の下部に示すように、同一部品を順次装着ヘッド１０３に提供しうる部品カセット１１１を横一列に並べて備えている。そして、部品供給部１１は、部品供給部１１をロータリーヘッド１００に対して図２中のＺ軸方向に移動位置決めすることにより装着すべき部品を選択しうる機能を有している。
【００１７】
部品カセット１１１は、図３に示すような同一部品を多数個保持する部品テープ１１０が巻き付けられたリール１１３と、当該部品テープ１１０に保持された部品を順次供給するテープフィーダ１１４とを備えており、部品供給部１１に対して着脱自在となっている。つまり、部品カセット１１１は、１種類の部品を提供するものに相当し、部品供給部１１は、部品カセット１１１の集合（または、さらにその集合を保持する収納部を含めたもの）に相当する。
【００１８】
図４は、ロータリーヘッド、基板および部品供給部の位置関係を模式的に示した図である。
【００１９】
同図に示すように、ロータリーヘッド１００の回転軸は移動せず、この回転軸の周りをその周囲に設けられた装着ヘッド１０３が間欠回転することにより各位置に対応した作業を行う。簡単に説明すると、部品カセット１１１がそれぞれ備える吸着開口部１１２の上部（位置Ｂ）に位置した装着ヘッド１０３が前記吸着開口部１１２を通して部品を吸着し、これと対向する位置Ｅに装着ヘッド１０３が位置したときにプリント基板Ｐに吸着した部品を装着する。
【００２０】
なお、部品の装着対象であるプリント基板Ｐは水平面方向に移動自在なＸＹテーブル（図示せず）上に載置されており、部品を装着すべき位置はプリント基板Ｐを移動させることにより決定される。
【００２１】
図５は、図４の位置Ｃに備えられた部品認識カメラの一例を示す図である。
部品認識カメラ１０５は、装着ヘッド１０３が吸着した部品１０６を認識するためのカメラであり、鏡筒１０５ａと、小視野カメラ１０５ｂと、大視野カメラ１０５ｃとを備えている。鏡筒１０５ａ内には、ミラー１０７ａおよび１０７ｃと、ハーフミラー１０７ｂとが設けられている。
【００２２】
小視野カメラ１０５ｂは、視野サイズが６ｍｍのカメラであり、ミラー１０７ａおよびハーフミラー１０７ｂで反射された部品１０６を撮像する。大視野カメラ１０５ｃは、視野サイズが２８ｍｍのカメラであり、ミラー１０７ａおよび１０７ｃで反射された部品１０６を撮像する。
【００２３】
図６は、ロータリーヘッド１００に備えられる装着ヘッド１０３の一つに着目した際の当該装着ヘッド１０３の動作を示すフローチャートである。
【００２４】
吸着ノズルの選択位置（図４の位置Ａ）に存在する装着ヘッド１０３は、次に装着する部品に適合した吸着ノズルを選択する（Ｓ４０１）。次に、回転基台１０１を前記装着ヘッド１０３が吸着部（図４の位置Ｂ）に位置するまで回転させる（Ｓ４０２）。この位置において、装着ヘッド１０３は吸着ノズルを用いて部品カセット１１１の吸着開口部１１２から部品を吸着保持する（Ｓ４０３）。
【００２５】
次に、前記装着ヘッド１０３が部品認識カメラ１０５（図４の位置Ｃ）に位置するまで回転基台１０１を回転させる（Ｓ４０４）。そして、この位置に備えられた小視野カメラ１０５ｂまたは大視野カメラ１０５ｃにより吸着搬送された部品の映像を撮像し、画像処理することにより部品の吸着状態を認識する（Ｓ４０５）。この吸着状態の認識では、部品の中心と吸着ノズルの中心との２次元的なずれ量や部品の回転ずれ量を検出し、さらには、部品の欠品や立ち吸着、認識エラー（認識処理ができない）の判断などを行なう。そして、部品の欠品など吸着状態に不具合があると判断されれば（Ｓ４０６でＹＥＳ）、吸着していた部品が廃棄される（Ｓ４１０）。一方、不具合がないと判断されれば（Ｓ４０６でＮＯ）、図４に示す位置Ｄで先ほど検出された回転ずれ量に基づき部品をθ方向に補正する（Ｓ４０７）。なお、２次元的なずれ量についてはＸＹテーブル１５によりプリント基板の位置を微調整して補正する。次に、装着ヘッド１０３が装着部（図４の位置Ｅ）に位置するまで回転基台１０１を回転させる（Ｓ４０８）。そして、装着ヘッド１０３を装着している部品の高さに対応して下方に移動させて部品をプリント基板Ｐに押し込み装着する（Ｓ４０９）。
【００２６】
図７は、部品供給部１１の各種モードを説明するための図である。図７（ａ）は交換モードを示す図であり、同図に示すように、部品供給部１１は、左側部品供給部ＺＬと右側部品供給部ＺＲとで構成されている。交換モードでは、左側部品供給部ＺＬと右側部品供給部ＺＲとに同じ種類の部品をセットする。たとえば、左側部品供給部ＺＬを用いた基板を生産中に部品切れが発生した場合には、待機位置にある右側部品供給部ＺＲをロータリーヘッド１００による吸着位置まで移動させ、引き続き右側部品供給部ＺＲを用いて基板を生産する。その間に、部品切れした部品を左側部品供給部ＺＬに補充する。このように、右側部品供給部ＺＲと左側部品供給部ＺＬとで同じ部品構成とすることにより、部品実装機１０の長時間連続運転が可能となる。
【００２７】
図７（ｂ）は準備モードを示す図であり、たとえば、左側部品供給部ＺＬを用いた基板の生産中に、右側部品供給部ＺＲに次に生産する基板の実装部品をセットしておくことにより、事前に生産基板の切り替えに対応させるモードである。このモードは、生産基板の切り替えが多い場合に最適なモードである。
【００２８】
図７（ｃ）は接続モードを示す図であり、たとえば、右側部品供給部ＺＲおよび左側部品供給部ＺＬを両方使用して、基板を生産するモードである。このモードは、１枚の基板に使用される部品種類が多い生産に適している。
【００２９】
図８は、部品実装順序決定装置の構成を示す機能ブロック図である。
部品実装順序決定装置３００は、基板上の部品の実装順序を決定するコンピュータであり、演算制御部３０１、表示部３０２、入力部３０３、メモリ部３０４、部品実装順序決定プログラム格納部３０５、通信Ｉ／Ｆ（インターフェース）部３０６およびデータベース部３０７等から構成される。
【００３０】
この部品実装順序決定装置３００は、部品実装順序決定プログラムをパーソナルコンピュータ等の汎用のコンピュータシステムが実行することにより実現され、部品実装機１０と接続されていない状態で、スタンドアローンのシミュレータ（部品実装順序の決定ツール）としても機能する。
【００３１】
演算制御部３０１は、ＣＰＵ（Central Processing Unit）や数値プロセッサ等であり、ユーザからの指示等に従って、部品実装順序決定プログラム格納部３０５からメモリ部３０４に必要なプログラムをロードして実行し、その実行結果に従って、各構成要素３０２〜３０７を制御する。
【００３２】
表示部３０２はＣＲＴ（Cathode-Ray Tube）やＬＣＤ（Liquid Crystal Display）等であり、入力部３０３はキーボードやマウス等であり、これらは、演算制御部３０１による制御の下で、部品実装順序決定装置３００と操作者とが対話する等のために用いられる。
【００３３】
通信Ｉ／Ｆ部３０６は、ＬＡＮ（Local Area Network）アダプタ等であり、部品実装順序決定装置３００と部品実装機１０との通信等に用いられる。メモリ部３０４は、演算制御部３０１による作業領域を提供するＲＡＭ（Random Access Memory）等である。
【００３４】
データベース部３０７は、この部品実装順序決定装置３００による部品実装順序決定処理に用いられる入力データ（実装点情報配列３０７ａおよび変換テーブル３０７ｂ等）や部品実装順序決定処理により決定された部品の実装順序等を記憶するハードディスク等である。
【００３５】
図９は、実装点情報配列３０７ａの一例を示す図である。
実装点情報配列３０７ａは、基板２０上の実装点の個数をｎ個とした場合、要素数がＮ（＝ｎ＋２）個のデータからなる配列である。
【００３６】
ここでは、図１０に示すように、基板２０には２個の基板マーク４０２および４０４が予め形成されており、その上に、５個の実装点（実装点１〜実装点５）設けられているものとする。５個の実装点は、部品実装機１０により部品が実装される点である。基板マーク４０２および基板マーク４０４は、基板２０の位置決めのために、ロータリーヘッド１００に設けられた基板認識カメラ（図示せず）により撮像され、その位置が認識される。なお、先に基板マーク４０２の位置が認識され、次に基板マーク４０４の位置が認識されるものとする。その他にも、ダミー点４０６と呼ばれる仮想的な点が基板２０には設けられている。ダミー点４０６は、図中基板マーク４０４の近傍に設けているが、仮想的な点であるため基板２０上に設けられていなくてもよいし、基板マーク４０４と同一の位置にあってもよい。
【００３７】
再度図９を参照して、各配列要素には、実装点の位置等に関する情報（以下、「実装点情報」という。）、基板マークの位置に関する情報およびダミー点の位置に関する情報のうちのいずれかの情報が記憶されている。図９には、実装点情報配列３０７ａ（Ｄａｔａ）の２番目の要素Ｄａｔａ［２］に記憶されている情報が示されている。要素Ｄａｔａ［２］には、実装点２の実装点情報が記憶されており、実装点２の基板２０上での位置を示すＸ座標「４５」およびＹ座標「１８」と、実装点２に実装される部品が収納されている部品カセット１１１の部品供給部１１におけるＺ軸上の位置（Ｚ番号）「２４」と、装着ヘッド１０３が部品を吸着してから装着するまでの速度（ヘッド速度）「６」と、ＸＹテーブルの移動速度「２」とが記憶されている。
【００３８】
ヘッド速度は、レベル「１」からレベル「８」までの８段階で示されており、レベル１が最も速いヘッド速度であり、レベル８が最も遅いヘッド速度である。すなわち、重い部品や大きい部品の場合は、速いヘッド速度で実装することができないため、ヘッド速度は遅くなる。なお、ヘッド速度は、装着ヘッド１０３が部品を吸着してから実装するまでの速度である。また、ここでは、処理の簡単化のため、装着ヘッド１０３の半回転は無いものとして考える。
【００３９】
ＸＹテーブルの移動速度は、レベル「１」からレベル「８」までの８段階で示されており、レベル１が最も速いＸＹテーブル１５の移動速度であり、レベル８が最も遅いＸＹテーブル１５の移動速度である。すなわち、実装される部品が重い部品や大きい部品の場合には、ＸＹテーブル１５の移動速度が速すぎると、実装された部品が基板２０より剥奪され飛んでしまう。このため、このような部品の場合には、ＸＹテーブル１５の移動速度は、大きいレベルに設定される。
【００４０】
なお、基板マークの位置に関する情報およびダミー点の位置に関する情報にも実装点情報と同様の情報が含まれるものとする。
【００４１】
図１１は、変換テーブル３０７ｂの一例を示す図である。変換テーブル３０７ｂは、ヘッド速度や、ＸＹテーブル１５の移動速度等を時間に置き換えるためのテーブルである。１列目は、置き換え後の時間ｔ（ｍｓｅｃ）を示している。２列目は、実装点ｉと実装点ｊとの間の距離Δｘｙを示している。３列目は、実装点ｉに実装する部品が収納された部品カセットと実装点ｊに実装する部品が収納された部品カセットとの間のＺ軸上の距離（Ｚ番号の差の絶対値）を示している。４列目は、部品ｊを実装する際のヘッド速度を示している。５列目は、最初の実装点に対するＸＹテーブル１５の移動速度から実装点ｉに対するＸＹテーブル１５の移動速度のうちの最大値Ｗmax(0→i)を示している。
【００４２】
たとえば、ヘッド速度、ＸＹ速度が共にレベル１の場合、実装点ｉから実装点ｊまでの距離Δｘｙが２０である場合には、移動に必要な時間が１２０ｍｓｅｃとして求められる。また、実装点ｊのヘッド速度、ＸＹ速度が共にレベル３の場合には、部品を吸着してから装着するまでにかかる時間が１４０ｍｓｅｃとして求められる。
【００４３】
なお、変換テーブル３０７ｂに記載されていない値については、すでに求められている値から直線補間等を行なうことにより求められる。たとえば、距離Δｘｙが１０３を超える場合には、次式（１）により、距離Δｘｙを移動するための時間ｔxy（Δｘｙ）が求められる。
【００４４】
ｔxy（Δｘｙ）＝５００＋（Δｘｙ−１０３）／０．３５６          （１）
なお、他のパラメータについても、同様の補間式を求めることにより、時間への置き換えが行なわれる。
【００４５】
図１２は、部品実装順序決定装置３００の実行する処理のフローチャートである。
演算制御部３０１は、データベース部３０７より、実装点情報配列３０７ａおよび変換テーブル３０７ｂを読み込む（Ｓ２）。図９に示した実装点情報配列３０７ａに従うと、図１３に示す矢印の順序で部品の実装が行なわれることがわかる。
【００４６】
次に、演算制御部３０１は、読み込んだ実装点情報配列３０７ａおよび変換テーブル３０７ｂに基づいて、タクトテーブルを作成する（Ｓ４）。タクトテーブルとは、実装点ｉに部品を実装してから実装点ｊに部品を実装するまでに要する時間をまとめた表である。
【００４７】
図１４は、タクトテーブルの一例を示す図である。ここでは、基板マーク４０４を実装点０とし、ダミー点４０６を実装点６としている。タクトテーブルの各値である実装点ｉから実装点ｊまでの実装時間ｔijは、次式（２）に従い求められる。
【００４８】
ｔij＝ｍａｘ｛ｔxy（Δｘｙ），ｔz（Δｚ），
ｔh（ｈj），ｔw（ｗmax(0→i)）｝                （２）
ここで、上述した実装点ｉに関する実装点情報ｉを（ｘi，ｙi，ｚi，ｈi，ｗi）と表し、実装点ｊに関する実装点情報ｊを（ｘj，ｙj，ｚj，ｈj，ｗj）と表すものとした場合、
Δｘｙ＝ｍａｘ｛｜ｘi−ｘj｜，｜ｙi−ｙj｜｝
ｘｙテーブル上での実装点ｉとｊとの間の距離
ｔxy（Δｘｙ）：Δｘｙを変換テーブル３０７ｂに基づいて時間に置き換えた値
Δｚ＝｜ｚi−ｚj｜
実装点ｉに実装する部品が収納された部品カセットと実装点ｊに実装する部品が収納された部品カセットとの間のｚ軸上の距離
ｔz（Δｚ）：Δｚを変換テーブル３０７ｂに基づいて時間に置き換えた値（装着ヘッド１０３への部品供給部１１からの部品供給に必要な時間）
ｈj：部品ｊのヘッド速度レベル（レベル１（速）〜８（遅））
ｔh（ｈj）：変換テーブル３０７ｂに基づいて算出された部品を吸着してから装着するまでの時間（ただし、装着ヘッド１０３の半回転分の移動時間は考慮しないものとする）
ｗmax(0→i)：最初の実装点に対するＸＹテーブル１５の移動速度から実装点ｉに対するＸＹテーブル１５の移動速度のうちの最大値（レベル１（速）〜８（遅））
ｔw（ｗmax(0→i)）：ｗmax(0→i)を変換テーブル３０７ｂに基づいて時間に置き換えた値
なお、各実装時間は、後述する巡回セールスマン問題における「コスト」に相当するものである。また、タクトテーブルの算出処理（Ｓ４）においては、ｔij＝ｔjiと仮定し、ｔjiの算出を行なわないようにしている。これにより、処理時間の短縮を図ることができる。なお、「コスト」としては、各実装時間のみならず、２つの実装点間の移動距離をコストと定義してもよい。
【００４９】
また、ダミー点から各実装点（実装点１〜実装点５）までの実装時間は、任意のどの実装点間の実装時間よりも大きい値（ここでは、１０００００００）であるものとする。また、基板マーク４０４とダミー点４０６との間の実装時間は、任意のどの実装点間の実装時間よりも小さい値（ここでは、１）であるものとする。なお、これらの値は例示であり、これらに限定されるものではない。
【００５０】
次に、演算制御部３０１は、実装点情報配列３０７ａに基づいて初期巡回路を作成する（Ｓ６）。図１５は、初期巡回路の作成方法を説明するための図である。初期巡回路は、実装点情報配列３０７ａをＸＹテーブルの移動速度が速い順（レベル値が小さい順）に並べ替えることにより作成される。ここで、基板マーク４０４（Ｄａｔａ［０］）のＸＹ速度レベルは０とし、ダミー点４０６（Ｄａｔａ［６］）のＸＹ速度レベルは９とする。このようにすることにより、スタート点が基板マーク４０４になり、終了点がダミー点４０６になる。なお、処理の高速化のために、実装点情報配列３０７ａの要素の入れ替えを行なうのではなく、実装点情報配列３０７ａの要素番号を別途記憶する実装順配列ｐを使用するものとする。ｐ［ｉ］はｉ＋１番目に実装される実装点の実装点情報配列３０７ａにおける要素番号を示している。すなわち、図１５の実装順配列ｐによると、基板マーク４０４、実装点４、実装点５、実装点１、実装点２、実装点３およびダミー点４０６の順に部品の実装が行なわれることになる。この実装順序を図示した図が、図１６である。すなわち、基板マーク４０４をスタート点として、上述の順序により実装が行なわれた後、ダミー点４０６に戻る閉ループが作成される。
【００５１】
次に、演算制御部３０１は、求められた初期巡回路における総実装時間を求める（Ｓ８）。すなわち、初期巡回路における総実装時間Ｔは次式（３）に従い求められる。
【００５２】
Ｔ＝ｔ04＋ｔ45＋ｔ51＋ｔ12＋ｔ23＋ｔ36＋ｔ60                  （３）
ここで、一例として、総実装時間を図１４に示したタクトテーブルに従い求めると以下のようになる。
【００５３】
Ｔ＝２００＋３８０＋４００＋４００＋３００＋１０００００００＋１
＝１０００２０８１（ｍｓｅｃ）
次に、演算制御部３０１は以下に説明する処理（Ｓ１０〜Ｓ１８）に従い総実装時間が最小となるような巡回路を求める。
【００５４】
初期巡回路作成処理（Ｓ６）で求められた初期巡回路を表す実装順配列ｐは、上述の説明によると、図１５に示すように作成されるが、後の説明の簡単化のために、初期巡回路作成処理（Ｓ６）で求められた初期巡回路を表す実装順配列ｐは、ここでは図１７のように作成されたものとする。また、説明の簡単化のために、実装点０（基板マーク４０４）のＸＹ速度はレベル０であり、実装点１から実装点５までのＸＹ速度はすべて１であり、実装点６（ダミー点４０６）の速度レベルは９であるものとする。
【００５５】
まず、演算制御部３０１は、ループカウンタｉを０に設定する（Ｓ１０）。次に、演算制御部３０１は、巡回路に対して巡回セールスマン問題の２−ＯＰＴ法を適用させ、実装順序の入れ替えを試みる（Ｓ１２）。２−ＯＰＴ法（Ｓ１２）の詳細については、後述する。２−ＯＰＴ法により実装順序の入れ替えが行なわれた場合には（Ｓ１４でＹＥＳ）、ループカウンタｉを０にリセットする（Ｓ１６）。実装順序の入れ替えが行なわれなかった場合には（Ｓ１４でＮＯ）、ループカウンタｉを１つインクリメントする（Ｓ１８）。以上の処理（Ｓ１２〜Ｓ１８）を、ループカウンタｉの値が７になるまで、すなわち（ｉ＝Ｎ＝ｎ＋２）になるまで繰り返す（ループＡ）。ループカウンタｉの値が７になった時点の巡回路が巡回セールスマン問題を用いて求められた総実装時間が最小となる巡回路である。すなわち、ループＡの繰り返し処理を７回（Ｎ回）連続して行なっても実装順序の入れ替えが行なわれなければ、その時点で求められている巡回路が最適な巡回路であるとして、部品実装順序を決定する。
【００５６】
次に、２−ＯＰＴ法（Ｓ１２）について詳細に説明する。図１８は、２−ＯＰＴ法の詳細な処理を示すフローチャートである。
【００５７】
演算制御部３０１は、ループカウンタｊにｉ＋２を設定する（Ｓ１０２）。なお、ループカウンタｊの値が７を超えた場合には、ループカウンタｊに（（ｉ＋２）  ｍｏｄ  ７）を代入する。ここで、「ｘ  ｍｏｄ  ｙ」はｘをｙで割ったときの余りを示す。
【００５８】
次に、演算制御部３０１は、実装順配列ｐの要素ｐ［ｉ＋１］で示される実装点（以下、要素ｐ［ｋ］で示される実装点を実装点ｐ［ｋ］という。）と実装点ｐ［ｊ］とのＸＹ速度が同一か否かを判断する（Ｓ１０４）。
【００５９】
ＸＹ速度が同一であれば（Ｓ１０４でＹＥＳ）、実装点ｐ［ｉ＋１］と実装点ｐ［ｊ］とを入れ替えた場合の巡回路の総実装時間を算出する（Ｓ１０６）。
【００６０】
演算制御部３０１は、算出された総実装時間が算出前の総実装時間よりも短くなっているか否かを判断する（Ｓ１０８）。
【００６１】
たとえば、ｉ＝０でｊ＝２の場合には、実装点ｐ［１］とｐ［２］との実装順序を入れ替える前後で総実装時間を求めると、総実装時間の変化は起こらない。これは、以下のような理由による。すなわち、総実装時間の変化に影響する部分の実装順序について考えると、実装順序の入れ替え前のｐ［０］からｐ［１］への２点間の実装時間はタクトテーブルよりｔ01＝２００（ｍｓｅｃ）となる。また、ｐ［２］からｐ［３］への２点間の実装時間はタクトテーブルよりｔ23＝３００（ｍｓｅｃ）となる。このため、ｐ［０］からｐ［３］への実装時間は５００（ｍｓｅｃ）となる。一方、実装順序入れ替え後のｐ［０］からｐ［２］への実装時間はタクトテーブルよりｔ02＝３００（ｍｓｅｃ）となり、ｐ［１］からｐ［３］への実装時間はタクトテーブルよりｔ13＝２００（ｍｓｅｃ）となる。このため、ｐ［０］からｐ［３］への実装時間は５００（ｍｓｅｃ）となり、実装順序入れ替え前と同じである。このため、総実装時間も変化しない。
【００６２】
実装点ｐ［ｉ＋１］と実装点ｐ［ｊ］とのＸＹ速度が同一でないか（Ｓ１０４でＮＯ）または総実装時間が短くなっていなければ（Ｓ１０８でＮＯ）、ループカウンタｊの値を１つインクリメントする（Ｓ１１４）。その後、ループカウンタｊの値が（ｉ＋ｎ＋１）よりも小さいという条件を満たす間、Ｓ１０４以下の処理を繰り返す（ループＢ）。なお、ｊがＮを超えた場合には、ｊの代わりに「ｊ  ｍｏｄ  Ｎ」を用い、（ｉ＋ｎ＋１）がＮを超えた場合には、（ｉ＋ｎ＋１）の代わりに「（ｉ＋ｎ＋１）  ｍｏｄ  Ｎ」を用いるものとする。ループＢの処理が終了した時点で２−ＯＰＴ法（図１２のＳ１２）を終了する。
【００６３】
実装点入れ替え後の総実装時間が実装点入れ替え前の総実装時間よりも短くなっていれば（Ｓ１０８でＹＥＳ）、演算制御部３０１は、総実装時間を実装点入れ替え後の総実装時間に更新する（Ｓ１１０）。また、演算制御部３０１は、実装順配列ｐの要素の入れ替えを行なうことにより、実装順序の入れ替えを行なう（Ｓ１１２）。なお、図２０を用いて後述するように、実装点の入れ替えは、閉ループのパスの入れ替えに相当する。パスの入れ替えを行なうと、入れ替えた後のパスの途中に存在するパスの向きを逆にしなければ、閉ループとならない。このため、実装順序の入れ替えを行なう際には、このようにパスの向きを逆にする処理も合わせて行なう。これにより、巡回セールスマン問題における２−ＯＰＴ法（図１２のＳ１２）を終了する。
【００６４】
たとえば、ｉ＝０，ｊ＝４とした場合、実装点ｐ［１］（ここでは実装点１）と実装点ｐ［４］（ここでは実装点４）との入れ替え前の各実装点間の実装時間は、図１９（ａ）の下段の表に示すようになる。また、実装点１と実装点４との入れ替え後の各実装点間の実装時間は図１９（ｂ）の下段の表に示すようになる。図２０（ａ）および図２０（ｂ）は、実装点の入れ替え前と入れ替え後との巡回路をそれぞれ示した図である。すなわち、実装点１と実装点４とを入れ替えるということは、実装点０から実装点１へのパスと、実装点４から実装点５へのパスとを入れ替えることに相当する。
【００６５】
総実装時間に影響する部分の実装時間のみを考えると、実装点入れ替え前の実装点０から実装点１への実装時間はタクトテーブルよりｔ01＝２００（ｍｓｅｃ）であり、実装点４から実装点５への実装時間はタクトテーブルよりｔ45＝３８０（ｍｓｅｃ）である。このため、これらの合計実装時間は５８０（ｍｓｅｃ）である。一方、実装点入れ替え後の実装点０から実装点４への実装時間はタクトテーブルよりｔ04＝２００（ｍｓｅｃ）であり、実装点１から実装点５への実装時間はタクトテーブルよりｔ15＝１００（ｍｓｅｃ）である。このため、これらの合計実装時間は３００（ｍｓｅｃ）であり、実装点入れ替え前よりも短くなっていることがわかる。なお、実装点ｐ［１］と実装点ｐ［４］との入れ替えに伴い、図１９（ｂ）に示すように、ｐ［１］とｐ［４］との間に存在する要素ｐ［２］、ｐ［３］の値の入れ替えも行なわれる。すなわち、ｐ［２］の値が２から３に変わり、ｐ［３］の値が３から２に変わる。これは、図２０に示すように、ｐ［１］とｐ［４］とを入れ替えたことにより、その間に存在しているｐ［１]からｐ［２］へのパス、ｐ［２］からｐ［３］へのパスおよびｐ［３］からｐ［４］へのパスの方向が逆向きになることに起因する。なお、パスの方向を逆向きにしたとしても、上述のタクトテーブルの算出処理（Ｓ４）においてｔij＝ｔjiとしてタクトテーブルを求めている。このため、パスの方向が変化した部分に関して言えば、総実装時間の変化には影響しない。
【００６６】
なお、図２０の説明をまとめると、図２０（ｂ）においては、パスの方向を逆にしたとしても、当該パスを構成する実装点間の実装時間は変わらないという事例を説明している。また、最終目標は、閉ループの総実装時間が短くすることである。したがって、この条件に当てはまるようであれば、図２０（ａ）から図２０（ｂ）のような実装順序の変更を行なってもよい。さらに、図２０（ｂ）では、ある２点の実装点の入れ替えを行なった場合には、適宜閉ループとなるようにパスの方向の入れ替えを行なわなければならないことを示している。
【００６７】
図２１は、上述した部品実装順序決定装置３００による実装順序決定処理の処理結果を表す図である。図２１（ａ）は、実装順配列ｐと、実装点間の実装時間を示した図である。図２１（ｂ）は、実際の基板上での実装点の巡回路と実装点間の実装時間を示した図である。実装順配列ｐによると実装点０、４、２、３、１、５、６および０の順で巡回路が生成され、総実装時間は１０００１００１であることが示されている。ここで、図２０（ｂ）に示した閉ループの総実装時間を計算すると１０００１２５１であり、図２１（ｂ）に示した閉ループの総実装時間のほうが短いことが分かる。
【００６８】
図２２は、図２１（ａ）に示した実装順配列ｐと実装点情報配列Ｄａｔａと、実装順序との関係を示した図である。図２２（ａ）に示す実装順配列ｐの各要素の値は、図２２（ｂ）に示す実装点情報配列Ｄａｔａのインデックスを示しており、実装順配列ｐと実装点情報配列Ｄａｔａとの間の矢印が、実装点配列ｐの各要素が示す実装点情報配列Ｄａｔａの要素を示している。すなわち、ｐ［０］の値０は、１番目に実装される実装点の実装点情報配列Ｄａｔａの要素のインデックスを示している。このため、Ｄａｔａ［０］を示していることになる。Ｄａｔａ［０］には、基板マーク４０４の位置に関する情報が記憶されている。また、ｐ［１］の値４は、２番目に実装される実装点の実装点情報配列Ｄａｔａの要素のインデックスを示している。このため、Ｄａｔａ［４］を示していることになる。Ｄａｔａ［４］には、実装点４の実装点情報が記憶されている。以上のようにして求められた巡回路から基板マーク４０４とダミー点４０６とを除き、実装順配列ｐの値に基づいて、実装点情報配列Ｄａｔａの並べ替えを行なうと、図２２（ｃ）に示されるように、実装点４、２、３、１および５の順に実装される実装点情報配列Ｄａｔａが生成される。
【００６９】
図２３は、実装点情報配列Ｄａｔａの他の作成方法を説明するための図である。図２３（ａ）に示すような実装点配列ｐと、図２３（ｂ）に示すような実装点情報配列Ｄａｔａとが与えられているものとする。これらによると、巡回路のスタート点はダミー点であることが示されている。このため、図２４に示されるような巡回路が生成される。このため、このような場合には、図２２で説明したのと同様の方法に従い、図２３（ｃ）に示すような実装点情報配列Ｄａｔａを作成した後、実装点情報配列Ｄａｔａにおける実装順序を入れ替える作業を行なう。その結果、図２１（ｃ）に示されるような巡回路が生成されることになる。このようにして実装点情報配列Ｄａｔａを求めることにより、基板マーク４０４に近い実装点から部品が実装されることになる。
【００７０】
図２５は、従来の方法と本願にかかる方法との実験結果を示す表である。
この表には、第１列目にサンプル番号を示しており、第２列目に実装点数を示しており、第３列目に部品種類数を示しており、第４列目に従来方法（貪欲法）により求められた実装順序に従い部品を実装した場合の総実装時間を示しており、第５列目は本願の方法である巡回セールスマン問題を用いて求められた実装順序に従い部品を実装した場合の総実装時間を示しており、第６列目は、第５列目に示す総実装時間に対する第４列目に示す総実装時間の百分比を示しており、第７列目は、本願の方法による実装順序を求めるのにかかる処理時間を示している。なお、従来方法と、本願の方法とではＺ軸の部品カセットの並びは同じにして、条件をそろえている。
【００７１】
第６列目に示す改善率によると、すべてのサンプルにおいて、１００％を超えており、最大で１８．２％の改善（サンプルＥ）が見られる。また、実装順序を求めるために必要な処理時間もすべて１秒未満である。
【００７２】
以上説明したように、本実施の形態によると、現実的な時間内で最適な部品実装順序を決定することができる。
【００７３】
以上、本発明の実施の形態にかかる部品実装システムについて説明したが、本発明は、この実施の形態に限定されるものではない。
【００７４】
例えば、上述の実施の形態では、ロータリーヘッドを有する部品実装機を前提として、各実装点間の実装時間の式（式（２））を求め、実装順序を求めたが、式（２）を他の式にすることにより、基板自体は移動せず、部品吸着ヘッドを基板上の実装点に移動させ、部品を装着するモジューラー機と呼ばれる部品実装機での部品実装順序を求めるようにしてもよい。
【００７５】
なお、図１２に示した部品実装順序の決定方法においては、実装点情報配列３０７ａをＸＹテーブルの移動速度が速い順（レベル値が小さい順）に並べ替えることにより初期巡回路を求めるようにしているが（図１２のＳ６）、貪欲法により初期巡回路を求めるようにしてもよい。このようにすることにより、その後の巡回セールスマン問題による部品実装順序の決定処理を高速に行なうことが可能になる。
【００７６】
また、上述の実施の形態では、基板マーク４０４の近傍にダミー点４０６を設けるようにしているが、必ずしも基板マーク４０４の近傍にダミー点４０６を設ける必要はなく、予め定められた最初に部品が実装される部品実装点の近傍にダミー点４０６を設けるようにしてもよい。
【００７７】
また、ダミー点４０６は、予め定められた最初に部品が実装される部品実装点と同一の位置にあってもよい。
【産業上の利用可能性】
【００７８】
本発明は、部品実装機における部品実装順序の決定方法に適用でき、特にロータリー機における部品実装順序の決定方法等に適用できる。
【図面の簡単な説明】
【００７９】
【図１】本発明の実施の形態に係る部品実装システムの外観図である。
【図２】部品供給部とロータリーヘッドとの位置関係を示す概略図である。
【図３】部品を保持する部品テープが巻きつけられたリールの外観図である。
【図４】ロータリーヘッド、基板および部品供給部の位置関係を模式的に示した図である。
【図５】図４の位置Ｃに備えられた部品認識カメラの一例を示す図である。
【図６】ロータリーヘッド１００に備えられる装着ヘッド１０３の一つに着目した際の当該装着ヘッド１０３の動作を示すフローチャートである。
【図７】部品供給部１１の各種モードを説明するための図である。
【図８】部品実装順序決定装置の構成を示す機能ブロック図である。
【図９】実装点情報配列３０７ａの一例を示す図である。
【図１０】基板２０上の実装点、基板マークおよびダミー点の位置関係を示す図である。
【図１１】変換テーブル３０７ｂの一例を示す図である。
【図１２】部品実装順序決定装置３００の実行する処理のフローチャートである。
【図１３】部品の実装順序を模式的に示した図である。
【図１４】タクトテーブルの一例を示す図である。
【図１５】初期巡回路の作成方法を説明するための図である。
【図１６】部品の実装順序を模式的に示した図である。
【図１７】実装点配列ｐの一例を示す図である。
【図１８】２−ＯＰＴ法の詳細な処理を示すフローチャートである。
【図１９】部品の実装順序入れ替え前後における実装点配列ｐを示す図である。
【図２０】部品の実装順序入れ替え前後における巡回路を示す図である。
【図２１】部品実装順序決定装置３００による実装順序決定処理の処理結果を表す図である。
【図２２】図２１（ａ）に示した実装順配列ｐと実装点情報配列Ｄａｔａと、実装順序との関係を示した図である。
【図２３】実装点情報配列Ｄａｔａの他の作成方法を説明するための図である。
【図２４】巡回路の一例を模式的に示した図である。
【図２５】従来の方法と本願にかかる方法との実験結果を示す表である。
【符号の説明】
【００８０】
１０  部品実装機
１１  部品供給部
１５  テーブル
２０  基板
１００  ロータリーヘッド
１０１  回転基台
１０３  装着ヘッド
１０５ａ  鏡筒
１０５ｂ  小視野カメラ
１０５ｃ  大視野カメラ
１０５  部品認識カメラ
１０６  部品
１０７ｂ  ハーフミラー
１０７ａ  ミラー
１１０  部品テープ
１１１  部品カセット
１１２  吸着開口部
１１３  リール
１１４  テープフィーダ
３００  部品実装順序決定装置
３０１  演算制御部
３０２  表示部
３０３  入力部
３０４  メモリ部
３０５  部品実装順序決定プログラム格納部
３０６  通信Ｉ／Ｆ部
３０７  データベース部
３０７ａ  実装点情報配列
３０７ｂ  変換テーブル
４０２，４０４  基板マーク
４０６  ダミー点
【図１】
2006173318.tif 000003
【図２】
2006173318.tif 000004
【図３】
2006173318.tif 000005
【図４】
2006173318.tif 000006
【図５】
2006173318.tif 000007
【図６】
2006173318.tif 000008
【図７】
2006173318.tif 000009
【図８】
2006173318.tif 000010
【図９】
2006173318.tif 000011
【図１０】
2006173318.tif 000012
【図１１】
2006173318.tif 000013
【図１２】
2006173318.tif 000014
【図１３】
2006173318.tif 000015
【図１４】
2006173318.tif 000016
【図１５】
2006173318.tif 000017
【図１６】
2006173318.tif 000018
【図１７】
2006173318.tif 000019
【図１８】
2006173318.tif 000020
【図１９】
2006173318.tif 000021
【図２０】
2006173318.tif 000022
【図２１】
2006173318.tif 000023
【図２２】
2006173318.tif 000024
【図２３】
2006173318.tif 000025
【図２４】
2006173318.tif 000026
【図２５】
2006173318.tif 000027