JPH04257968A - プリント回路基板製造における最適な作業割り当て方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は広義には組立ラインに
おける作業割り当てに関し、より詳細にはプリント回路
（ＰＣ）基板組立工程における作業割り当てに関する。

【０００２】

【従来の技術】有効な自動製造システムの出現にともな
って複雑な設計と制御上の問題が出てきた。これらの問
題には機械のグループ分け、部品タイプの選定、作業割
り当て、沿具の配置、ツールの取り付けといったものが
ある。これらの問題のあるものについては、フレキシブ
ル製造システム（ＦＭＳ）のように当該技術分野におい
てすでに考察されている。この問題は機械の技術的制約
や能力上の制約の範囲内で作業と機械のグループの中か
ら必要なツールの割り当てを行うことである。従来の技
術では機械の作業負荷のバランスを取る、あるいは機械
間の作業の移行回数を最小限にするといった多数の異な
る目的を掲げている。ＦＭＳツール取り付けの問題に関
する従来のとらえ方のひとつに線形の物体に関する割り
当ての問題とするもの、すなわち機械の能力上の制約の
中で１つの作業あたりの総変動加工コストを最小限にす
るように機械にジョブ種別を割り当てる問題とするもの
がある。

【０００３】ＦＭＳツールの取り付けの問題についての
従来の別のとらえ方にそれぞれの作業に関わる変動コス
トを考察するものがある。それに対して、この発明の割
り当ての問題は作業あたりの変動加工コストだけでなく
、あるジョブの作業が特定の機械で実行される場合のジ
ョブあたりのワンタイムセットアップコストをも含む。 このセットアップコストは以下のようなわれわれが考察
する特定の技術のために発生するものである。さらに、
ＦＭＳツールの取り付けの問題は、処理すべきジョブの
周知のセットに対して処理量を最大限としメークスパン
を最小限にするといった目的に関連する戦略的な問題で
ある。われわれの割り当ての問題は将来の予想需要の概
算に対する予想生産コストを最小限とする（あるいは単
位生産量あたりの平均予想コストを最小限とする）とい
う目的を有する長期計画の問題である。

【０００４】この発明の解決する問題は適当な部品を挿
入することによって１つの装置で多数の異なるＰＣボー
ドを組み立てる従来のプリント回路基板組立作業から発
生する。この加工は多様な基板が生産され、生産量が自
動化に見合うものでないために充分に自動化されていな
い。このハンドロードセルの部品挿入は手付けあるいは
半自動機械のいずれかによって行うことができる。従来
の技術ではこの種のＰＣボード製造ラインにおける組立
の問題を適切に解決することができなかった。

【０００５】

【発明が解決しようとする課題】この発明の目的は基板
上に手付けあるいは機械によって挿入することのできる
部品を含むプリント回路基板の製造における作業割り当
てを最適化するシステムと方法を提供することである。 また関連する目的としては、ある種の部品を手挿入する
可能性を残しながらすべての基板を組み立てるための総
セットアップおよび加工コストを最小限とする容量とさ
れた機械のセットに対する部品（作業）の最適な割り当
てを決定することである。

【０００６】他の目的は総セットアップおよび加工コス
トを最小限とする容量とされた機械のセットに対する作
業割り当てを決定する作業割り当て問題に焦点をあてる
ことである。これらのコストはセットアップと加工に要
する時間単位で表現することができるため、関連する目
的としては、各ＰＣボードを生産するのに要する平均時
間を最小限とすることである。

【０００７】この問題は混合整数線形計画として定式化
できるが、これは実際に解くには大きすぎる。したがっ
て、単一の機械の場合にはこの発明では個々には状況に
よって充分ではない場合もあるが、平均的には満足な結
果をもたらす２つの異なる解決法を提供する。複数の機
械の場合、この発明では４つの異なる解決法を提供する
。

【０００８】

【課題を解決するための手段】上記課題を解決するため
に、本発明によれば、組立ラインにおいて複数の部品を
アイテムに組み込むための所定の能力を有する１以上の
機械に対する作業の割り当てを決定するための方法であ
って；組み立てられる各異なるアイテムの部品リストを
作成し；各異なるアイテムに対する製品要求を決定し；
前記部品リストと前記製品要求に基づいてアルゴリズム
を適応して、総費用設定及び処理費用を最小化する、各
ステップからなることを特徴とする方法が提供される。

【０００９】

【実施例】この発明によって最適化することのできる従
来のＰＣボード組立作業は多数存在する。例えば、１つ
の手挿入工程は次のように行われる。基板がトレー上に
セットアップされ、作業者が作業指示書からこの特定の
基板に対する組立作業指示を捜す。次にその作業指示に
したがって組立エリアにあるラベルを貼った容器から個
々の部品を取り出し、それらを基板に手挿入する。半自
動挿入の場合は、基板は半自動部品挿入機のトレー上に
セットアップされ、作業者はその機械を制御するコンピ
ュータに基板識別番号を入力する。次に機械が１組の内
部部品容器の中から必要とする第１の部品の入った容器
を識別し、容器を開け、それをこの部品を挿入すべき基
板上に移動する。作業者は開いた容器から部品を取り出
し、それを基板に手で挿入し、別の部品が必要であるこ
とを示すスイッチを押す。次に機械がその容器を閉じ、
取り外して、必要とされる次の部品の入った容器を引き
上げ、同様の処理がすべての部品が挿入されるまで繰り
返される。２つの同タイプの基板を順次生産する場合に
はセットアップ上の省略化は得られないことに注意を要
する。各基板は部品挿入を行うすべての工程においてセ
ットアップを必要とする。これはスルーホール組立工程
の一例である。

