JP2019516155A - 構成グループを実装ラインへ割り当てるための方法および装置 - Google Patents

Abstract

本発明は、実装ライン（ＢＬ１〜ＢＬ２）ごとに予め与えられた最大の時間稼働容量のもとで最小の構成素子分散値を達成するために、複数の構成グループ（ＬＰ１〜ＬＰ６）を、当該構成グループ（ＬＰ１〜ＬＰ６）に複数の構成素子（Ｂ１〜Ｂ６）を実装するための複数の実装ライン（ＢＬ１〜ＢＬ６）へ割り当てるための方法に関する。本方法では、構成素子分散値が複数の実装ライン（ＢＬ１〜ＢＬ２）において必要とされる構成素子種類の数の合計として定められ、実装すべき構成グループ（ＬＰ１〜ＬＰ６）の各構成グループ種類および各実装ライン（ＢＬ１〜ＢＬ２）とについて、各実装ライン（ＢＬ１〜ＢＬ２）における構成グループ種類の各サイクル時間と、各変更時間と、各ライン利用容量と、構成グループ種類ごとに期待される生産すべき個数とを考慮して、期待される生産時間が求められ、実際の生産すべき個数が予め定め得る確率分布に従って発生し、１つのライン（ＢＬ１〜ＢＬ２）に割り当てられた構成グループ（ＬＰ１〜ＬＰ６）の集合について、これらの期待される総生産時間の合計が、各実装ライン（ＢＬ１〜ＢＬ２）の最大の時間稼働容量を上回ってはならず、複数の実装ライン（ＢＬ１〜ＢＬ２）への複数の構成グループ（ＬＰ１〜ＬＰ６）の実行可能な割り当てが既存のインフラストラクチャ又は使用者定義の設定によって制限されており、複数の個数に関する前記確率分布から結果として生じる実装ラインごとの期待される生産時間の合計に関する確率分布について、これらの結果として生じる確率分布の各期待値からの偏差が予め定め得る最大閾値によって制限されるように、前記割り当てが実施され、複数の実装ライン（ＢＬ１〜ＢＬ１）への複数の構成グループ（ＬＰ１〜ＬＰ６）の割り当てが、与えられた設定のもとで整数線形計画法により算定される。【選択図】図３

Description

本発明は、複数の構成グループ(構造体)を、当該構成グループに複数の構成素子（コンポーネント）を実装するための複数の実装ラインへ割り当てるための方法に関する。さらに、本発明は、複数の構成グループに複数の構成素子を実装するための製造又は組立ラインのための装置に関する。さらに、本発明は、コンピュータプログラム製品およびコンピュータ読取可能な媒体に関する。

特に電子機器生産の分野では、製造すべきプリント基板もしくは構成グループがＳＭＴ実装ラインにおいて表面実装技術（surface mounted technology，SMT）によって製造される。ＳＩＰＬＡＣＥなる製品名を有するＳＭＴ自動実装機およびシステムの製造元は、例えばＡＳＭ社（http://www.siplace.com/en/Home）である。

しかし、技術的制約のために、どの実装ラインにおいてもどの構成グループも製造可能であるとは限らない。構成グループは、実装ラインで異なる生産時間を有することも多い。さらに、実装ラインの最大生産時間能力を上回ることは許されない。

１つの実装システムの複数の実装ラインへの複数の構成グループの割り当ては、通常、経験値又はヒューリスティック法に基づいて手動又は半自動で実施される。

製造での計画視野は通常中期的であるため、異なる構成グループ種類の将来的な個数に関しては不確実性が存在する。これは、願わしくない実装ラインの稼働容量／生産時間の著しい変動をもたらし得る。それゆえ実際には個々のラインにおいて格別に大きい生産時間変動を生じさせ得るような構成グループ−ライン割り当てを回避することが望まれる。このような生産時間変動は、しばしば当該ラインの過負荷又は不足負荷をもたらす。

数理最適化法が使用できる場合に線形最適化法が考えられる。線形最適化法は、線形の等式および不等式によって制限されている集合について、線形目的関数の最適化に取り組む。線形最適化法は、（混合）整数線形最適化の解法の基礎である。いわゆるソルバーは、数学的問題を数値的に解くことができる特殊な数学的コンピュータプログラムに対する総称である。ＭＩＰ（mixed integer linear programming、混合整数線形計画法）との関連では、小さいＩＰプログラム（整数最適化モデル）のために、例えばＣＰＬＥＸ、Ｇｕｒｏｂｉのような標準ソルバーを使用することができる。小さいＩＰプログラムとしては、例えば２個のライン、１８１個の構成グループおよび８３９個の構成素子種類を有するインスタンスが考えられる。大きなインスタンスの場合には、ＣＰＬＥＸのような標準ソルバーに関して、この複雑な問題設定を解くという問題が生じ得る。

特許文献１は、電子的な構成グループの製造において個々の製造ラインの最適化のために混合整数線形計画法を使用することを提案している。

特許文献２は、１つの実装ラインにおいて異なる構成グループ種類を混合するための構成を決定する方法に関する。

特許文献３、特許文献４、特許文献５および特許文献６は、複数の構成グループを複数の実装ラインへ割り当てるためのＭＩＰを用いた最適化手法の例である方法を公開する。

