JPH0944471A - 組み合わせ最適化問題の解法および生産ラインにおける生産計画決定装置 - Google Patents

Abstract

(57)【要約】 【構成】 全ての組み合わせの集合の中の一つである現
行解を、設定された評価基準と制約とに基づき、その集
合の中の別の一つである近傍解と置換することで更新す
る過程を有する組み合わせ最適化問題の解法である。そ
の現行解と近傍解の前記制約の充足程度に対応する第１
評価関数が相等しくない場合は、現行解と近傍解とを第
１評価関数に基づき評価することで、解を更新するか否
かを判断する。その現行解の第１評価関数と近傍解の第
１評価関数とが相等しい場合は、現行解と近傍解とを前
記評価基準の充足程度に対応する第２評価関数に基づき
評価することで、解を更新するか否かを判断する。 【効果】 制約の緩い問題はもとより、制約の厳しい問
題であっても、実行可能で且つ評価の良好な解を導出す
ることができる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、例えば生産計画の
最適化や生産設備の配置の最適化を図る場合等におい
て、考えられる多数の組み合わせの中から、設定した評
価関数を最小化または最大化する組み合わせを探し出す
組み合わせ最適化問題の解決方法と、その解決方法を利
用した生産ラインにおける生産計画決定装置に関する。

【０００２】

【従来の技術】複数種類の製品を生産ラインにおいてロ
ット単位で生産するに際し、その各ロットの生産順序を
決定するような場合、その生産順序として多数の組み合
わせが考えられ、その多数の組み合わせの中から、設定
されたある評価基準を最も良く満たす組み合わせ、すな
わち評価関数を最適にする組み合わせであって、且つ、
設定された制約を充足するものを最適解として導出する
ため、組み合わせ最適化問題の解法が用いられている。

【０００３】そのような組み合わせ最適化問題の解法と
しては、考えられる全ての組み合わせを列挙して最適解
を導出する列挙的手法、一定のルール等を用いてただ１
つの解を導出する発見的手法、考えられる全ての組み合
わせの集合である解空間を繰り返し探索して最適解を導
出する探索的手法等がある。そのような手法の中で、組
み合わせの数が非常に多い大規模な問題において良好な
解を短時間で導出する上では、探索的手法が他の手法に
比べて優れている。

【０００４】その探索的手法の代表的なものとして、シ
ミュレーテッド・アニーリング法がある。そのシミュレ
ーテッド・アニーリング法は、考えられる全ての組み合
わせの集合である解空間の中の一つの解をｘ、その解ｘ
の評価関数をｆ（ｘ）として、設定された評価関数ｆ
（ｘ）を最小化あるいは最大化する最適解を解空間の中
から導出するために、温度と呼ばれるパラメータの値を
除々に下げながら、その解空間の中を所定の確率で解の
改悪を許容しつつ探索する手法である。なお、評価関数
ｆ（ｘ）を最大化する問題の場合、評価関数ｆ（ｘ）に
−１を乗じたものを最小化することで最適解を導出する
ことができる。

【０００５】従来のシミュレーテッド・アニーリング法
により、その評価関数ｆ（ｘ）を最小化する最適解ｘを
導出する場合、まず、解空間の中の適当な解（現行解）
ｘに注目し、その現行解ｘの近傍の解ｙを無作為に選択
する。次に、その近傍解ｙの評価関数ｆ（ｙ）が設定さ
れた制約を充足するか否かをチェックし、充足しない場
合は別の近傍解ｙを選択し、充足する場合は両解ｘ、ｙ
の評価関数ｆ（ｘ）、ｆ（ｙ）の値を比較する。その近
傍解ｙの評価関数ｆ（ｙ）の方が現行解ｘの評価関数ｆ
（ｘ）よりも小さければ、現行解ｘの内容を近傍解ｙの
内容と置換することで、現行解ｘの内容を更新する。ま
た、その近傍解ｙの評価関数ｆ（ｙ）の方が現行解ｘの
評価関数ｆ（ｘ）よりも大きい場合であっても、ある確
率に従って現行解ｘの内容を近傍解ｙの内容と置換する
ことで、現行解ｘの内容を更新して解の改悪を許容す
る。この解の改悪を許す確率は受理確率と呼ばれ、両解
ｘ、ｙの評価関数値の差ｆ（ｘ）−ｆ（ｙ）が大きいほ
ど、また、上記温度の値が低いほど、小さくなるように
設定される。このような受理確率により解の改悪を許し
て探索することにより、解空間を大域的に探索し、局所
解に陥ることなく大域的な最適解を導出することができ
る。探索は十分に高い温度から開始され、この解の更新
を繰り返し行ないながら除々に温度を下げていき、予め
設定された終了温度になると終了される。その過程にお
いて、それまでに探索された解の中で最良の解が暫定解
として保持され、探索終了時の暫定解がシミュレーテッ
ド・アニーリング法による解となる。

【０００６】図５は、従来のシミュレーテッド・アニー
リング法を実行する演算装置の機能ブロック図を示し、
１０１は、探索の出発点となる初期解を解空間の中から
ランダムに若しくは何らかのルールを用いて１つ生成す
る初期解生成部である。１０２は、現在探索の対象とし
て解空間において注目している現行解を保持する現行解
保持部である。１０３は、その現行解保持部１０２に保
持されている現行解を、ランダムに若しくは何らかのル
ールを用いて一部変更して近傍解を生成する近傍解生成
部であり、例えば、現行解が（Ａ、Ｂ、Ｃ、Ｄ）の様に
４つの要素の順列で表現されている場合、現行解中の２
つの要素をランダム選択し交換する等して、現行解から
その近傍の解を（Ａ、Ｃ、Ｂ、Ｄ）等の様に生成するこ
とができる。１０４は、その近傍解生成部１０３で生成
された近傍解が設定された制約を満たすか否かを調べる
制約チェック部である。１０５は、制約チェック部１０
４で制約を満たすと判定された近傍解を保持しておく近
傍解保持部である。１０６は、解の評価関数値を計算す
る評価関数値算出部である。１０７は、近傍解と現行解
の評価関数値を比較して、近傍解を受理してそれを現行
解とするか否かを判定する近傍解受理判定部である。１
０８は、温度パラメータを管理する温度管理部であり、
温度パラメータを比較的高い初期温度から低い終了温度
まで少しずつ減少させる。１０９は、現行解と暫定解の
評価関数値を比較して暫定解を変更するか否かを判定す
る暫定解更新判定部である。１１０は、解の探索中にお
ける最良の解を暫定解として保持する暫定解保持部であ
る。

