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.

Graphical abstractFigure optionsDownload full-size imageDownload as PowerPoint slide