とりわけ特許文献３は、複数のプリント基板を、当該プリント基板に複数の構成素子を実装するための複数の実装ラインへ割り当てるための方法を公開し、これにより、予め与えられた境界条件下で、できるだけ少ない構成素子分散値と、できるだけ最適な生産時間とが達成される。その際に構成素子分散値は、複数の実装ラインにおいて必要とされる構成素子種類の数の合計として定義されている。

装置設備ファミリは、１つの実装ラインにおいて実装のために用意されている構成素子種類の集合を変更することなく、１つの実装ラインにおいて実装することができる構成グループの集合であると規定されている。１つの実装ラインに用意されている構成素子種類の集合は装置設備とも称せられる。一般に、１つの実装ラインには１つの装置設備ファミリが含み得る構成グループよりも多い構成グループが割り当てられている。というのは、１つの実装ラインに任意に多くの構成素子種類を用意することができないからである。従って、実装ラインは時々装置設備交換される。その装置設備交換の際に、第１の装置設備ファミリのための装置設備が、第２の装置設備ファミリのための装置設備と交換される。この装置設備交換が稀であるほど、少ない時間コストで実装システムを運転することができる。実装システムにおいて使用される装置設備ファミリの全体の数は、例えば１つの実装ラインの構成素子分散値よりも実際的な品質指標を表すことができる。その場合に１つの実装ラインの構成素子分散値は、その実装ラインに割り当てられている複数の構成グループの１つへ実装すべきである構成素子が属している異なる構成素子種類の数によって与えられている。従って、特許文献３から公知の方法は、複数の実装ラインへの複数の構成グループの割り当てを決定することができ、それらの割り当ては実装システム全体の改善された稼働容量を可能にする。

個々のラインの最大の生産時間変動を制限するか、又はこれをできるだけ最小化するためには、ＩＰモデルでの更なる改善が必要である。

大きなインスタンスもしくは複雑な問題設定に対する解を完全に又は最適化した形で獲得することを可能にするためには、適用すべき制約条件もしくは使用者定義の設定を有するＩＰモデルもしくはＩＰプログラムにおいて良好もしくは正確なパラメータ選択が非常に重要である。

米国特許第６８２９５１４号明細書 独国特許出願公開第１９８３４６２０号明細書 独国特許出願公開第１０２０１１０７６５６５号明細書 国際特許出願公開第２０１４／００５７４１号明細書 国際特許出願公開第２０１４／００５７４３号明細書 国際特許出願公開第２０１４／００５７４４号明細書

本発明の課題は、上述の従来技術に対して改善された、構成グループを実装ラインへ割り当てるための最適化方法もしくは技術を提供することにある。

この課題は、本発明によれば独立請求項によって解決される。有利な発展形態は従属請求項に記載されている。

本発明は、実装ライン（ＢＬ１〜ＢＬ２）ごとに予め与えられた最大の時間稼働容量に対して最小の構成素子分散値を達成するために、複数の構成グループ（ＬＰ１〜ＬＰ６）を、当該構成グループ（ＬＰ１〜ＬＰ６）に複数の構成素子（Ｂ１〜Ｂ６）を実装するための複数の実装ライン（ＢＬ１〜ＢＬ６）へ割り当てるための方法に関する。本方法では、
構成素子分散値が複数の実装ライン（ＢＬ１〜ＢＬ２）において必要とされる構成素子種類の数の合計として定められ、
構成素子を実装すべき構成グループ（ＬＰ１〜ＬＰ６）の各構成グループ種類および各実装ライン（ＢＬ１〜ＢＬ２）について、各実装ライン（ＢＬ１〜ＢＬ２）における構成グループ種類の各サイクル時間と、各変更時間と、各ライン利用容量と、構成グループ種類ごとに期待される生産すべき個数と、を考慮して、期待される生産時間が求められ、
実際の生産すべき個数が予め定め得る確率分布に従って発生し、
１つのライン（ＢＬ１〜ＢＬ２）に割り当てられた構成グループ（ＬＰ１〜ＬＰ６）の集合について、これらの期待される（総）生産時間の合計が、各実装ライン（ＢＬ１〜ＢＬ２）の最大の時間稼働容量を超えてはならず、
複数の実装ライン（ＢＬ１〜ＢＬ２）への複数の構成グループ（ＬＰ１〜ＬＰ６）の実施可能な割り当てが、既存のインフラストラクチャ又は使用者定義の設定によって制限されており、
複数の個数に関する前記確率分布から結果として生じる実装ラインごとの期待される生産時間の合計に関する確率分布について、これらの結果として生じる確率分布の各期待値からの偏差が予め与え得る最大閾値によって制限されるように、前記割り当てが実施され、
複数の実装ライン（ＢＬ１〜ＢＬ１）への複数の構成グループ（ＬＰ１〜ＬＰ６）の割り当てが、整数線形計画法による与えられた設定のもとで算定される。

本発明の実施形態は、各期待値からの偏差の合計を最小化することである。

本発明による方法の利点は、大きいインスタンスを有する問題設定も今や、ヒューリスティック法によるよりも少ない計算費用で解くことができることにある。

