A comparative study to minimize the makespan of parallel-machine problem with job arrival in uncertainty

摘要

The continuously occurring random and unpredictable events in the manufacturing factories might change the system status or have negative impacts on the system, which includes dynamic order arriving, machine breakdowns, rush orders, due date changes, material shortages, or quality problems.Some proper actions such as rescheduling should be triggered to counter the impacts of dynamic arrival of jobs. In this paper,we develop a parallel insertion algorithm implemented with rescheduling criteria to minimize the makespan of parallel-machine problem with job arrival in uncertainty and sequence-dependent setup time. Furthermore, we provide the probabilistic model to estimate the makespan for identical parallel-machine problem with the inter-arrival time of jobs exponentially distributed and sequence-dependent setup time under the FIFO rule. Since the probabilistic model is under FIFO rule, which is a common and simple dispatching rule, the expected makespan generated by probability model can be regarded as a lower standard in performance comparison and be used to evaluate the superiority of scheduling algorithm, such as Parallel Insertion. The larger the deviation between the makespan respectively determined by the FIFO rule and the algorithm, the more superiority of the algorithm can be concluded. A comparative computation including the results by the LPT rule is provided to demonstrate the effectiveness of the proposed algorithm.