{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,5]],"date-time":"2026-01-05T17:16:32Z","timestamp":1767633392872,"version":"3.48.0"},"reference-count":88,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2026,1,4]],"date-time":"2026-01-04T00:00:00Z","timestamp":1767484800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001655","name":"DAAD","doi-asserted-by":"publisher","award":["57507438"],"award-info":[{"award-number":["57507438"]}],"id":[{"id":"10.13039\/501100001655","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Since the publication of the first scheduling paper in 1954, a huge number of works dealing with different types of single machine problems have appeared. They addressed many heuristics and enumerative procedures, complexity results or structural properties of certain problems. Regarding surveys, often particular subjects like special objective functions were discussed or more general scheduling problems were surveyed, in which a substantial part was devoted to single machine problems. In this paper, we focus on standard settings, basic structural properties of these settings, polynomial algorithms and complexity and approximation issues, which have not been reviewed so far, and suggest some future work in this area.<\/jats:p>","DOI":"10.3390\/a19010038","type":"journal-article","created":{"date-parts":[[2026,1,5]],"date-time":"2026-01-05T12:38:56Z","timestamp":1767616736000},"page":"38","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Single Machine Scheduling Problems: Standard Settings and Properties, Polynomially Solvable Cases, Complexity and Approximability"],"prefix":"10.3390","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9013-9334","authenticated-orcid":false,"given":"Nodari","family":"Vakhania","sequence":"first","affiliation":[{"name":"Centro de Investigaci\u00f3n en Ciencias, Universidad Aut\u00f3noma del Estado de Morelos, Cuernavaca 62209, Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0709-3591","authenticated-orcid":false,"given":"Frank","family":"Werner","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics, Otto-von-Guericke University, 39106 Magdeburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kevin Johedan","family":"Ram\u00edrez-Fuentes","sequence":"additional","affiliation":[{"name":"Centro de Investigaci\u00f3n en Ciencias, Universidad Aut\u00f3noma del Estado de Morelos, Cuernavaca 62209, Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2026,1,4]]},"reference":[{"key":"ref_1","first-page":"343","article-title":"Complexity of machine scheduling problems","volume":"1","author":"Lenstra","year":"1975","journal-title":"Ann. Oper. Res."},{"key":"ref_2","first-page":"1493","article-title":"A Review of Machine Scheduling: Complexity, Algorithms and Approximability","volume":"Volume 3","author":"Du","year":"1998","journal-title":"Handbook of Combinatorial Optimization"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/S0305-0483(98)00042-5","article-title":"A Review of Scheduling Research Involving Setup Considerations","volume":"27","author":"Allahverdi","year":"1999","journal-title":"Omega Int. J. Manag. Sci."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"985","DOI":"10.1016\/j.ejor.2006.06.060","article-title":"A Survey of Scheduling Problems with Setup Times or Costs","volume":"187","author":"Allahverdi","year":"2008","journal-title":"Eur. J. Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1016\/j.ejor.2015.04.004","article-title":"The Third Comprehensive Survey on Scheduling Problems with Setup Times\/Costs","volume":"246","author":"Allahverdi","year":"2015","journal-title":"Eur. J. Oper. Res."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ejor.2021.06.012","article-title":"A Survey of Scheduling with Parallel Batch (p-Batch) Processing","volume":"298","author":"Fowler","year":"2022","journal-title":"Eur. J. Oper. Res."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1007\/s10951-011-0231-3","article-title":"Parallel Machine Problems with Equal Processing Times: A Survey","volume":"14","author":"Kravchenko","year":"2011","journal-title":"J. Sched."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/S0377-2217(98)00246-X","article-title":"Single-Machine Schduling with Learning Considerations","volume":"115","author":"Briskorn","year":"1999","journal-title":"Eur. J. Oper. Res."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"9309","DOI":"10.1038\/s41598-023-36056-w","article-title":"Single-Machine Scheduling with Periodic Maintenance and Learning Effect","volume":"13","author":"Wu","year":"2023","journal-title":"Sci. Rep."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"999","DOI":"10.1016\/j.ejor.2022.03.043","article-title":"A Classification of Dynamic Programming Formulations for Offline Deterministic Single-Machine Scheduling Problems","volume":"305","author":"Koulamas","year":"2023","journal-title":"Eur. J. Oper. Res."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0166-218X(90)90103-J","article-title":"A Survey of Algorithms for the Single Machine Total Weighted Tardiness Scheduling Problem","volume":"26","author":"Potts","year":"1990","journal-title":"Discret. Appl. Math."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"219","DOI":"10.3934\/jimo.2014.10.219","article-title":"A Survey of Single Machine Scheduling to Minimize Weighted Number of Tardy Jobs","volume":"10","author":"Adumu","year":"2014","journal-title":"J. Ind. Manag. Optim."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1016\/j.omega.2010.06.006","article-title":"A Survey of Scheduling Problems with Late Work Criteria","volume":"39","author":"Sterna","year":"2011","journal-title":"Omega Int. J. Manag. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"102453","DOI":"10.1016\/j.omega.2021.102453","article-title":"Late and Early Work Scheduling: A Survey","volume":"104","author":"Sterna","year":"2021","journal-title":"Omega Int. J. Manag. Sci."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/s10479-012-1288-x","article-title":"Single Machine Total Tardiness Maximization Problems: Complexity and Algorithms","volume":"207","author":"Gafarov","year":"2013","journal-title":"Ann. Oper. Res."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1287\/opre.23.3.475","article-title":"On Scheduling with Ready Times and due-dates to Minimize Maximum Lateness","volume":"23","author":"McMahon","year":"1975","journal-title":"Oper. Res."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/S0377-2217(82)80007-6","article-title":"The One-Machine Sequencing Problem","volume":"11","author":"Carlier","year":"1982","journal-title":"Eur. J. Oper. Res."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1030","DOI":"10.1016\/j.ejor.2004.07.050","article-title":"Branch-and-bound Algorithms for Solving Hard Instances of the One-Machine Sequencing Problem","volume":"168","author":"Pan","year":"2006","journal-title":"Eur. J. Oper. Res."},{"key":"ref_19","unstructured":"Vakhania, N. (2022). Variable Parameter Analysis for Scheduling One Machine. arXiv."},{"key":"ref_20","unstructured":"Jackson, J.R. (1955). Scheduling a Production Line to Minimize the Maximum Tardiness. [Ph.D. Thesis, University of California]."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1002\/nav.3800210113","article-title":"Some Simple Scheduling Algorithms","volume":"21","author":"Horn","year":"1974","journal-title":"Nav. Res. Logist. Q."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1137\/0210018","article-title":"Scheduling Unit-Time Tasks with Arbitrary Release Times and Deadlines","volume":"10","author":"Garey","year":"1981","journal-title":"SIAM J. Comput."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1023\/B:ANOR.0000030692.69147.e2","article-title":"Single-Machine Scheduling with Release Times and Tails","volume":"129","author":"Vakhania","year":"2004","journal-title":"Ann. Oper. Res."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Vakhania, N. (2019). Dynamic Restructuring Framework for Scheduling with Release Times and Due-Dates. Mathematics, 7.","DOI":"10.3390\/math7111104"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1016\/j.tcs.2013.07.001","article-title":"Minimizing Maximum Lateness of Jobs with Naturally Bounded Job Data on a Single Machine in Polynomial Time","volume":"501","author":"Vakhania","year":"2013","journal-title":"Theor. Comput. Sci."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/s11590-016-1003-y","article-title":"Scheduling Jobs with Equal Processing Times on a Single Machine: Minimizing Maximum Lateness and Makespan","volume":"11","author":"Lazarev","year":"2017","journal-title":"Optim. Lett."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.tcs.2019.03.001","article-title":"Fast Solution of Single-Machine Scheduling Problem with Embedded Jobs","volume":"782","author":"Vakhania","year":"2019","journal-title":"Theor. Comput. Sci."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1007\/s10951-021-00708-4","article-title":"Theoretical and Practical Issues in Single-Machine Scheduling with two Job Release and Delivery Times","volume":"24","author":"Reynoso","year":"2021","journal-title":"J. Sched."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1080\/02331939508844112","article-title":"Single Machine Preemptive Scheduling with Special Cost Functions","volume":"34","author":"Azhanarok","year":"1995","journal-title":"Optimization"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/s10951-012-0307-8","article-title":"A Study of Single-Machine Scheduling Problem to Maximize Throughput","volume":"16","author":"Vakhania","year":"2013","journal-title":"J. Sched."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/BF02248588","article-title":"A Dynamic Programming Algorithm for Preemptive Scheduling of a Single Machine to Minimize the Number of Late Jobs","volume":"26","author":"Lawler","year":"1990","journal-title":"Ann. Oper. Res."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/S0167-6377(98)00045-5","article-title":"An O(n4) Algorithm for Preemptive Scheduling of a Single Machine to Minimize the Number of Late Jobs","volume":"24","author":"Baptiste","year":"1999","journal-title":"Oper. Res. Lett."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1016\/j.orl.2009.09.003","article-title":"Scheduling Jobs with Release Times Preemptively on a Single Machine to Minimize the Number of Late Jobs","volume":"37","author":"Vakhania","year":"2009","journal-title":"Oper. Res. Lett."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1002\/(SICI)1099-1425(199911\/12)2:6<245::AID-JOS28>3.0.CO;2-5","article-title":"Polynomial Time Algorithms for Minimizing the Weighted Number of Late Jobs on a Single Machine with Equal Processing Times","volume":"2","author":"Baptiste","year":"1999","journal-title":"J. Sched."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1016\/j.orl.2003.09.004","article-title":"Preemptive Scheduling of Equal-Length Jobs to Maximize Weighted Throughput","volume":"32","author":"Baptiste","year":"2004","journal-title":"Oper. Res. Lett."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"853","DOI":"10.1134\/S0005117920050069","article-title":"Minimizing Total Weighted Tardiness for Scheduling Equal-Length Jobs on a Single Machine","volume":"81","author":"Gafarov","year":"2020","journal-title":"Autom. Remote Control"},{"key":"ref_37","unstructured":"Ramirez, K., Vakhania, N., and Hernandez, A. (2025, January 3\u20135). Fast Algorithm for Single Machine Scheduling of Unit-Length Jobs with Non-renewable Resource Requirements to Minimize Maximum Job Lateness. Proceedings of the 12th Annual Conference on Computational Science & Computational Intelligence, Las Vegas, NV, USA."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1002\/nav.20095","article-title":"Basic Scheduling Problems with Raw Material Constraints","volume":"52","author":"Grigoriev","year":"2005","journal-title":"Nav. Res. Logist."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1007\/s42979-023-02042-2","article-title":"A Steady-State Genetic Algorithms for the Single Machine Scheduling Problem with Periodic Maintenance Availability","volume":"4","author":"Chaubey","year":"2023","journal-title":"SN Comput. Sci."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1007\/978-3-031-19945-5_8","article-title":"Simulated Annealing and Tabu Search for Solving the Single-Machine Problem","volume":"Volume 571","author":"Mexicano","year":"2023","journal-title":"Advances on P2P, Parallel, Grid, Cloud and Internet Computing"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Mellouli, A., Wafi, C., and Mellouli, R. (2025). An Efficent Ant Colony Optimization-Based Heuristic for the Single Machine Scheduling with Sequence-Dependent Setup Times. Advsnces in Mechanical Engineering, Materials and Mechanics II (ICAMEM2024), Springer.","DOI":"10.1007\/978-3-031-89733-7_19"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/j.endm.2018.03.007","article-title":"Algorithms based on VNS for Solving the Single Machine Scheduling Problem with Earliness and Tardiness Penalties","volume":"66","author":"Rosa","year":"2018","journal-title":"Electron. Notes Discret. Math."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"2169","DOI":"10.1007\/s11590-022-01913-6","article-title":"Variable Neighborhood Search for the Single Machine Scheduling Problem to Minimize the Total Early Work","volume":"17","author":"Benmansour","year":"2023","journal-title":"Optim. Lett."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1007\/s42979-024-03642-2","article-title":"An Iterative Local Search for the Single Machine Scheduling Problem with Periodic Machine Availability","volume":"6","author":"Israni","year":"2025","journal-title":"SN Comput. Sci."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1080\/01605682.2019.1596591","article-title":"A Dynamic Differential Evolution Algorithm for the Dynamic Single-Machine Scheduling Problem with Sequence-Dependent Setup Times","volume":"71","author":"Zhao","year":"2020","journal-title":"J. Oper. Res. Soc."},{"key":"ref_46","first-page":"20240373","article-title":"A New Metaheuristic Algorithm for Solving Multi-Objective Single-Machine Scheduling Problems","volume":"34","author":"Khraibet","year":"2025","journal-title":"J. Intell. Syst."},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Moharam, R., Morsy, E., Ali, A.F., Ahmed, M.A., and Mostafa, M.-S.M. (2022, January 5\u20137). A Discrete Grey Wolf Optimization Algorithm for Minimizing Penalties on a Single Machine Scheduling Problem. Proceedings of the 8th International Conference on Advanced Machine Learning and Technologies and Applications (AMLTA2022), Cairo, Egypt.","DOI":"10.1007\/978-3-031-03918-8_56"},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"2165","DOI":"10.1016\/j.cor.2006.10.017","article-title":"Meta-heuristics for Stable Scheduling on a Single Machine","volume":"35","author":"Ballestin","year":"2008","journal-title":"Comput. Oper. Res."},{"key":"ref_49","first-page":"422","article-title":"A Self-Adaptive Metaheuristic to Minimize the Total Weighted Tardiness for a Single-Machine Scheduling Problem with Flexible and Variable Maintenance","volume":"42","author":"Corsini","year":"2025","journal-title":"J. Ind. Prod. Eng."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"107281","DOI":"10.1016\/j.cor.2025.107281","article-title":"Minimizing the Weighted Number of Tardy Jobs: Data-Driven Heuristic for Single-Machine Scheduling","volume":"185","author":"Antonov","year":"2026","journal-title":"Comput. Oper. Res."},{"key":"ref_51","unstructured":"Schrage, L. (1971). Obtaining Optimal Solutions to Resource Constrained Network Scheduling Problems, Unpublished work."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"1436","DOI":"10.1287\/opre.28.6.1436","article-title":"Analysis of a Heuristic for One Machine Sequencing with Release Dates and Delivery Times","volume":"28","author":"Potts","year":"1980","journal-title":"Oper. Res."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0166-218X(92)00110-8","article-title":"An Approximation Algorithm for Single-Machine Scheduling with Release Times and Delivery Times","volume":"48","author":"Nowicki","year":"1994","journal-title":"Discret. Appl. Math."},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1287\/moor.17.1.22","article-title":"Jackson\u2019s Rule for Single-Machine Scheduling: Making a Good Heuristic Better","volume":"17","author":"Hall","year":"1992","journal-title":"Math. Oper. Res."},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1023\/A:1026272526225","article-title":"Efficient Approximation Schemes for Scheduling Problems with Release Dates and Delivery Times","volume":"6","author":"Mastrolilli","year":"2003","journal-title":"J. Sched."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1137\/S0895480196296823","article-title":"A Best Possible Deterministic On-line Algorithm for Minimizing Maximum Delivery Time on a Single Machine","volume":"13","author":"Hoogeveen","year":"2000","journal-title":"SIAM J. Discret. Math."},{"key":"ref_57","unstructured":"Lenstra, J.K. Private communication."},{"key":"ref_58","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","article-title":"Optimization and Approximation in Deterministic Sequencing and Scheduling: A Servey","volume":"5","author":"Graham","year":"1979","journal-title":"Ann. Discret. Math."},{"key":"ref_59","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1002\/nav.3800200106","article-title":"On Sequencing with Earliest Start Times and Due\u2013Dates with Application to Computing Bounds for (n\/m\/G\/Fmax) Problem","volume":"20","author":"Bratley","year":"1973","journal-title":"Nav. Res. Logist. Q."},{"key":"ref_60","doi-asserted-by":"crossref","first-page":"1321175","DOI":"10.1080\/23311916.2017.1321175","article-title":"Adjusting Scheduling Model with Release and due-dates in Production Planning","volume":"4","author":"Chinos","year":"2017","journal-title":"Cogent Eng."},{"key":"ref_61","unstructured":"Garey, M.R. (1979). D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman."},{"key":"ref_62","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1016\/j.orl.2010.08.002","article-title":"Improving the Preemptive Bound for the Single Machine Dynamic Maximum Lateness Problem","volume":"38","year":"2010","journal-title":"Oper. Res. Lett."},{"key":"ref_63","doi-asserted-by":"crossref","first-page":"2082","DOI":"10.1016\/j.cor.2010.02.008","article-title":"Jackson\u2019s Semi-preemptive Scheduling on a single Machine","volume":"37","author":"Gharbi","year":"2010","journal-title":"Comput. Oper. Res."},{"key":"ref_64","first-page":"57","article-title":"A scheme of an approximate solution of the 1|rj|Lmax problem","volume":"13","author":"Lazarev","year":"2006","journal-title":"Diskretn. Anal. Issled. Oper."},{"key":"ref_65","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1287\/moor.21.1.100","article-title":"Minimizing Maximum Promptness and Maximum Lateness on a Single Machine","volume":"21","author":"Hoogeveen","year":"1995","journal-title":"Math. Oper. Res."},{"key":"ref_66","doi-asserted-by":"crossref","unstructured":"Vakhania, N., and Werner, F. (4OR-Q J. Oper. Res., 2025). Scheduling a single machine with compressible jobs to minimize maximum lateness: N. Vakhania, F. Werner, 4OR-Q J. Oper. Res., published online.","DOI":"10.1007\/s10288-025-00606-x"},{"key":"ref_67","unstructured":"Escalona, D., and Vakhania, N. (2024). A Study of Single-Machine Scheduling Problem with a Fixed Number of Release Times and Two Delivery Times. Working Manuscript. [Bachelor\u2019s Thesis, Universidad Aut\u00f3noma del Estado de Morelos]. Available online: https:\/\/riaa.uaem.mx\/xmlui\/bitstream\/handle\/20.500.12055\/4772\/EACDNN07.pdf?sequence=1&isAllowed=y."},{"key":"ref_68","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1287\/opre.31.2.381","article-title":"Preemptive Scheduling of a Single Machine to Minimize Maximum Cost Subject to Release Dates and Precedence Constraints","volume":"31","author":"Baker","year":"1983","journal-title":"Oper. Res."},{"key":"ref_69","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1023\/A:1018968332237","article-title":"Jackson\u2019s Pseudo Preemptive Schedule for Pm\/ri,qi\/Cmax problem","volume":"83","author":"Carlier","year":"1998","journal-title":"Ann. Oper. Res."},{"key":"ref_70","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1287\/mnsc.34.3.391","article-title":"The Shifting Bottleneck Procedure for Job Shop Scheduling","volume":"34","author":"Adams","year":"1988","journal-title":"Manag. Sci."},{"key":"ref_71","doi-asserted-by":"crossref","unstructured":"Pacheco-Valencia, V.H., Vakhania, N., Hern\u00e1ndez-Mira, F.\u00c1., and Hern\u00e1ndez-Aguilar, J.A. (2022). A Multi-Phase Method for Euclidean Traveling Salesman Problems. Axioms, 11.","DOI":"10.3390\/axioms11090439"},{"key":"ref_72","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/s10951-006-5595-4","article-title":"A Note on Scheduling Equal-Length Jobs to Maximize Throughput","volume":"9","author":"Chrobak","year":"2006","journal-title":"J. Sched."},{"key":"ref_73","unstructured":"Brucker, P., and Kravchenko, S. (1999). Preemption can Make Parallel Machine Scheduling Problems Hard. Osnabru\u00a8cker Schriften Math. Fachbereich Mathematik\/Informatik, Reihe P, 211."},{"key":"ref_74","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1080\/02331939708844360","article-title":"Single Machine Scheduling with Deadlines, Release and due-dates","volume":"42","author":"Gordon","year":"1997","journal-title":"Optimization"},{"key":"ref_75","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1051\/ro:2001103","article-title":"Single Machine Preepmptive Scheduling to Minimize the Weighted Number of Late Jobs with Deadlines and Nested Release\/due-date Intervals","volume":"35","author":"Gordon","year":"2001","journal-title":"RAIRO Oper. Res."},{"key":"ref_76","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1287\/moor.15.3.483","article-title":"Minimizing Total Tardiness on One Processor is NP-hard","volume":"25","author":"Du","year":"1990","journal-title":"Math. Oper. Res."},{"key":"ref_77","first-page":"245","article-title":"Decomposition of the Single Machine Total Tardiness Problem","volume":"19","author":"Swarcz","year":"1996","journal-title":"Oper. Res. Lett."},{"key":"ref_78","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1287\/opre.17.4.701","article-title":"One-Machine Sequencing to Minimize Certain Functions of Job Tardiness","volume":"17","author":"Emmons","year":"1969","journal-title":"Oper. Res."},{"key":"ref_79","doi-asserted-by":"crossref","first-page":"1025","DOI":"10.1287\/opre.42.6.1025","article-title":"The Total Tardiness Problem: Review and Extensions","volume":"42","author":"Koulamas","year":"1994","journal-title":"Oper. Res."},{"key":"ref_80","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ejor.2009.04.007","article-title":"The Single-Machine Total Tardiness Scheduling Problem: Review and Extensions","volume":"202","author":"Koulamas","year":"2010","journal-title":"Eur. J. Oper. Res."},{"key":"ref_81","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0166-218X(99)00238-3","article-title":"Scheduling Equal-Length Jobs on Identical Parallel Machines","volume":"103","author":"Baptiste","year":"2000","journal-title":"Discret. Appl. Math."},{"key":"ref_82","doi-asserted-by":"crossref","first-page":"619","DOI":"10.1016\/j.camwa.2009.06.008","article-title":"A Graphical Realization of the Dynamic Programming Method for Solving NP-Hard Combinatorial Problems","volume":"58","author":"Lazarev","year":"2009","journal-title":"Comput. Math. Appl."},{"key":"ref_83","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1080\/00207543.2014.922708","article-title":"A New Graphical Approach for Solving Single Machine Problems Approximately","volume":"52","author":"Gafarov","year":"2014","journal-title":"Int. J. Prod. Res."},{"key":"ref_84","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1016\/j.ipl.2011.10.013","article-title":"A Note on a Single Machine Scheduling with Generalized Total Tardiness Objective Function","volume":"112","author":"Gafarov","year":"2012","journal-title":"Inf. Process. Lett."},{"key":"ref_85","doi-asserted-by":"crossref","first-page":"2061","DOI":"10.1016\/j.mcm.2009.01.003","article-title":"Algorithms for Special Cases of the Single Machine Total Tardiness Problem and an Application to the Even-Odd Partition Problem","volume":"49","author":"Lazarev","year":"2009","journal-title":"Math. Comput. Model."},{"key":"ref_86","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/S0022-0000(03)00070-9","article-title":"Preemptive Scheduling in Overloaded Systems","volume":"67","author":"Chrobak","year":"2003","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_87","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1002\/1099-1425(200011\/12)3:6<333::AID-JOS53>3.0.CO;2-8","article-title":"Restarts can Help in On-line Minimization of the Maximum Delivery Time on a Single Machine","volume":"3","author":"Hoogeveen","year":"2000","journal-title":"J. Sched."},{"key":"ref_88","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1016\/j.mathsocsci.2011.04.004","article-title":"Single Machine Scheduling Problems with Financial Resource Constraints: Some Complexity ResultResults and Properties","volume":"62","author":"Gafarov","year":"2011","journal-title":"Math. Soc. Sci."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/19\/1\/38\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,5]],"date-time":"2026-01-05T12:46:29Z","timestamp":1767617189000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/19\/1\/38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,4]]},"references-count":88,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,1]]}},"alternative-id":["a19010038"],"URL":"https:\/\/doi.org\/10.3390\/a19010038","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,4]]}}}