最適化法としては、いわゆる整数線形計画法を使用することができる。それによって、市販の標準ソルバーを使用することができる。

結果として生じる確率分布の期待値からの前記偏差は、類似した又は等しい値を取る。この場合に、「類似した」とは、最大偏差が上方又は下方に向けて許容されることを意味する。「等しい」とは同一を意味する。しかし、（ほとんど）等しい値の場合にも、上方又は下方に向けての僅かな偏差の形で僅かな不正確さがあってよく、「類似した」と違って、このような僅かな偏差は、ほとんど予定することができず、従ってほとんど予め定めることができない。

構成グループの使用者によって予め与えられた集合が同一の実装ラインに割り当てられるならば、これは有意義なことである

１つの実装ラインの期待される生産時間の合計からの偏差は、その生産時間の分散値として表すことができる。

実装ラインごとの分散値は、ある時間内における１つの構成グループ種類の期待される個数と、結果として生じる確率分布の付属した値との２乗偏差から、１つの実装ラインに割り当てられている全ての構成グループ種類にわたる合計によって決定されて、２乗されたサイクル時間と掛算されるとよい。

本発明の一つの発展形態は、構成素子分散値と、期待される生産時間の合計からの最大偏差とからなる重み付けされた合計が最小化される。

整数線形計画法のための入力データとして、前記インフラストラクチャを記述する次のデータが使用される：
− 実装ラインの数、
− 構成グループの数、
− 構成グループ種類の数、
− 構成素子種類の数、
− 構成グループ種類ごとの実装すべき構成素子種類の集合、
− 実装ラインごとの生産時間制限値、
− 構成グループ種類の期待される個数に関する確率分布。

各実装ラインにおける各構成グループ種類についての総生産時間が、
− 期待される個数、
− 期待すべきオーダーの数、
− ロットサイズ、
− 変更時間、
− 構成グループおよび実装ラインごとの個別生産時間、
− 実装ラインの最小サイクル時間、
− 実装ラインの利用容量、
から算定可能である。

線形計画法は、次のステップによって解かれる整数線形プログラムを用いて設定可能である。即ち、
ａ） 生産ラインへの構成グループの割り当てを表す１つの最初の現在解を求め、
ｂ） １つの現在解に基づいて構成グループの選択された集合を実装ラインへ割り当て、
ｃ） 最適化プログラム又は整数線形計画法に基づく標準ソルバーを用いて新たな割り当てを算定する。

上述のステップは反復して実行され、予め定められた制限時間又は解の品質に到達したときにプログラム停止が行われる。

特許請求されている方法は、最適化法の第１の目的関数を定義する一方で、各期待値からの偏差に関してできるだけ最善の結果に収束すべきである第２の目的関数により付加的に補足可能である。第１の目的関数は構成素子分散値である。

使用者は、２つの目的関数を用いる全体的最適化の場合に、第１の目的関数に大きい重み付けをするべきか、それとも第２の目的関数に大きい重み付けをするべきかを手動で設定することができる。

本発明の他の観点によれば、複数の構成グループを、当該構成グループに複数の構成素子を実装するための複数の実装ラインへ割り当てるための装置が提供される。本装置は、
− 構成素子を実装すべき構成グループの各構成グループ種類および各実装ラインについて、各実装ラインにおける構成グループ種類の各サイクル時間と構成グループ種類ごとに期待される生産すべき個数とを考慮して、期待される生産時間を求めるためのユニットを有しており、実際の生産すべき個数が予め定め得る確率分布に従って発生可能であり、１つのラインに割り当てられる構成グループの集合について、これらの期待される（総）生産時間の合計が、各実装ラインの最大の時間稼働容量を超えてはならず、実装ラインへの構成グループの実行可能な割り当てが、既存のインフラストラクチャおよび／又は使用者定義の設定によって制限可能であり、かつ実装ラインごとに、予め与えられる最大の時間稼働容量において最小の構成素子分散値を達成するべく、構成素子分散値が、複数の実装ラインにおいて必要とされる構成素子種類の数の合計として規定可能であり、
− 与えられる設定のもとで整数線形計画法により複数の実装ラインへの複数の構成グループの割り当てを算定するためのユニットを有しており、複数の個数に関する確率分布から結果として生じる実装ラインごとの期待される生産時間の合計に関する確率分布について、これらの結果として生じる確率分布の各期待値からの偏差が予め与え得る最大閾値によって制限可能であるように、前記割り当ての算定が実施される。

本装置は、上述の方法を実施するための手段および／又はユニットもしくは装置および／又はモジュールを含み、これらは、それぞれハードウェアおよび／又はファームウェアおよび／又はソフトウェアにより、もしくはコンピュータプログラムもしくはコンピュータプログラム製品として具体化することができる。

本装置は、上述の方法と同様に、相応に実施形態もしくは発展形態をとることができる。

本発明の他の観点は、複数の構成グループに複数の構成素子を実装するための製造又は組立ライン装置を提供する。製造又は組立ラインへの複数の構成グループの割り当てが前述の方法に従って決定可能である。

この製造ライン装置又は組立ライン装置は１つの設備の一部であってよい。