【０００７】図６、図７に示すフローチャートに基づ
き、上記従来の演算装置により評価関数を最小化する組
み合わせを探し出す手順を説明する。

【０００８】まず、初期解生成部１０１を用いて解空間
に含まれる初期解を生成し、この初期解を現行解保持部
１０２において現行解ｘとして保持し、暫定解保持部１
１０において暫定解ｚとして保持することで、現行解ｘ
および暫定解ｚを初期化する（ステップ２０１）。ま
た、温度管理部１０８により温度パラメータＴを初期化
する（ステップ２０２）。

【０００９】次に、近傍解生成部１０３を用いて現行解
ｘからその近傍の解ｙを生成し（ステップ２０３）、そ
の生成した近傍解ｙが設定された制約を満たすか否かを
制約チェック部１０４で判定する（ステップ２０４）。
その制約を満たすならば、近傍解保持部１０５により近
傍解ｙを保持し、評価関数値算出部１０６で現行解ｘ及
び近傍解ｙの評価関数ｆ（ｘ）、ｆ（ｙ）を算出し、近
傍解受理判定部１０７を用いて近傍解ｙを受理するか否
かを判定する（ステップ２０５）。

【００１０】図７のフローチャートは、その近傍解受理
判定部１０７において近傍解ｙを受理するか否かの判定
手順を示す。まず、近傍解ｙの評価関数ｆ（ｙ）が現行
解ｘの評価関数ｆ（ｘ）以下か否かを判定する（ステッ
プ３０１）。近傍解ｙの評価関数ｆ（ｙ）が現行解ｘの
評価関数ｆ（ｘ）以下であれば無条件に近傍解ｙを受理
すると判定する（ステップ３０２）。近傍解ｙの評価関
数ｆ（ｙ）が現行解ｘの評価関数ｆ（ｘ）を超える場
合、０以上１未満の一様乱数ｒｎｄを発生させ（ステッ
プ３０３）、受理確率α′を以下の式（１）により演算
する（ステップ３０４）。

【００１１】

【数１】

【００１２】次に、その乱数ｒｎｄが受理確率α′以下
か否かを判定し（ステップ３０５）、その乱数ｒｎｄが
受理確率α′以下であれば近傍解ｙを受理し（ステップ
３０２）、その乱数ｒｎｄが受理確率α′を超えている
場合は近傍解ｙを受理しない（ステップ３０６）。

【００１３】ステップ２０５において近傍解ｙを受理す
ると判定した場合、現行解保持部１０２に保持された現
行解ｘの内容を近傍解ｙの内容と置換することで、現行
解ｘの内容を更新する（ステップ２０６）。その現行解
ｘの内容を更新したならば、暫定解更新判定部１０９に
より、現行解ｘの評価関数ｆ（ｘ）が暫定解ｚの評価関
数ｆ（ｚ）未満か否かを判断する（ステップ２０７）。
現行解ｘの評価関数ｆ（ｘ）が暫定解ｚの評価関数ｆ
（ｚ）未満であれば、暫定解保持部１１０に保持された
暫定解ｚの内容を現行解ｘの内容と置換することで、暫
定解ｚの内容を更新する（ステップ２０８）。暫定解ｚ
の内容を更新した場合、ステップ２０４で近傍解ｙが制
約を満たさない場合、ステップ２０５で近傍解ｙを受理
しない場合、あるいは、ステップ２０７で現行解ｘの評
価関数ｆ（ｘ）が暫定解ｚの評価関数ｆ（ｚ）以上の場
合、温度管理部１０８で管理している温度パラメータＴ
の値を減少させ（ステップ２０９）、その温度パラメー
タＴが予め設定された終了温度に達しているか否かを判
定する（ステップ２１０）。その温度パラメータＴが終
了温度に達していない場合はステップ２０３へ戻り、終
了温度に達している場合は解の探索を終了する。探索が
終了した時点での暫定解ｚがシミュレーテッド・アニー
リング法による解となる。

【００１４】また、上記とは異なる従来のシミュレーテ
ッド・アニーリング法として、図６のフローチャートに
おけるステップ２０４における解が制約を満足している
か否かの判定を行わずに、制約を満足しないために実行
不能な解も探索の対象とする解法も提案されている（特
開平５‐１２０２５２号参照）。これは、問題本来の評
価関数と、解が満たすべき制約の充足度に対応する評価
関数との加重和を、解の評価関数として探索を行うもの
である。すなわち、制約の充足度に対応する解ｘの評価
関数をｆａ（ｘ）、問題本来の最小化を目的とした解ｘ
の評価関数をｆｂ（ｘ）、Ａ≧０、Ｂ≧０として、解ｘ
の評価関数ｆ（ｘ）は次式により表される。

【００１５】ｆ（ｘ）＝Ａｆａ（ｘ）＋Ｂｆｂ（ｘ）

【００１６】なお、制約の充足度に対応する評価関数ｆ
ａ（ｘ）は非負の値をとり、ｆａ（ｘ）＝０の場合は解
ｘが制約を全て満足していることを示し、値が大きくな
る程制約を満足していないことを示す。この評価関数ｆ
（ｘ）において、係数Ａが大きく設定され、制約の充足
度に対応する評価関数ｆａ（ｘ）の項の重みが大きくな
ると、探索された解は制約条件は満足するが、問題本来
の評価を最適化するとは限らない。また、係数Ｂが大き
く設定され、問題本来の評価関数ｆｂ（ｘ）の項の重み
が大きくなると、探索された解は問題本来の評価は良く
するが、制約条件を満足しない実行不能なものになる。
このことを考慮し、この解法では探索の過程で温度パラ
メータＴが大きい時は係数Ｂの値を大きく設定すること
で、実行不能ではあるが評価の良好な解を探索し、温度
パラメータＴが小さくなるにつれて係数Ａの値が大きく
なる様に調整し、最終的な探索領域の周辺で制約を満足
し且つ評価の良好な解を導出するものである。

