{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T10:17:28Z","timestamp":1773656248958,"version":"3.50.1"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2012,1,10]],"date-time":"2012-01-10T00:00:00Z","timestamp":1326153600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2012,7]]},"DOI":"10.1007\/s10479-011-1055-4","type":"journal-article","created":{"date-parts":[[2012,1,9]],"date-time":"2012-01-09T09:56:02Z","timestamp":1326102962000},"page":"247-261","source":"Crossref","is-referenced-by-count":8,"title":["Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one"],"prefix":"10.1007","volume":"196","author":[{"given":"Evgeny R.","family":"Gafarov","sequence":"first","affiliation":[]},{"given":"Alexander A.","family":"Lazarev","sequence":"additional","affiliation":[]},{"given":"Frank","family":"Werner","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,1,10]]},"reference":[{"issue":"5","key":"1055_CR1","doi-asserted-by":"crossref","first-page":"890","DOI":"10.1016\/j.cor.2009.03.021","volume":"37","author":"M. A. Aloulou","year":"2010","unstructured":"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\u2013898.","journal-title":"Computers & Operations Research"},{"key":"1055_CR2","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1023\/B:ANOR.0000030679.25466.02","volume":"129","author":"M. A. Aloulou","year":"2004","unstructured":"Aloulou, M. A., Kovalyov, M. Y., & Portmann, M.-C. (2004). Maximization problems in single machine scheduling. Annals of Operations Research, 129, 21\u201332.","journal-title":"Annals of Operations Research"},{"key":"1055_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1051\/ro:20070012","volume":"41","author":"M. A. Aloulou","year":"2007","unstructured":"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\u00e9rationnelle, 41, 1\u201318.","journal-title":"RAIRO. Recherche Op\u00e9rationnelle"},{"key":"1055_CR4","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1023\/B:ANOR.0000030680.29037.d0","volume":"129","author":"P. Babu","year":"2004","unstructured":"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\u201346.","journal-title":"Annals of Operations Research"},{"key":"1055_CR5","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1287\/moor.15.3.483","volume":"15","author":"J. Du","year":"1990","unstructured":"Du, J., & Leung, J. Y.-T. (1990). Minimizing total tardiness on one processor is NP-hard. Mathematics of Operations Research, 15, 483\u2013495.","journal-title":"Mathematics of Operations Research"},{"issue":"10","key":"1055_CR6","doi-asserted-by":"crossref","first-page":"2070","DOI":"10.1134\/S0005117910100061","volume":"71","author":"E. R. Gafarov","year":"2010","unstructured":"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\u20132084.","journal-title":"Automation and Remote Control"},{"key":"1055_CR7","unstructured":"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\u00e4t Magdeburg."},{"key":"1055_CR8","unstructured":"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\u00e4t Magdeburg."},{"key":"1055_CR9","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1016\/S0167-5060(08)70742-8","volume":"1","author":"E. L. Lawler","year":"1977","unstructured":"Lawler, E. L. (1977). A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness. Annals of Discrete Mathematics, 1, 331\u2013342.","journal-title":"Annals of Discrete Mathematics"},{"issue":"1","key":"1055_CR10","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1287\/mnsc.16.1.77","volume":"16","author":"E. L. Lawler","year":"1969","unstructured":"Lawler, E. L., & Moore, J. M. (1969). A functional equation and its application to resource allocation and sequencing problems. Management Science, 16(1), 77\u201384.","journal-title":"Management Science"},{"issue":"3","key":"1055_CR11","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1134\/S1064230706030117","volume":"45","author":"A. A. Lazarev","year":"2006","unstructured":"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\u2013458.","journal-title":"Journal of Computer and Systems Sciences International"},{"key":"1055_CR12","volume-title":"Scheduling theory. Total tardiness problem","author":"A. A. Lazarev","year":"2006","unstructured":"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)."},{"key":"1055_CR13","doi-asserted-by":"crossref","first-page":"619","DOI":"10.1016\/j.camwa.2009.06.008","volume":"58","author":"A. A. Lazarev","year":"2009","unstructured":"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\u2013631.","journal-title":"Computers and Mathematics with Applications"},{"issue":"9\u201310","key":"1055_CR14","doi-asserted-by":"crossref","first-page":"2061","DOI":"10.1016\/j.mcm.2009.01.003","volume":"49","author":"A. A. Lazarev","year":"2009","unstructured":"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\u201310), 2061\u20132072.","journal-title":"Mathematical and Computer Modelling"},{"key":"1055_CR15","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/BF02022094","volume":"21","author":"H. Matsuo","year":"1989","unstructured":"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\u2013108.","journal-title":"Annals of Operations Research"},{"key":"1055_CR16","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/BF02248586","volume":"26","author":"M. E. Posner","year":"1990","unstructured":"Posner, M. E. (1990). Reducibility among weighted completion time scheduling problems. Annals of Operations Research, 26, 91\u2013101.","journal-title":"Annals of Operations Research"},{"key":"1055_CR17","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1016\/0167-6377(82)90035-9","volume":"1","author":"C. N. Potts","year":"1982","unstructured":"Potts, C. N., & Van Wassenhove, L. N. (1982). A decomposition algorithm for the single machine total tardiness problem. Operations Research Letters, 1, 363\u2013377.","journal-title":"Operations Research Letters"},{"key":"1055_CR18","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1002\/(SICI)1099-1425(199903\/04)2:2<55::AID-JOS14>3.0.CO;2-5","volume":"2","author":"W. Szwarc","year":"1999","unstructured":"Szwarc, W., Della Croce, F., & Grosso, A. (1999). Solution of the single machine total tardiness problem. Journal of Scheduling, 2, 55\u201371.","journal-title":"Journal of Scheduling"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-011-1055-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10479-011-1055-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-011-1055-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T18:09:32Z","timestamp":1559153372000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10479-011-1055-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1,10]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["1055"],"URL":"https:\/\/doi.org\/10.1007\/s10479-011-1055-4","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1,10]]}}}