その設備の特徴をなしているのは、とりわけ次の設備種類である。これに関する例は、
− 自動化設備、
− 製造もしくは生産設備、
− 洗浄設備、
− 水処理設備、
− 機器又は機械、
− 流体機械、
− 発電設備、
− 電力供給網、
− 通信網、
− 医用装置もしくは機器、
− 病院情報システム、
である。

本発明の他の観点は、コンピュータプログラム（製品）が上述の装置又はその装置の手段において実行される際に上述の方法を実施するための手段を有するコンピュータプログラム製品もしくはコンピュータプログラムである。コンピュータプログラム又はコンピュータプログラム製品は、コンピュータ読取可能な媒体に記憶することができる。コンピュータプログラム又はコンピュータプログラム製品は、通常のプログラミング言語（Ｃ＋＋，Ｊａｖａ（登録商標））で作成することができる。処理装置は、適切な入力手段、出力手段および記憶手段を有する市販のコンピュータ又はサーバを含み得る。これらの処理装置は、本発明による装置又は該装置の手段に組み込むことができる。

以下において図面を参照して実施例を説明することにより、本発明の他の利点、詳細および発展形態を明らかにする。

図１は構成グループ製造のための複数の実装ラインを有する第１の模範的な組立設備を示す。 図２は構成グループライン割り当てのためのライン１および２の個数／生産時間に関する確率分布図を示す。 図３は構成グループライン割り当てのための本発明による最適化方法に基づく確率分布図を示す。

図１は、構成グループ製造のための複数の実装ラインＢＬ1〜ＢＬ２を有する第１の模範的な組立工場もしくは組立設備を示す。１つの実装ラインＢＬ1〜ＢＬ２は、通常複数の自動実装機ＢＡ１〜ＢＡ６からなり、これらの自動実装機は、それぞれ実装すべき構成グループもしくはプリント基板ＬＰ１〜ＬＰ６を搬送するための搬送システムＦＢ１〜ＦＢ２（例えばコンベヤベルト）によって互いに接続されている。複数の構成グループＬＰ１〜ＬＰ６に実装すべき複数の構成素子もしくは構成部品Ｂ１〜Ｂ６は、通常、複数のコンベヤＦ１〜Ｆ１１を介して供給される。その際に、１つの実装ラインＢＬ１，ＢＬ２に、構成グループ種類の集合Ｒからの１つの特定の構成グループ種類ｒ（ｒ∈Ｒ）の複数の構成グループＬＰ１〜ＬＰ６を割り当てることができる。

例えば、複数の基板に複数の構成素子Ｂ１〜Ｂ６を実装するための複数の自動実装機ＢＡ１〜ＢＡ６では、それらの基板のための搬送経路の横に、複数の構成素子Ｂ１〜Ｂ６のための複数の供給装置Ｆ１〜Ｆ１１が配置されている。位置決めシステムによって移動可能な自動実装機ＢＡ１〜ＢＡ６の実装ヘッドは、構成素子Ｂ１〜Ｂ６を供給装置Ｆ１〜Ｆ１１から取り出し、構成素子Ｂ１〜Ｂ６を、実装されるべき基板が用意されている自動実装機の実装領域に移動させ、構成素子Ｂ１〜Ｂ６を基板上に置く。構成素子Ｂ１〜Ｂ６を供給するために、例えば、ベルトに載せられた構成素子の搬送および供給に適したいわゆるベルトフィーダが使用される。ベルトフィーダはポケット状の凹部内に詰め込まれた構成素子を、取り出し位置まで搬送し、この取り出し位置で当該構成素子が実装ヘッドによってベルトポケットから取り出される。空のベルトは適切な個所で供給装置Ｆ１〜Ｆ１１を去る。

電子部品製造分野の多くの設備において、製造すべきプリント基板もしくは構成グループは、中期的には、各設備のＳＭＴ実装ライン（表面実装技術）に割り当てられる。技術的な制約に基づいて、すべての実装ラインですべてのプリント基板を製造することができるとは限らない。多くの部分でプリント基板は、ラインにおいて異なる生産時間を有することも多い。さらに、実装ラインの最大生産時間能力が超過されてはならない。

前記割り当ての際には次の目標が追求される：
変更時間を低減するために、ラインにおける装置設備ファミリの数をできるだけ少なくすべきである。
・ 必要とする装置設備装備（例えばコンベヤ）は、できるだけ少なくすべきである。
・ 総生産時間は、できるだけ最小であるべきである。

これらの目標は、通常、１つのラインの複数のプリント基板の構成素子のカバー範囲をできるだけ多くするよう努めることによって、もしくは複数のラインの構成素子分散値の合計を最小化することによって達成しようと努力される。１つのラインの構成素子分散値により、当該ラインにおいて使用される構成素子種類の数が表される。

