Min–Max Regret Single Machine Scheduling with Due-Date Assignment and Interval Processing Times

In real-world production systems, particularly in customized manufacturing environments, when making due-date assignment and scheduling decisions, decision makers often can’t estimate processing times precisely, but can leverage historical data or domain expertise to bound these uncertainties within interval ranges. In view of this, we investigate a single machine scheduling problem with due-date assignment and stochastic processing times, where only the lower and upper bounds of processing times are known to the decision maker. The objective is to simultaneously determine a scheduling policy and a set of due dates, so as to minimize the worst-case absolute deviation from optimality for the performance criterion of total non-individually weighted costs for earliness, tardiness and due-date assignment. To address the problem, we first formulate the min–max regret problem, discuss the determination of the worst-case scenario and analyze the optimal due-date assignment under a given schedule. Based on these analyzed properties, we show the complexity of the problem and propose three heuristic algorithms, including the midpoint scenario-based heuristic, the midpoint due-date-based heuristic, and the local search algorithm. Finally, a series of computational experiments are conducted to evaluate the performance of the solution algorithms and analyze the influence of various parameters.