Single machine total tardiness maximization problems: complexity and algorithms. (English) Zbl 1273.90079
Summary: In this paper, we consider some scheduling problems on a single machine, where weighted or unweighted total tardiness has to be maximized in contrast to usual minimization problems. These problems are theoretically important and have also practical interpretations. For the total weighted tardiness maximization problem, we present an NP-hardness proof and a pseudo-polynomial solution algorithm. For the unweighted total tardiness maximization problem with release dates, NP-hardness is proven. Complexity results for some other classical objective functions (e.g., the number of tardy jobs, total completion time) and various additional constraints (e.g., deadlines, weights and/or release dates of jobs may be given) are presented as well.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C60 | Abstract computational complexity for mathematical programming problems |
| 90C39 | Dynamic programming |
References:
| [1] | Aloulou, M. A., & Artigues, C. (2010). Flexible solutions in disjunctive scheduling: general formulation and study of the flow-shop case. Computers & Operations Research, 37(5), 890–898. · Zbl 1177.90140 · doi:10.1016/j.cor.2009.03.021 |
| [2] | Aloulou, M. A., Kovalyov, M. Y., & Portmann, M.-C. (2004). Maximization problems in single machine scheduling. Annals of Operations Research, 129, 21–32. · Zbl 1056.90050 · doi:10.1023/B:ANOR.0000030679.25466.02 |
| [3] | Aloulou, M. A., Kovalyov, M. Y., & Portmann, M.-C. (2007). Evaluation flexible solutions in single machine scheduling via objective function maximization: the study of computational complexity. RAIRO. Recherche Opérationnelle, 41, 1–18. · Zbl 1377.90024 |
| [4] | Baker, K. R. (1974). Introduction to sequencing and scheduling. New York: Wiley. |
| [5] | Gafarov, E. R., Lazarev, A. A., & Werner, F. (2010a). Algorithms for maximizing the number of tardy jobs or total tardiness on a single machine. Automation and Remote Control, 71(10), 2070–2084. · Zbl 1203.93126 · doi:10.1134/S0005117910100061 |
| [6] | Gafarov, E. R., Lazarev, A. A., & Werner, F. (2010b). Classical combinatorial and single machine scheduling problems with opposite optimality criteria. Preprint 11/10, FMA, Otto-von-Guericke-Universität Magdeburg. · Zbl 1203.93126 |
| [7] | Gafarov, E. R., Lazarev, A. A., & Werner, F. (2012). Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one. Annals of Operations Research, 196(1), 247–261. · Zbl 1251.90143 · doi:10.1007/s10479-011-1055-4 |
| [8] | Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic machine scheduling: a survey. Annals of Discrete Mathematics, 5, 287–326. · Zbl 0411.90044 |
| [9] | Lawler, E. L. (1977). A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness. Annals of Discrete Mathematics, 1, 331–342. · Zbl 0353.68071 |
| [10] | 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. · Zbl 0184.23303 · doi:10.1287/mnsc.16.1.77 |
| [11] | Lenstra, J. K., Rinnooy Kan, A. H. G., & Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 343–362. · Zbl 0353.68067 |
| [12] | van den Akker, M., & Hoogeveen, H. (2004). Minimizing the number of tardy jobs. In Y.-T. Leung (Ed.), Handbook of scheduling: algorithms, models and performance analysis. London: Chapman & Hall. |
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.
