An improved heuristic for parallel machine scheduling with rejection

作者：Ou, Jinwen; Zhong, Xueling^*; Wang, Guoqing

来源：European Journal of Operational Research, 2015, 241(3): 653-661.

DOI：10.1016/j.ejor.2014.09.028

• Scheduling
• Rejection
• Heuristic
• Worst-case bound

In this paper we study a classical parallel machine scheduling model with m machines and n jobs, where each job is either accepted and then processed by one of the machines, or rejected and then a rejection penalty is paid. The objective is to minimize the completion time of the last accepted job plus the total penalty of all rejected jobs. The scheduling problem is known to be NP-hard in the strong sense. We find some new optimal properties and develop an O(n log n + n/is an element of) heuristic to solve the problem with a worst-case bound of 1.5 + is an element of, where is an element of > 0 can be any small given constant. This improves upon the worst-case bound 2 - 1/m, of the heuristic presented by Bartal et al. (Bartal, Y., Leonardi, S., Marchetti-Spaccamela, A., Sgall, J., & Stougie, L (2000). Multiprocessor scheduling with rejection. SIAM Journal on Discrete Mathematics, 13, 64-78) in the scheduling literature.

• 出版日期2015-3-16
• 单位暨南大学; 广东金融学院