JPH0471075A - 配置問題解決システム - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 ［発明の目的］ （産業上の利用分野） 本発明は幾つかの配置対象を配置した時点における配置
状況を考慮して、次に配置すべき未配置対象を最適に選
択して配置していく配置問題解決システムに関する。

（従来の技術） 複数のＩＣを実装した回路基板を設計する場合、回路基
板上のどの部位（場所）にどのＩＣを配置するかを決定
することが非常に重要な要件となる。このような回路基
板設計のみならず、種々の配置対象をどのように配置す
るかと云う問題は、様々な分野に存在する。この種の配
置問題は、従来−船釣には試行錯誤的、或いは経験的知
識に基づいて解かれている。

しかし最近では全ての配置対象の中の任意の２つの配置
対象毎に、それらの配置対象を近接させて配置させたい
度合いを表す近接度を定義し、この近接度を用いて配置
対象の配置状況を評価しながら次の配置対象の配置場所
を決定することで、その配置問題を解決することが試み
られている。

即ち、この種の配置問題解決システムは、基本的には幾
つかの配置対象を配置決定した状態で、次に配置すべき
配置対象を前記近接度に基づいて選択的に決定し、これ
を未配置場所に配置するように構成される。

一般的には、先ず既に配置決定された配置済対象の全て
に対して、次に配置するに最適な配置対象を前記近接度
に基づいて選択決定する。その上で、既に配置対象が配
置決定されている配置済領域の周辺の、最適であろうと
考えられる場所を選定し、その場所に上述した如く選択
決定された配置対象を配置する。

然し乍ら、このような手順を踏まえながら配置対象とそ
の配置場所とを決定して行くには、配置済領域の周辺の
配置可能な場所の全てを、その都度チエツクする必要が
あり、配置場所を決定するのに手間が掛かると云う不具
合がある。

（発明が解決しようとする課題） このように従来の配置問題解決システムにあっては、選
択決定した配置対象の配置場所を決定するには、既に配
置対象が配置決定された配置済領域の周辺の配置可能な
場所の全てを、その都度チエツクする必要があり、非常
に手間が掛かると云う問題があった。

本発明はこのような事情を考慮してなされたもので、そ
の目的とするところは、配置結果に対する満足度を犠牲
にすることなく、配置可能な場所についてのチエツク数
を減らして簡易に効率良く配置問題を解決することので
きる配置問題解決システムを提供することにある。

〔発明の構成］ （課題を解決するための手段） 本発明に係る配置問題解決システムは、複数の配置対象
の中の任意の２つの配置対象毎にこれらの配置対象を近
接配置させたい度合いを示す近接度を定義したテーブル
用い、■このテーブルを参照して次に配置しようとする
未配置対象を選択する為の基準となる配置済対象を基準
対象として選択し、■次いで選択された基準対象に対し
て最も近接させて配置したい未配置対象を前記テーブル
を参照して選択決定し、■その上で前記基準対象に最も
近い未配置場所を配置場所として決定して、この配置場
所として決定された未配置場所に前記選択決定された未
配置対象を配置していくようにしたことを特徴とするも
のである。

（作　用） 本発明によれば、未配置対象を選択する為の基準となる
配置済対象をテーブルを参照して決定し、この決定され
た配置済対象を基準対象とじて次に配置すべき未配置対
象を前記テーブルを参照して選択決定した後、その未配
置対象を配置すべき場所を決定するので、配置可能な場
所のチエツク数を大幅に減らしてその処理効率を高める
ことが可能となり、且つ十分に満足度の高い配置結果を
得ることが可能となる。

（実施例） 以下、図面を参照して本発明の一実施例に係る配置問題
解決システムにつき説明する。

第１図は実施例システムの概略的な構成を示すブロック
図である。この実施例システムは、概略的には配置対象
データ入力部１．配置問題解決処理部２．配置結果出力
部３の３つのブロックから構成される。