【００１７】さらに異なる従来のシミュレーテッド・ア
ニーリング法として、解の探索過程においてオペレータ
による外部からの変更要求に応じて評価関数を随時変更
できる機能をもたせ、最初は実行可能性に重点をおいた
探索をし、途中で評価関数を修正することによって、後
半は解の評価に重点をおいた探索をすることが可能な解
法も提案されている（特開平６‐１９５０７号参照）。

【００１８】

【発明が解決しようとする課題】図５〜図７により説明
した従来の解の探索方法では、生成された近傍解が問題
の制約を満たす実行可能解である場合にのみ探索を続行
することができる。そのため、制約が厳しい問題では、
その制約を満たす実行可能解を生成することが困難で、
近傍解を生成しても実行可能な解であることが少なく、
解の更新ができないために十分に解空間を探索すること
ができないという問題がある。

【００１９】また、解の評価関数として、問題本来の評
価関数と制約の充足度に対応する評価関数との加重和を
とった従来技術では、近傍解が実行不能であっても探索
を進めることが可能である。しかし、探索の後半になっ
てから制約の充足度に対応する評価関数の項の重みを大
きくし、制約を満足するように解を更新するため、制約
が厳しい問題では実行可能な解が導出できなくなるおそ
れが大きい。

【００２０】また、オペレータが探索の過程で評価関数
を修正できる従来技術では、どのタイミングで修正すれ
ばよいのかを判定することが困難で、実行可能な解が導
出できなくなるおそれが大きい。

【００２１】本発明は、上記課題を解決することのでき
る組み合わせ最適化問題の解法と、この解法を利用した
生産ラインにおける生産計画決定装置とを提供すること
を目的とする。

【００２２】

【課題を解決するための手段】本発明の組み合わせ最適
化問題の解法は、全ての組み合わせの集合の中の一つで
ある現行解を、設定された評価基準と制約とに基づき、
その集合の中の別の一つである近傍解と置換することで
更新する過程において、解の前記制約の充足程度に対応
する第１評価関数と、解の前記評価基準の充足程度に対
応する第２評価関数とを設定し、その現行解の第１評価
関数と近傍解の第１評価関数とが相等しくない場合は、
現行解と近傍解とを第１評価関数に基づき評価すること
で、解を更新するか否かを判定し、その現行解の第１評
価関数と近傍解の第１評価関数とが相等しい場合は、そ
の現行解と近傍解とを第２評価関数に基づき評価するこ
とで、解を更新するか否かを判定することを特徴とす
る。

【００２３】その現行解と生成された近傍解が制約を満
足する場合は、現行解と近傍解の第１評価関数の値が相
等しくされるのが好ましい。

【００２４】本発明の生産ラインにおける生産計画決定
装置は、複数種類の製品を生産ラインにおいてロット単
位で生産するに際し、その各ロットの生産順序を決定す
る装置であって、全ての生産順序の組み合わせの集合の
中の一つである現行解の初期値を生成する手段と、その
現行解を保持する手段と、その保持された現行解を変更
して、前記集合の中の別の一つである近傍解を生成する
手段と、その生成された近傍解を保持する手段と、その
現行解と近傍解それぞれの制約の充足程度に対応する第
１評価関数値の演算手段と、その現行解と近傍解それぞ
れの評価基準の充足程度に対応する第２評価関数値の演
算手段と、その近傍解と現行解の第１評価関数値を比較
し、その近傍解を受理して現行解と置換して現行解を更
新するか否かを判定する第１近傍解受理判定手段と、そ
の現行解の第１評価関数と近傍解の第１評価関数とが相
等しい場合に、その近傍解と現行解の第２評価関数値を
比較し、その近傍解を受理して現行解と置換して現行解
を更新するか否かを判定する第２近傍解受理判定手段
と、全ての生産順序の組み合わせの集合の中の一つであ
る暫定解の初期値を生成する手段と、その更新された現
行解と暫定解の第１評価関数値を比較し、その現行解を
暫定解と置換して暫定解を更新するか否かを判定する第
１暫定解更新判定手段と、その現行解の第１評価関数と
暫定解の第１評価関数とが相等しい場合に、その現行解
と暫定解の第２評価関数値を比較し、その暫定解を現行
解と置換して暫定解を更新するか否かを判定する第２暫
定解更新判定手段と、探索を継続するか否かを判定する
手段と、その探索終了時点での暫定解を出力する手段と
を備えることを特徴とする。

【００２５】本発明による生産ラインにおける生産計画
決定装置において、現行解と生成された近傍解が制約を
満足する場合は、現行解と近傍解の第１評価関数の値が
相等しくされるのが好ましい。

【００２６】本発明による生産ラインにおける生産計画
決定装置において、各種類の製品それぞれの納期が制約
とされ、製品の在庫量が評価基準とされているのが好ま
しい。

【００２７】また、本発明の生産ラインにおける生産計
画決定装置において、各種類の製品は複数の生産ライン
において生産され、各ロットの生産を開始する時点にお
ける生産可能なラインの本数が制約とされているのが好
ましい。

【００２８】また、本発明の生産ラインにおける生産計
画決定装置において、各種類の製品は複数の生産ライン
において生産され、各生産ラインにおいて生産品種を変
更する際に作業者が必要とされ、各生産ラインにおける
品種変更時刻の重なり時に必要とされる作業者の人数が
制約とされているのが好ましい。

【００２９】さらに、本発明の生産ラインにおける生産
計画決定装置において、生産ラインにおける稼働可能時
間が制約とされているのが好ましい。

【００３０】

