{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T22:17:33Z","timestamp":1772057853590,"version":"3.50.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,10,13]],"date-time":"2024-10-13T00:00:00Z","timestamp":1728777600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,10,13]],"date-time":"2024-10-13T00:00:00Z","timestamp":1728777600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Karlsruher Institut f\u00fcr Technologie (KIT)"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The customer order scheduling problem has garnered considerable attention in the recent scheduling literature. It is assumed that each of several customer orders consists of several jobs, and each customer order is completed only if each job of the order is completed. In this paper, we consider the customer order scheduling problem in a machine environment where each customer places exactly one job on each machine. The objective is to minimize the earliness\u2013tardiness, where tardiness is defined as the time an order is finished past its due date, and earliness is the time a job is finished before its due date or the completion time of the corresponding order, whichever is later. Even though the earliness\u2013tardiness criterion is an important objective for just-in-time production, this problem has not been studied in the context of the customer order scheduling problem. We provide a mixed-integer linear programming (MILP) formulation for this problem and derive multiple problem properties. Furthermore, we develop six different heuristics for this problem configuration. They follow the structure of the iterated greedy algorithm and additionally use a refinement function in which they differ. In a computational experiment, the algorithms were compared with each other and outperformed a solver solution of the MILP, which proves their ability to efficiently solve the problem configuration.<\/jats:p>","DOI":"10.1007\/s10951-024-00814-z","type":"journal-article","created":{"date-parts":[[2024,10,13]],"date-time":"2024-10-13T21:01:43Z","timestamp":1728853303000},"page":"525-543","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Minimizing the earliness\u2013tardiness for the customer order scheduling problem in a dedicated machine environment"],"prefix":"10.1007","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7107-4213","authenticated-orcid":false,"given":"Julius","family":"Hoffmann","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0753-0517","authenticated-orcid":false,"given":"Janis S.","family":"Neufeld","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4711-2184","authenticated-orcid":false,"given":"Udo","family":"Buscher","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,10,13]]},"reference":[{"issue":"2","key":"814_CR1","doi-asserted-by":"publisher","first-page":"223","DOI":"10.5267\/j.ijiec.2021.11.002","volume":"13","author":"MP Antonioli","year":"2022","unstructured":"Antonioli, M. P., Rodrigues, C. D., & Prata, B. A. (2022). Minimizing total tardiness for the order scheduling problem with sequence-dependent setup times using hybrid matheuristics. International Journal of Industrial Engineering Computations, 13(2), 223\u2013236. https:\/\/doi.org\/10.5267\/j.ijiec.2021.11.002","journal-title":"International Journal of Industrial Engineering Computations"},{"issue":"4\u20135","key":"814_CR2","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/S0895-7177(00)00250-8","volume":"33","author":"J Bank","year":"2001","unstructured":"Bank, J., & Werner, F. (2001). Heuristic algorithms for unrelated parallel machine scheduling with a common due date, release dates, and linear earliness and tardiness penalties. Mathematical and Computer Modelling, 33(4\u20135), 363\u2013383. https:\/\/doi.org\/10.1016\/S0895-7177(00)00250-8","journal-title":"Mathematical and Computer Modelling"},{"issue":"3","key":"814_CR3","doi-asserted-by":"publisher","first-page":"167","DOI":"10.5267\/j.jpm.2022.1.001","volume":"7","author":"SA Braga-Santos","year":"2022","unstructured":"Braga-Santos, S. A., Barroso, G. C., & Prata, B. A. (2022). A size-reduction algorithm for the order scheduling problem with total tardiness minimization. Journal of Project Management, 7(3), 167\u2013176. https:\/\/doi.org\/10.5267\/j.jpm.2022.1.001","journal-title":"Journal of Project Management"},{"issue":"1\u20134","key":"814_CR4","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/s00170-016-9123-1","volume":"99","author":"H Dauod","year":"2018","unstructured":"Dauod, H., Li, D., Yoon, S. W., et al. (2018). Multi-objective optimization of the order scheduling problem in mail-order pharmacy automation systems. The International Journal of Advanced Manufacturing Technology, 99(1\u20134), 73\u201383. https:\/\/doi.org\/10.1007\/s00170-016-9123-1","journal-title":"The International Journal of Advanced Manufacturing Technology"},{"issue":"101","key":"814_CR5","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/j.swevo.2022.101149","volume":"75","author":"LR de Abreu","year":"2022","unstructured":"de Abreu, L. R., de Athayde, P. B., Gomes, A. C., et al. (2022). A novel BRKGA for the customer order scheduling with missing operations to minimize total tardiness. Swarm and Evolutionary Computation, 75(101), 149. https:\/\/doi.org\/10.1016\/j.swevo.2022.101149","journal-title":"Swarm and Evolutionary Computation"},{"key":"814_CR6","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/j.cor.2016.09.010","volume":"78","author":"JM Framinan","year":"2017","unstructured":"Framinan, J. M., & Perez-Gonzalez, P. (2017). New approximate algorithms for the customer order scheduling problem with total completion time objective. Computers & Operations Research, 78, 181\u2013192. https:\/\/doi.org\/10.1016\/j.cor.2016.09.010","journal-title":"Computers & Operations Research"},{"issue":"3","key":"814_CR7","doi-asserted-by":"publisher","first-page":"840","DOI":"10.1016\/j.ejor.2017.10.064","volume":"266","author":"JM Framinan","year":"2018","unstructured":"Framinan, J. M., & Perez-Gonzalez, P. (2018). Order scheduling with tardiness objective: Improved approximate solutions. European Journal of Operational Research, 266(3), 840\u2013850. https:\/\/doi.org\/10.1016\/j.ejor.2017.10.064","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"814_CR8","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1016\/j.ejor.2018.04.033","volume":"273","author":"JM Framinan","year":"2019","unstructured":"Framinan, J. M., Perez-Gonzalez, P., & Fernandez-Viagas, V. (2019). Deterministic assembly scheduling problems: A review and classification of concurrent-type scheduling models and solution procedures. European Journal of Operational Research, 273(2), 401\u2013417. https:\/\/doi.org\/10.1016\/j.ejor.2018.04.033","journal-title":"European Journal of Operational Research"},{"issue":"9","key":"814_CR9","doi-asserted-by":"publisher","first-page":"1927","DOI":"10.1016\/j.cor.2011.08.004","volume":"39","author":"E Gerstl","year":"2012","unstructured":"Gerstl, E., & Mosheiov, G. (2012). Scheduling job classes on uniform machines. Computers & Operations Research, 39(9), 1927\u20131932. https:\/\/doi.org\/10.1016\/j.cor.2011.08.004","journal-title":"Computers & Operations Research"},{"issue":"5\u20136","key":"814_CR10","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1007\/s00170-007-0998-8","volume":"37","author":"O Haz\u0131r","year":"2008","unstructured":"Haz\u0131r, O., G\u00fcnalay, Y., & Erel, E. (2008). Customer order scheduling problem: A comparative metaheuristics study. The International Journal of Advanced Manufacturing Technology, 37(5\u20136), 589\u2013598. https:\/\/doi.org\/10.1007\/s00170-007-0998-8","journal-title":"The International Journal of Advanced Manufacturing Technology"},{"issue":"10","key":"814_CR11","doi-asserted-by":"publisher","first-page":"1594","DOI":"10.1016\/j.ifacol.2022.09.618","volume":"55","author":"J Hoffmann","year":"2022","unstructured":"Hoffmann, J., Neufeld, J. S., & Buscher, U. (2022). Iterated greedy algorithms for customer order scheduling with dedicated machines. IFAC-PapersOnLine, 55(10), 1594\u20131599. https:\/\/doi.org\/10.1016\/j.ifacol.2022.09.618","journal-title":"IFAC-PapersOnLine"},{"issue":"8","key":"814_CR12","doi-asserted-by":"publisher","first-page":"1464","DOI":"10.1016\/j.cor.2009.11.002","volume":"37","author":"S Kedad-Sidhoum","year":"2010","unstructured":"Kedad-Sidhoum, S., & Sourd, F. (2010). Fast neighborhood search for the single machine earliness-tardiness scheduling problem. Computers & Operations Research, 37(8), 1464\u20131471. https:\/\/doi.org\/10.1016\/j.cor.2009.11.002","journal-title":"Computers & Operations Research"},{"issue":"1","key":"814_CR13","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s10951-017-0549-6","volume":"22","author":"A Kramer","year":"2019","unstructured":"Kramer, A., & Subramanian, A. (2019). A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems. Journal of Scheduling, 22(1), 21\u201357. https:\/\/doi.org\/10.1007\/s10951-017-0549-6","journal-title":"Journal of Scheduling"},{"key":"814_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1155\/2018\/4657368","volume":"2018","author":"JY Kung","year":"2018","unstructured":"Kung, J. Y., Duan, J., Xu, J., et al. (2018). Metaheuristics for order scheduling problem with unequal ready times. Discrete Dynamics in Nature and Society, 2018, 1\u201313. https:\/\/doi.org\/10.1155\/2018\/4657368","journal-title":"Discrete Dynamics in Nature and Society"},{"issue":"1","key":"814_CR15","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1016\/j.ijpe.2013.01.025","volume":"144","author":"IS Lee","year":"2013","unstructured":"Lee, I. S. (2013). Minimizing total tardiness for the order scheduling problem. International Journal of Production Economics, 144(1), 128\u2013134. https:\/\/doi.org\/10.1016\/j.ijpe.2013.01.025","journal-title":"International Journal of Production Economics"},{"issue":"5","key":"814_CR16","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/s10951-005-2860-x","volume":"8","author":"JYT Leung","year":"2005","unstructured":"Leung, J. Y. T., Li, H., & Pinedo, M. (2005). Order Scheduling in an Environment with Dedicated Resources in Parallel. Journal of Scheduling, 8(5), 355\u2013386. https:\/\/doi.org\/10.1007\/s10951-005-2860-x","journal-title":"Journal of Scheduling"},{"issue":"3","key":"814_CR17","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/j.ipl.2007.03.002","volume":"103","author":"JYT Leung","year":"2007","unstructured":"Leung, J. Y. T., Li, H., Pinedo, M., et al. (2007). Minimizing total weighted completion time when scheduling orders in a flexible environment with uniform machines. Information Processing Letters, 103(3), 119\u2013129. https:\/\/doi.org\/10.1016\/j.ipl.2007.03.002","journal-title":"Information Processing Letters"},{"issue":"1","key":"814_CR18","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.ejor.2007.05.052","volume":"190","author":"JYT Leung","year":"2008","unstructured":"Leung, J. Y. T., Lee, C., Ng, C., et al. (2008). Preemptive multiprocessor order scheduling to minimize total weighted flowtime. European Journal of Operational Research, 190(1), 40\u201351. https:\/\/doi.org\/10.1016\/j.ejor.2007.05.052","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"814_CR19","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/s10479-007-0270-5","volume":"159","author":"JYT Leung","year":"2008","unstructured":"Leung, J. Y. T., Li, H., & Pinedo, M. (2008). Scheduling orders on either dedicated or flexible machines in parallel to minimize total weighted completion time. Annals of Operations Research, 159(1), 107\u2013123. https:\/\/doi.org\/10.1007\/s10479-007-0270-5","journal-title":"Annals of Operations Research"},{"issue":"14","key":"814_CR20","doi-asserted-by":"publisher","first-page":"4189","DOI":"10.1080\/00207543.2014.985392","volume":"53","author":"D Li","year":"2015","unstructured":"Li, D., & Yoon, S. W. (2015). A novel fill-time window minimisation problem and adaptive parallel tabu search algorithm in mail-order pharmacy automation system. International Journal of Production Research, 53(14), 4189\u20134205. https:\/\/doi.org\/10.1080\/00207543.2014.985392","journal-title":"International Journal of Production Research"},{"issue":"9\u201312","key":"814_CR21","doi-asserted-by":"publisher","first-page":"2171","DOI":"10.1007\/s00170-018-2222-4","volume":"99","author":"D Li","year":"2018","unstructured":"Li, D., Chen, K., Da, T., et al. (2018). Medication planogram design to minimize collation delays and makespan in parallel pharmaceutical automatic dispensing machines. The International Journal of Advanced Manufacturing Technology, 99(9\u201312), 2171\u20132180. https:\/\/doi.org\/10.1007\/s00170-018-2222-4","journal-title":"The International Journal of Advanced Manufacturing Technology"},{"issue":"21","key":"814_CR22","doi-asserted-by":"publisher","first-page":"4146","DOI":"10.3390\/math10214146","volume":"10","author":"LY Li","year":"2022","unstructured":"Li, L. Y., Xu, J. Y., Cheng, S. R., et al. (2022). A genetic hyper-heuristic for an order scheduling problem with two scenario-dependent parameters in a parallel-machine environment. Mathematics, 10(21), 4146. https:\/\/doi.org\/10.3390\/math10214146","journal-title":"Mathematics"},{"issue":"2","key":"814_CR23","doi-asserted-by":"publisher","first-page":"265","DOI":"10.5267\/j.ijiec.2023.2.002","volume":"14","author":"LY Li","year":"2023","unstructured":"Li, L. Y., Lin, W. C., Bai, D., et al. (2023). Composite heuristics and water wave optimality algorithms for tri-criteria multiple job classes and customer order scheduling on a single machine. International Journal of Industrial Engineering Computations , 14(2), 265\u2013274. https:\/\/doi.org\/10.5267\/j.ijiec.2023.2.002","journal-title":"International Journal of Industrial Engineering Computations"},{"issue":"9","key":"814_CR24","doi-asserted-by":"publisher","first-page":"890","DOI":"10.1080\/09511920902866104","volume":"22","author":"CH Liu","year":"2009","unstructured":"Liu, C. H. (2009). Lot streaming for customer order scheduling problem in job shop environments. International Journal of Computer Integrated Manufacturing, 22(9), 890\u2013907. https:\/\/doi.org\/10.1080\/09511920902866104","journal-title":"International Journal of Computer Integrated Manufacturing"},{"key":"814_CR25","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.cor.2013.10.013","volume":"44","author":"S Polyakovskiy","year":"2014","unstructured":"Polyakovskiy, S., & M\u2019Hallah, R. (2014). A multi-agent system for the weighted earliness tardiness parallel machine problem. Computers & Operations Research, 44, 115\u2013136. https:\/\/doi.org\/10.1016\/j.cor.2013.10.013","journal-title":"Computers & Operations Research"},{"issue":"4","key":"814_CR26","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/s10951-006-7042-y","volume":"9","author":"TA Roemer","year":"2006","unstructured":"Roemer, T. A. (2006). A note on the complexity of the concurrent open shop problem. Journal of Scheduling, 9(4), 389\u2013396. https:\/\/doi.org\/10.1007\/s10951-006-7042-y","journal-title":"Journal of Scheduling"},{"issue":"1\u20132","key":"814_CR27","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1080\/00207543.2017.1401247","volume":"56","author":"Z Shi","year":"2018","unstructured":"Shi, Z., Huang, Z., & Shi, L. (2018). Customer order scheduling on batch processing machines with incompatible job families. International Journal of Production Research, 56(1\u20132), 795\u2013808. https:\/\/doi.org\/10.1080\/00207543.2017.1401247","journal-title":"International Journal of Production Research"},{"issue":"1","key":"814_CR28","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1093\/comjnl\/bxx021","volume":"61","author":"CC Wu","year":"2018","unstructured":"Wu, C. C., Liu, S. C., Zhao, C., et al. (2018). A multi-machine order scheduling with learning using the genetic algorithm and particle swarm optimization. The Computer Journal, 61(1), 14\u201331. https:\/\/doi.org\/10.1093\/comjnl\/bxx021","journal-title":"The Computer Journal"},{"key":"814_CR29","doi-asserted-by":"publisher","first-page":"913","DOI":"10.1016\/j.swevo.2018.10.003","volume":"44","author":"CC Wu","year":"2019","unstructured":"Wu, C. C., Yang, T. H., Zhang, X., et al. (2019). Using heuristic and iterative greedy algorithms for the total weighted completion time order scheduling with release times. Swarm and Evolutionary Computation, 44, 913\u2013926. https:\/\/doi.org\/10.1016\/j.swevo.2018.10.003","journal-title":"Swarm and Evolutionary Computation"},{"key":"814_CR30","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/j.jmsy.2020.12.013","volume":"58","author":"CC Wu","year":"2021","unstructured":"Wu, C. C., Bai, D., Zhang, X., et al. (2021). A robust customer order scheduling problem along with scenario-dependent component processing times and due dates. Journal of Manufacturing Systems, 58, 291\u2013305. https:\/\/doi.org\/10.1016\/j.jmsy.2020.12.013","journal-title":"Journal of Manufacturing Systems"},{"issue":"9","key":"814_CR31","doi-asserted-by":"publisher","first-page":"1545","DOI":"10.3390\/math10091545","volume":"10","author":"CC Wu","year":"2022","unstructured":"Wu, C. C., Gupta, J. N. D., Lin, W. C., et al. (2022). Robust scheduling of two-agent customer orders with scenario-dependent component processing times and release dates. Mathematics, 10(9), 1545. https:\/\/doi.org\/10.3390\/math10091545","journal-title":"Mathematics"},{"key":"814_CR32","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/j.cor.2016.04.021","volume":"74","author":"J Xu","year":"2016","unstructured":"Xu, J., Wu, C. C., Yin, Y., et al. (2016). An order scheduling problem with position-based learning effect. Computers & Operations Research, 74, 175\u2013186. https:\/\/doi.org\/10.1016\/j.cor.2016.04.021","journal-title":"Computers & Operations Research"},{"issue":"16","key":"814_CR33","doi-asserted-by":"publisher","first-page":"4797","DOI":"10.1080\/00207543.2013.774475","volume":"51","author":"M Yousefi","year":"2013","unstructured":"Yousefi, M., & Yusuff, R. M. (2013). Minimising earliness and tardiness penalties in single machine scheduling against common due date using imperialist competitive algorithm. International Journal of Production Research, 51(16), 4797\u20134804. https:\/\/doi.org\/10.1080\/00207543.2013.774475","journal-title":"International Journal of Production Research"},{"issue":"3","key":"814_CR34","doi-asserted-by":"publisher","first-page":"1941","DOI":"10.1109\/TASE.2021.3062994","volume":"19","author":"Z Zhao","year":"2022","unstructured":"Zhao, Z., Zhou, M., & Liu, S. (2022). Iterated greedy algorithms for flow-shop scheduling problems: A tutorial. IEEE Transactions on Automation Science and Engineering, 19(3), 1941\u20131959. https:\/\/doi.org\/10.1109\/TASE.2021.3062994","journal-title":"IEEE Transactions on Automation Science and Engineering"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-024-00814-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-024-00814-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-024-00814-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,16]],"date-time":"2024-11-16T13:03:43Z","timestamp":1731762223000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-024-00814-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,13]]},"references-count":34,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["814"],"URL":"https:\/\/doi.org\/10.1007\/s10951-024-00814-z","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,13]]},"assertion":[{"value":"10 June 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 October 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflicts of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}