【００１０】セットアップと加工はいずれも機械で行う
方が速い（すなわち安価である）。しかし、機械が別種
の部品を保持する容量には制約があり、また用いること
のできる機械の数も限られる。さらに、機械の容器に対
する部品の割り当てを変更することにも費用がかかる。 このような変更には機械内の容器の中で部品を物理的に
置き換えることを要するばかりでなく、機械のコンピュ
ータをプログラムし直すことも必要になる。さらに、生
産工程が変更される場合（たとえば特定の基板を別の機
械で組み立てる場合）、基板品質と歩留まりの低下は非
常に高くつくものになる場合がある。したがって、部品
割り当てはＰＣボードの組立前に行われなければならず
、基板の組立工程中には一切変更することができない。 すべての基板が完全に組み立てられるまでは機械上の部
品のセットを変更することはできない。通常の場合、次
の１年あるいは半年間の機械のワンタイムツーリング（
すなわち、容器に対する部品の割り当て）は各種基板に
対する年間あるいは半年間の予想される（高い概算値の
）需要に基づいて決定される。その期間の最後に新しい
需要見積りが作成され、機械が再度ツーリングされる。

【００１１】ＰＣボード組立作業においては通常、多数
の部品から組み立てられた異なるＰＣボードを多数生産
しなければならない。たとえば、ある代表的な製造工程
においては、４０００種ほどの異なる部品から５００種
類にも及ぶＰＣボードが生産される。他の興味ある特徴
として、他の部品よりはるかに頻繁に用いられる部品が
あることである。図１には３００以上の部品から組み立
てられた３０の基板のサンプルに対する総使用のパーセ
ンテージとしての実際の累計部品使用を示す。

【００１２】最後に、基板間には低レベルではあるが無
意味とは言えない部品の共通性がある。図２には５８の
基板と１８０の部品の代表的なサンプルに対する部品が
用いられた異なる基板の数の実際の分布を示す。これの
例では、約３５％の部品が１つ以上の基板上で用いられ
、それらの部品の５％は５つ以上の基板上で用いられて
いる。 この低レベルの部品の共用は部分的にはこれらのＰＣボ
ードを用いた製品の多くが長い製品寿命を有することか
ら起こる。

【００１３】われわれが考察する問題は、すべての基板
を組み立てるためのセットアップおよび加工コストを最
小限にするために各工程（これはどの機械でもよく、ま
たどのマニュアル組立工程であってもよい）にどの部品
（作業）を割り当てるべきかを決定する問題である。特
定の基板用の部品のすべてが同じ工程（すなわち同じ機
械、あるいは同じマニュアル組立工程）に割り当てられ
ていない場合、この基板に対しては１つ以上のセットア
ップが必要となる。（しかし、部品挿入の順序は問題で
はなく、したがって１つの基板には１工程あたり最大で
も１つのセットアップが必要となるものと仮定する。）
多数のセットアップを避けるために、同じ部品を異なる
工程に割り当てることができる。したがって、この問題
はまた異なる機械のレイアウトの決定の問題、すなわち
組み立てが並列的工程で行われるべき範囲と直列的工程
で行われるべき範囲を決定するという問題でもある。こ
こでわれわれは向こう６か月から１２ヶ月の間の予想需
要の見積を用いて長期計画の問題を解決しようとしてお
り、バッチングやシーケンシングを問題としていないこ
とに注意を要する。

【００１４】実際には目的は戦略実行の基礎となる作業
方針を立てる（すなわち、機械の中を流れる基板種別の
流れを決定する）ことである。週間計画には需要の多い
期間には作業を外注すること、また需要の少ない期間に
は作業者の訓練コースを設けること等を含めることがで
きる。いずれの場合も施設と人員が配置されると（これ
はすでに行われたものと仮定する）それらは大部分は固
定費であり、したがって効率的な戦略実行を可能とする
設計が必要とされる。生産される基板あたりの平均予想
コストを最小限とするという目的は実際の製造計画を反
映し、われわれが考察する種類の長期計画の問題に適し
ている。われわれは（予想される将来の需要を用いて）
長期計画の問題を解決しようとするものであるため、短
期的で、需要条件のわかっている問題に対して適用する
ことのできる作業時間の最小化やスループットの最大化
といった方法ではなく、生産される基板あたりの平均コ
ストを最小限とすることを考察することがこの目的にか
なっている。コストはそれぞれの作業に要する時間単位
を用いて表現することが可能であることに注意を要する
。この場合、同時に動作している並列の機械がある場合
があるため、この目的は作業時間の最小化よりむしろ基
板の加工に要する平均時間を最小化することと同等であ
る（すべての基板が時間内に加工できるものと仮定する
。そうでなければこの問題には実現性のある解決法がな
い）。

【００１５】われわれのモデルでは作業割り当ては固定
された将来の需要見積りを用いて決定される。ここで当
然これらの需要見積りの不確実性が考慮される。この場
合、将来起こりうる需要の変化に関してしっかりとした
割り当て計画を作成することが望まれる。このような割
り当て計画は異なる製品に対する将来の需要のレベルに
関するある範囲の想定のもとに発生するコストを抑える
ことができる。

【００１６】以下の項では、この問題を混合整数計画と
して正式に定義する。正確な解を発見するための方法が
ここでは検討される。しかし、実際のアプリケーション
の多くにおいて、現実の問題は正確に解くには大きすぎ
ることがある。さらにある実施例においては技術者がメ
インフレームコンピュータではなくデスクトップコンピ
ュータで実施することのできる解決法を望んだ。したが
って、われわれはこの問題に対して解の発見法を展開し
ていく。まず分析を１つの機械の場合に特定することと
する。われわれは２つの異なる解の発見法を提案する。 われわれはアルゴリズムが最適な解を発生する条件を特
定し、最悪の場合のサンプルを提出し、ランダムに生成
された問題のセットに対する計算結果を提出する。われ
われはそれぞれのアルゴリズムが悪い場合もありうるが
、典型的な問題に対してはこれらのアルゴリズムはよく
はたらく。その後、われわれは多数の機械を用いるより
一般的な場合を考察する。われわれは４つの異なる解の
発見法を展開し、計算の実績を提出する。最後に、われ
われは実際の組立ライン上でのわれわれの結果の実施に
ついて論じる。

