Reactive Schedule Repair of Job Shops

Abstract

Disruptions to job shop schedules are tedious and difficult to incorporate after the schedule has been generated and implemented on the shop floor. In order to deal with such disruptions, a real time reactive scheduling strategy is essential. Reactive scheduling is the process of repairing the predictive schedule during online execution for internal disruptions (e.g. machine breakdowns) and external deviations (e.g. prepone or postpone of orders). Existing approaches for schedule repair in real time mainly utilize heuristics such as Right Shift Rescheduling (RSR), and Affected Operation Rescheduling (AOR). In the present form, both these approaches are only used for handling machine breakdowns in the shop floor, but are inept in accommodating new and unexpected job orders. These approaches also neglect specific issues related to urgent jobs, for instance multiple job routings during the repair of the schedule. In this paper the existing heuristics (RSR and AOR) have been modified to include urgent jobs. Also a modified AOR approach (mAOR) is proposed that considers urgent jobs with multiple job routings. An extensive simulation study has been conducted on a job shop simulation testbed for the efficiency and stability of the repaired schedule using the mAOR and RSR heuristics. The efficiency of the repaired schedule is a measure of the percentage change in the makespan after incorporating repairs whereas the stability of the schedule is a function of starting time deviations that indicate the degree by which it deviates from the original schedule. The results of the experiments indicate significant benefits of the modified AOR algorithm over the existing RSR schedule repair heuristic.