【発明の作用および効果】本発明による組み合わせ最適
化問題の解法によれば、生成された近傍解が制約を満足
するか否かを判定することなく、制約の充足程度に対応
する第１評価関数に基づき現行解と近傍解とを評価する
ことで解を更新するか否かを判定するので、制約が厳し
く近傍解が実行不可能であっても、実行可能性に基づき
解の探索を進めることができ、解空間を充分に探索でき
る。さらに、現行解と生成された近傍解が制約を満足す
る場合は、現行解と近傍解の第１評価関数の値が相等し
くなるようにすることで、現行解と近傍解とを本来の評
価基準の充足程度に対応する第２評価関数により評価し
て解を更新するか否かを判定できるので、解が実行可能
な場合には問題本来の評価関数に従って解の探索を進め
ることができる。すなわち、解が実行不能である時は実
行可能性を優先して解空間を探索し、解が実行可能であ
る時には問題本来の評価を最適化するように解空間を探
索することで、制約の緩い問題はもとより、制約の厳し
い問題であっても、実行可能で且つ評価の良好な解を導
出することができる。

【００３１】また、従来の解法であれば、制約が厳しく
解の探索ができない場合は実行不能であることしか知る
ことができなかったが、本発明の解法によれば、制約が
厳しく実行可能解が存在しない場合であっても、実行可
能性に応じた解を得て実行不能の程度を知ることがで
き、評価基準の見直し等に供することができる。

【００３２】本発明の生産ラインにおける生産計画決定
装置によれば、各ロットの生産順序を実行可能で且つ評
価が良好になるように決定できる。現行解と生成された
近傍解が制約を満足する場合に、現行解と近傍解の第１
評価関数の値を相等しくすることで、その生産順序の組
み合わせの集合である解空間を、解が実行不能である時
は実行可能性を優先して探索し、実行可能である時には
問題本来の評価を最適化するように探索するように、そ
の解の状況に応じて自動的に評価関数を設定できる。そ
の制約を製品の納期とし、その評価基準を製品の在庫量
とすることで、納期を満足し、且つ、在庫量を少なくす
ることができる。複数の生産ラインを用いて製品を生産
する場合、納期だけでなく、その生産ラインの数を制約
とすることで、使用する生産ラインの数に不足がないよ
うに、その生産順序を決定することができる。複数の生
産ラインを用いて製品を生産し、各生産ラインにおいて
生産品種を変更する際に作業者が必要である場合に、作
業者の人数を制約とすることで、作業者の数が不足する
ことがないように、その生産順序を決定できる。また、
生産ラインの稼働可能時間を制約とすることで、予定の
稼働可能時間内で生産できるように生産順序を決定でき
る。

【００３３】

【発明の実施の形態】以下、図面を参照して本発明の実
施形態を説明する。

【００３４】図１は、生産ラインにおける生産計画決定
装置の機能ブロック図を示す。その決定装置は、コンピ
ュータＣと、入力装置Ｉと、出力装置Ｏとを備える。そ
のコンピュータＣは、中央処理装置と記憶装置と入出力
インターフェイスとを有し、その入力装置１から入力さ
れて記憶装置に記憶された制御プログラムに従い、機能
ブロック図により示された各機能を奏することで、後述
のように生産ラインにおけるロットの生産順序を決定
し、その決定結果を出力装置Ｏに出力する。そのコンピ
ュータＣにおいて、１は、探索の出発点となる初期解を
解空間の中からランダムに若しくは何らかのルールを用
いて生成する初期解生成部である。２は、現在探索の対
象として解空間において注目している現行解を保持する
現行解保持部である。３は、その現行解保持部２に保持
されている現行解を、ランダムに若しくは何らかのルー
ルを用いて一部変更して近傍解を生成する近傍解生成部
である。４は、その近傍解生成部３で生成された近傍解
を保持しておく近傍解保持部である。５は、解が問題の
制約を満たさない度合を算出する第１評価関数値算出部
である。６は、問題本来の評価基準の充足程度に対応す
る評価関数値を算出する第２評価関数値算出部である。
７は、近傍解と現行解の第１評価関数値を比較して、近
傍解を受理してそれを現行解とするか否かを判定する第
１近傍解受理判定部である。８は、第１近傍解受理判定
部で判定できなかった場合に、近傍解と現行解の第２評
価関数値を比較して、近傍解を受理してそれを現行解と
するか否かを判定する第２近傍解受理判定部である。９
は、温度パラメータを管理する温度管理部であり、温度
パラメータを比較的高い初期温度から低い終了温度まで
少しずつ減少させる。１０は、現行解と暫定解の第１評
価関数値を比較して暫定解を変更するか否かを判定する
第１暫定解更新判定部である。１１は、第１暫定解更新
判定部１０で判定できなかった場合に、現行解と暫定解
の第２評価関数値を比較して暫定解を変更するか否かを
判定する第２暫定解更新判定部である。１２は、暫定解
を保持する暫定解保持部である。