【００１７】

【問題の定式化】ｉを工程のインデックスとし（１，２
，３，…，Ｉ−１＝機械、Ｉ＝マニュアル）、ｊを部品
のインデックスとし（ｊ＝１，…，Ｊ）、ｋを基板のイ
ンデックスとする（ｋ＝１，…，Ｋ）。われわれの目的
は、Ｘｉｊｋ＝基板ｋの部品ｊの工程ｉへの割り当ての
最適の値を決定することであり、ここで、Ｘｉｊｋ＝割
り当てが行われたときは１、そうでなければ０である。

【００１８】また以下の見かけ変数を定義する。

【００１９】Ｙｉｋ　＝工程ｉでの挿入のために基板ｋ
がセットアップされている場合１；そうでなければ０Ｚ
ｉｊ　＝部品ｊが工程ｉに割り当てられている場合１；
そうでなければ０生産条件は次の通りである。

【００２０】ｄｋ　　＝その期間（固定）中の基板ｋに
対する総需要 ｒｊｋ　＝部品ｊが基板ｋに用いられている場合１；そ
うでなければ０ ｎｊｋ　＝基板タイプｋのうちの１つに用いられる部品
ｊの数これらを用いて、 ｖｊｋ　＝　ｄｋｒｊｋｎｊｋ ＝その期間中にタイプｋの基板に用いられた部品ｊの総
量 機械毎のセットアップおよび加工コストはすべての基板
と部品に対して同じである。

【００２１】ｓｉ　　＝工程ｉでの１つの基板の１回の
セットアップのためのセットアップコストｃｉ　　＝工
程ｉによる１回の挿入のための加工コスト最後に、機械
の制約が次のように与えられる。

【００２２】Ｎｉ　　＝工程ｉに割り当てることのでき
る部品のタイプの総数 これらの定義から、問題は次のように表すことができる
。

【００２３】

【数１】

【００２４】目的（１）は総加工およびセットアップコ
ストを最小限とすることである。制約条件（２）はすべ
ての必要な部品がある工程に割り当てられることを確実
とする。基板ｋの部品がある工程に割り当てられると、
（３）がセットアップが充電されるようにインジケータ
変数ｙｉｋを設定する。制約条件（４）と（５）はいず
れかの工程に割り当てることのできる異なるタイプの部
品の数の上限を表す。マニュアル加工はＮｉ＝Ｊを有す
ると仮定され、したがって（５）には含まれない。（６
）からｘｉｊｋに対する積分制約条件は不必要である。 上記の混合ＩＬＰによればすべてのｉ、ｊ、ｋに対して
常にｘｉｊｋ＝０または１となる。同様に、ｚｉｊ（見
かけ変数）に対する整数制約条件を指定する必要はない
。工程ｉのすべての容器がコスト最小化の解法に用いら
れる場合、ｚｉｊはその工程に対してはすべて２値の整
数値である。すべての容器が用いられない場合、最適な
解法は縮重であり、ｚｉｊは２値の整数値ではない場合
がある。しかし、これは（ｙｉｋとｘｉｊｋによって指
定される最適の解法に影響しない。このように問題はＩ
・Ｋ２値整数変数とＩ・Ｊ・（ｋ＋１）線形変数のうち
の１つである。

【００２５】上記の定式化によって単一の部品タイプを
１つ以上の工程に割り当てることが可能である。（工程
（ｚｉｊ）への部品の割り当てに対する唯一の制約条件
は１つの工程に割り当てられた異なる部品タイプの数は
その工程の能力を越えることができないということであ
る）セットアップ工数が加工コストに対して高く（した
がって１つ以上の工程を用いて基板を作成するとコスト
高になる）、各部品タイプを合計した必要数が利用可能
な部品スロットの数よりも大きくなるため、大量使用部
品を用いるすべての基板は１つの機械では充分に組み立
てることができない。したがってその部品を１つ以上の
工程に割り当てるのが最適な場合がある。この問題に対
する１つの解決法として、分岐限定法を用いる方法があ
る。すなわち部品割り当てを分岐し（すなわちｚｉｊ＝
０または１に設定する）、緩和された線形計画を解く（
ｙｉｋの整数制約条件を落とす）ことによって限定する
。分岐法を効率的に実行する方法はまず最も頻繁に用い
られる部品（すなわち

【００２６】

【数２】

【００２７】の最も高い値を持つもの）を分岐する。な
ぜならこれらの部品は総コストに最も大きな影響を持つ
ためである。ある部品がマニュアル工程に割り当てられ
ているかどうかを明示的に指定する必要はない。なぜな
らこのマニュアル工程は能力を与えられていないものと
考えられているため、必要であれば、あるいは希望すれ
ば部品は線形計画によってその工程に自動的に割り当て
られる。良好な初めの上限は３項および４項に示す発見
法を用いて得ることができる。

【００２８】現実の問題に対して整数計画を正確に解く
際の困難は問題の大きさにある。たとえば、中程度の大
きさの２工程の割り当ての問題（機械１台とマニュアル
工程）には２００の基板と６０００の部品が関係し、１
２０００の２値の整数変数と２００万以上の線形変数が
あることになる。整数の制約がないとしても、このよう
な問題は現在のＬＰコードを用いて解くには大きすぎる
。さらに、われわれの実験的なアプリケーションにおい
ては技術者はメインフレームコンピュータではなくデス
クトップコンピュータ上で実施することのできる解法を
望んだ。したがって、われわれはここで発見的な問題の
解法を展開する。まず、機械１台の場合について考察し
、次に多数の機械の場合について考察する。

【００２９】