上記配置対象データ入力部１は、全ての配置対象の中の
任意の２つの配置対象毎に、それらの配置対象を近接配
置させたい度合いを示す近接度を定義したテーブルとし
て、配置対象に関するデータや、これらの配置対象が配
置される領域についてのデータを入力する為のものであ
る。この入力データによって配置処理しようとする配置
対象が幾つ存在し、これらの配置対象間にどのような配
置制約条件があるか、つまりどの配置対象とどの配置対
象とを近接させて配置させれば良いかの条件が与えられ
る。またその配置゛領域がどのように定義されているか
が示される。

尚、上記近接度は２つの配置対象を近接配置させたい度
合いを示すもので、例えば正の整数値として定義され、
近接配置させたい度合いが高いほど大きい数値として与
えられる。

しかして配置問題解決処理部２は、上記配置対象データ
入力部ｌから与えられる入力データに従って配置問題を
解決処理するもので、基準対象選択部２ａ、配置対象選
択部２ｂ、配置場所決定部２ｃの３つの処理機能を備え
ている。これらの３つの処理機能は互いに関連して動作
する。

基本的には先ず基準対象選択部２ａにて前記入力データ
に基づいて、既に配置決定された配置済対象の中から、
以下に示す配置対象を選択決定する為の基準となる配置
済対象を基準対象Ａとして選択する。この１基準対象Ａ
の選択決定の手法は配置処理の対象とする問題の種類、
例えば基板に部品を配置する問題に依存する。

具体的には、例えば配置済対象のそれぞれについて、未
配置対象との間の近接度の和をそれぞれ求め、上記近接
度の和が最大となる配置済対象を基準対象αとして選択
する。或いは後述する評価関数の下で上記未配置対象と
の間の近接度を評価し、その評価結果に従って基準対象
Ａを選択する。

尚、既に配置決定された配置済対象か存在しない場合、
つまり全ての配置対象か未配置の初期状態にあっては、
この処理手続きは省略される。

次に配置対象選択部２ｂか起動され、前述した如く選択
された基準対象αに対して、その基準対象αとの近接度
か最大となる未配置対象βを１つ選択する。近接度が最
大の未配置対象βか複数個存在する場合は、所定の選択
規則に従っていづれか１つを選択する。また基準対象α
が定められない初期時においては、未配置対象βの中の
１つを所定の規則に従って選択する。このような選択は
、例えば未配置対象βの重要度や機能・役割等を配慮す
る等して行われる。

しかる後、配置場所決定部２Ｃを起動し、例えば上述し
た如く基準対象αに基づいて選択決定された配置対象β
と、既に配置決定されている配置済対象との近接度を上
記基準対象α以外の全ての配置済対象について求め、そ
の近接度の情報に従って前記未配置対象βを配置する為
の配置場所を決定する。

具体的には、基準対象ａに基づいて選択決定された未配
置対象αと上記基準対象α以外の全ての配置済対象との
近接度の和が、前記未配置対象βと基準対象αとの近接
度より小さい場合は、基準対象αに最も近い未配置場所
を前記未配置対象βの配置場所として決定する。逆に前
記近接度の和が未配置対象βと基準対象αとの近接度よ
り大きい場合には、未配置対象βを配置したときの評価
度が最良となる未配置場所を上記未配置対象βの配置場
所と決定する。

以上の処理操作を未配置対象がなくなるまで繰り返し実
行することにより、配置対象の全てについての配置決定
がなされ、配置問題か解決される。

そしてその解決結果を前記配置結果出力部３から出力し
てその処理手続きを終える。

このように構成された配置問題解決システムにおける配
置対象の配置決定について、更に詳しく説明する。

今、第２図に示すように回路基板の予め定められた格子
上の各点（配置領域）に６個のＩＣ部品（配置対象）を
、その１番ピンが格子上の点に位置するように配置する
問題を解くものとする。但し、ここでは上記格子点を列
と行の対（ｍ、ｎ）で表すものとする。そしてその配置
結果の評価度は、２つのＩＣ部品か配置された格子点間
の距離と、その２つのＩＣ部品間の結合度（接続本数）
との積を、全てのＩＣ部品対について求め、その和をと
った値とする。この場合の評価度は、上記積和の値が小
さいほど良いことになる。

