Iterative Repair Approach to Job Shop Scheduling in a Dynamic Environment

Abstract

In this paper, we propose an approach for job-shop scheduling based on iterative repair. This approach starts with a heuristically generated schedule which may be infeasible, then applies local search techniques to generate a good conflict-free schedule. The proposed system will not only generate a feasible schedule, but also maintain the schedule to react to "disturbance", such as the insertion/deletion of a job, that occurs during the execution of the scheduled events on a shop floor. This approach can be adapted to different performance measures for job-shop scheduling and even to different scheduling applications. The implementation examines a due-date-based performance measure: weighted job tardiness. Experimental results show the efficiency and effectiveness of this approach for both of the static schedule generation and dynamic rescheduling problems.