【単一の機械の問題】この項では機械１台の場合に限定
して論じる。ここでｉ＝１の機械とし、ｉ＝２をマニュ
アル工程とする。するとこの問題は機械にどの部品を割
り当てるかを決定するという問題（ｚｉｊ）になる。機
械の容器がいっぱいになると割り当てられていないすべ
ての部品はマニュアル工程に割り当てられる。さらに機
械に割り当てられた部品の中にはマニュアル工程にも割
り当てられるものがある。部品割り当てが行われると各
基板に対するコスト最小化の解法（ｘｉｊｋとそれに対
応するｙｉｋ）を個々に決定することができる。

【００３０】現実の大きさの問題は実際に正確な解法で
特には大きすぎるが、問題のある特殊な特性から最適の
解法に近い優れた解法を構築することが可能となる。ま
ず、他のものよりはるかに頻繁に用いられる部品があり
、また他のものよりはるかに頻繁に組み立てられる基板
がある（図１のデータは部品と基板の使用はともに周知
の８０／２０ルールにしたがっていることを示す）。セ
ットアップと挿入はいずれもマニュアル工程より機械に
よる方が安価であるため、最適な解法では多くの（ある
いはすべての）頻繁に用いられる部品もしくは基板が機
械に割り当てられることが予想される。またある種の頻
繁に用いられる部品を除いて基板にはあまり部品の共通
性がないことがわかる。このことからわれわれは「グリ
ーディな（ｇｒｅｅｄｙ）」アプローチに基づいて２つ
の異なる解の発見法を構築する。１つは個々の部品を割
り当て、他は基板全部を割り当てるものである。

【００３１】われわれが「スティンギー部品（Ｓｔｉｎ
ｇｙ　Ｃｏｍｐｏｎｅｎｔ）」アルゴリズムと呼ぶ第１
の解法のアプローチはすべての部品を機械に割り当てる
（したがって機械の容量の制約を越える）ことから始ま
り、次に機械の容量に合うまでコスト増大の最も小さい
部品を順次除いていく。機械に割り当てられない部品は
すべてマニュアル工程に割り当てられる。さらにコスト
をより低減できる場合にはある種の部品を両方の工程に
割り当てることもできる。

【００３２】このアプローチの考え方は使用頻度の低い
部品の多くはコスト最小化の解法では機械に割り当てら
れることは決してなく、同様に最も頻繁に用いられる部
品は常に機械に割り当てられると考えられることである
。「スティンギー（Ｓｔｉｎｇｙ）」なアプローチは基
板全体より個々の部品の割り当てに注目しているため、
このアルゴリズムはセットアップコストが低いときに良
好にはたらくと考えられる。実際に、セットアップコス
トがゼロであるとき、スティンギーアルゴリズムは常に
最適な問題の解法を発生する。それはこの場合にはそれ
ぞれの部品を個々に考察することができるためである。

【００３３】ｉ＝１を機械とし、ｉ＝２をマニュアル工
程とする。すると「スティンギー部品（Ｓｔｉｎｇｙ　
Ｃｏｍｐｏｎｅｎｔ）」アルゴリズムは次のようになる
。

【００３４】

【数３】

【００３５】ステップ１ではすべての部品を機械に割り
当てる。ステップ２では機械から各部品を取り除く際の
インクリメンタルコスト（Δｊ）が計算される。これは
単位（ｃ２−ｃ１）あたりのインクリメンタル変動加工
コストに総影響量

【００３６】

【数４】

【００３７】を掛けたものとその部品を用いる基板であ
ってまだマニュアルセットアップコストのかかっていな
いもの（すなわちこのステップでδｋ＝１となる基板）
に対するインクリメンタルなマニュアルセットアップコ
ストからなる。インクリメンタルコストが最小でなる部
品が除かれ、目的関数、セットアップインジケータδｋ
およびコストが更新される。この取り除き作業は機械の
容器の容量に正確に適合するまで続けられる。ステップ
３は決定変数を設定する後加工ステップである。マニュ
アルセットアップを必要としない基板（δｋ＝１）はす
べて機械で完全に加工される。マニュアルセットアップ
を必要とする基板（δｋ＝０）についてはその基板全部
をマニュアル工程で加工するかどうかの決定が行われる
。そのほうが安価にできる場合、決定変数が調製され、
目的関数が更新される。

【００３８】ステップ２にいたる度に最大でＪの和が計
算され、分類が行われてその都度最大Ｊ２ｊｏｇ（Ｊ）
の計算が行われる。ステップ２にはＪ−Ｎ１回なるため
、スティンギー部品アルゴリズムの計算の複雑さの上限
はＪ３ｊｏｇ（Ｊ）ステップである。

【００３９】「グリーディ基板（Ｇｒｅｅｄｙ　Ｂｏａ
ｒｄ）」アルゴリズムと呼ばれる第２の解法のアプロー
チはすべての基板をマニュアル工程に割り当てることか
ら始まり次に基板全部を１つずつ機械に割り当てていき
使用される部品容器あたりの生産されるインクリメンタ
ルな基板数を最大とする。スティンギー部品アルゴリズ
ムと違ってグリーディ基板アルゴリズムは基板全体に注
目する。このアプローチの動機となっている考え方は、
（ａ）部品の共通性が小さいため、基板を分けるよりそ
の全部を機械あるいはマニュアル工程に割り当てるほう
がよい。（ｂ）既存の部品共通性を検討して機械に割り
当てられた基板のコスト減を得られる可能性がある。

【００４０】このアルゴリズムは正式には以下のように
記述することができる。

【００４１】

【数５】

【００４２】ステップ１ではすべての基板をマニュアル
工程に割り当てる。ステップ２では生産される基板あた
りの新しいスロットのインクリメンタルな数（γｋ）が
それぞれの基板について計算され、それぞれの基板の機
械へのインクリメンタルな割り当てはスロット容量の制
約を越えず、最小値を有する基板が機械に割り当てられ
る。（これは使用される追加のスロットあたりの生産さ
れるインクリメンタルな基板数を「グリーディに（Ｇｒ
ｅｅｄｙ）」最大化することに等しい。）この過程は基
板に割り当てることのできる基板がなくなるまで続けら
れる。 後加工ステップであるステップ３はスティンギー部品発
見法と同様であり（この場合、マニュアルセットアップ
が必要な基板

