JPH10207861A - 計画立案装置および計画立案方法 - Google Patents

Abstract

(57)【要約】 （修正有） 【課題】製造プロセスの計画問題において、工程内で能
力の異なる使用可能設備が複数有る場合、設備の使用パ
ターン（設備への投入量、使用台数、使用順等）を決定
する必要がある。生産設備全体にて設備の使用パターン
を目的関数にて評価した場合、短時間に最適解を見つけ
出す手段の提供。 【解決手段】問題の解決に必要な変数の値を少なくとも
受け付ける設定手段３と、前記計画対象となる問題にお
いて、部分問題における、最小化または最大化を図る項
目を表わす目的関数を作成し、作成された目的関数の値
を最小化または最大化する計画を立案する部分最適化手
段２と、各部分問題の該計画に対して、全体問題に関す
る最小化または最大化を図る項目を表わす目的関数を作
成し、作成された目的関数の値を最小化または最大化す
る計画を立案する最適化手段１と、計画立案に必要な変
数を少なくとも記憶する記憶手段４とを備える計画立案
装置。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、各種分野の様々な
計画立案等における、最適な計画案提供する手段に関
し、特に、製造ラインのように、順列、組合わせの数が
膨大で、かつ、必ず最適解となる計画案が存在する問題
を、簡易な構成で極めて高速に解決する計画立案装置及
び方法に関する。

【０００２】

【従来の技術】従来から、多種多様な分野における、各
種問題を対象とする計画問題において、最大、あるい
は、最少とする項目を決め、該項目を、最大、あるい
は、最少とするとする計画案である最適解を、現実的に
許容し得る時間内に見つけ出すために各種の手法が提案
されてきた。

【０００３】計画立案の必要な分野として、例えば、使
用可能な設備が複数有る製造ラインにおける各設備の使
用パターンの問題がある。すなわち、製造ラインのある
工程内で能力の異なる使用可能設備が複数有る場合、設
備の使用パターン例えば、設備への投入量、使用台数、
使用順等を決定する必要がある。

【０００４】図６は、各工程内で能力の異なる使用可能
設備が複数有るバッチプロセス向け製造ラインの一例を
示す図である。図６において、バッチプロセス向け製造
ラインは工程１乃至工程６からなり、工程１及び工程５
は能力の異なる生産設備Ａ（Ａ−１，Ａ−２，Ａ−３，
Ａ−４）を備えている。また、工程２，３，４，６も、
それぞれ能力の異なる生産設備Ｂ，Ｃ，Ｄ，Ｅを備えて
いる。製造ラインに投入された原料は、工程１において
生産設備Ａ−１，Ａ−２，Ａ−３のいずれかによって所
定の加工処理がなされた後、工程２の生産設備Ｂ−１，
Ｂ−２，Ｂ−３のいずれかに位相され、所定の加工処理
がなされる。以下、工程３，４，５，６で同じように、
いずれかの生産設備で加工処理された後、製品となる。

【０００５】従来は、与えられた複数（ｌ）生産量を、
複数（ｎ）工程内の複数（ｍ）設備を使用して生産する
場合に、最短期間となる様計画する問題において、計画
問題全体に対する前記目的関数を求めていた。

【０００６】

【発明が解決しようとする課題】しかし、図６のように
各工程内で能力の異なる使用可能設備が複数有る設備の
使用パターン（設備への投入量、使用台数、使用順等）
を決定するとき、従来通り生産設備全体にて前記設備の
使用パターンを前記目的関数にて評価した場合、膨大な
使用パターンの組合せが発生する。

【０００７】このように、従来の方法では、各工程が能
力の異なる使用可能な設備を複数有る場合に、使用パタ
ーンの組合せが多すぎて、最適の使用パターンを決定し
ようとしても現実的に許容し得る時間内に最適解を見つ
け出すことは不可能であった。 特に化学分野でのバッ
チ型製造プロセスでの設備のやり繰りと、設備への投入
量決定問題については、実用解を得る上での障害となっ
ている。

