JPH0934715A - 組み合わせ最適化処理方法 - Google Patents
組み合わせ最適化処理方法Info
- Publication number
- JPH0934715A JPH0934715A JP18117395A JP18117395A JPH0934715A JP H0934715 A JPH0934715 A JP H0934715A JP 18117395 A JP18117395 A JP 18117395A JP 18117395 A JP18117395 A JP 18117395A JP H0934715 A JPH0934715 A JP H0934715A
- Authority
- JP
- Japan
- Prior art keywords
- time
- solution
- determined
- job
- neighborhood search
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Withdrawn
Links
Landscapes
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
- Devices For Executing Special Programs (AREA)
Abstract
(57)【要約】
【課題】計算機を用いた組み合わせ最適化処理方法に関
し，スケジューリング問題のような大規模な組み合わせ
最適化問題について高速に準最適解を求めることを可能
とする。 【解決手段】グリーディアルゴリズム１を用いて，まだ
値の決まっていない変数集合の一部分の変数の値を決
め，その部分解２の部分集合を対象として近傍探索３に
よる部分解２の改善を行う。その結果の部分解４をもと
に，さらにグリーディアルゴリズム１による部分解２の
生成と，その一部分に対する近傍探索３とを繰り返し，
最終解５を決定する。
し，スケジューリング問題のような大規模な組み合わせ
最適化問題について高速に準最適解を求めることを可能
とする。 【解決手段】グリーディアルゴリズム１を用いて，まだ
値の決まっていない変数集合の一部分の変数の値を決
め，その部分解２の部分集合を対象として近傍探索３に
よる部分解２の改善を行う。その結果の部分解４をもと
に，さらにグリーディアルゴリズム１による部分解２の
生成と，その一部分に対する近傍探索３とを繰り返し，
最終解５を決定する。
Description
【０００１】
【発明の属する技術分野】本発明は，計算機を用いてス
ケジューリング問題などの組み合わせ最適化問題の解を
求める組み合わせ最適化処理方法に関するものである。
ケジューリング問題などの組み合わせ最適化問題の解を
求める組み合わせ最適化処理方法に関するものである。
【０００２】組み合わせ最適化問題はいろいろなところ
で利用されており，計算機応用技術の一つとして，近
年，ますます重要になってきている。例えば，スケジュ
ーリングは製造業全般に必要な作業であり，人手で行う
のが困難であることから自動処理化のニーズが高い。ス
ケジューリング問題の定式化としては，ジョブショップ
モデルが汎用的であり，広く用いられている。
で利用されており，計算機応用技術の一つとして，近
年，ますます重要になってきている。例えば，スケジュ
ーリングは製造業全般に必要な作業であり，人手で行う
のが困難であることから自動処理化のニーズが高い。ス
ケジューリング問題の定式化としては，ジョブショップ
モデルが汎用的であり，広く用いられている。
【０００３】ジョブショップスケジューリングの例を図
６に示す。各ジョブは複数のオペレーション（作業）か
らなっており，各オペレーションを実行する機械と処理
時間は予め与えられている。利用する機械の順番はジョ
ブごとに異なっていてもよい。図６（Ａ）に示す例で
は，ジョブ１〜３があり，各ジョブはそれぞれ３オペレ
ーションからなる。例えば，ジョブ１は，オペレーショ
ン１，２，３の順序で作業が進められること，オペレー
ション１は機械Ｍ１で５時間，オペレーション２は機械
Ｍ２で８時間，オペレーション３は機械Ｍ３で４時間か
かることなどが問題の条件として与えられる。
６に示す。各ジョブは複数のオペレーション（作業）か
らなっており，各オペレーションを実行する機械と処理
時間は予め与えられている。利用する機械の順番はジョ
ブごとに異なっていてもよい。図６（Ａ）に示す例で
は，ジョブ１〜３があり，各ジョブはそれぞれ３オペレ
ーションからなる。例えば，ジョブ１は，オペレーショ
ン１，２，３の順序で作業が進められること，オペレー
ション１は機械Ｍ１で５時間，オペレーション２は機械
Ｍ２で８時間，オペレーション３は機械Ｍ３で４時間か
かることなどが問題の条件として与えられる。
【０００４】このようなジョブショップスケジューリン
グ問題は，与えられた目的関数を最適にするように，各
機械におけるオペレーションの実行順序を決めることで
ある。この目的関数としてはいろいろなものが用いられ
るが，代表的なものとして，総所要時間（全てのジョブ
の実行が終了する時間）を最小にするものがある。
グ問題は，与えられた目的関数を最適にするように，各
機械におけるオペレーションの実行順序を決めることで
ある。この目的関数としてはいろいろなものが用いられ
るが，代表的なものとして，総所要時間（全てのジョブ
の実行が終了する時間）を最小にするものがある。
【０００５】図６（Ｂ）は，図６（Ａ）に示す条件のジ
ョブショップスケジューリング問題の解の一例を示す。
機械Ｍ１は，オペレーション１，５，９の順序で作業を
行い，機械Ｍ２は，オペレーション４，２，８の順序で
作業を行い，機械Ｍ３は，オペレーション７，６，３の
順序で作業を行い，総所要時間は３０時間となってい
る。なお，この解は最適解ではない。
ョブショップスケジューリング問題の解の一例を示す。
機械Ｍ１は，オペレーション１，５，９の順序で作業を
行い，機械Ｍ２は，オペレーション４，２，８の順序で
作業を行い，機械Ｍ３は，オペレーション７，６，３の
順序で作業を行い，総所要時間は３０時間となってい
る。なお，この解は最適解ではない。
【０００６】
【従来の技術】組み合わせ最適化問題を処理する方法と
しては，大きく分けて，(1) 厳密解法，(2) グリーディ
アルゴリズム，(3) 近傍探索法がある。
しては，大きく分けて，(1) 厳密解法，(2) グリーディ
アルゴリズム，(3) 近傍探索法がある。
【０００７】厳密解法は，全ての組み合わせを網羅的に
探索していく処理方法で，厳密な最適解を発見すること
が保証されているが，ある規模以上の問題に対しては，
処理時間が膨大となり，実際的な時間内で厳密解を発見
することは困難である。
探索していく処理方法で，厳密な最適解を発見すること
が保証されているが，ある規模以上の問題に対しては，
処理時間が膨大となり，実際的な時間内で厳密解を発見
することは困難である。
【０００８】グリーディアルゴリズムは，ある基準に従
って順番に変数の値を決めていく処理方法で，探索を行
わないで解を求める方法である。この方法によれば，一
度決まった変数の値を変更しないために，最適性は保証
されないものの非常に高速に処理することができる。こ
のため大規模な問題に対しては広く用いられている。ス
ケジューリング問題においては，この基準はディスパッ
チング・ルール（dispatching rule）と呼ばれ，いろい
ろなルールが提案されている。
って順番に変数の値を決めていく処理方法で，探索を行
わないで解を求める方法である。この方法によれば，一
度決まった変数の値を変更しないために，最適性は保証
されないものの非常に高速に処理することができる。こ
のため大規模な問題に対しては広く用いられている。ス
ケジューリング問題においては，この基準はディスパッ
チング・ルール（dispatching rule）と呼ばれ，いろい
ろなルールが提案されている。
【０００９】近傍探索法は，限られた時間で，できるだ
け最適な解を求めるための処理方法で，暫定的な初期解
を生成し，その後に解の改善を行っていく。この近傍探
索法として，山登り法，シミュレーテッドアニーリン
グ，タブーサーチなどの方法がある。
け最適な解を求めるための処理方法で，暫定的な初期解
を生成し，その後に解の改善を行っていく。この近傍探
索法として，山登り法，シミュレーテッドアニーリン
グ，タブーサーチなどの方法がある。
【００１０】例えば，山登り法による近傍探索の場合，
現在の解を少し変更して新しい解を生成し（これを近傍
と呼ぶ），解が改善されたときに新しい解に移ることが
行われる。近傍探索法は，大規模な問題に対して有効な
処理方法であるが，それでも問題の規模が大きくなると
近傍の数が増え，急速に効率が悪くなるという問題点が
あった。
現在の解を少し変更して新しい解を生成し（これを近傍
と呼ぶ），解が改善されたときに新しい解に移ることが
行われる。近傍探索法は，大規模な問題に対して有効な
処理方法であるが，それでも問題の規模が大きくなると
近傍の数が増え，急速に効率が悪くなるという問題点が
あった。
【００１１】よく用いられる従来の方法は，前述したグ
リーディアルゴリズムと近傍探索法とを組み合わせて最
終解を求める方法である。図７は，その従来技術の説明
図である。この従来の方法は，まずグリーディアルゴリ
ズム１１を用いて全ての変数の値を決め，次にこれを近
傍探索法における初期解１２として，この初期解１２に
対して近傍探索１３を適用することにより解を改善し，
最終解１４を求めるものである。この方法によれば，比
較的良好な初期値からの探索が可能であるが，やはり問
題の規模が大きくなると近傍の数は増加し，依然として
効率が悪くなるという問題点があった。
リーディアルゴリズムと近傍探索法とを組み合わせて最
終解を求める方法である。図７は，その従来技術の説明
図である。この従来の方法は，まずグリーディアルゴリ
ズム１１を用いて全ての変数の値を決め，次にこれを近
傍探索法における初期解１２として，この初期解１２に
対して近傍探索１３を適用することにより解を改善し，
最終解１４を求めるものである。この方法によれば，比
較的良好な初期値からの探索が可能であるが，やはり問
題の規模が大きくなると近傍の数は増加し，依然として
効率が悪くなるという問題点があった。
【００１２】
【発明が解決しようとする課題】本発明は上記問題点の
解決を図り，スケジューリング問題のような大規模な組
み合わせ最適化問題に対して，近傍の数を減らした効率
のよい近傍探索を行うことができるようにし，高速に最
適解もしくはそれに近い準最適解を求めることができる
ようにすることを目的とする。
解決を図り，スケジューリング問題のような大規模な組
み合わせ最適化問題に対して，近傍の数を減らした効率
のよい近傍探索を行うことができるようにし，高速に最
適解もしくはそれに近い準最適解を求めることができる
ようにすることを目的とする。
【００１３】
【課題を解決するための手段】上記問題を解決するた
め，本発明では，グリーディアルゴリズムによって変数
の集合の一部分の変数の値を決めながら，その部分解に
対して近傍探索を適用することによって部分解を改善
し，効率的に（準）最適解を求めるようにしている。
め，本発明では，グリーディアルゴリズムによって変数
の集合の一部分の変数の値を決めながら，その部分解に
対して近傍探索を適用することによって部分解を改善
し，効率的に（準）最適解を求めるようにしている。
【００１４】図１は，本発明の原理説明図である。図１
（Ｂ）のステップＳ１では，問題のデータが与えられる
と，グリーディアルゴリズム１を用いて，まだ値の決ま
っていない変数の集合の一部分の変数の値を決め，それ
を部分解２とする。グリーディアルゴリズム１は，ある
基準に従って順番に変数の値を決める処理方法であり，
ここで用いるディスパッチング・ルールとしては，通常
用いられる種々のルールが適用できる。
（Ｂ）のステップＳ１では，問題のデータが与えられる
と，グリーディアルゴリズム１を用いて，まだ値の決ま
っていない変数の集合の一部分の変数の値を決め，それ
を部分解２とする。グリーディアルゴリズム１は，ある
基準に従って順番に変数の値を決める処理方法であり，
ここで用いるディスパッチング・ルールとしては，通常
用いられる種々のルールが適用できる。
【００１５】ステップＳ２では，既に値の決まった変数
集合（部分解２）の部分集合を対象として，近傍探索３
を適用し部分解２の改善を行う。近傍探索３により部分
解２を改善したものを部分解４とする。近傍探索３とし
て，例えば山登り法，シミュレーテッドアニーリング，
タブーサーチなどの方法のいずれも適用できる。
集合（部分解２）の部分集合を対象として，近傍探索３
を適用し部分解２の改善を行う。近傍探索３により部分
解２を改善したものを部分解４とする。近傍探索３とし
て，例えば山登り法，シミュレーテッドアニーリング，
タブーサーチなどの方法のいずれも適用できる。
【００１６】ステップＳ３では，全ての変数の値が決ま
ったかどうかを判定し，全ての変数の値が決まるまでス
テップＳ１，Ｓ２の処理を繰り返す。次のステップＳ１
では，部分解４をもとに，再度，部分的なグリーディア
ルゴリズム１による部分解２の生成を行う。さらに部分
解２に対して近傍探索３を繰り返していく。全ての変数
の値が決まった場合には，それを最終解５として処理を
終了する。
ったかどうかを判定し，全ての変数の値が決まるまでス
テップＳ１，Ｓ２の処理を繰り返す。次のステップＳ１
では，部分解４をもとに，再度，部分的なグリーディア
ルゴリズム１による部分解２の生成を行う。さらに部分
解２に対して近傍探索３を繰り返していく。全ての変数
の値が決まった場合には，それを最終解５として処理を
終了する。
【００１７】以上の方法をジョブのスケジューリング問
題に適用する場合，例えば以下のように行う。 現時刻ｔを初期化する。 現時刻ｔに所定の第１の時間assigntimeを加えた値
を，現時刻ｔとする。 グリーディアルゴリズム１を用いて，現時刻ｔまで
ジョブを配置する。それを部分解２とする。 部分解２における，現時刻ｔと所定の第１の時間as
signtimeと所定の第２の時間margintime，または現時刻
ｔと所定の第１の時間assigntimeと所定の第２の時間ma
rgintimeと所定の第３の時間rescheduletimeとによって
定まる時間について，近傍探索３を適用し，スケジュー
ルの改善を行う。その結果を部分解４とする。 部分解４において，現時刻ｔと所定の第１の時間ma
rgintimeとによって定まる時刻以後のジョブを削除す
る。
題に適用する場合，例えば以下のように行う。 現時刻ｔを初期化する。 現時刻ｔに所定の第１の時間assigntimeを加えた値
を，現時刻ｔとする。 グリーディアルゴリズム１を用いて，現時刻ｔまで
ジョブを配置する。それを部分解２とする。 部分解２における，現時刻ｔと所定の第１の時間as
signtimeと所定の第２の時間margintime，または現時刻
ｔと所定の第１の時間assigntimeと所定の第２の時間ma
rgintimeと所定の第３の時間rescheduletimeとによって
定まる時間について，近傍探索３を適用し，スケジュー
ルの改善を行う。その結果を部分解４とする。 部分解４において，現時刻ｔと所定の第１の時間ma
rgintimeとによって定まる時刻以後のジョブを削除す
る。
【００１８】以後，処理〜を繰り返し，全てのジョ
ブの配置が終了したならば，その結果を最終解５とし
て，処理を終了する。
ブの配置が終了したならば，その結果を最終解５とし
て，処理を終了する。
【００１９】
【発明の実施の形態】以下，本発明の実施の形態とし
て，本発明をジョブショップスケジューリング問題に適
用した場合について説明する。なお，ジョブショップス
ケジューリング問題以外の組み合わせ最適化問題にも，
同様に本発明を適用することが可能である。
て，本発明をジョブショップスケジューリング問題に適
用した場合について説明する。なお，ジョブショップス
ケジューリング問題以外の組み合わせ最適化問題にも，
同様に本発明を適用することが可能である。
【００２０】図２は，本発明をジョブショップスケジュ
ーリング問題に適用した場合の動作例を説明する図，図
３は，本実施の形態における処理フローチャートであ
る。処理のパラメータとして，assigntime，margintim
e，rescheduletimeを用いる。これらは予め用意された
定数であっても，外部から値が与えられる変数であって
もいずれでもよい。assigntimeは，１回分のグリーディ
アルゴリズムと近傍探索によって，ジョブが配置される
範囲を定める時間である。margintimeは，近傍探索の実
行結果に対して，ジョブの削除対象となる範囲を定める
時間である。rescheduletimeは，既に近傍探索が行われ
て値が定まった変数値のうち，再度近傍探索の対象とな
る範囲を定める時間である。
ーリング問題に適用した場合の動作例を説明する図，図
３は，本実施の形態における処理フローチャートであ
る。処理のパラメータとして，assigntime，margintim
e，rescheduletimeを用いる。これらは予め用意された
定数であっても，外部から値が与えられる変数であって
もいずれでもよい。assigntimeは，１回分のグリーディ
アルゴリズムと近傍探索によって，ジョブが配置される
範囲を定める時間である。margintimeは，近傍探索の実
行結果に対して，ジョブの削除対象となる範囲を定める
時間である。rescheduletimeは，既に近傍探索が行われ
て値が定まった変数値のうち，再度近傍探索の対象とな
る範囲を定める時間である。
【００２１】ステップＳ１１では，時刻ｔをｔ＝margin
timeに初期化する。ステップＳ１２では，時刻ｔからma
rgintimeを引いた時刻（ｔ−margintime）または時刻０
のいずれか遅いほうの時刻以後のジョブを削除する。初
回の場合は，時刻ｔ＝margintimeであり，削除すべきジ
ョブはない。
timeに初期化する。ステップＳ１２では，時刻ｔからma
rgintimeを引いた時刻（ｔ−margintime）または時刻０
のいずれか遅いほうの時刻以後のジョブを削除する。初
回の場合は，時刻ｔ＝margintimeであり，削除すべきジ
ョブはない。
【００２２】ステップＳ１３では，時刻ｔにassigntime
を加え，現時刻を（ｔ＋assigntime）に進める。ステッ
プＳ１４では，グリーディアルゴリズムを用いて，時刻
ｔまでのジョブの配置を行う。最初，図２（Ａ）に示す
時刻ｔまでの配置区間Ｇ1 について，所定のディスパッ
チング・ルーチンによりジョブが配置されることにな
る。
を加え，現時刻を（ｔ＋assigntime）に進める。ステッ
プＳ１４では，グリーディアルゴリズムを用いて，時刻
ｔまでのジョブの配置を行う。最初，図２（Ａ）に示す
時刻ｔまでの配置区間Ｇ1 について，所定のディスパッ
チング・ルーチンによりジョブが配置されることにな
る。
【００２３】ステップＳ１５では，時刻（ｔ−marginti
me−assigntime−rescheduletime）または時刻０のいず
れか遅いほうの時刻から，時刻（ｔ−margintime）また
は時刻０のいずれか遅いほうの時刻までの区間につい
て，近傍探索を適用してジョブの再配置を行う。最初，
図２（Ｂ）に示すように，時刻０から時刻（ｔ−margin
time）までの区間Ｎ1 について, 近傍探索によるジョブ
の再配置が行われることになる。なお，ここで近傍探索
の対象となるジョブは，区間Ｎ1 にその一部分でも含ま
れるジョブである。
me−assigntime−rescheduletime）または時刻０のいず
れか遅いほうの時刻から，時刻（ｔ−margintime）また
は時刻０のいずれか遅いほうの時刻までの区間につい
て，近傍探索を適用してジョブの再配置を行う。最初，
図２（Ｂ）に示すように，時刻０から時刻（ｔ−margin
time）までの区間Ｎ1 について, 近傍探索によるジョブ
の再配置が行われることになる。なお，ここで近傍探索
の対象となるジョブは，区間Ｎ1 にその一部分でも含ま
れるジョブである。
【００２４】ステップＳ１６では，全てのジョブが配置
されて，かつ，最終ジョブの実行終了時刻が時刻（ｔ−
margintime）より早いかどうかを判定する。全てのジョ
ブが配置されて，かつ，最終ジョブの実行終了時刻が時
刻（ｔ−margintime）より早い場合には処理を終了す
る。全てのジョブの配置が完了していないか，または，
最終ジョブの実行終了時刻が時刻（ｔ−margintime）よ
り遅い場合にはステップＳ１２の処理へ戻る。
されて，かつ，最終ジョブの実行終了時刻が時刻（ｔ−
margintime）より早いかどうかを判定する。全てのジョ
ブが配置されて，かつ，最終ジョブの実行終了時刻が時
刻（ｔ−margintime）より早い場合には処理を終了す
る。全てのジョブの配置が完了していないか，または，
最終ジョブの実行終了時刻が時刻（ｔ−margintime）よ
り遅い場合にはステップＳ１２の処理へ戻る。
【００２５】図２の例では，図２（Ｂ）の状態の後，ス
テップＳ１２へ戻り，時刻（ｔ−margintime）以降の暫
定的に配置された部分，すなわち図２（Ｃ）に示す削除
区間について，ジョブの削除が行われる。この後，ステ
ップＳ１３，Ｓ１４の実行により，図２（Ｄ）に示す新
しい時刻ｔまでの配置区間Ｇ2 について，グリーディア
ルゴリズムのディスパッチング・ルールを用いたジョブ
の配置が行われる。
テップＳ１２へ戻り，時刻（ｔ−margintime）以降の暫
定的に配置された部分，すなわち図２（Ｃ）に示す削除
区間について，ジョブの削除が行われる。この後，ステ
ップＳ１３，Ｓ１４の実行により，図２（Ｄ）に示す新
しい時刻ｔまでの配置区間Ｇ2 について，グリーディア
ルゴリズムのディスパッチング・ルールを用いたジョブ
の配置が行われる。
【００２６】続いてステップＳ１５により，図２（Ｅ）
に示すように，探索区間Ｎ1 のうちrescheduletimeに相
当する区間と配置区間Ｇ2 のうちassigntimeに相当する
区間を合わせた探索区間Ｎ2 について，近傍探索を適用
してジョブの配置の改善が行われる。このとき，resche
uduletime 分の区間については，前回の近傍探索が行わ
れた区間について，もう一度近傍探索が行われることに
なる。
に示すように，探索区間Ｎ1 のうちrescheduletimeに相
当する区間と配置区間Ｇ2 のうちassigntimeに相当する
区間を合わせた探索区間Ｎ2 について，近傍探索を適用
してジョブの配置の改善が行われる。このとき，resche
uduletime 分の区間については，前回の近傍探索が行わ
れた区間について，もう一度近傍探索が行われることに
なる。
【００２７】次に，ステップＳ１６を経て，ステップＳ
１２により，図２（Ｆ）に示すように，配置区間Ｇ2 の
うちmargintimeに相当する区間のジョブが削除され，以
下，同様にグリーディアルゴリズムによるジョブの配置
と近傍探索とが繰り返される。
１２により，図２（Ｆ）に示すように，配置区間Ｇ2 の
うちmargintimeに相当する区間のジョブが削除され，以
下，同様にグリーディアルゴリズムによるジョブの配置
と近傍探索とが繰り返される。
【００２８】
【実施例】図４および図５は，本発明の実施例によるジ
ョブショップスケジューリングの具体例を説明する図で
ある。以下，図４および図５に従って，図６（Ａ）に示
すジョブショップスケジューリング問題について，本発
明を適用した場合の処理を説明する。
ョブショップスケジューリングの具体例を説明する図で
ある。以下，図４および図５に従って，図６（Ａ）に示
すジョブショップスケジューリング問題について，本発
明を適用した場合の処理を説明する。
【００２９】まず，図４（Ａ）に示すように，時刻０か
ら時刻ｔ（ｔ＝margintime＋assigntime）までの区間に
ついて, グリーディアルゴリズムにより，ジョブをオペ
レーションの実行順序に従って，各機械（Ｍ１〜Ｍ３）
に配置する。ディスパッチング・ルールとしては，例え
ば，空き機械においてすぐに実行可能なオペレーション
のうち，処理時間が長いものを優先して配置する，とい
うような基準を用いる。
ら時刻ｔ（ｔ＝margintime＋assigntime）までの区間に
ついて, グリーディアルゴリズムにより，ジョブをオペ
レーションの実行順序に従って，各機械（Ｍ１〜Ｍ３）
に配置する。ディスパッチング・ルールとしては，例え
ば，空き機械においてすぐに実行可能なオペレーション
のうち，処理時間が長いものを優先して配置する，とい
うような基準を用いる。
【００３０】ここでは，機械Ｍ１に対して，オペレーシ
ョン１，オペレーション５の順でジョブを配置し，機械
Ｍ２に対して，オペレーション４，オペレーション２，
オペレーション８の順でジョブを配置し，機械Ｍ３に対
して，オペレーション７，オペレーション６の順でジョ
ブを配置している。
ョン１，オペレーション５の順でジョブを配置し，機械
Ｍ２に対して，オペレーション４，オペレーション２，
オペレーション８の順でジョブを配置し，機械Ｍ３に対
して，オペレーション７，オペレーション６の順でジョ
ブを配置している。
【００３１】続いて，図４（Ｂ）に示すように，assign
time分の区間に対して, 近傍探索を実行し，オペレーシ
ョンの配置を改善する（この例では，簡単な例を扱って
いるため，図４（Ａ）から図４（Ｂ）においては近傍探
索による改善は行われていないが，通常の問題ではオペ
レーションの並べ替えにより配置が改善されることにな
る）。改善されたかどうかは，探索区間のオペレーショ
ンを実行可能な範囲で並べ替えたとき，最終オペレーシ
ョンの終了時刻が早くなったかどうかで判断する。この
例では，図４（Ａ）の状態から，オペレーション１，
５，４，２，７，６に対する近傍探索が行われている
が，これ以上の改善はできないので，図４（Ｂ）の結果
が図４（Ａ）と同じ状態で，次へ進む。
time分の区間に対して, 近傍探索を実行し，オペレーシ
ョンの配置を改善する（この例では，簡単な例を扱って
いるため，図４（Ａ）から図４（Ｂ）においては近傍探
索による改善は行われていないが，通常の問題ではオペ
レーションの並べ替えにより配置が改善されることにな
る）。改善されたかどうかは，探索区間のオペレーショ
ンを実行可能な範囲で並べ替えたとき，最終オペレーシ
ョンの終了時刻が早くなったかどうかで判断する。この
例では，図４（Ａ）の状態から，オペレーション１，
５，４，２，７，６に対する近傍探索が行われている
が，これ以上の改善はできないので，図４（Ｂ）の結果
が図４（Ａ）と同じ状態で，次へ進む。
【００３２】次に，図４（Ｃ）に示すように，配置済み
ジョブの削除を行う。削除区間は，時刻（ｔ−marginti
me）から時刻ｔまでの区間であり，この区間にかかって
いるオペレーション２，６，８が削除されることにな
る。
ジョブの削除を行う。削除区間は，時刻（ｔ−marginti
me）から時刻ｔまでの区間であり，この区間にかかって
いるオペレーション２，６，８が削除されることにな
る。
【００３３】その後，図５（Ａ）に示すように，グリー
ディアルゴリズムによるジョブの配置を行う。ジョブを
配置する区間は，元の時刻ｔにassigntimeを加えた新し
い時刻ｔまでとする。ここでは，図４（Ｃ）に示す状態
から，さらに機械Ｍ２に対してオペレーション２，機械
Ｍ３に対してオペレーション６，機械Ｍ２に対してオペ
レーション８，機械Ｍ３に対してオペレーション３，機
械Ｍ１に対してオペレーション９を順に配置している。
ディアルゴリズムによるジョブの配置を行う。ジョブを
配置する区間は，元の時刻ｔにassigntimeを加えた新し
い時刻ｔまでとする。ここでは，図４（Ｃ）に示す状態
から，さらに機械Ｍ２に対してオペレーション２，機械
Ｍ３に対してオペレーション６，機械Ｍ２に対してオペ
レーション８，機械Ｍ３に対してオペレーション３，機
械Ｍ１に対してオペレーション９を順に配置している。
【００３４】次に，図５（Ｂ）に示すように，近傍探索
を実行する。近傍探索の適用区間は，時刻（ｔ−margin
time−assigntime−rescheduletime）から時刻（ｔ−ma
rgintime）までである。rescheduletime分の区間につい
ては，前回の近傍探索が行われた区間についてもう一度
近傍探索が行われることになる。図５（Ｂ）では，機械
Ｍ２において，オペレーション８とオペレーション２の
実行順序が入れ替わり，これによって全ジョブの実行終
了時刻の改善がなされている。
を実行する。近傍探索の適用区間は，時刻（ｔ−margin
time−assigntime−rescheduletime）から時刻（ｔ−ma
rgintime）までである。rescheduletime分の区間につい
ては，前回の近傍探索が行われた区間についてもう一度
近傍探索が行われることになる。図５（Ｂ）では，機械
Ｍ２において，オペレーション８とオペレーション２の
実行順序が入れ替わり，これによって全ジョブの実行終
了時刻の改善がなされている。
【００３５】これにより，すべてのジョブの配置とその
改善が行われたことになるので，図５（Ｂ）に示す結果
を最終解として出力する。
改善が行われたことになるので，図５（Ｂ）に示す結果
を最終解として出力する。
【００３６】
【発明の効果】以上説明したように，本発明によれば，
スケジューリング問題のような大規模な組み合わせ最適
化問題に対して，近傍の数を減らした近傍探索を行うこ
とができるので，高速に最適解もしくはそれに近い準最
適解を求めることができる。
スケジューリング問題のような大規模な組み合わせ最適
化問題に対して，近傍の数を減らした近傍探索を行うこ
とができるので，高速に最適解もしくはそれに近い準最
適解を求めることができる。
【図１】本発明の原理説明図である。
【図２】本発明をジョブショップスケジューリング問題
に適用した場合の動作例を説明する図である。
に適用した場合の動作例を説明する図である。
【図３】本実施の形態における処理フローチャートであ
る。
る。
【図４】本発明の実施例によるジョブショップスケジュ
ーリングの具体例を説明する図である。
ーリングの具体例を説明する図である。
【図５】本発明の実施例によるジョブショップスケジュ
ーリングの具体例を説明する図である。
ーリングの具体例を説明する図である。
【図６】ジョブショップスケジューリングを説明する図
である。
である。
【図７】従来技術の説明図である。
１ グリーディアルゴリズム ２ 部分解 ３ 近傍探索 ４ 部分解 ５ 最終解
Claims (3)
- 【請求項１】 計算機を用いて組み合わせ最適化問題を
処理する方法において，グリーディアルゴリズムを用い
て，まだ値の決まっていない変数集合の一部分の変数の
値を決め，部分解を定める第１の過程と，既に値の決ま
った変数集合の部分集合を対象として近傍探索を適用
し，部分解の改善を行う第２の過程とを有し，最終解が
定まるまで前記第１の過程と第２の過程とを繰り返すこ
とを特徴とする組み合わせ最適化処理方法。 - 【請求項２】 請求項１記載の組み合わせ最適化処理方
法において，前記第２の過程と，次の繰り返しにおける
前記第１の過程との間に，近傍探索によって新たに値の
決まった変数集合の一部分の値を削除する過程を有する
ことを特徴とする組み合わせ最適化処理方法。 - 【請求項３】 計算機を用いてジョブのスケジューリン
グに関する組み合わせ最適化問題を処理する方法におい
て，現時刻を初期化する過程と，現時刻に所定の第１の
時間を加えた値を，現時刻とする過程と，グリーディア
ルゴリズムを用いて，現時刻までジョブを配置する過程
と，現時刻と前記所定の第１の時間と所定の第２の時
間，または現時刻と前記所定の第１の時間と所定の第２
の時間と所定の第３の時間とによって定まる時間につい
て，近傍探索を適用し，スケジュールの改善を行う過程
と，現時刻と前記所定の第２の時間とによって定まる時
刻以後のジョブを削除する過程とを有し，最終解が定ま
るまで前記現時刻を初期化する過程を除く過程を繰り返
すことを特徴とする組み合わせ最適化処理方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP18117395A JPH0934715A (ja) | 1995-07-18 | 1995-07-18 | 組み合わせ最適化処理方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP18117395A JPH0934715A (ja) | 1995-07-18 | 1995-07-18 | 組み合わせ最適化処理方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH0934715A true JPH0934715A (ja) | 1997-02-07 |
Family
ID=16096168
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP18117395A Withdrawn JPH0934715A (ja) | 1995-07-18 | 1995-07-18 | 組み合わせ最適化処理方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0934715A (ja) |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2003204624A (ja) * | 2002-01-08 | 2003-07-18 | Mitsubishi Electric Corp | 離散値を含む最適化問題の解法 |
| JP2007084201A (ja) * | 2005-09-21 | 2007-04-05 | Jfe Steel Kk | スラブヤードの置場管理方法および装置 |
| US8195496B2 (en) * | 2008-11-26 | 2012-06-05 | Sap Aktiengesellschaft | Combining multiple objective functions in algorithmic problem solving |
| WO2013133366A1 (ja) * | 2012-03-09 | 2013-09-12 | 新日鐵住金株式会社 | ヤード管理装置、ヤード管理方法およびコンピュータプログラム |
-
1995
- 1995-07-18 JP JP18117395A patent/JPH0934715A/ja not_active Withdrawn
Cited By (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2003204624A (ja) * | 2002-01-08 | 2003-07-18 | Mitsubishi Electric Corp | 離散値を含む最適化問題の解法 |
| JP2007084201A (ja) * | 2005-09-21 | 2007-04-05 | Jfe Steel Kk | スラブヤードの置場管理方法および装置 |
| US8195496B2 (en) * | 2008-11-26 | 2012-06-05 | Sap Aktiengesellschaft | Combining multiple objective functions in algorithmic problem solving |
| WO2013133366A1 (ja) * | 2012-03-09 | 2013-09-12 | 新日鐵住金株式会社 | ヤード管理装置、ヤード管理方法およびコンピュータプログラム |
| JP5365759B1 (ja) * | 2012-03-09 | 2013-12-11 | 新日鐵住金株式会社 | ヤード管理装置、ヤード管理方法およびコンピュータプログラム |
| US10032128B2 (en) | 2012-03-09 | 2018-07-24 | Nippon Steel & Sumitomo Metal Corporation | Yard management apparatus, yard management method, and computer program |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH05250377A (ja) | スケジューリング方式 | |
| CN110716522B (zh) | 基于任意时间a*启发式搜索的制造企业车间调度优化方法 | |
| CN115640898B (zh) | 一种基于ddqn算法的大规模柔性作业车间调度方法 | |
| CN107730029B (zh) | 基于量子行为粒子群算法的生产制造过程优化方法和装置 | |
| JPH09304570A (ja) | 炉心装荷配置を決定する方法 | |
| CN115222107B (zh) | 一种可重入混合流水车间调度问题的优化方法及装置 | |
| Holtsclaw et al. | Machine criticality measures and subproblem solution procedures in shifting bottleneck methods: a computational study | |
| JPH09320918A (ja) | 生産制御システムおよび生産制御方法 | |
| JPH0934715A (ja) | 組み合わせ最適化処理方法 | |
| He et al. | An exchange heuristic imbedded with simulated annealing for due-dates job-shop scheduling | |
| Halperin et al. | Optimal randomized erew pram algorithms for finding spanning forests | |
| CN110852500B (zh) | 一种资源受限混合流水车间优化方法 | |
| JPH086630A (ja) | 生産スケジュール作成装置 | |
| CN119228072A (zh) | 考虑调整时间的柔性作业车间调度问题的优化方法 | |
| US5568381A (en) | Combinatorial optimization system that extracts an undersirable relationship from a present solution | |
| Crauwels et al. | Branch and bound algorithms for single machine scheduling with batching to minimize the number of late jobs | |
| Shih et al. | A fast algorithm for scheduling imprecise computations with timing constraints to minimize weighted error | |
| CN117933632A (zh) | 一种基于学习遗忘效应的流水车间调度优化方法及系统 | |
| CN112269648B (zh) | 一种多阶段程序分析的并行任务分配方法及装置 | |
| US5933348A (en) | Method for biasing designs of experiments | |
| JPH07234897A (ja) | 生産スケジュール作成装置 | |
| Wang et al. | Hybrid flow shop scheduling of new arrival jobs and locked jobs | |
| CN119151082B (zh) | 一种求解分布式异构流水车间成组调度的优化方法 | |
| Kim et al. | Resource-Constrained Parallel Machine Scheduling for Tire Manufacturing | |
| KR102828856B1 (ko) | 작업 스케줄링 방법 및 작업 스케줄링을 수행하는 서버 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A300 | Application deemed to be withdrawn because no request for examination was validly filed |
Free format text: JAPANESE INTERMEDIATE CODE: A300 Effective date: 20021001 |