Abstract
In this paper, we study a vector scheduling problem with rejection on a single machine, in which each job is characterized by a d-dimension vector and a penalty, in the sense that, jobs can be either rejected by paying a certain penalty or assigned to the machine. The objective is to minimize the sum of the maximum load over all dimensions of the total vector of all accepted jobs, and the total penalty of rejected jobs. We prove that the problem is NP-hard and design two approximation algorithms running in polynomial time. When d is a fixed constant, we present a fully polynomial time approximation scheme.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alon N, Azar Y, Woeginger GJ, Yadid T (1998) Approximation schemes for scheduling on parallel machines. J Sched 1:55–66
Bansal N, Oosterwijk T, Vredeveld T, Zwaan R (2016) Approximating vector scheduling: almost matching upper and lower bounds. Algorithmica 76(4):1077–1096
Bartal Y, Leonardi S, Spaccamela AM, Sgall J, Stougie L (2000) Multiprocessor scheduling with rejection. SIAM J Discrete Math 13(1):64–78
Bonifaci V, Wiese A (2012) Scheduling unrelated machines of few different types. arXiv:1205.0974vl,
Chekuri C, Khanna S (2004) On multidimensional packing problems. SIAM J Comput 33(4):837–851
Chen L, Jansen K, Zhang G (2014) On the optimality of approximation schemes for the classical scheduling problem. In: Proceedings of the 25th annual ACM-SIAM symposium 19 on discrete algorithms (SODA), pp 657–668
Christensen HI, Khan A, Pokutta S, Tetali P (2017) Approximation and online algorithms for multidimensional bin packing: a survey. Comput Sci Rev 24:63–79
Epstein L, Tassa T (2003) Vector assignment problems: a general framework. J Algorithms 48(2):360–384
Epstein L, Tassa T (2006) Vector assignment schemes for asymmetric settings. Acta Inform 42(6–7):501–514
Garey MR, Johnson DS (1979) Computers and intractablity: a guide to the theory of NP-completeness. Freeman, San Francisco
He C, Leung JYT, Lee K, Pinedo ML (2016) Improved algorithms for single machine scheduling with release deates and rejections. 4OR Q J Oper Res 14(1):41–55
Hochbaum DS, Shmoys DB (1987) Using dual approximation algorithms for scheduling theoretical and practical results. J ACM 34(1):144–162
Im S, Kell N, Kulkarni J, Panigrahi D (2015) Tight bounds for online vector scheduling. In: IEEE 56th annual symposium on foundations of computer science (FOCS), pp 525–544
Jansen K, Klein KM, Verschae J (2016) Closing the gap for makespan scheduling via sparsification techniques. arXiv preprint arXiv:1604.07153
Karmarkar N (1984) A new polynomial-time algorithm for linear programming. In: Proceedings of the sixteenth annual ACM symposium on theory of computing (STOC), pp 302–311
Li W, Li J, Zhang X, Chen Z (2015) Penalty cost constrained identical parallel machine scheduling problem. Theoret Comput Sci 607:181–192
Meyerson A, Roytman A, Tagiku B (2013) Online multidimensional load balancing. Lect Notes Comput Sci 8096:287–302
Ou J, Zhong X, Li C-L (2016) Faster algorithms for single machine scheduling with release dates and rejection. Inf Process Lett 116(8):503–507
Ou J, Zhong X, Wang G (2015) An improved heuristic for parallel machine scheduling with rejection. Eur J Oper Res 241(3):653–661
Shabtay D, Gaspar N, Kaspi M (2013) A survey on offline scheduling with rejection. J Sched 16(1):3–28
Shabtay D, Gaspar N, Yedidsion L (2012) A bicriteria approach to scheduling a single machine with job rejection and positional penalties. J Comb Optim 23(4):395–424
Slotnick SA (2011) Order acceptance and scheduling: a taxonomy and review. Eur J Oper Res 212:1–11
Zhang L, Lu L (2016) Parallel-machine scheduling with release dates and rejection. 4OR Q J Oper Res 14:165–172
Zhang L, Lu L, Yuan J (2009) Single machine scheduling with release dates and rejection. Eur J Oper Res 198(3):975–978
Zhang L, Lu L, Yuan J (2010) Single-machine scheduling under the job rejection constraint. Theoret Comput Sci 411(16–18):1877–1882
Zhong X, Ou J (2016) Improved approximation algorithms for parallel machine scheduling with release dates and job rejection. 4OR Q J Oper Res. doi:10.1007/s10288-016-0339-6.
Zhong X, Pan Z, Jiang D (2017) Scheduling with release times and rejection on two parallel machines. J Comb Optim 33(3):934–944
Zhu X, Li Q, Mao W, Chen G (2014) Online vector scheduling and generalized load balancing. J Parallel Distrib Comput 74(4):2304–2309
Acknowledgements
We are grateful to the anonymous referees for numerous helpful comments and suggestions which helped to improve the presentation of our work. The work is supported in part by the National Natural Science Foundation of China [Nos. 61662088, 11301466], the Natural Science Foundation of Yunnan Province of China [No. 2014FB114], IRTSTYN, and Program for Excellent Young Talents, Yunnan University.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Li, W., Cui, Q. Vector scheduling with rejection on a single machine. 4OR-Q J Oper Res 16, 95–104 (2018). https://doi.org/10.1007/s10288-017-0356-0
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10288-017-0356-0
Keywords
- Vector scheduling
- Approximation algorithms
- Dynamic programming
- Fully polynomial time approximation scheme