【０００８】本発明の目的は、上記問題点を解決し、計
画対象となる問題が選択可能な多数の使用パターンの組
合せからなる問題において、組合せの数が膨大である計
画問題の中から使用パターンの最適解を短期間に求める
計画立案装置及び方法を提供することである。

【０００９】本発明の他の目的は、上記問題点を解決
し、与えられた複数（ｌ）生産量を、複数（ｎ）工程内
の複数（ｍ）設備を使用して生産する場合に、最短期間
となる様計画する問題において、組合せの数が膨大であ
る計画問題の中から設備使用パターンの最適解を短期間
に求める計画立案装置及び方法を提供することである。

【００１０】

【課題を解決するための手段】本発明の特徴は、与えら
れた計画対象となる問題において最少化または最大化を
図る項目を表わす目的関数を作成し該目的関数の値を最
少化または最大化する計画を立案する最適化手段と、前
記計画に必要な変数を記憶する記憶手段とを具備し、前
記最適化手段は、前回立案された計画による目的関数値
と新たに立案された計画による目的関数値を比較して新
たに立案された計画が優れている場合に、前回立案した
計画を新たに立案した計画に置き換え最適計画候補とす
る計画立案装置において、前記最適化手段は、与えられ
た計画対象の各部分毎に、各部分問題において最少化ま
たは最大化を図る項目を表わす部分目的関数を作成し、
該部分目的関数の値を最少化または最大化する部分計画
を立案する複数の部分最適化手段と、該部分最適化手段
を選択する選択手段とを具備し、部分問題を解決しつつ
全体の問題を解決するように構成されていることにあ
る。

【００１１】本発明の他の特徴は、与えられた計画対象
となる問題、該問題の解決に必要な変数の値を少なくと
も受け付ける設定手段と、前記計画対象となる問題にお
いて、部分問題における最小化または最大化を図る項目
を表わす目的関数を作成し、作成された目的関数の値を
最小化または最大化する計画を作成し、各部分問題の該
計画に対して、全体問題に関する最小化または最大化を
図る項目を表わす目的関数を作成し、作成された目的関
数の値を最小化または最大化する計画を立案する最適化
手段と、計画立案に必要な変数を少なくとも記憶する記
憶手段とを具備し、前記最適化手段は、各部分問題にお
いて前回立案された計画と、新たに立案された計画にお
ける前記目的関数の差分値を計算する演算手段と、前記
目的関数の差分値と前記記憶手段内に、予め設定された
変数の値とを比較して、前記目的関数の差分値が、前記
予め設定された変数の値より小さい場合に、前回立案し
た計画を、今回立案した計画に置き換え、最適計画候補
とする再計画手段を備え、次に各部分問題についての最
適計画候補の集合を、全体問題の今回立案した計画と
し、全体問題において前回立案された計画と、新たに今
回立案された計画における前記目的関数の差分値を計算
する演算手段と、前記目的関数の差分値と前記記憶手段
内に、予め設定された変数の値とを比較して、前記目的
関数の差分値が、前記予め設定された変数の値より小さ
い場合に、前回立案した計画を、今回立案した計画に置
き換え、最適計画候補とす再計画手段を備えることにあ
る。

【００１２】本発明の他の特徴は、前記計画対象となる
問題が、製造プロセスにおける各工程内で能力の異なる
使用可能設備が複数有る設備の使用パターンを計画する
ものであり、前記部分問題が、前記工程毎の使用設備の
使用パターンの組合せ計画であり、部分最適化処理を行
い、各部分問題についての最適計画候補の集合を、全体
問題の計画として全体問題を処理することにある。

【００１３】本発明の他の特徴は、与えられた計画対象
となる問題において最少化または最大化を図る項目を表
わす目的関数を作成し、該目的関数の値を最少化または
最大化する計画を立案し、前回立案された計画による目
的関数値と新たに立案された計画による目的関数値を比
較して新たに立案された計画が優れている場合に、前回
立案した計画を新たに立案した計画に置き換え最適計画
候補とする計画立案方法において、前記計画対象となる
問題が、製造プロセスにおける各工程内で能力の異なる
使用可能設備が複数有る設備の使用パターンを計画する
ものであり、前記部分問題が、前記工程毎の使用設備の
使用パターンの組合せ計画であり、部分最適化処理を行
い、各部分問題についての最適計画候補の集合を、全体
問題の計画として全体問題を処理することにある。

