Reactive scheduling to minimize makespan of parallel-machine problem with job arrival in uncertainty

摘要

Unpredictable events such as uncertain job arrivals might change the system status or affect the system negatively. Proper actions, such as rescheduling, should be triggered to keep the performance of the system at a specific level. The adoption of the event-driven rescheduling policy counters the impacts of dynamic arrival of jobs, and the parallel insertion algorithm with adjusting procedure is designed to minimize makespan of parallel-machine problem with sequence-dependent setup time. To estimate makespan, probabilistic model is developed with exponentially distributed inter-arrival time and sequence-dependent setup time for identical parallel-machine under First-in First-out (FIFO) rule. The estimated makespan under FIFO can be regarded as a lower level of standard in performance comparison because FIFO is a simple and widely used dispatching rule, which can be used to evaluate the superiority of the proposed scheduling algorithm. The larger the difference between makespans, respectively determined by the probabilistic model under FIFO and the proposed algorithm, the more superior algorithm can be concluded. Comparative computations are provided to demonstrate the effectiveness of the proposed algorithm and the accuracy of the probabilistic model in estimating makespan and setup time.