フローショップスケジューリングを対象とした列生成法に関する研究

摘要

近年，生産システムは大規模·複雑化の一途を辿っており，柔軟かつ的確な生産スケジューリングが求められてきている．しかしスケジューリング問題は実行可能解の数が膨大であるため厳密解法では現実的な時間での求解が困難である．そこでスケジューリング手法の一つである列生成法の研究がなされている．本研究では総納期遅れ最小化を目的とするフローショップスケジューリング問題に対し，列生成法を用いて解の精度の改善を目的として，列生成子問題における列生成手法に関して新たな手法を提案する．提案手法は，動的計画法で生成された列以外に，その近傍となる列を新たに生成し，追加するといったものである．数値実験により，提案手法の有効性を確認する．