JPH0630010B2

JPH0630010B2 - 電子部品挿入順序決定方法

Info

Publication number: JPH0630010B2
Application number: JP22485885A
Authority: JP
Inventors: 良尚荒井; 志乃高橋; 茂佐藤
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1985-10-11
Filing date: 1985-10-11
Publication date: 1994-04-20
Anticipated expiration: 2009-04-20
Also published as: JPS6286412A

Description

【発明の詳細な説明】〔発明の利用分野〕本発明は、通過順序に関し一部の点については制約条件
をもつ多数の点を含むようにして、これら点を結ぶ経路
が定められる場合に、複数存在する経路より経路長が最
も短いものを速やかに求めるための最短経路決定方法に
拘わり、特にプリント板上の部品挿入位置各々を点とし
て見なした上、自動挿入機によるプリント板上への電子
部品挿入時での挿入ヘッドの移動距離の和が最短となる
べく、電子部品の挿入順序を最適に決定するための電子
部品挿入順序決定方法に関するものである。

〔発明の背景〕

これまで多数の点を結ぶ経路より最短経路を決定する方
法としては、特開昭59-108106号公報に記載のように、
いくつかの方法が知られているが、点の通過順序に関す
る制約条件については配慮されていないものとなってい
る。また、すべての通過順序を求め、制約条件を満足す
るものの中から最短経路となる通過順序を求める「全数
列挙法（完全列挙法）」も知られているが、点の数が大
きくなると計算時間が実用範囲を越えてしまうという不
具合がある。

〔発明の目的〕

本発明の目的は、電子部品のプリント板上への挿入順序
に事前の部品相互間干渉チェックにもとづく制約がある
場合であっても、自動挿入機によるプリント板上への電
子部品挿入時での挿入ヘッド移動距離の和が最短となる
べく、電子部品の挿入順序が最適に決定されるための電
子部品挿入順序決定方法を供するにある。

〔発明の概要〕

この目的のため本発明は、各種電子部品各々のプリント
板上への挿入位置が予め知れている場合に、自動挿入機
により電子部品各々が挿入ヘッドで順次把持された上、
所定の挿入位置に順次挿入せしめられる際に、挿入位置
各々を点と見なした上、任意の組合せに係る２点間の距
離が予め与えられ、かつ一部に電子部品が挿入される上
での順序について、事前の部品相互間干渉チェックにも
とづく制約条件が与えられている多数の点に関して、部
品の挿入順序上での制約条件を満たし、かつ部品挿入時
での挿入ヘッドの移動距離の和が最短となる挿入順序を
決定するための電子部品挿入順序決定方法であって、部
品の挿入順序上での制約条件を満たす点の集合の中より
特定の点を選択する度に、該点を該集合より除くととも
に、該点を選択したことによって部品の挿入順序上での
制約条件がなくなった点を該集合に新たに加え、該新た
な集合の中より上記特定の点に最近隣のものを次の特定
の点として選択することを順次繰り返すことによって、
ある特定の点を出発点としてｎ（ｎ≠１）個の点を求
め、該出発点を含む該ｎ個の点について求められた全て
の部品の挿入順序より、挿入順序上での制約条件を満た
し、かつ移動経路が最短なものを選択することによっ
て、上記出発点の次の点を新たな出発点として選択する
ことを順次繰り返すことで達成される。

〔発明の実施例〕

以下、本発明を第１図から第９図により説明する。

先ず、第１図，第２図により本発明の原理の概要につい
て説明する。例えば第２図(a)に示す点Ｐ１〜Ｐ５に対
し同図(b)に示す距離行列が与えられている場合を想定
する。この場合距離としては単に２点を結ぶ直線の長さ
のみではなく他の意味を加えてもよい。これらの点に対
し第２図(a)に示すような通過順序に関する制約条件
（Ｐ２→Ｐ５，Ｐ２→Ｐ１，Ｐ１→Ｐ３）があるものと
する。ここでいう制約条件（Pi→Pj）とは、点Piを通っ
た後でないと点Pjを通ることができないことを意味して
おり、必ずしもPiの直後にPiを通る必要はない。

