バッファ無しジョブショップスケジューリング問題に対する複数仕事の同時処理順序変更（ガントチャート上の不整合に着目した仕事の選択）

概要

論文の詳細を見る
We propose a method for multiple exchanges of job operating orders to find a feasible schedule in the neighborhood of a current plan. The method supports the local search for job shop scheduling problems under no buffer constraint. This constraint results in a blocking state which prevents any new operation after a machine completes one job, and this blocking complicates a partial change of a schedule once made. In the present paper, a tentative time for the operations is scheduled permitting operations disturbing blocking states on machines, and the conflicts between operations and blocking states, or infeasible blocking states, are detected on the Gantt chart if the schedule is infeasible. The procedures of the proposed method are for cancelling infeasible blocking states one by one, and as a result of the cancellations, a feasible schedule is derived by multiple exchanges of job operating orders. The proposed method is adopted to both simple hill climbing and simulated annealing for improvement of a schedule planned by a dispatching rule. The performances are discussed here in comparison with the optimum schedule planned by mathematical programming.
一般社団法人日本機械学会の論文