以下において、この問題設定のためのＩＰモデル（ＩＰは、Integer ProgrammierungもしくはInteger Programm（整数計画法）又はganzzahliges Optimierungsmodell（整数最適化モデル）を表す。）を説明する。数理最適化法として、この問題のためのＩＰモデル（ＩＰは、Integer ProgrammierungもしくはInteger Programm（整数計画法）又はganzzahliges Optimierungsmodell（整数最適化モデル）を使用することができる。このようなＩＰ解法は次の利点を有する：
・ グローバルな最適化アプローチ、
・ 容易に拡張可能、
・ 実際に広く普及しており有効性が実証されている非常に良好な市販の標準ソルバー（例えば、Ｃｐｌｅｘ、Ｇｕｒｏｂｉ）、
・ 標準ソルバーは絶えず改善されるので、将来はインスタンスをさらに高速で解くことが期待できる。

さらに、ＩＰに基づく方法が提案されており、この方法により、そのために非常に良好な結果品質を有する解を比較的短い実行時間で見つけることができる。

以下に示すＩＰモデルは、実行可能な定式化の例示にすぎず、本発明による方法に対して制限を加えるものではない。

Ｌは全ての（実装）ラインの集合、Ｒは全ての構成グループ種類の集合、Ｒ_ｌはラインｌにおいて実装可能な構成グループ種類の集合であるとする。さらに、Ｃは構成素子種類ｃの集合を表し、Ｒ_ｃは構成素子種類ｃを有する構成グループ種類の集合を表す。

次のパラメータを使用する：
ＴｉｍｅＬｉｍｉｔ_ｌ 実装ラインｌにおける生産時間制限値、
ｗ_Ｓ 構成素子分散値を最小化するための重み付け係数、
ｗ_Ｖ 最大生産時間分散値を最小化するための重み付け係数。

次は２値変数である：
Ａｓｓｉｇｎ_ｒ，ｌ 実装ラインｌへの構成グループｒの割り当て、
Ｓｅｔｕｐ_ｃ，ｌ ラインｌにおける構成素子ｃの使用（使用の場合にこれは値１を取り、それ以外の場合には値０を取る）。

計画期間内では、複数のＳＭＴラインにおいて構成グループ集合に異なる構成素子種類の複数の構成素子を実装しなければならない。各構成グループ種類ｒについて、それに幾つのオーダーが与えられるか推定される。１つの構成グループ種類の実際の生産すべき個数は、例えば過去データ又は予測から求め得る確率分布に従って発生される。異なる（実装）ラインにおけるサイクル時間と、推定装置設備変更時間と、ライン利用容量とを用いて、構成グループ種類およびラインごとに、入力として使用できる総生産時間に関する確率分布を求めることができる。さらに、計画期間において、ラインごとに最大生産時間が設定される。図示されていないユニットにより、構成グループごとの期待される生産時間を求めることができる。このようなユニットは、１つの自動実装機に、例えば実装ラインＢＬ１のＢＡ１に、組み込まれているとよい。実装ラインへの構成グループの割り当てを算定するための図示されていないユニットも、このような１つの自動実装機に組み込まれているとよい。

これらのユニットは、自動実装機から分離されている、自動実装機を制御するコンピュータで実行可能にされていてもよいし、あるいはそのコンピュータに組み込まれていてもよい。

さらに、目的は、個々のラインの生産時間変動を制限すること、又は当該変動をできるだけ最小化することにある。

実施例では、ＩＰモデルにおいて次の他のパラメータが使用される：
ｎ_ｒ ある特定の時間内での構成グループ種類ｒの生産すべき個数に関する独立の確率変数、
ｃ_ｒ 構成グループ種類ｒの任意の個数を生産する際の固定の生産時間、
ｔ_ｒ,ｌ ラインｌにおいて構成グループ種類ｒの１つの構成グループを生産するためのサイクル時間、
ＶａｒＭａｘ_ｌ 実装ラインｌにおける最大生産時間分散値、
ｐ 複数のラインにおける生産時間分散値の最大許容差のパーセント値。

連続的な補助変数：
Ｖ_Ｍａｘ 全てのラインにおける最大生産時間分散値、
Ｖ_Ｍｉｎ 全てのラインにおける最小生産時間分散値。

１つのラインにおける１つの構成グループの生産時間がｔ_ｒ,ｌｎ_ｒ＋ｃ_ｒであると仮定する。但し、ｃ_ｒは一定成分であり、この成分には、例えば装置設備変更時間が含まれている。１つのラインにおける１つの構成グループの生産時間は、独立の確率変数でもある。

それゆえ、１つのラインｌに割り当てられている構成グループ種類ｒの集合Ｒ_ｌ’⊆Ｒ_ｌについては、生産時間が確率変数でもあり、その生産時間の分散値に関して、

が当てはまる。

ＩＰモデルでは一般に制約条件が使用される。ＩＰモデルの次の制約条件は、ラインにおける期待される生産時間を制限し、解の許容性を保証する。

次の制約条件、即ち

は、構成素子を実装可能である実装ラインにのみ構成グループを割り当て得ることを保証する。

次の制約条件、即ち

によって、各構成グループ種類が厳密に１つの実装ラインに割り当てられる。

さらに、ＩＰモデルでは、１つの実装ラインの生産時間分散値を次のように表すことができる：

ラインにおける最大生産時間分散値を制限するために次の変形例が実行可能である：

（１）固定して予め与えられたパラメータＶａｒＭａｘ_ｌによって、全てのラインｌについての生産時間分散値を、

なる付加的な制約条件により制限することができる。