尚、ここではその説明が徒に複雑化することを避けるべ
く、ＩＣ部品のサイズは全て［２ｃｍＸ３ｃｍ］である
とし、これを配置する時の向きはその１番ビンが左下に
くる向きとする。そしてこれらのＩＣ部品か配置される
格子の間隔（大きさ）は［３ｅｆｆｉＸ　４　ｃｍ］で
あるとする。そしてこのような寸法関係に従って前述し
た評価度を求め、その配置結果を評価するものとする。

しかして上述した６個のＩＣ部品についての結合度の情
報は、前記配置対象データ入力部１がら全てのＩＣ部品
についてのサイズと配置の向き、２つのＩＣ部品間の近
接度として、全てのＩＣ部品対について例えば第３図に
示すような行列で示されるテーブルとして与えられる。

このテーブルからは、例えばＩＣＣ部品色ＩＣＣ部品色
の結合度は［７］でその結合度が最も強く、これらを近
接させて配置する必要があることが求められる。

またＩＣＣ部品色ＩＣＣ部品色の結合度は［０］であり
、これらについては格別に近接配置する必要かないこと
が求められる。

配置問題解決処理部２ては、先ず前記配置対象選択部２
ｂを起動し、初期処理として上述した第３図に示すよう
なテーブルを参照して６個のＩＣＣ部品色Ｂ、〜Ｆ中の
最も近接させて配置すべき２つのＩＣ部品を選択し、そ
れらの配置を決定する。

この例ではＩＣＣ部品色ＩＣＣ部品色の結合度が［７］
で、その結合度が最も高いことから、これらのＩＣＣ部
品色Ｂを、例えば第４図（ａ）に示すように近接させて
配置決定する。

このような初期処理を経た後、前記基準対象選択部２ａ
を既に配置された配置済対象の中から、前記テーブルに
示される結合度の情報に従って・基準対象α（基準とな
るＩＣ部品）を選択する。

基準対象αの選択処理は、配置済対象（第４図（ａ）に
示す例ではＩＣＣ部品色Ｂ）のそれぞれについて、未配
置対象（第４図（ａ）に示す例ではＩＣＣ部品色Ｄ、Ｅ
、Ｆ）との間の結合度をそれぞれ調べ、例えば次のよう
な評価関数ｆ　（ｘ）の下で、上記配置済対象を評価し
、最小値を与える既配置部品の１つを選択することによ
り行われる。

ｆ　（ｘ）　＝　（１／ｍ（ｘ）　十ｋ（ｘ）　／　ｔ
　（ｘ）　）　／２但し、Ｘは任意の配置済対象（ＩＣ
部品）であり、ｋ　（ｘ）は上記任意の配置済対象Ｘと
の結合度が正である未配置対象Ｙ　１．Ｙ　２．・・・
の個数である。

またｍ　（Ｘ）は前記任意の配置済対象Ｘと未配置対象
Ｙ　１．Ｙ　２．・・・との結合度の最大値、そしてｔ
　（ｘ）は前記任意の配置済対象Ｘと未配置対象Ｙｌ、
Ｙ２゜・・・との結合度の和である。

尚、このような評価関数ｆ　（ｘ）の下で求められる評
価値で、最小値を与える既配置部品が複数個ある場合に
は、その中の何れか１つを選ぶ。

具体的には第４図（ａ）に示すようにＩｃ部品Ａ。

