Skip to content

Lam Quoc Anh, Huy Minh Le, Kien Trung Nguyen, Le Xuan Thanh, An algorithmic approach to the robust downgrading makespan scheduling problem

Full Text: PDF
DOI: 10.23952/asvao.6.2024.3.02
Volume 6, Issue 3, 1 December 2024, Pages 263-273

 

Abstract. 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 linear-time 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.

 

How to Cite this Article:
L.Q. Anh, H.M. Le, K.T. Nguyen, L.X. Thanh, An algorithmic approach to the robust downgrading makespan scheduling problem, Appl. Set-Valued Anal. Optim. 6 (2024), 263-273.