ブロッキングジョブショップスケジューリング問題を解決するための再構築戦略に基づく効率的なタブーサーチの近傍

ブロッキングジョブショップスケジューリング問題（BJSS）は、機械間に中間バッファがない古典的なジョブショップスケジューリングのバージョンです。BJSSは強い意味でNP困難であることが知られています。このような問題を解決するための既知の方法は、最適化問題を解決するために設計されたより高次のヒューリスティック手法であるタブーサーチアルゴリズム（TS）を使用することです。これは他の方法が局所最適に捕らわれるのを逃れる手助けをします。しかし、BJSS問題で古典的なTS近傍を使用することは、ほとんどの場合（98%のケース）不適切な解を生じさせます。これにより、不適切な解を探索するのに貴重な時間を浪費することになります。この欠点を克服するために、私たちは再構築戦略に基づく新しいタブーサーチの近傍を提案します。この近傍は、不適合を引き起こす弧を取り除き、ヒューリスティックスを使用して隣接解を再構築する構成になっています。参照ベンチマークインスタンスに関する実験では、提案された近傍を使用したTSアルゴリズムが文献のほとんどの既知の結果を改善し、BJSSの両ケース（スワップがあるBJSSとスワップがないBJSS）で52以上のベンチマークに対して新しい上限を提供することが示されました。さらに、提案されたアプローチは最適に解決されたベンチマークのほとんどに対して、最適解に非常に迅速に到達します。