PBILと厳密解法の融合による繰返しスケジューリング問題の解法

摘要

組合せ最適化問題に対するアプローチとして，計算時間はかかっても厳密解を求める厳密解法と，短い時間で近似解を求めるヒューリスティクス解法がある．本論文では，これらの2つを組合わせて，解の質と計算時間のトレードオフを考慮しながら問題を解く方法を検討している．具体的には，定式化された混合整数計画問題においてメタヒューリスティクスにより，変数の一部分を固定することにより問題の次元を下げ，次元を下げた問題において，厳密解を求めるものである．本研究では，組み合わせ最適化問題として，繰り返しジョブショップスケジューリング問題（Cyclic Job Shop Scheduling Problem （CJSSP））を扱う．