Ｂが配置済の状態では、配置済対象であるＩＣＣ部品色
Ｈに対して、上記関数ｆ　（ｘ）の値を計算する。する
と ｆ　（Ａ）　＝　（１／ｍ（＾）十ｋ（＾）／１（Ａ）
）／２−　（１１５＋　　２／９）／２ −　１９　／　９０ ｆ　（Ｂ）　＝　（１／ｍ（Ｂ）　＋ｋ（Ｂ）　／　ｔ
　（Ｂ）　）　／２−（１／３＋　　３／８）／２ −５／１２ か求められ、［１９／９０　　＜　　５／１２］なる大
小関係から、基準部品としてＩＣＣ部品色選択される。

このようにしてＩＣＣ部品色基準部品として選択された
ならば、次に前記配置対象選択部２ｂにて次に配置決定
するべく、前記テーブルを参照して未配置対象を選択決
定する。この場合には未配置対象はＩＣＣ部品色Ｄ、Ｅ
、Ｆであり、基準部品αがＩＣＣ部品色あることがら、
このＩＣＣ部品色の結合度が最も大きい未配置対象を前
記ＩＣ部品Ｃ，Ｄ、Ｅ、Ｆの中から選択決定する。この
例では、前述した第３図に示すテーブルの結合度行列よ
り、ＩＣＣ部品色の結合度が［５］であるＩＣ部品りが
選択決定される。

しかる後、配置場所決定部２ｃにて上述した如く選択決
定されたＩＣ部品りの配置場所を決定する。

この配置場所の決定は、前述した基準部品αであるＩＣ
Ｃ部品量以外配置済対象はＩＣＣ部品色けであり、選択
決定されたＩＣ部品りと上記基準部品αであるＩ　Ｃ，
部品Ａ以外の配置済対象であるＩＣＣ部品色の結合度は
［１コ　またＩＣ部品りと前記基準部品αであるＩＣＣ
部品色の結合度は［５］であることから、ＩＣ部品りの
配置場所としては、ＩＣ部品Ａに最も近い未配置場所で
ある格子点（１，２）として決定する。

このようにしてＩＣ部品りの配置場所を決定した後、こ
のＩＣ部品りを配置済対象に加え、この状態で上述した
処理手続きを繰り返し実行する。

そして全ての配置対象（ＩＣ部品Ａ、Ｂ、〜Ｆ）につい
ての配置が決定し、未配置対象がなくなるまで、上述し
た配置処理を繰り返し実行する。この結果、第４図（ｂ
）に示すような配置構造が配置結果として求められ、配
置結果出力部３を介して出力される。

このようにして配置処理された配置構造の評価度は、前
述したように任意の２つのＩＣ部品が配置された格子点
間の距離と、その２つのＩＣ部品間の結合度（接続本数
）との積の和を評価値とした場合、 ［３Ｘ　　９］＋　　［４Ｘ　　　１１］＋　　［５Ｘ
　　８］＋　　［８Ｘ　　２］−［１１７コとなる。

ちなみに、従来にあってはＩＣ部品Ａ、Ｂを配置決定し
た後、未配買置対象のそれぞれについて（配置済対象全
体との結合度）／（配置対象全体との結合度）か最大の
未配置部品を選択しなから、その配置決定か行われる。

従って、前述した例の場合には、ＩＣＣ部品−ついては （０＋２）／　（０＋２＋０＋１＋１）−２／４ か求められ、同様にしてＩＣ部品り、Ｅ、Ｆについては
［６／１０コ、［７／１０］　、　　［０／３コが求め
られる。この結果、上記評価値に従ってＩＣ部品Ｅか選
択される。その上で、ＩＣ部品Ａ、Ｂが配置された領域
の周辺にある未配置領域について、具体的には格子点（
１，２）、（２゜２）、（３，１）にＩＣ部品Ｅを配置
した時の評価度を前述したように計算する。この場合、
上記各格子点についての評価度がそれぞれ、例えば［２
７］、　　［２９コ、　［４４コ　として計算されるこ
とから、その中の最小値をとる格子点（１，２）を前記
ＩＣ部品Ｅを配置する場所として決定する。