【００１４】本発明によれば、例えば、製造プロセスの
ある工程内で能力の異なる使用可能設備が複数有る製造
プロセスの計画問題において、設備の使用パターンを決
定する場合のように、組合せの数が膨大である計画問題
の中から最適解を短期間に求める計画立案装置及び方法
を提供することができる。

【００１５】

【発明の実施の形態】以下、本発明を図に従って説明す
る。すなわち、１つの工程内に生産可能な能力の異なる
生産設備が複数（ｍ）あるとき、複数（ｎ）の工程を経
て完了する複数（ｌ）ロットの作業を最短期間になるよ
う計画する問題と、その計画方法を図を用いて説明す
る。

【００１６】ここでは、図６に示したバッチプロセス向
け製造ラインのような設備において、作業を最短期間に
なるよう計画する問題について説明する。

【００１７】バッチプロセスでは、図１に示すように、
各ロットｊ（１，２，３…）は、設備Ｋ（１〜ｍａｘ）
に格納され生産量に関わらず一定時間の作業を施されて
次の工程ｉの生産設備へ搬送されるため、最短期間での
生産を行うにはロットの投入量を各設備Ｋの空具合をみ
て決定する必要がある。

【００１８】該問題の状態は、各工程ｉの作業時間ａｉ
ｊを要素として、行方向を工程ｉの順序、列方向を作業
ｊの着手順とすると、行列Ａの様に表現できる。各工程
の作業時間ａｉｊは、ロットサイズＶｊに対し処理可能
な設備組合せ（Ｍｉ）を発生させこの中から作業時間最
小の組合せを求め作業時間とする。各工程毎に作業時間
最小の設備パターン及作業時間を決定し、最後に全ロッ
トの作業時間を求める関数を目的関数としｆ＝（Ａ）と
する。該問題は、全体の目的関数ｆ（Ａ）を最小にする
ようなＡを決定する時に、行列Ａの要素となる各工程ｉ
毎の作業時間の最小を図りながら行う為、部分問題解決
を図りながら全体問題を解決することになる。

【００１９】次に、図２は、本発明の一実施例になる計
画立案装置の構成例を示す図である。 計画立案装置
は、最適化手段１と、部分最適化手段２と、設定手段３
と、記憶手段４とを有している。

【００２０】最適化手段１は、最適な計画を立案する手
段であり、与えた計画対象となる問題において最小また
は最大とする項目を表現する目的関数を作成し、該目的
関数の値を、最大または最小にするための処理を行う手
段である。例えば、ＣＰＵと、図３に示す最適化処理手
順を実行するプログラムを保持したＲＯＭ、及び定数や
処理結果を保持するＲＡＭ等の電子デバイスにて実現で
きる。最適化手段１は、各工程内で能力の異なる使用可
能設備が複数有る設備の使用パターン（設備への投入
量、使用台数、使用順等）を選択し、部分最適化手段２
に部分問題最適化処理を行わせる機能も備えている。

【００２１】すなわち、最適化手段１は、前回立案され
た計画と、新たに立案された計画における前記目的関数
の差分値を計算する第１の機能と、前記目的関数の差分
値と前記記憶手段内に、予め設定された変数の値とを比
較して、前記目的関数の差分値が、前記予め設定された
変数の値より小さい場合に、前回立案した計画を、今回
立案した計画に置き換え、計画候補とする第２の機能と
をそなえている。また、部分最適化手段２の選択機能も
備えている。

