An algorithmic approach to the robust downgrading makespan scheduling problem

This paper addresses the robust downgrading (single-machine) makespan scheduling problem, a scheduling challenge where processing times are augmented at a minimum cost to achieve a specified downgrading level in the makespan.The associated costs are modeled as intervals, and we employ the minmax regret criterion to handle uncertainty.The deterministic case is initially examined with a lineartime algorithm.Subsequently, the robust version of the problem is transformed into a single-variable objective, characterized by a piecewise linear function.Then, we develop a combinatorial algorithm with polynomial time complexity to solve the corresponding problem.