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

• Address the robust single machine scheduling with uncertain job data.
• Represent uncertain processing times and setup times using intervals.
• Minimize the absolute deviation from the optimal makespan in worst case scenario.
• Reformulate the problem as a robust traveling salesman problem.
• Propose a local search-based heuristic to solve the reformulated problem.

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.

Figure optionsDownload as PowerPoint slide