Abstract
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.
Similar content being viewed by others
Notes
Computable functions are functions that are computable by a Turing machine. That is, a function f is computable if there exists a Turing machine that outputs f(x) on any given input x (or outputs “undefined” in case x does not belong to the domain of f).
References
Adamu, M. O., & Adewumi, A. (2014). Single machine scheduling to minimize weighted number of tardy jobs. Journal of Industrial and Management Optimization, 10(3), 219–241.
Bodlaender, H. L., & Fellows, M. R. (1995). W[2]-hardness of precedence constrained k-processor scheduling. Operations Research Letters, 18(2), 93–97.
Brucker, P., & Kravchenko, S. A. (2006). Scheduling equal processing time jobs to minimize the weighted number of late jobs. Journal of Mathematical Modelling and Algorithms, 5(2), 143–165.
Cieliebak, M., Erlebach, T., Hennecke, F., Weber, B., & Widmayer, P. (2004). Scheduling with release times and deadlines on a minimum number of machines. In J. J. Levy, E. W. Mayr, & J. C. Mitchell (Eds.), Exploring new frontiers of theoretical informatics (pp. 209–222). New York, NY: Springer.
Cygan, M., Fomin, F. V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., et al. (2015). Parameterized algorithms. Cham: Springer.
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).
Dauzère-Pérès, S., & Sevaux, M. (2004). An exact method to minimize the number of tardy jobs in single machine scheduling. Journal of Scheduling, 7(6), 405–420.
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).
Downey, R. G., & Fellows, M. R. (1999). Parameterized complexity. New York, NY: Springer.
Fellows, M. R., & McCartin, C. (2003). On the parametric complexity of schedules to minimize tardy tasks. Theoretical Computer Science, 298(2), 317–324.
Flum, J., & Grohe, M. (1998). Parameterized complexity theory. Berlin: Springer.
Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. New York, NY: Freeman.
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. H. G. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 3, 287–326.
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).
Karp, R. M. (1972). Reducibility among combinatorial problems. In R.E. Miller & J.W. Thatcher (Eds.), Complexity of computer computations (pp. 85–103).
Knop, D., & Koutecký, M. (2018). Scheduling meets n-fold integer programming. Journal of Scheduling,. https://doi.org/10.1007/s10951-017-0550-0.
Lawler, E. L., & Moore, J. M. (1969). A functional equation and its application to resource allocation and sequencing problems. Management Science, 16(1), 77–84.
Lenstra, H. L. (1983). Integer programming with a fixed number of variables. Mathematics of Operations Research, 8(4), 538–548.
Lenté, C., Liedloff, M., Soukhal, A., & T’Kindt, V. (2013). On an extension of the sort and search method with application to scheduling theory. Theoretical Computer Science, 511, 13–22.
M’Hallah, R., & Bulfin, R. L. (2003). Minimizing the weighted number of tardy jobs on a single machine. European Journal of Operational Research, 145(1), 45–56.
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).
Mnich, M., & van Bevern, R. (2017). Parameterized complexity of machine scheduling: 15 open problems. CoRR, arxiv: 1709.01670. Accessed 4 Jan 2018.
Mnich, M., & Wiese, A. (2015). Scheduling and fixed-parameter tractability. Mathematical Programming, 154(1), 533–562.
Moore, J. M. (1968). An \(n\) job, one machine sequencing algorithm for minimizing the number of late jobs. Management Science, 15, 102–109.
Niedermeier, R. (2006). Invitation to fixed-parameter algorithms. Oxford: Oxford Univerity Press.
Peha, J. M. (1995). Heterogeneous-criteria scheduling: minimizing weighted number of tardy jobs and weighted completion time. Computers and Operations Research, 22(10), 1089–1100.
Sahni, S. K. (1976). Algorithms for scheduling independent tasks. Journal of the ACM, 23(1), 116–127.
Tang, G. (1990). A new branch and bound algorithm for minimizing the weighted number of tardy jobs. Annals of Operations Research, 24(1), 225–232.
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).
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).
van Bevern, R., Niedermeier, R., & Suchỳ, O. (2017). 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.
Villarreal, F. J., & Bulfin, R. L. (1983). Scheduling a single machine to minimize the weighted number of tardy jobs. AIIE Transactions, 15(4), 337–343.
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was supported by Grant No. 2016049 from the United States-Israel Binational Science Foundation. The first author is also supported by the People Programme (Marie Curie Actions) of the European Unions Seventh Framework Programme (FP7/2007-2013) under REA Grant Agreement Number 631163.11, and by the Israel Science Foundation (Grant No. 551145/14).
Rights and permissions
About this article
Cite this article
Hermelin, D., Karhi, S., Pinedo, M. et al. New algorithms for minimizing the weighted number of tardy jobs on a single machine. Ann Oper Res 298, 271–287 (2021). https://doi.org/10.1007/s10479-018-2852-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-018-2852-9