さて、本例での場合距離の和が最短となる経路は、Ｐ４
→Ｐ１→Ｐ２→Ｐ３→Ｐ５でありその経路の長さは58と
なるが、この経路は通過順序に関する制約条件（Ｐ２→
Ｐ１）を満足していないので、これを解とすることはで
きない。この例の場合では、経路Ｐ２→Ｐ１→Ｐ４→Ｐ
３→Ｐ５が経路の長さが66で、制約条件を満たす経路の
うち、最短のものとなる。

この例のように点の数が少ない場合はすべての経路を求
めたうえ制約条件を満足するものを選択し、更に制約条
件を満足する経路の中から経路の長さが最短のものを選
択する「完全列挙法」を用いることができるが、点の数
Ｎが大きくなると経路はＮ！通り存在するため実用的な
方法とはいえない。

また、このような多数の点の最短経路を求める手法とし
て「巡回セールスマン問題」の解法があるが、これによ
る場合は制約条件を表現することができないものとなっ
ている。

ここで本発明を具体的に説明すれば、第１図に示すよう
に、点の通過順序に関する制約条件を考慮し点をグラフ
の頂点として、また、制約条件→を辺とした有向グラフ
で表現するが、このとき第１の点として選択できる点は
Ｐ２，Ｐ４であり、先ずＰ２が選択されるようになって
いる。Ｐ２を選択することでＰ２→Ｐ１，Ｐ２→Ｐ５と
いう制約条件が無くなりＰ１，Ｐ５は通過順序の制約条
件を満足する点の集合に新たに加えられるものである。
以下、図に示す如くＰ１，Ｐ４，Ｐ３，Ｐ５が次々と選
択され、Ｐ２→Ｐ１→Ｐ４→Ｐ３→Ｐ５が制約条件を満
足する経路のうち最短なものとして得られるものであ
る。なお、本例では最適解が得られたが、必ずしも最適
解が得られるとは限らない。しかし、最適解に近い解を
得ることはできる。

本発明の原理は基本的には以上のようなものであるが、
解の精度を上げるためには更に以下の方法が採られるよ
うになっている。

即ち、小さい正の整数ｎ（≠１）をとり、出発点に近い
順にｎ個の点を選択し、これらｎ個の連続した点の通過
順序のうちから制約条件を満たす最短のものを選ぶよう
にして、その出発点の次の点を決定しようというもので
ある。この求め方は、第ｉ通過点Ｐ(0)が既に求められ
ているとすれば、次の通過点としての第（ｉ＋１）通過
点は以下のように求められるものとなっている。

制約条件を満たす点の集合の中からＰ(0)に最近接の
点Ｐ(1)を選ぶ。

Ｐ(1)を制約条件を満たす点の集合から除去するとと
もに、Ｐ(1)を選択することによって制約条件のなくな
った点を制約条件を満たす点の集合に加える。

制約条件を満たす点の集合の中からＰ(0)に最近接の
点をＰ(2)を選ぶ。

このようにしてＰ(0)に近い点をｎ個選ぶ。

Ｐ(0)を出発点としてＰ(1)〜Ｐ(n)の通過順序より制
約条件を満足する経路を選びだしたうえその中より経路
最短のものを選ぶ。

で求めた最短経路の第２通過点、即ち、Ｐ(0)の次
に通過する点をＰ(k)とすると、これを第（ｉ＋１）通
過点として定める。

このように〜の処理を次々と繰り返すことによっ
て、全体の通過順序が求められるものである。ところ
で、の処理より判るように、ｎを大きくすると制約条
件を満足する経路の数が多くなることから、ｎの値とし
ては最大でも８程度が好ましいものとなっている。この
方法を用いると、孤立点がある場合も対処することがで
きる。

