A Robust Single-Machine Scheduling Problem with Two Job Parameter Scenarios

Abstract

In many real-world environments, machine breakdowns or worker performance instabilities cause uncertainty in job processing times, while working environment changes or transportation delays will postpone finished production for customers. The factors that impact the task processing times and/or deadlines vary. In view of the uncertainty, job processing times and/or job due dates cannot be fixed numbers. Inspired by this fact, we introduce a scenario-dependent processing time and due date concept into a single-machine environment. The measurement minimizes the total job tardiness in the worst case. The same problem without the presence of processing time uncertainty has been an NP-hard problem. First, to solve this difficult model, an exact method, including a lower bound and some dominance properties, is proposed. Next, three scenario-dependent heuristic algorithms are proposed. Additionally, a population-based iterated greedy algorithm is proposed in the hope of increasing the diversity of the solutions. The results of all related algorithms are determined and compared using the appropriate statistical tools.

Keywords

• iterated greedy
• scheduling
• total tardiness
• scenario-dependent