（２）補助変数Ｖｍａｘと付加的な制約条件を用いて、

なる式でＶ_ｍａｘを最小化することによって、ラインの最大生産時間分散値をできるだけ最小化することを達成することができる。その際に、Ｖ_ｍａｘを、重み付け係数ｗ_ＶにてＩＰモデルの目的関数の中に取り込むとよい。

（３）他のオプションは、予め与えられたパーセント値ｐについて、ラインの最大分散値と最小分散値との偏差を制限することにある。

さらに、Ｖ_ｍｉｎは他の補助変数である。付加的な制約条件は、

および

である。

さらに、上記変形例（１）および（３）の上述の制約条件により、それぞれ特許文献３、特許文献４、特許文献５、特許文献６からのＩＰモデルを拡張することができる。上述の特許文献から公知の方法は、複数の構成グループを複数の実装ラインへ割り当てるためのＭＩＰによる最適化方法の例である。

従って、これらのＩＰモデルにおいても、生産時間変動を制限することができる。上記変形例（２）により、これらのＩＰモデルは、その新たな制約条件に加えて、選択された重み付けにてＶ_ｍａｘを目的関数の中に取り込むことによって、同様に拡張可能である。

整数線形計画法は次のステップによって解くことができる：
ａ）初期解もしくは最初の現在解を求め、
ｂ）現在解に基づいて構成グループＬＰ１〜Ｌ６の選択された集合を実装ラインＢＬ１〜ＢＬ２へ割り当て、
ｃ）整数線形計画法に基づく最適計画法又は標準ソルバーによる新たな割り当てを算定する。

それらのステップは反復して実行され、予め定められた制限時間又は結果品質に到達したときに、プログラム停止が行われる。

拡張されたＩＰ定式化の次の変形例が実行可能である：

変形例（１）に対するＩＰ定式化：

但し、

なる条件が存在する。

変形例（２）および（３）に対するＩＰ定式化：

但し、

の条件が存在する。

以下において簡単化された最適化処理の例を説明する。この例は、生産時間変動の制限により構成素子分散値を最小化することに関して、上述の複雑に示された最適化プロセスを理解のために簡単化して説明しようとするものであって、この簡単化された例に限定しようとするものではない。小さいインスタンスを有する以下に説明する簡単な例を大きなインスタンスもしくは複雑な問題設定に転用する場合に、既述の標準ソルバーを用いて完全に又は最適化した形で複雑な問題設定の解を得ることができるようにするためには、適用すべき制約条件もしくは使用者定義の設定によるＩＰモデルにおけるパラメータの良好もしくは正確な選択が重要である。

次の例では、１つの構成グループ種類について期待される個数がｎである場合に、実際に製造すべきもしくは実装すべき個数が次の確率分布に従って変動することを仮定する。
・ ０．８の確率で、期待される値ｎを仮定する。
・ それぞれ０．１の確率で、値ｎの上方もしくは下方に向けて１０％の偏差を仮定する。

６個の異なる構成グループ種類が２つのラインＢＬ１およびＢＬ２に割り当てられるものとする。期待される個数ｎは：

それらの構成グループ種類には構成素子種類ｃ１〜ｃ９が次の表に従って実装されるものとする。

割り当ては、２つのラインが等しく能力を活用するように、即ち等しい期待される生産時間を有するように実施されるべきである。サイクル時間は、全ての構成グループ種類について１分であり、従って、例えば個数が１０００である場合に生産時間は１０００分である。

目標基準が構成素子分散値の最小化である場合には、ｒ１およびｒ２が実装ラインＢＬ１へ割り当てられ、構成グループｒ３〜ｒ６がラインＢＬ２へ割り当てられる。というのは、それによりラインＢＬ１では構成素子種類ｃ１〜ｃ３が必要とされ、ラインＢＬ２では構成素子種類ｃ４〜ｃ９が必要とされ、全体として、９なる最小の構成素子分散値が生じる。それにより、次の表および図２に示されているように、２つのラインＢＬ１およびＢＬ２において次の個数／生産時間の確率分布Ｗ１およびＷ２が生じる。

ラインＢＬ１においては、大きい個数を有する２つの構成グループ種類によって、個数／生産時間について大きな変動幅が生じる。

ラインＢＬ１における生産時間に関する分散値は最大であり、かつ
2*(400²*0.01+200²*0.16) = 16000
である。

付加的に、生産時間に関する分散値を、（１）において説明した制約条件によって、全てのラインにおいて１２０００に制限する場合には、構成グループ種類ｒ１，ｒ３およびｒ４がラインＢＬ１へ割り当てられ、構成グループ種類ｒ２，ｒ５およびｒ６がラインＢＬ２へ割り当てられる。

それにより、次の表および図３に示されているように、２つのラインＢＬ１およびＢＬ２において次の個数／生産時間の確率分布Ｗ１およびＷ２が生じる。

生産時間に関する最大分散値は、この第２の割り当ての場合に、２５％だけ減少して、
2*(400²*0.001+300²*0.016+200²*0.074+100²*0.144)= 12000
となる。

