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

Abstract

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