段取り時間を考慮した1 機械重み付き納期遅れ和最小化問題に対する厳密解法におけるメモリ使用量削減について

摘要

本研究では，スケジューリング問題の一つである，順序依存段取り時間を考慮した1 機械重み付き納期遅れ和最小化問題を対象とする．この問題に対しては，従来より近似解法の研究が盛hに行われており(文献の参考文献参照)，Cicirelloによる60仕事のベンチマーク問題120 題を用いて探索性能を評価するのが一般的となっている．しかし，これらの例題の最適解は，納期遅れが発生しない解が求まった20 題以外は知られていなかった．そこで，著者らは，この問題に対する厳密解法を構成し，最適解が知られていない100 題のうち，89 題に対する最適解を与えた．しかし，残りの11問に関してはメモリ使用量が上限(3.5GB)を超えてしまい，解くことができなかった．そこで，本研究では，dominance theorem および制約伝搬に基づく状態削減，状態の圧縮，さらに分枝により，メモリ使用量の低減を図った．この解法により，新たに9 問の最適解が得られたことを報告する．