Minimizing worst-case regret of makespan on a single machine with uncertain processing and setup times

作者：Lu Chung Cheng; Lin Shih Wei^*; Ying Kuo Ching

来源：Applied Soft Computing, 2014, 23: 144-151.

DOI：10.1016/j.asoc.2014.06.006

• Single machine scheduling
• Sequence-dependent setup times
• Uncertainty modeling

This research addresses a single machine scheduling problem with uncertain processing times and sequence-dependent setup times represented by intervals. Our objective is to obtain a robust schedule with the minimum absolute deviation from the optimal makespan in the worst-case scenario. The problem is reformulated as a robust traveling salesman problem (RTSP), whereby a property is utilized to efficiently identify worst-case scenarios. A local search-based heuristic that incorporates this property is proposed to solve the RTSP, along with a simulated annealing-based implementation. The effectiveness and efficiency of the proposed heuristic are compared to those of an exact solution method in the literature.

• 出版日期2014-10
• 单位长春大学