【００３５】上記決定装置により生産計画を決定される
生産ラインは、製品として例えば複数種類の液体洗浄剤
を、原料を配合してタンクから製品容器に充填すること
で、ロット単位で生産するものである。その各ロットの
生産順序が、本実施形態の決定装置により生産計画とし
て決定される。すなわち、各ロットの生産順序の組み合
わせの中で、各ロットそれぞれの納期に遅れることな
く、製品の在庫量が最小となるものを求める組み合わせ
最適化問題を解くことになり、その在庫量が評価関数と
なり、納期が制約となる。例えば、３種類の製品Ａ、
Ｂ、Ｃそれぞれの３つのロットＡ１、Ａ２、Ａ３、Ｂ
１、Ｂ２、Ｂ３、Ｃ１、Ｃ２、Ｃ３の組み合わせ最適化
問題においては、１つの解は（Ａ１、Ｂ１、Ｂ２、Ａ
２、Ｃ１、Ａ３、Ｃ２、Ｃ３、Ｂ３）である。ここでｔ
ｉを解におけるｉ番目のロットの実際の納入時点、ｔａ
ｉをロットＡｉの納期、ｔｂｉをロットＢｉの納期、ｔ
ｃｉをロットＣｉの納期、ａを製品Ａの各ロットの個
数、ｂを製品Ｂの各ロットの個数、ｃを製品Ｃの各ロッ
トの個数とすると、その解の評価関数値はａ×（ｔａ１
−ｔ１）＋ｂ×（ｔｂ１−ｔ２）＋ｂ×（ｔｂ２−ｔ
３）＋ａ×（ｔａ２−ｔ４）＋ｃ×（ｔｃ１−ｔ５）＋
ａ×（ｔａ３−ｔ６）＋ｃ×（ｔｃ２−ｔ７）＋ｃ×
（ｔｃ３−ｔ８）＋ｂ×（ｔｂ３−ｔ９）である。ま
た、その時の制約は、（ｔａ１−ｔ１）、（ｔｂ１−ｔ
２）、（ｔｂ２−ｔ３）、（ｔａ２−ｔ４）、（ｔｃ１
−ｔ５）、（ｔａ３−ｔ６）、（ｔｃ２−ｔ７）、（ｔ
ｃ３−ｔ８）、および（ｔｂ３−ｔ９）それぞれが負に
ならないことである。

【００３６】図２〜図４に示すフローチャートは、上記
決定装置による各ロットの生産順序の決定手順を示す。
まず、初期解生成部１を用いて解空間に含まれる初期解
を生成し、この初期解を現行解保持部２において現行解
ｘとして保持し、暫定解保持部１２において暫定解ｚと
して保持することで、現行解ｘおよび暫定解ｚを初期化
する（ステップ１）。なお、現行解ｘおよび暫定解ｚの
初期値は異なるものとしてもよい。また、温度管理部９
により温度パラメータＴを初期化する（ステップ２）。

【００３７】次に、近傍解生成部３を用いて現行解ｘか
らその近傍の解ｙを生成し、その生成した近傍解ｙを近
傍解保持部４に保持する（ステップ３）。例えば、現行
解ｘが（Ａ１、Ｂ１、Ｂ２、Ａ２、Ｃ１、Ａ３、Ｃ２、
Ｃ３、Ｂ３）である場合に、近傍解生成部３でこれを
（Ａ１、Ｂ１、Ｂ２、Ｃ１、Ａ２、Ａ３、Ｃ２、Ｃ３、
Ｂ３）の様に第４要素と第５要素を交換して一部変更す
ることによって近傍解ｙが生成されて保持される。

【００３８】次に、その近傍解保持部４に保持された近
傍解ｙを受理するか否かを判定する（ステップ４）。

【００３９】図３のフローチャートは、その近傍解ｙを
受理するか否かの判定手順を示す。まず、第１評価関数
値算出部５で現行解ｘ及び近傍解ｙの第１評価関数ｆ１
（ｘ）、ｆ１（ｙ）の値を算出する（ステップ１′）。

【００４０】その第１評価関数ｆ１は、解が問題の制約
を満たさない度合であり、制約を満たさない場合には正
の値、制約を満たす場合には零になるように定義され
る。本実施形態では、納期の遅れ、つまり製品の納入時
点から納期を引いた値と零との大きい方の値とする。例
えば、ある解ｘに対し、製品Ａの納入時点が１９９６年
１１月２５日で納期が１９９６年１１月１５日であり、
製品Ｂの納入時点が１９９６年１１月２７日で納期が１
９９６年１１月１７日であり、製品Ｃの納入時点が１９
９６年１１月３０日で納期が１９９６年１１月２０日で
ある場合、その解ｘは制約を満たしておらず、第１評価
関数ｆ（ｘ）＝ｍａｘ（２５−１５、０）＋ｍａｘ（２
７−１７、０）＋ｍａｘ（３０−２０、０）＝３０とな
る。また、ある解ｘに対し、製品Ａの納入時点が１９９
６年１１月５日で納期が１９９６年１１月１５日であ
り、製品Ｂの納入時点が１９９６年１１月７日で納期が
１９９６年１１月１７日であり、製品Ｃの納入時点が１
９９６年１１月１０日で納期が１９９６年１１月２０日
である場合、解ｘは制約を満たし、第１評価関数ｆ
（ｘ）＝ｍａｘ（５−１５、０）＋ｍａｘ（７−１７、
０）＋ｍａｘ（１０−２０、０）＝０となる。

【００４１】次に、第１近傍解受理判定部７で、近傍解
ｙの第１評価関数ｆ１（ｙ）の値と現行解ｘの第１評価
関数ｆ１（ｘ）の値とを比較する（ステップ２′）。そ
の近傍解ｙの第１評価関数ｆ１（ｙ）の値が現行解ｘの
第１評価関数ｆ１（ｘ）の値未満の場合、無条件に近傍
解ｙを受理すると判定する（ステップ３′）。

【００４２】例えば、現行解ｘの第１評価関数ｆ１
（ｘ）＝３０で、近傍解ｙの第１評価関数ｆ１（ｙ）＝
１０である場合、近傍解ｙは制約を満たさないが、その
第１評価関数ｆ（ｙ）の値は現行解ｘの第１評価関数ｆ
（ｘ）の値未満なので受理される。

【００４３】ステップ２′において、その近傍解ｙの第
１評価関数ｆ１（ｙ）の値が現行解ｘの第１評価関数ｆ
１（ｘ）の値を超える場合、０以上１未満の一様乱数ｒ
ｎｄを発生させ、第１受理確率αを以下の式（２）によ
り演算し、その乱数ｒｎｄが第１受理確率α以下か否か
を第１近傍解受理判定部７で判定する（ステップ
４′）。なお、その式（２）において、第２評価関数ｆ
２（ｙ）と第１評価関数ｆ１（ｙ）との比の絶対値を含
んでいるのは、第１評価関数である納期と第２評価関数
である在庫量とは桁が異なることに鑑み、第１受理確率
αと後述の第２受理確率βとの差が過大になるのを防止
するためである。

【００４４】

【数２】

