Production in a two-machine flowshop scheduling environment with uncertain processing and setup times to minimize makespan
研究了两机流水车间中加工和准备时间不确定时的调度问题，目标是最小化完工时间。评估了现有支配关系，提出了更有效的支配关系，并开发了25种多项式时间算法实现，最佳实现与最优解的误差小于0.3%。
A wide range of uncertainties exists in some real-world production environments which result in uncertain setup and/or processing times. Factors such as crew skills, shortages in equipment and resource breakdowns can be the sources of these uncertainties. This study considers a two-machine production flowshop scheduling problem where both setup and processing times are treated as uncertain variables. The objective is to minimise makespan which is an effective way of resource utilisation. There exists a dominance relation in the literature for the two-machine flowshop scheduling problem with uncertain setup and processing times. However, the dominance relation has not been evaluated. In this study, we evaluate the existing dominance relation. Moreover, a new dominance relation is established and shown to be more effective than the existing one. Furthermore, twenty-five implementations of a polynomial time algorithm are developed. Extensive computational experiments are conducted to evaluate the performance of the implementations of the algorithm. The computational experiments indicate that the overall gap (error) of the best implementation of the algorithm is less than 0.3% when compared to the optimal solution. Moreover, the performance of this implementation of the algorithm is the best one when compared to the remaining implementations for all the considered experimental environments. Additionally, the performance of this implementation of the algorithm is shown to be insensitive to the uncertainty in setup times.