Improved approximation algorithms for parallel machine scheduling with release dates and job rejection. (English) Zbl 1387.90099
Summary: In this paper, we study a parallel machine scheduling model with different job release dates, where each job is either accepted and processed by a machine at or after its release date, or it is rejected and a certain penalty cost is paid. The objective is to minimize the makespan of the accepted job plus the total penalty of all rejected jobs. The scheduling problem is NP-hard in the strong sense. In [4OR 14, No. 2, 165–172 (2016; Zbl 1338.90189)], L. Zhang and L. Lu have proposed a 2-approximation for the problem, and a fully polynomial time approximation scheme (FPTAS) for the special case when the number of machines \(m\) is fixed. In this paper, we present an improved 2-approximation and a polynomial time approximation scheme for the problem. We also propose an improved FPTAS for the case when \(m\) is fixed.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
Citations:
Zbl 1338.90189References:
| [1] | Bartal Y, Leonardi S, Marchetti-Spaccamela A, Sgall J, Stougie L (2000) Multiprocessor scheduling with rejection. SIAM J Discrete Math 13:64-78 · Zbl 0936.68012 · doi:10.1137/S0895480196300522 |
| [2] | Chen B, Vestjens APA (1997) Scheduling on identical machines: how good is LPT in an on-line setting? Oper Res Lett 21:165-169 · Zbl 0892.90098 · doi:10.1016/S0167-6377(97)00040-0 |
| [3] | Fishkin AV, Jansen K, Mastrolilli M (2008) Grouping techniques for scheduling problems: simpler and faster. Algorithmica 51:183-199 · Zbl 1159.90403 · doi:10.1007/s00453-007-9086-6 |
| [4] | Gusfield D (1984) Bounds for naive multiple machine scheduling with release times and deadlines. J Algorithms 5:1-6 · Zbl 0535.68018 · doi:10.1016/0196-6774(84)90035-X |
| [5] | Hall LA, Shmoys DB (1989) Approximation schemes for constrained scheduling problems. In: Proceedings of the 30th annual IEEE symposium on foundations of computer science, pp 134-139 |
| [6] | He C, Leung JY-T, Lee K, Pinedo ML (2016) Improved algorithms for single machine scheduling with release dates and rejections. 4OR Q J Oper Res 14:41-55 · Zbl 1333.90043 · doi:10.1007/s10288-016-0303-5 |
| [7] | Lenstra HW Jr (1983) Integer programming with a fixed number of variables. Math Oper Res 8:538-548 · Zbl 0524.90067 · doi:10.1287/moor.8.4.538 |
| [8] | Li C-L, Wang XL (2010) Scheduling parallel machines with inclusive processing set restrictions and job release times. Eur J Oper Res 200:702-710 · Zbl 1177.90170 · doi:10.1016/j.ejor.2009.02.011 |
| [9] | Li WD, Li JP, Zhang XJ, Chen ZB (2015) Penalty cost constrained identical parallel machine scheduling problem. Theor Comput Sci 607:181-192 · Zbl 1333.90048 · doi:10.1016/j.tcs.2015.10.007 |
| [10] | Mastrolilli M (2003) Efficient approximation schemes for scheduling problems with release dates and delivery times. J Sched 6:521-531 · Zbl 1154.90473 · doi:10.1023/A:1026272526225 |
| [11] | Ou JW, Zhong XL (2016) Order acceptance and scheduling with consideration of service level. Ann Oper Res. doi:10.1007/s10479-016-2277-2 · Zbl 1357.90055 · doi:10.1007/s10479-016-2277-2 |
| [12] | Ou JW, Zhong XL, Wang GQ (2015) An improved heuristic for parallel machine scheduling with rejection. Eur J Oper Res 241:653-661 · Zbl 1339.90148 · doi:10.1016/j.ejor.2014.09.028 |
| [13] | Ou JW, Zhong XL, Li C-L (2016) Faster algorithms for single machine scheduling with release dates and rejection. Inf Process Lett 116:503-507 · Zbl 1335.68306 · doi:10.1016/j.ipl.2016.02.008 |
| [14] | Shabtay D, Gaspar N, Kaspi M (2013) A survey on offline scheduling with rejection. J Sched 16:3-28 · Zbl 1297.90058 · doi:10.1007/s10951-012-0303-z |
| [15] | Shmoys D, Tardos E (1993) An approximation algorithm for the generalized assignment problem. Math Program 62:461-474 · Zbl 0804.90077 · doi:10.1007/BF01585178 |
| [16] | Slotnick SA (2011) Order acceptance and scheduling: a taxonomy and review. Eur J Oper Res 212:1-11 · doi:10.1016/j.ejor.2010.09.042 |
| [17] | Zhang LQ, Lu LF (2016) Parallel-machine scheduling with release dates and rejection. 4OR Q J Oper Res 14:165-172 · Zbl 1338.90189 · doi:10.1007/s10288-016-0304-4 |
| [18] | Zhang LQ, Lu LF, Yuan JJ (2009) Single machine scheduling with release dates and rejection. Eur J Oper Res 198:975-978 · Zbl 1176.90255 · doi:10.1016/j.ejor.2008.10.006 |
| [19] | Zhong XL, Pan ZM, Jiang DK (2016) Scheduling with release times and rejection on two parallel machines. J Comb Optim. doi:10.1007/s10878-016-0016-x · Zbl 1372.90056 · doi:10.1007/s10878-016-0016-x |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