このような処理を繰り返し行うことにより、その最終的
な配置結果が第４図（Ｃ）に示すように求められる。そ
してその配置結果に対する評価値は、前述した積和の値
として ［３Ｘ　６コ＋　［４Ｘ　　１３　　］＋　　［５Ｘ　
　９］−［１１５コとして求められる。

この従来の配置処理と前述した実施例システムでの配置
処理とを対比すれば明らかなように、その配置結果の評
価値としては殆ど差異はない。然し乍ら、実施例システ
ムによれば配置場所の決定に一々全ての配置候補場所に
ついての評価を行う必要がない分だけ、その処理を高速
に実行することができる。このような違いは、配置対象
の数が多くなるに従って顕著に生じ、従って実用化レベ
ルでの数多くの対象を配置処理する場合、非常に大きな
効果として現れることになる。しかも基準対象を選択し
た上で配置対象を選択決定していくと云う簡単な処理に
て多大なる効果が奏せられる。

尚、本発明は上述した実施例に限定されるものではない
。例えば実際的には配置場所や配置対象部品の大きさ等
を考慮して配置問題を解いていくことは勿論のことであ
る。また配置対象の配置の向きを考慮することも勿論の
ことである。また選択の基準となる評価の手法について
も種々の評価関数を適用することかできる。その他、本
発明はその要旨を逸脱しない範囲で種々変形して実施す
ることかできる。

［発明の効果］ 以上詳述したように本発明の配置問題解決システムによ
れば、配置隅対象の中から基準対象を選択し、その基準
対象に対して近接度が最大の未配置対象を選択し、その
基準対象に最も近い未配置場所に配置すると云う処理を
優先的に実行するので、配置場所決定の為のチエツク数
を減らすことができる。しかもその配置結果の評価度に
ついては従来のシステムの場合と略々同等程度に確保す
ることかでき、配置対象の個数か多いほどより一層大き
な効果を発揮する等の実用上多大なる効果を奏し得る。

【図面の簡単な説明】

第１図は本発明の一実施例に係る配置問題解決システム
の概略的な構成を示すブロック図、第２図は実施例にお
ける配置領域について示す図、第３図は実施例における
配置対象間の近接度（結合度）のテーブル構造を示す図
、第４図（ａ）はＩＣ部品Ａ、Ｂの配置状態を示す図、
第４図（ｂ）は実施例システムによる配置結果を示す図
、第４図（ｅ）は従来の手法による配置結果を第４図（
ｂ）に対比して示す図である。 １・・・配置対象データ入力部、２・・・配置問題解決
処理部、２ａ・・・基準対象選択部、２ｂ・・・配置対
象選択部、２ｃ・・・配置場所決定部、３・・・配置結
果出力部。

Claims (2)

【特許請求の範囲】
1. （１）予め規定された複数の配置場所に幾つかの配置対
   象を配置した状態で、次に配置すべき最適な未配置対象
   を選択し、この選択された未配置対象の配置場所を未配
   置場所の中から選択決定するに際し、 複数の配置対象の中の任意の２つの配置対象毎にこれら
   の配置対象を近接配置させたい度合いを示す近接度を定
   義したテーブルを備え、このテーブルを参照して次に配
   置しようとする未配置対象を選択する為の基準となる配
   置済対象を基準対象として選択する手段と、選択された
   基準対象に対して最も接近させて配置したい未配置対象
   を前記テーブルを参照して選択決定する手段と、前記基
   準対象に最も近い未配置場所を配置場所として決定し、
   この配置場所として決定された未配置場所に前記選択決
   定された未配置対象を配置する手段とを具備したことを
   特徴とする配置問題解決システム。
2. （２）近接度は、２つの配置対象を近接配置させたい度
   合いが高いほど大きい数値として定義され、基準対象は
   、配置済対象のそれぞれについて、未配置対象との間の
   近接度に基づく所定の評価関数を作用させて求められる
   評価値を相互に比較して選択決定されることを特徴とす
   る請求項（１）に記載の配置問題解決システム。