以上解の精度を向上せしめる方法を一般的に説明した
が、この方法を第３図(a),(b)により具体的に説明すれ
ば以下のようである。

即ち、通過点としてＰ１〜Ｐ９が、また、制約条件とし
てＰ７→Ｐ２，Ｐ６→Ｐ９が、更にＰ１を出発点として
ｎ＝４の場合を想定すれば、制約条件を満たす点の集合
は｛Ｐ３，Ｐ４，Ｐ５，Ｐ６，Ｐ７，Ｐ８｝であり、こ
のうちＰ１に最も近い点Ｐ７が第３図(b)に示す距離行
列を参照することによって先ず選ばれる。Ｐ７をその集
合からとり除くと、Ｐ２が新たに集合に加えられ集合は
｛Ｐ２，Ｐ３，Ｐ４，Ｐ５，Ｐ８｝となる。次にはＰ１
に最も近い点Ｐ２が選ばれるものである。このようにし
て４点Ｐ２，Ｐ３，Ｐ７，Ｐ８が選ばれるわけである。
さて、Ｐ１を出発点としてこれら４点を通過する経路は
２４通りあるが、制約条件を満たすもののうち最短経路
はＰ１→Ｐ８→Ｐ７→Ｐ２→Ｐ３である。よってＰ８を
次の通過点として定めるものである。

次に、Ｐ８を出発点とする経路を考えれば、この場合に
選択される４点はＰ２，Ｐ３，Ｐ６，Ｐ７であり、最短
経路はＰ８→Ｐ７→Ｐ２→Ｐ３→Ｐ６となる。よってＰ
８の次の通過点としてはＰ７が選ばれるものである。こ
のように、次々と通過点を求めることによって、経路Ｐ
１→Ｐ８→Ｐ７→Ｐ２→Ｐ３→Ｐ６→Ｐ９→Ｐ５→Ｐ４
が第４図に示す如く求められるものである。これを先に
述べた基本的な方法（ｎ＝１の場合）で解くと、第５図
に示すように経路はＰ１→Ｐ７→Ｐ２→Ｐ３→Ｐ６→Ｐ
９→Ｐ５→Ｐ４→Ｐ８となり、ｎ＝４の方法が優ってい
ることが判る。因みに本例での場合距離は20％以上短縮
されたものとなっている。

最後に、以上の最短経路決定方法を本発明、即ち、プリ
ント板に電子部品を実装する際での電子部品挿入順序決
定方法について説明する。プリント板への実装では自動
挿入機によって電子部品を次々と挿入するが、挿入順序
をうまく選ぶことによって全挿入時間を10％〜20％短縮
できるといわれている。ところで、このプリント板への
挿入順序に関しては第６図に示すような制約条件があ
る。

即ち、基板Ｑ上に部品Ｉを挿入するときには挿入機の挿
入ヘッド（ヘッド位置は破線表示）と部品Ｊとは干渉し
ないが、部品Ｊを挿入するときには部品Ｉが挿入ヘッド
と干渉するため、部品Ｉが既に挿入されている状態では
部品Ｊを挿入することができないというものである。換
言すれば、部品Ｊ→部品Ｉという挿入順序に関する制約
条件があり、これを満たさないと自動挿入を行なうこと
ができないというわけである。

実際、プリント板上への実装部品数は1000点を越える場
合があり、また、１台の自動挿入機で挿入する部品数は
300を越える場合がある。このような場合に２部品間の
挿入順序に関する制約条件は多数発生するため、これら
をすべて考慮しつつ全体の挿入作業時間を短くするよう
な挿入順序を人間が決定するには多くの時間がかかり、
また、良い解が得られないばかりか、制約条件を満たさ
ない順序を決めてしまうことになる。よって、干渉が発
生し挿入不良のみならず部品やヘッドの破損を引き起こ
す虞れがあり、本発明による方法を用いることが必要と
なる。