【００４３】

【数６】

【００４４】に対して）、部品のいくつかを機械で加工
するかどうかの決定が行われる。

【００４５】グリーディ基板アルゴリズムについては、
最大でＫの和とＫの分類が行われ、Ｋ２ｌｏｇ（Ｋ）が
計算される。ステップ２には最大でＫ回なり、したがっ
て必要な計算の上限はＫ３ｌｏｇ（Ｋ）ステップである
。Ｋ≦Ｊであり、典型的な問題ではＫ＜＜Ｊであるため
、グリーディ基板アルゴリズムは通常スティンギー部品
アルゴリズムより計算が少なくてすむ。

【００４６】基板に部品の共通性がないときは、グリー
ディ基板アルゴリズムは基板上の部品スロットを正確に
満たすことができ、したがってこのアルゴリズムは常に
最適の解法をもたらす。この場合、このアルゴリズムは
、値と重量の比率に基づいて品目をナップザックに順次
加えるグリーディ発見法である０−１ナップザック問題
用の高率高速アルゴリズムに類似する。この発見法はナ
ップザックを正確に満たすことができるとき最適の解法
を提供する。またわれわれはグリーディ基板アルゴリズ
ムが２つの工程上での加工コストが同様であるとき良好
にはたらくと考えることができる。なぜなら、この場合
基板を分けることによってはコストの節約が達成できな
いためである。しかし、マニュアルと機械による加工コ
ストが同一であり、グリーディ基板アルゴリズムがすべ
ての機械スロットを用いる場合にも、このアルゴリズム
は最適な解法を導かない。なぜなら、このアルゴリズム
は部品の共通性を近視的に考慮するにすぎないためであ
る。これらの条件下での最適な解法は機械に割り当てら
れる基板の量を最大限にする解法である。グリーディ基
板割り当てからは必ずしもこの解法は得られない。図３
にその一例を示す。ここでこの２つの解法アルゴリズム
の性能を検討する。それぞれの発見法の最悪の場合の性
能は悪い場合もあるが、平均的にはそれぞれがランダム
に発生した問題の大きなサンプルに対してきわめて良好
にはたらいた。

【００４７】われわれの問題は最小化の問題であるため
、ここでは最悪の場合の動作性能Ｒ＝〔ＪＨ−Ｊ＊〕／
〔Ｊｍａｘ−Ｊ＊〕；を用いる。ＪＨは発見的解法のコ
ストを表し、Ｊ＊は最適の解法を表し、Ｊｍａｘは最大
目的関数値の上限を表す。その率が１に近いほど発見法
の性能は悪くなる。上限としては

【００４８】

【数７】

【００４９】を用いる。これはすべての基板をマニュア
ル工程で組み立てることに対応する。 命　　題　　１ スティンギー部品発見法は悪い解法を発生することがあ
る。

【００５０】証　　　　　　明 図４に示す例を考察されたい。スティンギー部品発見法
は次の通りになる。

【００５１】

【数８】

【００５２】われわれは同様にグリーディ基板発見法も
悪い解法を発生しうることを例示することができる。

【００５３】命　　題　　２ グリーディ基板発見法は基板上のすべてのスロットを用
いるときにも悪い解法を発生することがある。

【００５４】証　　　　　　明 図５に示す例を考察されたい。第１のＮ１の基板はそれ
ぞれ１つの部品１、…、Ｎ１を用いる。残りの基板はそ
れぞれ第１のＮ１部品のうちの１つに加えて、部品Ｎ１
＋１、…、２Ｎ１のうち２つ以上を用いる。このような
可能な組み合わせがすべて含まれる。したがって、たと
えば部品Ｎ１＋１、…、２Ｎ１のうち２つ（加えて部品
１、…Ｎ１のうちの１つ）を用いる異なる基板の数は

【
００５５】

【数９】

【００５６】である。グリーディ基板発見法は（最適な
解法で行うように）機械上のすべてのスロットを用いる
。たとえば、次の通りである。

【００５７】

【数１０】

【００５８】平均的性能を評価するために、２つのアル
ゴリズムを、観察された基板量の分布、組立工程におけ
る部品の使用頻度および共通性からランダムに発生した
問題例のセットを用いてテストされた。ここに用いられ
たセットアップコストと加工コストは相対的な実コスト
を反映し、それぞれの作業に要する時間に比例する。そ
れぞれの問題に対して、真の最適な解法が徹底的な調査
によって決定された。計算結果を表１に示す。

【００５９】

【表１】

【００６０】１０×１５の大きさ（基板１０枚と部品１
５）の問題については、スティンギー発見法はグリーデ
ィ発見法より少し良く、平均誤差はグリーディ発見法の
４．２％に対して約３．１％であった。１０×２０の大
きさの問題については、グリーディ発見法の方が良く、
平均誤差はスティンギー発見法の４．８％に対して約４
．２％であった。興味深いことに、大きなサイズの問題
については平均誤差がわずかに増大したが、それぞれの
発見法の最大誤差は大きく減少した。

【００６１】この２つの発見法は問題の異なる側面に注
目する（スティンギー発見法は個々の部品の量に注目し
、グリーディ発見法は基板間の部品の共通性に注目する
）ため、この２つの解法の最小値を用いた複合的な発見
法が作成された。この複合的発見法の平均性能はいずれ
かのアルゴリズムを単独に用いた場合に比べてはるかに
良かった。

【００６２】

