×
Hermelin, Danny; Karhi, Shlomo; Pinedo, Michael; Shabtay, Dvir

New algorithms for minimizing the weighted number of tardy jobs on a single machine. (English) Zbl 1467.90008

Ann. Oper. Res. 298, No. 1-2, 271-287 (2021).
Summary: In this paper we study the classical single machine scheduling problem where the objective is to minimize the weighted number of tardy jobs. Our analysis focuses on the case where one or more of three natural parameters is either constant or is taken as a parameter in the sense of parameterized complexity. These three parameters are the number of different due dates, processing times, and weights in our set of input jobs. We show that the problem belongs to the class of fixed parameter tractable (FPT) problems when combining any two of these three parameters. We also show that the problem is polynomial-time solvable when either one of the latter two parameters are constant, complementing Karp’s result who showed that the problem is NP-hard already for a single due date.

Cited in 9 Documents

MSC:

90B35 Deterministic scheduling theory in operations research

Keywords:

single machine scheduling; weighted number of tardy jobs; fixed parametrized tractability; NP-hard; polynomial time algorithms
Cite Review PDF
Full Text: DOI arXiv

References:

[1] Adamu, MO; Adewumi, A., Single machine scheduling to minimize weighted number of tardy jobs, Journal of Industrial and Management Optimization, 10, 3, 219-241 (2014) · Zbl 1276.90001 · doi:10.3934/jimo.2014.10.219
[2] Bodlaender, HL; Fellows, MR, W[2]-hardness of precedence constrained k-processor scheduling, Operations Research Letters, 18, 2, 93-97 (1995) · Zbl 0857.90056 · doi:10.1016/0167-6377(95)00031-9
[3] Brucker, P.; Kravchenko, SA, Scheduling equal processing time jobs to minimize the weighted number of late jobs, Journal of Mathematical Modelling and Algorithms, 5, 2, 143-165 (2006) · Zbl 1126.90019 · doi:10.1007/s10852-005-9011-4
[4] Cieliebak, M.; Erlebach, T.; Hennecke, F.; Weber, B.; Widmayer, P.; Levy, JJ; Mayr, EW; Mitchell, JC, Scheduling with release times and deadlines on a minimum number of machines, Exploring new frontiers of theoretical informatics, 209-222 (2004), New York, NY: Springer, New York, NY · Zbl 1161.68360 · doi:10.1007/1-4020-8141-3_18
[5] Cygan, M.; Fomin, FV; Kowalik, L.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M., Parameterized algorithms (2015), Cham: Springer, Cham · Zbl 1334.90001 · doi:10.1007/978-3-319-21275-3
[6] Dadush, D., Peikert, C., & Vempala, S. (2011). Enumerative lattice algorithms in any norm via m-ellipsoid coverings. In IEEE 52nd annual symposium on foundations of computer science (FOCS) (pp. 580-589). · Zbl 1292.68091
[7] Dauzère-Pérès, S.; Sevaux, M., An exact method to minimize the number of tardy jobs in single machine scheduling, Journal of Scheduling, 7, 6, 405-420 (2004) · Zbl 1154.90437 · doi:10.1023/B:JOSH.0000046073.05827.15
[8] Downey, R. G., & Fellows, M. R. (1992). Fixed-parameter intractability. In Proceedings of the 7th annual structure in complexity theory conference (COCO ’92) (pp. 36-49).
[9] Downey, RG; Fellows, MR, Parameterized complexity (1999), New York, NY: Springer, New York, NY · doi:10.1007/978-1-4612-0515-9
[10] Fellows, MR; McCartin, C., On the parametric complexity of schedules to minimize tardy tasks, Theoretical Computer Science, 298, 2, 317-324 (2003) · Zbl 1038.68049 · doi:10.1016/S0304-3975(02)00811-3
[11] Flum, J.; Grohe, M., Parameterized complexity theory (1998), Berlin: Springer, Berlin
[12] Garey, MR; Johnson, DS, Computers and intractability: A guide to the theory of NP-completeness (1979), New York, NY: Freeman, New York, NY · Zbl 0411.68039
[13] Graham, RL; Lawler, EL; Lenstra, JK; Kan, AHGR, Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, 3, 287-326 (1979) · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X
[14] Hermelin, D., Kubitza, J. M., Shabtay, D., Talmon, N., & Woeginger, G. (2015). Scheduling two competing agents when one agent has significantly fewer jobs. In Proceedings of the 10th international symposium on parameterized and exact computation (IPEC) (pp. 55-65). · Zbl 1378.68021
[15] Karp, R. M. (1972). Reducibility among combinatorial problems. In R.E. Miller & J.W. Thatcher (Eds.), Complexity of computer computations (pp. 85-103). · Zbl 1467.68065
[16] Knop, D.; Koutecký, M., Scheduling meets n-fold integer programming, Journal of Scheduling (2018) · Zbl 1418.90113 · doi:10.1007/s10951-017-0550-0
[17] Lawler, EL; Moore, JM, A functional equation and its application to resource allocation and sequencing problems, Management Science, 16, 1, 77-84 (1969) · Zbl 0184.23303 · doi:10.1287/mnsc.16.1.77
[18] Lenstra, HL, Integer programming with a fixed number of variables, Mathematics of Operations Research, 8, 4, 538-548 (1983) · Zbl 0524.90067 · doi:10.1287/moor.8.4.538
[19] Lenté, C.; Liedloff, M.; Soukhal, A.; T’Kindt, V., On an extension of the sort and search method with application to scheduling theory, Theoretical Computer Science, 511, 13-22 (2013) · Zbl 1358.68084 · doi:10.1016/j.tcs.2013.05.023
[20] M’Hallah, R.; Bulfin, RL, Minimizing the weighted number of tardy jobs on a single machine, European Journal of Operational Research, 145, 1, 45-56 (2003) · Zbl 1012.90009 · doi:10.1016/S0377-2217(02)00180-7
[21] Micciancio, D., & Voulgaris, P. (2010). A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations. In Proceedings of the 42nd ACM symposium on theory of computing (STOC) (pp. 351-358). · Zbl 1293.68172
[22] Mnich, M., & van Bevern, R. (2017). Parameterized complexity of machine scheduling: 15 open problems. CoRR, arxiv: 1709.01670. Accessed 4 Jan 2018. · Zbl 1458.90333
[23] Mnich, M.; Wiese, A., Scheduling and fixed-parameter tractability, Mathematical Programming, 154, 1, 533-562 (2015) · Zbl 1332.68089 · doi:10.1007/s10107-014-0830-9
[24] Moore, JM, An \(n\) job, one machine sequencing algorithm for minimizing the number of late jobs, Management Science, 15, 102-109 (1968) · Zbl 0164.20002 · doi:10.1287/mnsc.15.1.102
[25] Niedermeier, R., Invitation to fixed-parameter algorithms (2006), Oxford: Oxford Univerity Press, Oxford · Zbl 1095.68038 · doi:10.1093/acprof:oso/9780198566076.001.0001
[26] Peha, JM, Heterogeneous-criteria scheduling: minimizing weighted number of tardy jobs and weighted completion time, Computers and Operations Research, 22, 10, 1089-1100 (1995) · Zbl 0838.90067 · doi:10.1016/0305-0548(94)00090-U
[27] Sahni, SK, Algorithms for scheduling independent tasks, Journal of the ACM, 23, 1, 116-127 (1976) · Zbl 0326.68024 · doi:10.1145/321921.321934
[28] Tang, G., A new branch and bound algorithm for minimizing the weighted number of tardy jobs, Annals of Operations Research, 24, 1, 225-232 (1990) · Zbl 0717.90035 · doi:10.1007/BF02216825
[29] van Bevern, R., & Pyatkin, A. V. (2016). Completing partial schedules for open shop with unit processing times and routing. In Proc. of the 11th international computer science symposium in Russia (CSR) (pp. 73-87). · Zbl 1475.90025
[30] van Bevern, R., Bredereck, R., Bulteau, L., Komusiewicz, C., Talmon, N., & Woeginger, G. J. (2016). Precedence-constrained scheduling problems parameterized by partial order width. In Proc. of the 9th international conference on discrete optimization and operations research (DOOR) (pp. 105-120). · Zbl 1385.90010
[31] van Bevern, R.; Niedermeier, R.; Suchỳ, O., A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: Few machines, small looseness, and small slack, Journal of Scheduling, 20, 3, 255-265 (2017) · Zbl 1376.90028 · doi:10.1007/s10951-016-0478-9
[32] Villarreal, FJ; Bulfin, RL, Scheduling a single machine to minimize the weighted number of tardy jobs, AIIE Transactions, 15, 4, 337-343 (1983)
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.