【００４５】その乱数ｒｎｄが第１受理確率α以下であ
ればステップ３′において近傍解ｙを受理すると判定
し、その乱数ｒｎｄが第１受理確率αを超えている場合
は近傍解ｙを受理しないと判定する（ステップ５′）。

【００４６】例えば、現行解ｘの第１評価関数ｆ１
（ｘ）＝３０で、近傍解ｙの第１評価関数ｆ１（ｙ）＝
４０である場合、近傍解ｙは制約を満たさず、その第１
評価関数ｆ（ｙ）の値は現行解ｘの第１評価関数ｆ
（ｘ）の値を超えるので、解の改悪を許して受理される
確率は第１受理確率αである。

【００４７】ステップ２′において、その近傍解ｙの第
１評価関数ｆ１（ｙ）の値と現行解ｘの第１評価関数ｆ
１（ｘ）の値とが等しく、第１近傍解受理判定部７では
近傍解ｙを受理するか否か判定できない場合、第２評価
関数値算出部６で現行解ｘおよび近傍解ｙの第２評価関
数値ｆ２（ｘ）、ｆ２（ｙ）を算出し（ステップ
６′）、第２近傍解受理判定部８で近傍解ｙの第２評価
関数値ｆ２（ｙ）が現行解ｘの第２評価関数値ｆ２
（ｘ）以下か否かを判定する（ステップ７′）。

【００４８】例えば、現行解ｘも近傍解ｙも制約を満た
し、それぞれの第１評価関数ｆ（ｘ）、ｆ１（ｙ）が零
となって相等しい場合、若しくは、現行解ｘも近傍解ｙ
も制約を満たさないが、それぞれの第１評価関数ｆ
（ｘ）、ｆ１（ｙ）が相等しい場合、第２評価関数値ｆ
２（ｘ）、ｆ２（ｙ）を算出し、第２近傍解受理判定部
８で近傍解ｙを受理するか否かが判定される。

【００４９】その第２評価関数ｆ２は、本来の解の評価
関数であり、本実施形態では製品の在庫量である。

【００５０】ステップ７′において、近傍解ｙの第２評
価関数値ｆ２（ｙ）が現行解ｘの第２評価関数値ｆ２
（ｘ）以下であれば、無条件にステップ３′において近
傍解ｙを受理すると判定する。例えば、現行解ｘに対し
て第２評価関数ｆ２（ｘ）＝８００であり、近傍解ｙに
対して第２評価関数ｆ２（ｙ）＝７２０である場合、近
傍解ｙは受理される。

【００５１】近傍解ｙの第２評価関数値ｆ２（ｙ）が現
行解ｘの第２評価関数値ｆ２（ｘ）を超える場合、０以
上１未満の一様乱数ｒｎｄを発生させ、第２受理確率β
を以下の式（３）により演算し、その乱数ｒｎｄが第２
受理確率β以下か否かを第２近傍解受理判定部８で判定
する（ステップ８′）。

【００５２】

【数３】

【００５３】その乱数ｒｎｄが第２受理確率β以下であ
ればステップ３′において近傍解ｙを受理すると判定
し、その乱数ｒｎｄが第２受理確率βを超えている場合
はステップ５′において近傍解ｙを受理しないと判定す
る。

【００５４】例えば、現行解ｘに対して第２評価関数ｆ
２（ｘ）＝８００であり、近傍解ｙに対して第２評価関
数ｆ２（ｙ）＝１０００である場合、解の改悪を許して
近傍解ｙが受理される確率は第２受理確率βである。

【００５５】ステップ４において、近傍解ｙを受理する
と判定された場合、現行解保持部２に保持された現行解
ｘの内容を近傍解ｙの内容と置換することで、現行解ｘ
の内容を更新する（ステップ５）。その現行解ｘの内容
を更新したならば、暫定解保持部１２に保持された暫定
解ｚを更新するか否かを判定する（ステップ６）。

【００５６】図４のフローチャートは、その暫定解ｚを
更新するか否かの判定手順を示す。まず、第１評価関数
値算出部５で現行解ｘ及び暫定解ｚの第１評価関数ｆ１
（ｘ）、ｆ１（ｚ）の値を算出する（ステップ１″）。
次に、第１暫定解更新判定部１０で、暫定解ｚの第１評
価関数ｆ１（ｚ）の値と現行解ｘの第１評価関数ｆ１
（ｘ）の値とを比較する（ステップ２″）。その現行解
ｘの第１評価関数ｆ１（ｘ）の値が暫定解ｚの第１評価
関数ｆ１（ｚ）の値未満の場合、無条件に暫定解ｚを更
新すると判定する（ステップ３″）。その現行解ｘの第
１評価関数ｆ１（ｘ）の値が暫定解ｚの第１評価関数ｆ
１（ｚ）の値を超える場合、暫定解ｚを更新しないと判
定する（ステップ４″）。

【００５７】ステップ２″において、その暫定解ｚの第
１評価関数ｆ１（ｚ）の値と現行解ｘの第１評価関数ｆ
１（ｘ）の値とが等しく、第１暫定解更新判定部１０で
は暫定解ｚを更新するか否か判定できない場合、第２評
価関数値算出部６で現行解ｘおよび暫定解ｚの第２評価
関数値ｆ２（ｘ）、ｆ２（ｚ）を算出し（ステップ
５″）、第２暫定解更新判定部１１で現行解ｘの第２評
価関数値ｆ２（ｘ）が暫定解ｚの第２評価関数値ｆ２
（ｚ）未満か否かを判定する（ステップ６″）。その現
行解ｘの第２評価関数ｆ２（ｘ）の値が暫定解ｚの第２
評価関数ｆ２（ｚ）の値未満の場合、無条件にステップ
３″で暫定解ｚを更新すると判定する。その現行解ｘの
第２評価関数ｆ２（ｘ）の値が暫定解ｚの第２評価関数
ｆ２（ｚ）の値以上の場合、ステップ４″で暫定解ｚを
更新しないと判定する。