中央部および縁部において、第２の構成グループライン割り当ての場合のラインＢＬ１およびラインＢＬ２に関する分布値が、第１の構成グループライン割り当ての場合のラインＢＬ１に関する分布値よりも低い。それどころか縁部では確率が１０分の１しかない。

第２の割り当ての場合には、ラインＢＬ１において構成素子種類ｃ１〜ｃ２およびｃ４〜ｃ６が必要とされ、ラインＢＬ２において構成素子種類ｃ２〜ｃ３およびｃ７〜ｃ９が必要とされる。従って、全体として、１０なる構成素子分散値が生じる。

第１の割り当てに比べて、ラインにおいて必要とされる構成素子種類の合計は９から１０へ増しただけであるのに対して、ラインにおける生産時間に関する最大分散値は明らかに１６０００から１２０００に減少した。

適切にパラメータを選択するならば、狙いどおりに上述の第２の構成グループライン割り当てを求めることができる。最適化のステップは反復して実行され、予め定められた制限時間又は予め設定可能な結果品質に到達したときに、プログラム停止が行われるとよい。

本発明の詳細を好ましい実施例に基づいて詳しく図示および説明したが、本発明は開示された例に限定されておらず、当業者が本発明の保護範囲を逸脱することなくこれらの例から他の変形例を導き出すことができる。

Ｂ１〜Ｂ６ 構成素子
ＢＡ１〜ＢＡ６ 自動実装機
ＢＬ１〜ＢＬ２ 実装ライン
Ｆ１〜Ｆ１２ コンベヤ（供給装置）
ＦＢ１〜ＦＢ２ 搬送システム
ＬＰ１〜ＬＰ６ 構成グループ

Claims (18)

1. 実装ライン（ＢＬ１〜ＢＬ２）ごとに予め与えられた最大の時間稼働容量に対して最小の構成素子分散値を達成するために、複数の構成グループ（ＬＰ１〜ＬＰ６）を、当該構成グループ（ＬＰ１〜ＬＰ６）に複数の構成素子（Ｂ１〜Ｂ６）を実装するための複数の実装ライン（ＢＬ１〜ＢＬ６）へ割り当てる方法であって、
   構成素子分散値が複数の実装ライン（ＢＬ１〜ＢＬ２）において必要とされる構成素子種類の数の合計として定められ、
   構成素子を実装すべき構成グループ（ＬＰ１〜ＬＰ６）の各構成グループ種類および各実装ライン（ＢＬ１〜ＢＬ２）について、各実装ライン（ＢＬ１〜ＢＬ２）における構成グループ種類の各サイクル時間と、各変更時間と、各ライン利用容量と、構成グループ種類ごとに期待される生産すべき個数とを考慮して、期待される生産時間が求められ、
   実際の生産すべき個数が予め定め得る確率分布に従って発生し、
   １つのライン（ＢＬ１〜ＢＬ２）に割り当てられる構成グループ（ＬＰ１〜ＬＰ６）の集合について、これらの期待される総生産時間の合計が、各実装ライン（ＢＬ１〜ＢＬ２）の最大の時間稼働容量を超えてはならず、
   複数の実装ライン（ＢＬ１〜ＢＬ２）への複数の構成グループ（ＬＰ１〜ＬＰ６）の実行可能な割り当てが、既存のインフラストラクチャ又は使用者定義の設定によって制限されており、
   複数の個数に関する前記確率分布から結果として生じる、実装ラインごとの期待される生産時間の合計に関する確率分布について、これらの結果として生じる確率分布の各期待値からの偏差が予め与え得る最大閾値によって制限されるように、前記割り当てが実施され、
   複数の実装ライン（ＢＬ１〜ＢＬ１）への複数の構成グループ（ＬＰ１〜ＬＰ６）の割り当てが、与えられた設定のもとで整数線形計画法により算定される、方法。
2. 複数の実装ライン（ＢＬ１−ＢＬ１）の期待される生産時間の合計が、整数線形計画法により最小化される、請求項１記載の方法。
3. 結果として生じる確率分布の期待値からの前記偏差が類似した又は等しい値を取ることを特徴とする請求項１又は２記載の方法。
4. １つの実装ラインの期待される生産時間の合計からの偏差がその分散値として表されることを特徴とする請求項１〜３の１つに記載の方法。
5. 構成素子分散値と期待される生産時間の合計からの最大偏差とからなる重み付けされた合計が最小化されることを特徴とする請求項１〜４の１つに記載の方法。
6. 使用者によって予め与えられた構成グループ（ＬＰ１〜ＬＰ６）の集合が同一の実装ライン（ＢＬ１〜ＢＬ２）に割り当てられる、請求項１〜５の１つに記載の方法。
7. 整数線形計画法のための入力データとして、前記インフラストラクチャを記述する次のデータ、即ち、
   − 実装ライン（ＢＬ１〜ＢＬ２）の数、
   − 構成グループ（ＬＰ１〜ＬＰ６）の数、
   − 構成グループ種類の数、
   − 構成素子種類の数、
   − 構成グループ種類ごとの実装すべき構成素子種類の集合、
   − 実装ライン（ＢＬ１〜ＢＬ２）ごとの生産時間制限値、
   − 構成グループ種類の期待される個数についての確率分布、
   が使用される、請求項１〜６の１つに記載の方法。