【００２２】部分最適化手段２（部分最適化手段１，部
分最適化手段２，…）は、各工程毎の作業時間最適化を
行う手段であり、与えた計画対象となる問題において部
分問題最適化のための処理を少なくとも行う手段であ
る。例えば、ＣＰＵと、図４に示す部分最適化処理手順
を実行するプログラムを保持したＲＯＭ、及び定数や処
理結果を保持するＲＡＭ等の電子デバイスにて実現でき
る。部分最適化手段２は、あるロットに対し工程毎の使
用設備の組合せ（使用パターン）を選定し、この使用パ
ターンを目的関数にて評価する機能を備えている。部分
最適化手段２の選択は最適化手段１によってなされる。
部分最適化手段２は、与えられた計画対象の各部分問題
においても、最少化または最大化を図る項目を表わす目
的関数を作成し、作成された目的関数の値を最少化また
は最大化する部分計画を立案する機能を有する。

【００２３】設定手段３は、与えた計画対象となる問題
を受け付ける機能、計画立案に必要なパラメータを示す
定数等を受け付け、記憶手段４に記憶保持する機能等を
少なくとも有する手段であり、例えば、キーボード、マ
ウス等により実現できる。

【００２４】次に、記憶手段４は、設定手段３を介して
与えられた問題、最適化のために使用する定数等及び、
最適化手段１、部分最適化手段２の処理結果を少なくと
も記憶する手段であり、例えばＲＡＭにて実現される。

【００２５】なお、図２には、図示しないが、デイスプ
レイ等の表示手段を最適手段に接続し、設定手段を介し
て記憶手段に格納された計画対象問題、必要な定数、最
適手段による処理結果、部分最適手段による処理結果等
を表示する構成にするのが好ましい。

【００２６】次に、図３に最適化手段１の最適化処理手
順を示す。本発明は、下記ステップにより、各工程での
作業時間最小を図りながら、Ａの最適化することを可能
としている。 ステップ１０：問題、最適化のために使用する定数等及
び目的関数ｆ＝（Ａ）の初期値を設定する。すなわち、
図１に示したように、各工程ｉの作業時間ａｉｊを要素
として、行列Ａの様に表現する。各工程の作業時間ａｉ
ｊは、ロットサイズＶｊに対し処理可能な設備組合せ
（Ｍｉ）を発生させこの中から作業時間最小の組合せを
求め作業時間とする。各工程毎に作業時間最小の設備パ
ターン及作業時間を決定し、最後に全ロットの作業時間
を求める関数を目的関数とし、ｆ＝（Ａ）とする。

【００２７】ステップ２０：行列Ａの行を交換する。す
なわち、前回のＡにもとずき、ある行を交換した新しい
Ａのロット投入順を決定する。 ステップ３０：部分最適化手段（部分最適化手段１，部
分最適化手段２，…）のいずれかを選定する。選定され
た部分最適化手段では、あるロットに対し工程毎の使用
設備の組合せを発生させて、部分最適化処理により最適
の使用パターンが決定される。

【００２８】ステップ４０：新しいＡについて目的関数
ｆ（Ａ）を求める。 ステップ５０，５５：前回と今回の目的関数を判定し、
今回のほうが優れている場合は今回のＡを残し、前回の
方が優れている場合は前回のＡを残す。 ステップ６０：ステップ２０〜５５を４×（ｎの２乗）
回繰り返す。

【００２９】以上のステップにより求められたＡの順列
がロットの最適投入順を示し、各工程毎の作業時間が最
適作業時間を示す。

【００３０】使用可能な設備組合せの中から工程内作業
時間最小の組合せ及作業時間をもとめる。次に、図４、
図５に部分最適化手段２による部分最適化処理手順を示
す。

【００３１】ステップ７１：問題、最適化のために使用
する定数等及び目的関数ｆ＝（Ｂ）の初期値を設定す
る。すなわち、図５に示したように、特定の工程ｉ内で
の作業時間Ｌｊｋを要素として、行列Ｂの様に表現す
る。工程ｉ内での作業時間Ｌｊｋは、ロットＪ（＝１〜
ｍ）に対し処理可能な設備Ｋ（＝１〜ｓ）を発生させ、
この中から作業時間最小の組合せを求め作業時間とす
る。部分最適化手段１，部分最適化手段２，…は、各工
程における設備パターンに対応した作業時間を求める関
数を目的関数とし、ｆ＝（Ｂ）とする。