【多数の機械の問題】ここで多数の機械の問題を考察す
る。機械が同一であり、したがってｓｉ＝ｓｉ＋１，ｃ
ｉ＝ｃｉ＋１，Ｎｉ＋１，ｉ＝１，…，Ｉ−１であると
仮定する。これはわれわれのアプリケーションの場合で
ある。多数の機械の場合のわれわれの解法アプローチは
それぞれの機械に単一機械の発見法を順次適用すること
である。そこで、前述の通り、機械に対する初期の部品
割り当てを行った後後加工ステップを実行して割り当て
し直すことによってより安くすることのできる基板があ
るかどうかを判定する。単一機械発見法のそれぞれ（ス
ティンギー部品発見法およびグリーディ基板発見法）に
ついて、われわれは２つの異なる多数機械発見法を展開
する。これらの発見法は１つ以上の機械への部品割り当
てを可能とする範囲において異なっている。第１の場合
において、部品ｊが機械ｉに割り当てられる場合、部品
を機械ｉ＋１に割り当てるときもはや部品ｊは考慮され
ない。一方、第２の場合には機械ｉ＋１に対する部品ｊ
の潜在的な割り当てを考慮する。スティンギーアルゴリ
ズムの多数機械の場合への適用は以下の通りである。

【００６３】多数機械スティンギー部品アルゴリズム：
バージョン１ １．初期設定：ｉ＝１、ＳＫ＝｛１，…，Ｋ｝，ＳＪ＝
｛１，…，Ｊ｝ ２．「スティンギー」部品割り当て：基板のセットＳＫ
と部品のセットＳＪを考慮してスティンギー部品アルゴ
リズムを機械ｉに適用する。

【００６４】３．更　　新：機械ｉで完全に加工される
基板をＳＫから除き、機械ｉに割り当てられた部品をセ
ットＳＪから除く。

【００６５】ｉ＝ｉ＋１、ｉ＜Ｉとし、ステップ２に戻
る。

【００６６】４．後処理：機械への部品割り当てが終わ
った後、単一の機械で完全に加工されない基板のそれぞ
れについてその基板を生産する最も低コストの方法を判
定する（すなわち、機械の組み合わせか、機械とマニュ
アルを用いるか、あるいはマニュアルのみでおこなうか
の判定）。

【００６７】停止。

【００６８】多数機械スティンギー部品アルゴリズムの
第２バージョンは単一機械スティンギー部品アルゴリズ
ムを適用した後、機械ｉで完全に加工することのできる
基板にのみ関わる部品だけを考慮の対象から除外する。

【００６９】多数機械スティンギー部品アルゴリズム：
バージョン２ １．初期設定：ｉ＝１、ＳＫ＝｛１，…，Ｋ｝，ＳＪ＝
｛１，…，Ｊ｝ ２．「スティンギー」部品割り当て：基板のセットＳＫ
と部品のセットＳＪを考慮してスティンギー部品アルゴ
リズムを機械ｉに適用する。

【００７０】３．更　　新：機械ｉで完全に加工される
基板をＳＫから除き、機械ｉで完全に加工することので
きる基板にのみ関連した部品をセットＳＪから除く。

【００７１】ｉ＝ｉ＋１とし、ｉ＜Ｉであればステップ
２に戻る。

【００７２】４．後処理：機械への部品割り当てが終わ
った後、単一の機械で完全に加工されない基板のそれぞ
れについてその基板を生産する最も低コストの方法を判
定する（すなわち、機械の組み合わせか、機械とマニュ
アルを用いるか、あるいはマニュアルのみでおこなうか
の判定）。

【００７３】停止。

【００７４】同様に、多数機械グリーディ基板アルゴリ
ズムの２つのバージョンを展開する。 多数機械グリーディ基板アルゴリズム：バージョン１１
．初期設定：ｉ＝１、ＳＫ＝｛１，…，Ｋ｝，ＳＪ＝｛
１，…，Ｊ｝ ２．「グリーディ」基板割り当て：基板のセットＳＫと
部品のセットＳＪを考慮してグリーディ基板アルゴリズ
ムを機械ｉに適用する。

【００７５】３．更　　新：機械ｉで完全に加工される
基板をＳＫから除き、機械ｉに割り当てられた部品をセ
ットＳＪから除く。

【００７６】ｉ＝ｉ＋１とし、ｉ＜Ｉであればステップ
２に戻る。

【００７７】４．後処理：機械への部品割り当てが終わ
った後、単一の機械で完全に加工されない基板のそれぞ
れについてその基板を生産する最も低コストの方法を判
定する（すなわち、機械の組み合わせか、機械とマニュ
アルを用いるか、あるいはマニュアルのみでおこなうか
の判定）。

【００７８】停止。

【００７９】第２のバージョンは次の通りである。

【００８０】多数機械グリーディ基板アルゴリズム：バ
ージョン２ １．初期設定：ｉ＝１、ＳＫ＝｛１，…，Ｋ｝，ＳＪ＝
｛１，…，Ｊ｝ ２．「グリーディ」基板割り当て：基板のセットＳＫと
部品のセットＳＪを考慮してグリーディ基板アルゴリズ
ムを機械ｉに適用する。

【００８１】３．更　　新：機械ｉで完全に加工される
基板をＳＫから除き、機械ｉで完全に加工することので
きる基板にのみ関連した部品をセットＳＪから除く。

【００８２】ｉ＝ｉ＋１とし、ｉ＜Ｉであればステップ
２に戻る。

【００８３】４．後処理：機械への部品割り当てが終わ
った後、単一の機械で完全に加工されない基板のそれぞ
れについてその基板を生産する最も低コストの方法を判
定する（すなわち、機械の組み合わせか、機械とマニュ
アルを用いるか、あるいはマニュアルのみでおこなうか
の判定）。

【００８４】停止。

【００８５】これらのアルゴリズムは観察された基板の
量の分布と組立工程中の部品の使用頻度の共通性からラ
ンダムに発生した３０の２機械の問題例のセットにおい
てテストされた。用いられたセットアップコストと加工
コストは相対的な実コストを反映し、それぞれの作業に
要する時間に比例する。問題例はそれぞれ２０の基板と
１００の部品を含み、２つの機械のそれぞれにおいて３
５の部品スロットが利用可能である。問題のサイズが大
きいため（１００部品）、それぞれの問題に対する真の
最適な解法を判定することはできなかった。したがって
そのかわりに下限として単一の機械でそれぞれの基板を
生産するコスト