8. 各実装ライン（ＢＬ１〜ＢＬ２）における各構成グループ種類についての総生産時間が、
   − 期待されるオーダーの数、
   − ロットサイズ、
   − 変更時間、
   − 構成グループ（ＬＰ１〜ＬＰ６）および実装ライン（ＢＬ１〜ＢＬ１）ごとの個別生産時間、
   − 実装ライン（ＢＬ１〜ＢＬ１）の最小サイクル時間、
   − 実装ライン（ＢＬ１〜ＢＬ２）の利用容量、
   から算定される、請求項１〜７の１つに記載の方法。
9. 線形計画法が、次のステップ、即ち、
   ａ） 生産ラインへの構成グループの割り当てを表す最初の現在解を求め、
   ｂ） 現在解に基づいて実装ライン（ＢＬ１〜ＢＬ２）へ構成グループ（ＬＰ１〜ＬＰ６）の選択された集合を割り当て、
   ｃ） 整数線形計画法に基づく最適化プログラム又は標準ソルバーにより新たな割り当てを算定する、
   ステップによって解かれる整数線形プログラムにより設定されることを特徴とする請求項１〜８の１つに記載の方法。
10. ステップが反復して実行され、予め定められた制限時間又は解の品質に到達したときにプログラム停止が行われることを特徴とする請求項１〜９の１つに記載の方法。
11. 複数の構成グループ（ＬＰ１〜ＬＰ６）を、当該構成グループ（ＬＰ１〜ＬＰ６）に複数の構成素子（Ｂ１〜Ｂ６）を実装するための複数の実装ライン（ＢＬ１〜ＢＬ２）へ割り当てるための装置であって、
    − 構成素子を実装すべき構成グループ（ＬＰ１〜ＬＰ６）の各構成グループ種類および各実装ライン（ＢＬ１〜ＢＬ２）について、各実装ライン（ＢＬ１〜ＢＬ２）における構成グループ種類の各サイクル時間と、構成グループ種類ごとに期待される生産すべき個数とを考慮して、期待される生産時間を求めるためのユニットを有しており、実際の生産すべき個数が予め定め得る確率分布に従って発生可能であり、１つのライン（ＢＬ１〜ＢＬ２）に割り当てられる構成グループ（ＬＰ１〜ＬＰ６）の集合について、これらの期待される総生産時間の合計が、各実装ライン（ＢＬ１〜ＢＬ２）の最大の時間稼働容量を超えてはならず、実装ライン（ＢＬ１〜ＢＬ２）への構成グループ（ＬＰ１〜ＬＰ６）の実行可能な割り当てが、既存のインフラストラクチャおよび／又は使用者定義の設定によって制限可能であり、かつ実装ライン（ＢＬ１〜ＢＬ２）ごとに、予め与えられる最大の時間稼働容量において最小の構成素子分散値を達成するために、構成素子分散値が、複数の実装ライン（ＢＬ１〜ＢＬ２）において必要とされる構成素子種類の数の合計として規定可能であり、
    − 与えられる設定のもとで整数線形計画法により複数の実装ライン（ＢＬ１〜ＢＬ２）への複数の構成グループ（ＬＰ１〜ＬＰ６）の割り当てを算定するためのユニットを有しており、複数の個数に関する前記確率分布から結果として生じる実装ラインごとの期待される生産時間の合計に関する確率分布について、これらの結果として生じる確率分布の各期待値からの偏差が予め与え得る最大閾値によって制限可能であるように、前記割り当ての算定が実施される、装置。
12. 結果として生じる確率分布の期待値からの前記偏差が類似した又は等しい値を取り得ることを特徴とする請求項１１記載の装置。
13. １つの実装ラインの期待される生産時間の合計からの偏差がその生産時間の分散値として表されることを特徴とする請求項１１〜１２の１つに記載の装置。
14. 構成素子分散値と、期待される生産時間の合計からの最大の偏差とからなる重み付けされた合計が最小化可能であることを特徴とする請求項１１〜１３の１つに記載の装置。
15. 使用者によって予め与えられた構成グループ（ＬＰ１〜ＬＰ６）の集合が同一の実装ライン（ＢＬ１〜ＢＬ２）へ割り当て可能である、請求項１１〜１４の１つに記載の装置。
16. 製造又は組立ラインへの複数の構成グループ（ＬＰ１〜ＬＰ６）の割り当てが請求項１〜１０の１つに記載の方法に従って決定可能である、複数の構成グループ（ＬＰ１〜ＬＰ６）に複数の構成素子（Ｂ１〜Ｂ６）を実装するための製造又は組立ライン（ＢＬ１〜ＢＬ２）。
17. コンピュータプログラムが、請求項１１〜１５の１つに記載の１つの装置上又は装置の手段内で実行される際に請求項１〜１０の１つに記載の方法を実施するための手段を有するコンピュータプログラム。
18. 命令を含んでおり、請求項１１〜１５の１つに記載の１つの適切な処理装置又は前記装置、又は前記装置の１つ又は複数の手段において実行される際に、前記コンピュータ又は前記装置又は前記手段に、請求項１〜１０の１つに記載の方法を実施させるコンピュータ読取可能な媒体。