Multiple Exchanges of Job Orders for No Buffer Job Shop Scheduling Problem (Identification of Jobs to be Changed on Gantt Chart)

DOI Web Site 1 References

Bibliographic Information

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

Abstract

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.

Journal

References(1)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top