【００８６】

【数１１】

【００８７】を用いる。

【００８８】表２にその結果を示す。３０の問題のすべ
てに対してグリーディ基板アルゴリズムはスティンギー
部品アルゴリズムより優れていた。グリーディアルゴリ
ズムのバージョン２は最良の解法を導いた。スティンギ
ー部品アルゴリズムのＪｍｉｎからの平均偏差は７−１
０％であり、グリーディ基板アルゴリズムのＪｍｉｎか
らの平均偏差は３−５％であった。これらのパーセンテ
ージの差は、測定された偏差が実現性のない下限との比
較に基づくものであるため充分小さい。

【００８９】われわれの多数機械発見法はスティンギー
発見法とグリーディ発見法を個々にそれぞれの機械に適
用する。したがって、多数機械スティンギー部品アルゴ
リズムの計算の複雑性はＩ・Ｊ３ｌｏｇ（Ｊ）であり、
多数機械グリーディ基板アルゴリズムの計算の複雑性は
Ｉ・Ｋ３ｌｏｇ（Ｋ）である。これらの差はアルゴリズ
ムの実行時間に反映される。表２の２機械の例について
、Ｍａｃｉｎｔｏｓｈ　ＩＩｃ／ｘ　上でＰＡＳＣＡＬ
プログラムを用いた実行時間はスティンギー部品アルゴ
リズムについては平均２７秒、グリーディ基板アルゴリ
ズムについては平均３秒であった。

【００９０】ここまでわれわれは作業負荷のバランシン
グについてなにも言及しなかった。上述の解法アルゴリ
ズムはある種の機械に他の機械よりもはるかに大きな生
産量が割り当てられるような解法を発生することが可能
である。われわれは作業負荷のバランシングの問題を次
のように取り扱う。解法アルゴリズムを実行するとき、
各機械上で利用することのできるスロットの数を利用可
能なスロットの実数より多少小さい数に設定する。（わ
れわれのアプリケーション例では実際のスロット容量の
約９７％の数字を用いた。）次に特別に、われわれは各
工程への潜在的な基板の再割り当てを考察する。再割り
当てが可能になるように、使用されていないスロットに
頻繁に用いられる部品を当てはめる。これは次のような
実験的なアプリケーションにおいてきわめて有効であっ
た。

【００９１】

【表２】

【００９２】

【適用例】われわれのアルゴリズムは２つの異なるＰＣ
ボード製造問題に適用された。

【００９３】いずれの問題においても、グリーディ基板
アプローチが用いられた。スティンギー部品アプローチ
よりもこのアプローチが好まれた理由はセットアップコ
ストが挿入コストに対して割高であり、またグリーディ
基板アプローチは各基板に対するセットアップが少ない
点であった。さらにグリーディ基板アプローチは技術者
によって好まれた。それは１つの工程を用いて完全に組
み立てられた基板は１つ以上の工程を用いて生産された
基板より品質が高く、手直しの必要が少ないためである
。

【００９４】第１のアプリケーションは試験測定機器を
製造する部門における部品割り当てに関する。この部門
は数千の部品から５００近い基板をマニュアルで組み立
てていた。この部門はそれぞれが６４０の部品に対する
スロットを有する６台の新しい半自動部品挿入機を購入
し、生産の一部を機械に移行しようとした。この問題は
多数機械グリーディ基板アルゴリズムのバージョン２を
用いて解かれた。このアルゴリズムの結果は基板を同じ
機械で加工することのできる種別に分類することであっ
た。 基板の種別（６台の機械のそれぞれに対して１種別、残
ったものはマニュアル工程に割り当て）を決定するため
にアルゴリズムを適用した後、次のステップで機械間の
作業負荷のバランスをとるために機械に割り当てられた
部品のいくつかを再割り当てした。前述した手順を用い
て行われるこの再割り当てが実行された。それはこの６
台の機械がそれぞれ異なる作業者によって管理されてい
たためである。

【００９５】第２のアプリケーションは他の部門のコン
ピュータ用のＰＣボードの製造に関連している。この作
業においては、多種の基板がピックアンドプレース部品
挿入機のセットからなる面実装（ＳＭＴ）ラインで組み
立てられる。２つの連続する基板を生産するにあたって
、第１の基板が完成したとき機械上にない第２の基板に
必要な部品は第２の基板の生産を行う前に機械上にセッ
トアップされなければならない。しかし、同種の２つの
基板が順次生産されるときは追加のセットアップは必要
ではない。問題は生産コストを最小限とする基板の生産
計画を決定することであった。２つの異なる解法アプロ
ーチが考察された。第１のアプローチは基板間のセット
アップ時間を最小限にするために基板のリアルタイムシ
ーケンシングを適用することであった。このアプローチ
は次の基板を生産する前に機械上にセットアップしなけ
ればならない新しい部品の数を最小限にするものである
。 第２のアプローチは基板を基板間でのセットアップなく
生産することのできるような種別にグループ分けするた
めに多数機械グリーディ基板アルゴリズムのバージョン
２を適用することであった。この場合、アルゴリズムに
よって考慮された機械スロットの数はＳＭＴラインの機
械スロットの数と等しい。このアルゴリズムのステップ
２はすべての基板が各種別にグループ分けされるまで繰
り返された。グリーディ基板解法の考え方は１つの基板
種別に対して１回のセットアップを行い、その種別に属
するすべての基板を生産し、次の基板種別に対するセッ
トアップ等を行うことである。基板が各種別にグループ
分けされた後、ここに概略を示した手順を用いて異なる
基板グループに関連する作業負荷のバランスが取られる
。 基板は各グループの生産量のバランスが適切に取られる
までグループ間で切り替えられる。