先ず挿入順序に関する制約条件の決定方法について説明
すれば、この決定方法としてはいくつか考えられるが、
そのうちの最も簡便な１つについて以下説明する。

第７図(a)に示すように挿入ヘッドＰによって部品ｍを
基板Ｑ上に挿入する場合、挿入時での挿入ヘッドの位置
はＰ′となる。この場合、既に挿入されている部品ｋ，
ｌがあるとき、部品ｌは挿入ヘッドＰと挿入時に干渉す
ることになる。第７図(b)に示すように、平面上に部品
ｍの部品領域をＭ、部品ｋの部品領域をＫ、部品ｌの部
品領域をＬ、部品ｍの挿入作業スペースをＮとして表現
した場合、干渉チェックはこれらの図形Ｋ〜Ｎの重なり
状態をチェックすることによって行なわれるようになっ
ている。ここで、部品ｍの挿入作業スペースＮと部品ｌ
の部品領域Ｌとが重なっていることから、制約条件とし
ての挿入作業先行関係（部品ｍ→部品ｌ）が求まる。第
７図から判るように挿入作業スペースＮとしては、その
周辺に位置する部品の高さによりその大きさを変化させ
る必要がある。そのため、先ず周辺に位置する部品がす
べての部品のうちで最大の高さをもつとして挿入作業ス
ペースを求め、これを用いて重なり状態をチェックし、
重なり合う部品がある場合はその部品の高さに従って挿
入作業スペースを小さく修正し、再度重なりをチェック
するという方法をとることができる。

以上、干渉チェックとして挿入作業スペース、部品領域
を矩形，円等の簡単な平面図形で表わし、それらの図形
の重なり状態によって干渉を調べる方法を述べたが、挿
入作業スペース、部品領域をそれぞれ矩形，円等の組み
合わせとして表現する方法や、更には直方体，円柱等の
三次元立体及びその組み合わせとして表現し、その重な
り状態によって干渉を調べることもできる。

次に部品領域が矩形または円の場合について、その図形
重なりチェックのアルゴリズムの一実施例について説明
すれば、本例では重なりチェックは以下のようにして行
なわれるようになっている。

即ち、図形が矩形同士の場合には、一方の矩形を基準と
してその左下点（左下の頂点）で交差する両辺によって
定まる直角領域（同矩形を含むもの）および同右上点
（右上の頂点）で交差する両辺によって定まる直角領域
（同矩形を含むもの）何れの中にも他の矩形が存在すれ
ば、両矩形は互いに重なり合うものとする。また、図形
が矩形と円の場合には、矩形の周囲に円の半径に相当す
る幅の領域を設定し、この領域内、同矩形内の何れかに
円の中心が存在するときは、その矩形と円とは互いに重
なり合うものとする。更に図形が円同士の場合には、各
円の中心間の距離が両円の半径の和以下であるときは、
それらの円は互いに重なり合うものとしている。

第８図はその挿入作業先行関係決定（干渉チェック）処
理のフローを示すが、各ステップでの処理内容は以下の
ようである。

(step1) 部品情報中の部品寸法データを用い、組立情報中の全挿
入部品に関して部品領域を求める。

(step2) 挿入作業先行関係決定は、工程ごとに順番に行なうが、
その対象となる工程（対象工程）を前もって指定された
工程順序から決定する。すべての工程について挿入作業
先行関係の決定を終了した場合は、全処理を終了する。

(step3) すべての挿入部品の中から、組立情報中の部品レコード
の挿入工程データ項目の内容に従って、対象工程で挿入
する部品（対象工程挿入部品）と、対象工程よりも前の
工程で挿入される部品（挿入済部品）とを選び出す。

(step4) すべての対象工程挿入部品に対して、その挿入作業スペ
ースを求める。

(step5) 対象工程挿入部品の中から１部品を選択する。すべての
部品を選択した場合はstep２に戻る。

