A robust single-machine scheduling problem with scenario-dependent processing times and release dates

• DOI: 10.5267/j.ijiec.2024.11.002
• Publication Date: 2024-12-06T07:49:44Z
• Authors: Chin-Chia Wu; Juin-Han Chen; Win-Chin Lin; Xingong Zhang; Tao Ren; Zong-Lin Wu; Yu-Hsiang Chung
• Keywords: Single-machine scheduling

Many uncertainties arise during the manufacturing process, such as changes in working environment, traffic transportation delays, machine breakdowns, and worker performance instabilities. These factors can cause job processing times ready to change. In this study, we address a scheduling model for single where both release dates are scenario dependent. The objective is minimize total completion time across worst-case scenarios. Even without uncertainty factor, problem NP-hard. To solve it, derive several properties lower bound used branch-and-bound method find an optimal solution. We propose nine heuristics based on linear combination of scenario-dependent approximate solutions. Additionally, offer iterated greedy population-based algorithm that efficiently solves by taking advantage diversity evaluate proposed algorithm.