【００９６】セットアップの最小化とグリーディ基板解
法はともにコンピュータシミュレーションを用いて評価
された。セットアップ最小化アプローチはグリーディ基
板アプローチに比して生産量が２％大きい解を導いたが
、セットアップ最小化解法では基板に対するサイクル時
間が長くなった。これはリアルタイムセットアップ最小
化アルゴリズムは基板の要するセットアップ時間が長す
ぎる場合、それらの基板の組み立てを不定に延期するこ
とができるためである。グリーディ基板解法はサイクル
時間が短いという利点があった。さらに基板を各種別に
分類する際に製造工程の管理がはるかに簡単である。 それは基板の各種別に対して１回のセットアップを行う
だけでよいためである。この理由でグリーディ基板解法
が選択され、実施された。

【００９７】

【発明の効果】以上の説明から当該技術の熟練者にはこ
の発明は２つの異なる発見的解法アプローチを提供し、
そのうち一方は部品の割り当てに注目し、他方は基板の
割り当てに注目するものであることが理解されるであろ
う。これらのアルゴリズムはともに上述のような問題に
対しては良好な解法を与えるが、ある実際の組立工程の
コストデータが与えられている場合、グリーディ基板ア
ルゴリズムの方が実験的なアプリケーションにおいては
多少良好な解法を提供した。これはセットアップコスト
が低いときにはスティンギー部品アルゴリズムがより良
い解法を提供する傾向があることを反映している。グー
ディ基板アルゴリズムはセットアップコストが高いとき
により良い解法を提供するようである。グリーディ基板
アプローチはほとんどの基板がわずか１つの工程に割り
当てられる解法を提供するという別の利点を有すること
がわかった。これは基板を各工程に分ける割り当てより
も高い品質をもたらし手直しの必要を低減する。

【００９８】ここまで２つの異なる生産工程について、
われわれの得た結果を実験的に実施したものについて論
じてきた。第１のアプリケーション、すなわち試験測定
機器のＰＣボード組立用の部品割り当てがわれわれのモ
デルと解法アプローチのもととなった元の問題であった
。第２のアプリケーション、すなわちコンピュータ製造
作業におけるＰＣボード生産のための基板種別の作成は
われわれの解法アプローチとグループ技術の考え方のつ
ながりを示すものである。われわれのアプローチは従来
のグループ技術アプローチより優れた利点を有すると考
えられる。それはわれわれが異なる製品間における基板
の共通性を考慮するだけでなく、製品と部品の量をも考
慮するためである。

【００９９】定式化されたように、われわれのモデルで
は異なる組立工程に関連するセットアップコストを考慮
するが、異なる工程間で基板を移動するのに要する輸送
時間とコストを考慮していない。特定のアプリケーショ
ンにおいて、機械の容量が個々の基板に要求される部品
に対してきわめて大きいため、輸送コストは重要ではな
い。したがって、問題が解かれたとき１つの基板が２つ
以上の工程に分けられるということはほとんど起こらな
かった。しかし、ある種のアプリケーションにおいては
工程間での輸送コストを考慮することが重要な場合があ
る。このモデル（および解の発見法）を輸送時間を取り
入れるように拡張する簡単な方法は、２つの工程間での
固定輸送コスト（ｔ）を想定し、目的関数（１）に、（
−１＋Σｉｙｉｋ）ｔに等しい輸送コストを加えるとい
う方法である。スティンギー部品アルゴリズムにおいて
は、われわれがインクリメンタルなセットアップコスト
を加えるとき（ステップ２）、輸送コストをも加える。 グリーディ基板アルゴリズムを用いて初期の割り当てを
行う（ステップ１および２）とき輸送コストを加える必
要はない。それは基板が工程間で分けられることがない
ためである。次に、後加工ステップ（ステップ３）中に
輸送コストを両方のアルゴリズムに加えることができる
。

【０１００】われわれのグリーディ基板アルゴリズムお
よびスティンギー部品アルゴリズムはＰＣボード組立工
程に通常見られるデータ構造を利用するように設計され
ている。われわれのアルゴリズムは、部品の共通性や部
品使用と基板需要における変化といったＰＣボード需要
と部品条件のある種の特性を利用している。われわれは
通常のＰＣボードや部品の需要データに対して、これら
のアルゴリズムが最適なものに非常に近い解法を与える
ことを示した。

【０１０１】以上この発明の実施例を説明したが、以下
のクレームに定義するこの発明の精神と範囲から逸脱す
ることなくさまざまな変更や改造が可能であることが理
解されるであろう。

【図面の簡単な説明】

【図１】例示ＰＣ基板組立ラインに関する実際のデータ
の図表である。

【図２】図１の例示ＰＣ基板組立ラインの別の図表であ
り、基板の間で共有される部品を示している。

【図３】グリーディ基板アルゴリズムを部品と基板の例
示の組合わせに適用した場合を示している。

【図４】スティンギー部品アルゴリズムを部品と基板の
別の例示の組合わせに適用した場合を示している。

【図５】グリーディ基板アルゴリズムを部品と基板のさ
らに別の組合わせに適用した場合を示している。

【図６】本発明の高レベルの流れ図である。

【図７】単一機械組立に適用されるスティンギー部品ア
ルゴリズムを示す流れ図である。

【図８】単一機械組立に適用されるグリーディ基板アル
ゴリズムを示す流れ図である。

【図９】複数機械組立に適用されるスティンギー部品ア
ルゴリズムを示す流れ図である。

Claims (1)

【特許請求の範囲】
1. 【請求項１】組立ラインにおいて複数の部品をアイテム
   に組み込むための所定の能力を有する１以上の機械に対
   する作業の割り当てを決定するための方法であって；組
   み立てられる各異なるアイテムの部品リストを作成し；
   各異なるアイテムに対する製品要求を決定し；前記部品
   リストと前記製品要求に基づいてアルゴリズムを適応し
   て、総費用設定及び処理費用を最小化する、各ステップ
   からなることを特徴とする方法。