【００５８】ステップ６において暫定解ｚを更新すると
判定した場合、暫定解保持部１２に保持された暫定解ｚ
の内容を現行解ｘの内容と置換することで、暫定解ｚの
内容を更新する（ステップ７）。暫定解ｚの内容を更新
した場合、ステップ４において近傍解ｙを受理しないと
判定した場合、あるいはステップ６において暫定解ｚを
更新をしないと判定した場合、温度管理部９で管理して
いる温度パラメータＴの値を減少させ（ステップ８）、
その温度パラメータＴが予め設定された終了温度に達し
ているか否かを判定する（ステップ９）。その温度パラ
メータＴが終了温度に達していない場合はステップ３へ
戻り、終了温度に達している場合は解の探索を終了す
る。探索が終了した時点での暫定解ｚが、本実施形態の
解法による解となり、出力装置Ｏに出力される。

【００５９】上記構成によれば、生成された近傍解が制
約を満足するか否かを判定することなく、制約の充足程
度に対応する第１評価関数ｆ１（ｘ）、ｆ１（ｙ）に基
づき現行解ｘと近傍解ｙとを評価することで解を更新す
るか否かを判定するので、制約が厳しく近傍解ｙが実行
不可能であっても、実行可能性に基づき解の探索を進め
ることができ、生産ラインにおける各ロットの生産順序
の組み合わせの集合である解空間を充分に探索できる。
さらに、現行解ｘと生成された近傍解ｙが制約を満足す
る場合は、現行解ｘと近傍解ｙの第１評価関数ｆ１
（ｘ）、ｆ１（ｙ）の値が相等しくなり、現行解ｘと近
傍解ｙとを本来の評価基準の充足程度に対応する第２評
価関数ｆ２（ｘ）、ｆ２（ｙ）により評価して解を更新
するか否かを判定できるので、解が実行可能な場合には
問題本来の評価関数に従って解の探索を進めることがで
きる。すなわち、解空間を、解が実行不能である時は実
行可能性を優先して探索し、実行可能である時には問題
本来の評価を最適化するように探索するように、その解
の状況に応じて自動的に評価関数を設定できる。これに
より、制約の緩い問題はもとより、制約の厳しい問題で
あっても、実行可能で且つ評価の良好な解を導出するこ
とができ、各ロットの生産順序を実行可能で且つ評価が
良好になるように決定でき、さらに、製品の納期を満足
し、在庫量を少なくすることができる。

【００６０】また、制約が厳しく実行可能解が存在しな
い場合であっても、実行可能性に応じた解を得て実行不
能の程度を知ることができ、問題の制約の緩和等に供す
ることができる。

【００６１】上記実施形態においては製品の納期を制約
としたが、以下の用に他の条件を制約とすることができ
る。

【００６２】すなわち、複数の生産ラインを用いて製品
を生産する場合、納期だけでなく、その生産ラインの数
を制約とすることができる。例えば、３種類の製品Ａ、
Ｂ、Ｃそれぞれの３つのロットＡ１、Ａ２、Ａ３、Ｂ
１、Ｂ２、Ｂ３、Ｃ１、Ｃ２、Ｃ３の組み合わせ最適化
問題において、１つの解が（Ａ１、Ｂ１、Ｃ１、Ｂ２、
Ａ２、Ａ３、Ｃ２、Ｃ３、Ｂ３）であり、ロットＡ１、
Ｂ１、Ｃ１の納期が重複し余裕がない場合、それらの納
期を満足するためには３つの生産ラインが必要となるこ
とがある。このように、各ロット毎に納期が設定されて
いるので、それらの納期を満足するためには生産ライン
の生産能力に限界があるため、場合によっては別の代替
生産ラインが必要となる。このようにして各時点時点に
おいて各ロットの納期を充足する上で必要な生産ライン
の数が算出され、それは与えられた生産ラインの数以下
でなければならない。このように、納期だけでなく、生
産ラインの数を制約とし第１評価関数の対象とすること
で、使用する生産ラインの数に不足がないように、その
生産順序を決定することができる。

【００６３】また、複数の生産ラインを用いて製品が生
産され、各生産ラインにおいて生産品種を変更する際に
作業者が必要である場合、各生産ラインにおける品種変
更時刻が重なると、多くの作業者が必要になることか
ら、その作業者の人数を制約とすることができる。例え
ば、３種類の製品Ａ、Ｂ、Ｃそれぞれの３つのロットＡ
１、Ａ２、Ａ３、Ｂ１、Ｂ２、Ｂ３、Ｃ１、Ｃ２、Ｃ３
の組み合わせ最適化問題において、１つの解が（Ａ１、
Ｂ１、Ｂ２、Ｃ１、Ｃ２、Ｃ３、Ａ２、Ａ３、Ｂ３）で
あり、３本の生産ラインにより生産が行われ、各ライン
における品種変更時に一人の作業者が必要である場合を
考える。この場合、まず、一つのラインでロットＡ１
が、一つのラインでロットＢ１が、一つのラインでロッ
トＢ２が生産を開始され、その後に各ラインにおける生
産品種は製品Ｃに変更される。その生産品種の変更時刻
は、製品Ａのロットと製品Ｂのロットの生産に要する時
間が同一であると、同一時刻になるため、３人の作業者
が必要になる。この場合、同一時刻に作業可能な作業者
の人数が２人である場合は制約を満たさないことにな
り、３人以上の場合は制約を満たすことになる。このよ
うに作業者の人数を制約とすることで、複数の生産ライ
ンにおいて製品を生産する場合に、各生産ラインにおい
て生産品種を変更する際に必要な作業者の数が不足する
ことがないように、その生産順序を決定できる。