(step6) 選択した部品の挿入作業スペースと、挿入済部品及び選
択した部品以外のすべての対象工程挿入部品の部品領域
との重なりチェックを行なう。ここで、基板サイズを越
える範囲、基板ホルダや基板ローダで使用される範囲も
挿入制限領域として挿入済部品の部品領域と同等に扱
う。

(step7) step６の結果から挿入作業先行関係を求め、磁気ディス
ク上の挿入作業先行関係ファイルに登録したのち、step
５に戻る。

このようにして作成した挿入作業先行関係から、挿入順
序を変えても相互に干渉してしまう部品（挿入不可部
品）を求め、これをディスプレイに表示し、例えば設計
者により、挿入工程及び挿入方向の変更を行なう。この
処理も各工程ごとに行なうが、挿入不可部品は次の２つ
の場合に生じる。

(i)部品ｉ→部品ｊという挿入作業先行関係があり、部
品ｊの挿入工程が部品ｉの挿入工程より前の場合。

(ii)同一工程で挿入する部品であっても、例えば、部品
ｉ→部品ｊかつ部品ｊ→部品ｉという挿入作業先行関係
がある場合。３部品以上でも、部品ｋ→部品ｌ，部品ｌ
→部品ｍ，部品ｍ→部品ｋという挿入作業先行関係があ
る場合。

このような場合の対策方法としては、イ挿入工程を変更する方法ロ挿入方向を変更する方法がある。

挿入工程を変更した場合、例えば、部品ｉ→部品ｊとい
う挿入作業先行関係があり、部品ｊの挿入工程が部品ｉ
の挿入工程よりも前のとき、部品ｊの挿入工程を部品ｉ
の挿入工程の後に変更すれば、この挿入作業先行関係を
満足する挿入順序が存在する。また、例えば、部品ｉの
挿入工程を手動組立工程に変更すれば、挿入作業スペー
スが小さくてすむので、部品ｉ→部品ｊという挿入作業
先行関係がなくなる場合もある。

挿入方向を変更した場合、例えば、部品ｐ→部品ｑとい
う挿入作業先行関係があるとき、部品ｐに極性がなけれ
ば、部品ｐの挿入方向を180゜回転させて挿入すること
も可能である。これによって部品ｐの挿入作業スペース
が変化するため、部品ｐ→部品ｑという挿入作業先行関
係がなくなる場合もある。

何れの方法を採用しても、全体の挿入作業先行関係は変
化するため、第８図に示した挿入作業先行関係決定（干
渉チェック）の段階を再度実行させる必要がある。

同一工程で挿入する部品で、第８図で作成した挿入作業
先行関係から、どのような順序で挿入しても干渉が発生
する挿入不可部品グループを求める方法の１つとして、
以下にグラフ理論を応用した解法を示す。

本解法では各挿入作業（挿入部品）を頂点、挿入作業先
行関係を辺（矢印の方向）として挿入作業先行関係を有
向グラフで表現する。第９図は、本方法における挿入作
業先行関係の有向グラフであって、その(a)は一例とし
て９種類の部品11〜19に関して図中に示した挿入作業先
行関係がある場合でのものである。このグラフ上で強連
結部分、すなわち互いに辺に従って到達できる頂点の集
合を求めると、これが１組の挿入不可部品グループとな
る。例えば、部品12〜14は、１つの挿入不可部品グルー
プであり、この３つの部品は、これらの挿入作業先行関
係を満足する挿入順序を持たない。同様のことが、部品
18,19の組についてもいえる。このような挿入不可部品
グループは、公知のグラフ理論を用いて容易に求めるこ
とができる。

以上のように挿入工程、挿入方向の変更を行なうことに
よって、すべての挿入不可部品グループを除外し、最終
的な挿入作業先行関係を作成することができる。例え
ば、第９図(a)で、部品12の挿入工程を後の挿入工程に
変更し、かつ、部品19の挿入方向を変更すると、部品11
→部品12，部品12→部品13，部品14→部品12，部品19→
部品18の挿入作業先行関係がなくなるため、第９図(b)
に示すように、少なくとも１つの挿入順序が存在する最
終的な挿入作業先行関係の有向グラフを作成することが
できる。