【００３２】ステップ７２としては、前回のＢにもとず
き、ある行を交換した新しいＢのロット投入順を決定す
る。そして、新しいロット投入順に従い、各ロット毎に
各工程内での使用可能設備の使用組合せを発生させる。

【００３３】ステップ７３としては、新しいＢについて
目的関数ｆ（Ｂ）を求める。

【００３４】ステップ７４としては、前回と今回の目的
関数を判定し、今回のほうが優れている場合は今回のＢ
を残し（ステップ７５）、前回の方が優れている場合は
前回のＢを残す。

【００３５】ステップ７６としては、ステップ１〜６を
４×（ｎの２乗）回繰り返す。

【００３６】本発明によれば、各工程内で能力の異なる
使用可能設備が複数有る設備の使用パターン（設備への
投入量、使用台数、使用順等）を決定するとき、部分最
適化手段２により、例えばロットに対し工程毎の使用設
備の組合せを発生させて、部分最適化処理を行い、各部
分問題についての最適計画候補の集合を、全体問題の計
画として全体問題を処理することにより、最適の使用パ
ターンが、ごく短時間に決定される。すなわち、膨大な
使用パターンの組合せが発生する可能性のある設備選択
問題を、容易に解決出来る。本発明は、特に、バッチ型
製造プロセスにおけるバッチ分割を伴う設備の選択に有
利である。

【００３７】本発明によれば、最適化手段の一部に部分
最適化手段の選択手段を組込み、部分最適化手段によっ
て得られた各部分問題についての最適計画候補の集合を
全体問題の計画とし、全体問題における最適な計画を立
案するようにしたので、簡単な構成により、与えられた
生産計画問題に対する最適な計画立案を高速に行うこと
が出来る。

【００３８】本発明は、実施例で述べた製造プロセスに
限らず、工程毎に選択可能な使用パターンの組み合わせ
が複数存在するような、各種のプロセスにおける計画立
案に広く応用できる。

【００３９】

【発明の効果】本発明によれば、簡単な構成により、与
えられた生産計画問題に対する最適な計画立案を高速に
行う手段を提供できる効果がある。具体的には、次のよ
うな効果がある。 （１）部分問題となる設備選択問題を解決出来る。特
に、バッチ型製造プロセスにおけるバッチ分割を伴う設
備の選択に有利である。 （２）部分問題を解決したうえで全体の最適化問題を解
決することが出来る。

【図面の簡単な説明】 【符号の説明】

【図１】本発明による計画問題の数式化の説明図であ
る。

【図２】本発明の一実施例になる最適化装置の構成例を
示す図である。

【図３】図２の最適化装置の処理手順の説明図である。

【図４】図２の部分最適化装置の処理手順の説明図であ
る。

【図５】図４の処理の説明図である。

【図６】各工程内で能力の異なる使用可能設備が複数有
るバッチプロセス向け製造ラインの一例を示す図であ
る。 １・・・最適化手段、２・・・部分最適化手段、３・・
・設定手段 ４・・・記憶手段

Claims (7)

【特許請求の範囲】
1. 【請求項１】与えられた計画対象となる問題において最
   少化または最大化を図る項目を表わす目的関数を作成し
   該目的関数の値を最少化または最大化する計画を立案す
   る最適化手段と、前記計画に必要な変数を記憶する記憶
   手段とを具備し、前記最適化手段は、前回立案された計
   画による目的関数値と新たに立案された計画による目的
   関数値を比較して新たに立案された計画が優れている場
   合に、前回立案した計画を新たに立案した計画に置き換
   え最適計画候補とする計画立案装置において、 前記最適化手段は、与えられた計画対象の各部分毎に、
   各部分問題において最少化または最大化を図る項目を表
   わす部分目的関数を作成し、該部分目的関数の値を最少
   化または最大化する部分計画を立案する複数の部分最適
   化手段と、該部分最適化手段を選択する選択手段とを具
   備し、部分問題を解決しつつ全体の問題を解決するよう
   に構成されていることを特徴とする計画立案装置。
