In this paper, we discuss the application of the distributed simulated annealing(DSA) to the graph partition problem and the wiring problem which occurred in the process of circuit board design. DSA is a parallel algorithm that needs a shorter computation time than using the traditional simulated annealing algorithm. We carried out the experiment in the environment of PC cluster using DSA. Through comparing the solutions and the computation time with some of the results based on the traditional simulated annealing algorithm, it was confirmed that DSA is more effective.

基板設計の工程の中には次の３つのステップがある。一つは部品を複数の基板に分割して配置する分割問題があり，二つ目に基板のどの部分に部品を置くかを決める配置問題又はフロアプラン問題がある。そして三つ目に，部品間の配線を決定する配線問題がある。これら三つのステップは組み合わせ最適化問題となり，NP－完全問題に分類される。本論文では，シミュレーティッドアニーリング法（SA法）を並列計算に適応させた分散シミュレーティッドアニーリング法（DSA法）をPCクラスタ上で基板設計工程で生じる上述の一つ目の分割問題と三つ目の配線問題に適応させて実験をし，基板設計時における分散シミュレーティッドアニーリング法の活用を模索した。SA法と比較することによって，分散シミュレーテッドアニーリング法の有効性を実証した。