{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:59:31Z","timestamp":1760241571972,"version":"build-2065373602"},"reference-count":26,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2018,6,5]],"date-time":"2018-06-05T00:00:00Z","timestamp":1528156800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We study a scheduling problem in which jobs with release times and due dates are to be processed on a single machine. With the primary objective to minimize the maximum job lateness, the problem is strongly NP-hard. We describe a general algorithmic scheme to minimize the maximum job lateness, with the secondary objective to minimize the maximum job completion time. The problem of finding the Pareto-optimal set of feasible solutions with these two objective criteria is strongly NP-hard. We give the dominance properties and conditions when the Pareto-optimal set can be formed in polynomial time. These properties, together with our general framework, provide the theoretical background, so that the basic framework can be expanded to (exponential-time) implicit enumeration algorithms and polynomial-time approximation algorithms (generating the Pareto sub-optimal frontier with a fair balance between the two objectives). Some available in the literature experimental results confirm the practical efficiency of the proposed framework.<\/jats:p>","DOI":"10.3390\/a11060080","type":"journal-article","created":{"date-parts":[[2018,6,5]],"date-time":"2018-06-05T11:04:46Z","timestamp":1528196686000},"page":"80","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Scheduling a Single Machine with Primary and Secondary Objectives"],"prefix":"10.3390","volume":"11","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 Autonoma del Estado de Morelos, 62210 Cuernavaca, Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,6,5]]},"reference":[{"key":"ref_1","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP\u2014Completeness, W. H. Freeman and Company."},{"key":"ref_2","unstructured":"Jackson, J.R. (1955). Schedulig a Production Line to Minimize the Maximum Tardiness. Manegement Scince Research Project, University of California, Office of Technical Services."},{"key":"ref_3","unstructured":"Schrage, L. (1971). Obtaining Optimal Solutions to Resource Constrained Network Scheduling Problems, Unpublished work."},{"key":"ref_4","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_5","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":"Mathem. Oper. Res."},{"key":"ref_6","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_7","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1080\/05695557808975201","article-title":"heuristic procedures for the single machine problem to minimize maximum lateness","volume":"10","author":"Larson","year":"1978","journal-title":"AIIE Trans."},{"key":"ref_8","first-page":"205","article-title":"Performance analysis of six approximation algorithms for the one-machine maximum lateness scheduling problem with ready times","volume":"22","author":"Kise","year":"1979","journal-title":"J. Oper. Res. Soc. Japan"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"484671","DOI":"10.1155\/2015\/484671","article-title":"Theoretical Expectation versus Practical Performance of Jackson\u2019s heuristic","volume":"2015","author":"Vakhania","year":"2015","journal-title":"Math. Probl. Eng."},{"key":"ref_10","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_11","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/S0377-2217(82)80007-6","article-title":"The one\u2013machine sequencing problem","volume":"11","author":"Carlier","year":"1982","journal-title":"Eur. J. Oper. Res."},{"key":"ref_12","unstructured":"Sadykov, R., and Lazarev, A. (2005, January June). Experimental comparison of branch-and-bound algorithms for the 1|rj|Lmax problem. Proceedings of the Seventh International Workshop MAPSP\u201905, Siena, Italy."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1016\/0377-2217(86)90191-8","article-title":"A block approach for single-machine scheduling with release dates and due dates","volume":"26","author":"Grabowski","year":"1986","journal-title":"Eur. J. Oper. Res."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1080\/07408178508975300","article-title":"Dessouky and Richard E. DeVor. A Forward-Backward Procedure for the Single Machine Problem to Minimize Maximum Lateness","volume":"17","author":"Larson","year":"1985","journal-title":"IIE Trans."},{"key":"ref_15","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_16","doi-asserted-by":"crossref","first-page":"1537","DOI":"10.1016\/j.cor.2009.11.008","article-title":"Single machine scheduling to minimize maximum lateness subject to release dates and precedence constraints","volume":"37","author":"Liu","year":"2010","journal-title":"Comput. Oper. Res."},{"key":"ref_17","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_18","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","article-title":"Complexity of machine scheduling problems","volume":"1","author":"Lenstra","year":"1977","journal-title":"Ann. Discret. Math."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1016\/j.dam.2011.07.005","article-title":"Approximation algorithms for no idle time scheduling on a single machine with release times and delivery times","volume":"164","author":"Kacem","year":"2011","journal-title":"Discret. Appl. Math."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"943","DOI":"10.1134\/S1064230706060098","article-title":"The Pareto-optimal set of the NP-hard problem of minimization of the maximum lateness for a single machine","volume":"45","author":"Lazarev","year":"2006","journal-title":"J. Comput. Syst. Sci. Int."},{"key":"ref_21","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":"2016","journal-title":"Optim. Lett."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/j.cie.2010.03.007","article-title":"Exact resolution of the one-machine sequencing problem with no machine idle time","volume":"59","author":"Carlier","year":"2010","journal-title":"Comp. Ind. Eng."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"2543","DOI":"10.1016\/j.dam.2008.03.010","article-title":"On single-machine scheduling without intermediate delays","volume":"156","year":"2008","journal-title":"Discrete Appl. Math."},{"key":"ref_24","unstructured":"Ehrgott, M. (2005). Multicriteria Optimization, Springer Science & Business Media."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1","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_26","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/S0196-6774(03)00072-5","article-title":"A better algorithm for sequencing with release and delivery times on identical processors","volume":"48","author":"Vakhania","year":"2003","journal-title":"J. Algorithms"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/6\/80\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:07:26Z","timestamp":1760195246000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/6\/80"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,5]]},"references-count":26,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2018,6]]}},"alternative-id":["a11060080"],"URL":"https:\/\/doi.org\/10.3390\/a11060080","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2018,6,5]]}}}