2. 【請求項２】与えられた計画対象となる問題、該問題の
   解決に必要な変数の値を少なくとも受け付ける設定手段
   と、前記計画対象となる問題において、部分問題におけ
   る最小化または最大化を図る項目を表わす目的関数を作
   成し、作成された目的関数の値を最小化または最大化す
   る計画を作成し、各部分問題の該計画に対して、全体問
   題に関する最小化または最大化を図る項目を表わす目的
   関数を作成し、作成された目的関数の値を最小化または
   最大化する計画を立案する最適化手段と、計画立案に必
   要な変数を少なくとも記憶する記憶手段とを具備し、 前記最適化手段は、各部分問題において前回立案された
   計画と、新たに立案された計画における前記目的関数の
   差分値を計算する演算手段と、前記目的関数の差分値と
   前記記憶手段内に、予め設定された変数の値とを比較し
   て、前記目的関数の差分値が、前記予め設定された変数
   の値より小さい場合に、前回立案した計画を、今回立案
   した計画に置き換え、最適計画候補とする再計画手段を
   備え、 次に各部分問題についての最適計画候補の集合を、全体
   問題の今回立案した計画とし、全体問題において前回立
   案された計画と、新たに今回立案された計画における前
   記目的関数の差分値を計算する演算手段と、前記目的関
   数の差分値と前記記憶手段内に、予め設定された変数の
   値とを比較して、前記目的関数の差分値が、前記予め設
   定された変数の値より小さい場合に、前回立案した計画
   を、今回立案した計画に置き換え、最適計画候補とす再
   計画手段を備える計画立案装置。
3. 【請求項３】請求項１または２において、前記計画対象
   となる問題が、製造プロセスにおける各工程内で能力の
   異なる使用可能設備が複数有る設備の使用パターンを計
   画するものであり、前記部分問題が、前記工程毎の使用
   設備の使用パターンの組合せ計画であり、部分最適化処
   理を行い、各部分問題についての最適計画候補の集合
   を、全体問題の計画として全体問題を処理することを特
   徴とする計画立案装置。
4. 【請求項４】請求項１または２において、前記計画対象
   となる問題が、バッチ型製造プロセスにおけるバッチ分
   割を伴う設備の選択に関するものであることを特徴とす
   る計画立案装置。
5. 【請求項５】請求項１において、前記計画対象となる問
   題が、製造プロセスにおける各工程内で能力の異なる使
   用可能設備が複数有る設備の使用パターンを決定するも
   のであり、前記選択手段により選択された前記部分最適
   化手段により工程毎の使用設備の組合せを発生させて部
   分最適化処理を行い、各部分問題についての最適計画候
   補の集合を、全体問題の計画として全体問題を処理する
   ことを特徴とする計画立案装置。
6. 【請求項６】請求項１または２において、前記計画立案
   装置はさらに、表示手段を備え、該表示手段は、前記最
   適化手段での計画立案を表示することを特徴とする計画
   立案装置。
7. 【請求項７】与えられた計画対象となる問題において最
   少化または最大化を図る項目を表わす目的関数を作成
   し、該目的関数の値を最少化または最大化する計画を立
   案し、前回立案された計画による目的関数値と新たに立
   案された計画による目的関数値を比較して新たに立案さ
   れた計画が優れている場合に、前回立案した計画を新た
   に立案した計画に置き換え最適計画候補とする計画立案
   方法において、 前記計画対象となる問題が、製造プロセスにおける各工
   程内で能力の異なる使用可能設備が複数有る設備の使用
   パターンを計画するものであり、 前記部分問題が、前記工程毎の使用設備の使用パターン
   の組合せ計画であり、部分最適化処理を行い、各部分問
   題についての最適計画候補の集合を、全体問題の計画と
   して全体問題を処理することを特徴とする計画立案方
   法。