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.
Tạp chí khoa học Trường Đại học Cần Thơ
Lầu 4, Nhà Điều Hành, Khu II, đường 3/2, P. Xuân Khánh, Q. Ninh Kiều, TP. Cần Thơ
Điện thoại: (0292) 3 872 157; Email: tapchidhct@ctu.edu.vn
Chương trình chạy tốt nhất trên trình duyệt IE 9+ & FF 16+, độ phân giải màn hình 1024x768 trở lên