Abstract
We consider the problem of maximizing total tardiness on a single machine, where the first job starts at time zero and idle times between the processing of jobs are not allowed. We present a modification of an exact pseudo-polynomial algorithm based on a graphical approach, which has a polynomial running time. This result settles the complexity status of the problem under consideration which was open.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Note that we can prove that \(u_{l}^{1}< \dots<u_{l}^{w_{l}+1}\) holds also in another way. Functions Φ 1(t) and Φ 2(t) are convex and thus, function
$$F_l(t) = \max\{\varPhi^1(t), \varPhi^2(t)\}$$is convex as well. The value \(u_{l}^{s}\) corresponds to tanα, where α is the angle between the t-axis and the linear segment of F l (t) (see Fig. 1).
References
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.
Aloulou, M. A., Kovalyov, M. Y., & Portmann, M.-C. (2004). Maximization problems in single machine scheduling. Annals of Operations Research, 129, 21–32.
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.
Babu, P., Peridy, L., & Pinson, E. (2004). A branch and bound algorithm to minimize total weighted tardiness on a single processor. Annals of Operations Research, 129, 33–46.
Du, J., & Leung, J. Y.-T. (1990). Minimizing total tardiness on one processor is NP-hard. Mathematics of Operations Research, 15, 483–495.
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.
Gafarov, E. R., Lazarev, A. A., & Werner, F. (2010b). A modification of dynamic programming algorithms to reduce the running time or/and complexity. Preprint 20/10, FMA, Otto-von-Guericke-Universität Magdeburg.
Gafarov, E. R., Lazarev, A. A., & Werner, F. (2010c). Classical combinatorial and single machine scheduling problems with opposite optimality criteria. Preprint 11/10, FMA, Otto-von-Guericke-Universität Magdeburg.
Lawler, E. L. (1977). A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness. Annals of Discrete Mathematics, 1, 331–342.
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.
Lazarev, A. A., & Gafarov, E. R. (2006a). Special case of the single-machine total tardiness problem is NP-hard. Journal of Computer and Systems Sciences International, 45(3), 450–458.
Lazarev, A. A., & Gafarov, E. R. (2006b). Scheduling theory. Total tardiness problem. Moscow: Computing Center of the Russian Academy of Sciences, 128 pp. (in Russian).
Lazarev, A. A., & Werner, F. (2009a). A graphical realization of the dynamic programming method for solving NP-hard combinatorial problems. Computers and Mathematics with Applications, 58, 619–631.
Lazarev, A. A., & Werner, F. (2009b). Algorithms for special cases of the single machine total tardiness problem and an application to the even-odd partition problem. Mathematical and Computer Modelling, 49(9–10), 2061–2072.
Matsuo, H., Suh, C. J., & Sullivan, R. S. (1989). A controlled search simulated annealing method for the single machine weighted tardiness problem. Annals of Operations Research, 21, 85–108.
Posner, M. E. (1990). Reducibility among weighted completion time scheduling problems. Annals of Operations Research, 26, 91–101.
Potts, C. N., & Van Wassenhove, L. N. (1982). A decomposition algorithm for the single machine total tardiness problem. Operations Research Letters, 1, 363–377.
Szwarc, W., Della Croce, F., & Grosso, A. (1999). Solution of the single machine total tardiness problem. Journal of Scheduling, 2, 55–71.
Acknowledgements
This work was partially supported by DAAD (Deutscher Akademischer Austausch- dienst): A/08/80442/Ref. 325. The authors are grateful to the referees for their constructive comments, which substantially improved the presentation of the results.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Gafarov, E.R., Lazarev, A.A. & Werner, F. Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one. Ann Oper Res 196, 247–261 (2012). https://doi.org/10.1007/s10479-011-1055-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-011-1055-4