以上、挿入工程変更，挿入方向変更を一例として対話形
により設計者の判断に基づいて行なう方法について述べ
たが、この設計者の判断を自動化し、挿入不可部品（グ
ループ）について、次々と挿入工程，挿入方向の変更と
挿入作業先行関係決定とを繰り返して行なうことによっ
て、挿入不可部品グループのない最終的な挿入作業先行
関係を求めることもできる。

さて、以上のようにして挿入工程や挿入方向の変更によ
って最終的な挿入作業先行関係が決まると、これらの制
約条件を満足して対象工程挿入部品を挿入することがで
きる順序が必ず存在する。挿入順序決定段階では、これ
らの挿入順序のうちから最適なものを求める。例えば、
挿入時の挿入ヘッドの移動距離（挿入機のＸＹテーブル
の移動距離）の総和を最小にする挿入順序（この挿入順
序は、全電子部品をプリント板上に所定に挿入するのに
要される時間が決定される上での重要要因となる）が考
えられるわけであるが、この挿入順序決定に既述の最短
経路決定方法を適用すれば、移動距離がほぼ最短とされ
るものが、容易に、しかも速やかに求められるものであ
る。このようにして挿入工程、挿入順序が決定されれ
ば、これに従って各挿入機ごとに部品挿入ＮＣデータを
作成されるところとなるが、これは公知技術により容易
となっている。

〔発明の効果〕

以上説明したように本発明による場合は、電子部品の挿
入順序に制約がある場合であっても、自動挿入機による
プリント板上への電子部品挿入時での挿入ヘッド移動距
離の和が最短となるべく、電子部品の挿入順序が最適に
決定され得るものとなっている。

【図面の簡単な説明】

第１図，第２図(a),(b)は、本発明の基本的な原理概要
を説明するための図、第３図(a),(b)は、改良された本
発明の原理概要を説明するための図、第４図，第５図
は、その改良された原理による効果の程を説明するため
の図、第６図，第７図(a),(b)，第８図，第９図(a),(b)
は、その改良された原理をプリント板への電子部品実装
に適用した場合を説明するための図である。

───────────────────────────────────────────────────── フロントページの続き (56)参考文献特開昭59−108105（ＪＰ，Ａ) 特開昭59−108106（ＪＰ，Ａ) 特開昭59−229604（ＪＰ，Ａ)

Claims

【特許請求の範囲】

【請求項１】各種電子部品各々のプリント板上への挿入
位置が予め知れている場合に、自動挿入機により電子部
品各々が挿入ヘッドで順次把持された上、所定の挿入位
置に順次挿入せしめられる際に、挿入位置各々を点と見
なした上、任意の組合せに係る２点間の距離が予め与え
られ、かつ一部に電子部品が挿入される上での順序につ
いて、事前の部品相互間干渉チェックにもとづく制約条
件が与えられている多数の点に関して、部品の挿入順序
上での制約条件を満たし、かつ部品挿入時での挿入ヘッ
ドの移動距離の和が最短となる挿入順序を決定するため
の電子部品挿入順序決定方法であって、部品の挿入順序
上での制約条件を満たす点の集合の中より特定の点を選
択する度に、該点を該集合より除くとともに、該点を選
択したことによって部品の挿入順序上での制約条件がな
くなった点を該集合に新たに加え、該新たな集合の中よ
り上記特定の点に最近隣のものを次の特定の点として選
択することを順次繰り返すことによって、ある特定の点
を出発点としてｎ（ｎ≠１）個の点を求め、該出発点を
含む該ｎ個の点について求められた全ての部品の挿入順
序より、挿入順序上での制約条件を満たし、かつ移動経
路が最短なものを選択することによって、上記出発点の
次の点を新たな出発点として選択することを順次繰り返
すことを特徴とする電子部品挿入順序決定方法。