【００６４】また、生産ラインにおいて複数種類の製品
を生産する場合、その生産ラインの稼働可能時間を制約
としてもよい。例えば、２種類の製品Ａ、Ｂそれぞれの
３つのロットＡ１、Ａ２、Ａ３、Ｂ１、Ｂ２、Ｂ３の組
み合わせ最適化問題において、一つの解が（Ａ１、Ｂ
１、Ａ２、Ｂ２、Ａ３、Ｂ３）であり、各ロットの生産
に要する時間がそれぞれ１０時間、製品Ａから製品Ｂお
よび製品Ｂから製品Ａへの設備段取り替え時間がそれぞ
れ５時間である場合、生産総所要時間は８５時間にな
る。この場合に、生産ラインの稼働可能時間が８０時間
である場合は制約を満たさないことになり、稼働可能時
間が１００時間である場合は制約を満たすことになる。
このように稼働可能時間を制約とすることで、複数種類
の製品を生産ラインを用いて生産する場合に、予定の稼
働可能時間内で生産できるように生産順序を決定でき
る。

【００６５】なお、上記実施形態の第１評価関数は、制
約を満たさない度合いに対応し、それが最小化されるよ
うに解の探索を行ったが、制約を満たす度合いに対応す
るものとし、それが最大化されるように解の探索を行っ
てもよく、第１評価関数は制約の充足程度に対応してい
ればよい。

【図面の簡単な説明】

【図１】 本発明の実施形態の演算装置の機能ブロック
図

【図２】 本発明の実施形態による解の探索手順を示す
フローチャート

【図３】 本発明の実施形態による解の探索手順の一部
を示すフローチャート

【図４】 本発明の実施形態による解の探索手順の一部
を示すフローチャート

【図５】 従来例の演算装置の機能ブロック図

【図６】 従来例による解の探索手順を示すフローチャ
ート

【図７】 従来例による解の探索手順の一部を示すフロ
ーチャート

【符号の説明】

１ 初期解生成部 ２ 現行解保持部 ３ 近傍解生成部 ４ 近傍解保持部 ５ 第１評価関数値算出部 ６ 第２評価関数値算出部 ７ 第１近傍解受理判定部 ８ 第２近傍解受理判定部 ９ 温度管理部 １０ 第１暫定解更新判定部 １１ 第２暫定解更新判定部

Claims (8)

【特許請求の範囲】
1. 【請求項１】 全ての組み合わせの集合の中の一つであ
   る現行解を、設定された評価基準と制約とに基づき、そ
   の集合の中の別の一つである近傍解と置換することで更
   新する過程を有する組み合わせ最適化問題の解法におい
   て、 解の前記制約の充足程度に対応する第１評価関数と、解
   の前記評価基準の充足程度に対応する第２評価関数とを
   設定し、 その現行解の第１評価関数と近傍解の第１評価関数とが
   相等しくない場合は、現行解と近傍解とを第１評価関数
   に基づき評価することで、解を更新するか否かを判定
   し、 その現行解の第１評価関数と近傍解の第１評価関数とが
   相等しい場合は、その現行解と近傍解とを第２評価関数
   に基づき評価することで、解を更新するか否かを判定す
   ることを特徴とする組み合わせ最適化問題の解法。
2. 【請求項２】 現行解と生成された近傍解が制約を満足
   する場合は、現行解と近傍解の第１評価関数の値が相等
   しくされる請求項１に記載の組み合わせ最適化問題の解
   法。
3. 【請求項３】 複数種類の製品を生産ラインにおいてロ
   ット単位で生産するに際し、その各ロットの生産順序を
   決定する装置であって、 全ての生産順序の組み合わせの集合の中の一つである現
   行解の初期値を生成する手段と、 その現行解を保持する手段と、 その保持された現行解を変更して、前記集合の中の別の
   一つである近傍解を生成する手段と、 その生成された近傍解を保持する手段と、 その現行解と近傍解それぞれの制約の充足程度に対応す
   る第１評価関数値の演算手段と、 その現行解と近傍解それぞれの評価基準の充足程度に対
   応する第２評価関数値の演算手段と、 その近傍解と現行解の第１評価関数値を比較し、その近
   傍解を受理して現行解と置換して現行解を更新するか否
   かを判定する第１近傍解受理判定手段と、 その現行解の第１評価関数と近傍解の第１評価関数とが
   相等しい場合に、その近傍解と現行解の第２評価関数値
   を比較し、その近傍解を受理して現行解と置換して現行
   解を更新するか否かを判定する第２近傍解受理判定手段
   と、 全ての生産順序の組み合わせの集合の中の一つである暫
   定解の初期値を生成する手段と、 その更新された現行解と暫定解の第１評価関数値を比較
   し、その現行解を暫定解と置換して暫定解を更新するか
   否かを判定する第１暫定解更新判定手段と、 その現行解の第１評価関数と暫定解の第１評価関数とが
   相等しい場合に、その現行解と暫定解の第２評価関数値
   を比較し、その暫定解を現行解と置換して暫定解を更新
   するか否かを判定する第２暫定解更新判定手段と、 探索を継続するか否かを判定する手段と、 その探索終了時点での暫定解を出力する手段とを備える
   生産ラインにおける生産計画決定装置。
4. 【請求項４】 現行解と生成された近傍解が制約を満足
   する場合は、現行解と近傍解の第１評価関数の値が相等
   しくされる請求項３に記載の生産ラインにおける生産計
   画決定装置。
5. 【請求項５】 各種類の製品それぞれの納期が制約とさ
   れ、製品の生産時点から納期までの在庫量が評価基準と
   されている請求項３または４に記載の生産ラインにおけ
   る生産計画決定装置。
6. 【請求項６】 各種類の製品は複数の生産ラインにおい
   て生産され、各ロットの生産を開始する時点における生
   産可能なラインの本数が制約とされている請求項５に記
   載の生産ラインにおける生産計画決定装置。
7. 【請求項７】 各種類の製品は複数の生産ラインにおい
   て生産され、各生産ラインにおいて生産品種を変更する
   際に作業者が必要とされ、各生産ラインにおける品種変
   更時刻の重なり時に必要とされる作業者の人数が制約と
   されている請求項３〜６の何れかに記載の生産ラインに
   おける生産計画決定装置。
8. 【請求項８】 生産ラインにおける稼働可能時間が制約
   とされている請求項３または請求項４に記載の生産ライ
   ンにおける生産計画決定装置。