二重評価尺度に基づく単一工程スケジューリング問題

概要

論文の詳細を見る
スケジューリング問題において、目標とする評価尺度に基づく最適解が複数個存在する場合がある。そのような場合に、第2の評価尺度を用いて最適スケジュールを選択する問題は、二重評価尺度問題とよばれ、Smith(1956)以来いくつかの研究がなされている。Smithは最大納期遅れ時間をゼロに(最適化)するという条件下で、重みつき平均滞留時間を最小にする単一工程スケジューリング問題を取りあげた。HeckとRoberts(1972)は、Smithの結果を最大納期遅れ時間が正の場合に拡張した。Smithらの提案したアルゴリズムは、のちにEmmons(1975)やBurns(1976)らによって最適化アルゴリズムではないことが反例で示された。しかし、どのような条件のもとで最適解が得られないかの解析は行われていない。本研究では、Smithらのアルゴリズムで得られる隣接ジョブに関する最適スケジュールが全ジョブに関する最適解に一致しない場合の必要条件と、そのときの改善スケジュールを与える定理を導く。その定理に基づいて、従来の手法よりさらに多くの問題で最適解を得ることのできるアルゴリズムを提案する。提案したアルゴリズムの有効性を検証するために、ジョブ数を4水準(8、10、12、15)に設定して数値実験を行った。例題では、納期の厳しさおよび納期のバラツキがアルゴリズムに専える影響を調べるために4タイプの納期を設定した。またジョブの重みは、1〜10と1〜40の2種類の一様乱数で与えた。上述の三つの要因(ジョブ数、納期、重み)の組合せすべてについてそれぞれ10個の問題をランダムに作成した。このようにして得た合計320種類(4×4×2×10)の問題を、提案アルゴリズム、Smithのアルゴリズム、Burnsのアルゴリズムで解いた。上記の三つのアルゴリズムで求めた解とDPによる最適解とを比較したところ、次のような結果が得られた。提案アルゴリズムによる解は、3問題で最適解に一致しなかったものの、他はすべて最適解に一致した。一方、Smithで最適解の得られたかったのは38問題、Burnsでは20問題であった。Burnsの計算時間は、ジョブ数の3乗に比例し、実験データでもそのことが確かめられた。提案アルゴリズムの計算時間は、ジョブ数の3乗未満のオーダであり、実験データではジョブ数とほぼ線形の関係になった。また必要な主記憶容量は、提案アルゴリズムの場合ジョブ数と線形の関係にあり、大規模な問題を解く際の障害とならない。DPの計算時間、記憶容量は指数的に増大し、ジョブ数が増加した場合の致命的な障害となる。得られる解の性質、および計算時間や記憶容量の点で、提案アルゴリズムは実用上効果を発揮するものと思われる。
社団法人日本オペレーションズ・リサーチ学会の論文

著者

宮崎茂次
大阪府立大学

二重評価尺度に基づく単一工程スケジューリング問題

スポンサーリンク

概要

著者

関連論文

スポンサーリンク