{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T15:34:59Z","timestamp":1786980899194,"version":"build-2736575974"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T00:00:00Z","timestamp":1685577600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,7,4]],"date-time":"2023-07-04T00:00:00Z","timestamp":1688428800000},"content-version":"vor","delay-in-days":33,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"TU Wien"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>The Oven Scheduling Problem (OSP) is a new parallel batch scheduling problem that arises in the area of electronic component manufacturing. Jobs need to be scheduled to one of several ovens and may be processed simultaneously in one batch if they have compatible requirements. The scheduling of jobs must respect several constraints concerning eligibility and availability of ovens, release dates of jobs, setup times between batches as well as oven capacities. Running the ovens is highly energy-intensive and thus the main objective, besides finishing jobs on time, is to minimize the cumulative batch processing time across all ovens. This objective distinguishes the OSP from other batch processing problems which typically minimize objectives related to makespan, tardiness or lateness. We propose to solve this NP-hard scheduling problem using exact techniques and present two different modelling approaches, one based on batch positions and another on representative jobs for batches. These models are formulated as constraint programming (CP) and integer linear programming (ILP) models and implemented both in the solver-independent modeling language MiniZinc and using interval variables in CP Optimizer. An extensive experimental evaluation of our solution methods is performed on a diverse set of problem instances. We evaluate the performance of several state-of-the-art solvers on the different models and on three variants of the objective function that reflect different real-life scenarios. We show that our models can find feasible solutions for instances of realistic size, many of those being provably optimal or nearly optimal solutions.<\/jats:p>","DOI":"10.1007\/s10601-023-09347-2","type":"journal-article","created":{"date-parts":[[2023,7,10]],"date-time":"2023-07-10T09:05:00Z","timestamp":1688979900000},"page":"320-361","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Exact methods for the Oven Scheduling Problem"],"prefix":"10.1007","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9916-9011","authenticated-orcid":false,"given":"Marie-Louise","family":"Lackner","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christoph","family":"Mrkvicka","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nysret","family":"Musliu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Walkiewicz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Felix","family":"Winter","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,7,4]]},"reference":[{"issue":"2","key":"9347_CR1","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1016\/S0377-2217(99)00153-8","volume":"120","author":"CN Potts","year":"2000","unstructured":"Potts, C. N., & Kovalyov, M. Y. (2000). Scheduling with batching: A review. European Journal of Operational Research, 120(2), 228\u2013249.","journal-title":"European Journal of Operational Research"},{"issue":"9\u201310","key":"9347_CR2","doi-asserted-by":"publisher","first-page":"990","DOI":"10.1007\/s00170-005-2585-1","volume":"29","author":"M Mathirajan","year":"2006","unstructured":"Mathirajan, M., & Sivakumar, A. I. (2006). A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor. The International Journal of Advanced Manufacturing Technology, 29(9\u201310), 990\u20131001.","journal-title":"The International Journal of Advanced Manufacturing Technology"},{"issue":"1","key":"9347_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2021.06.012","volume":"298","author":"JW Fowler","year":"2022","unstructured":"Fowler, J. W., & M\u00f6nch, L. (2022). A survey of scheduling with parallel batch (p-batch) processing. European Journal of Operational Research, 298(1), 1\u201324.","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"9347_CR4","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1016\/j.ejor.2012.04.008","volume":"221","author":"A Malapert","year":"2012","unstructured":"Malapert, A., Gu\u00e9ret, C., & Rousseau, L.-M. (2012). A constraint programming approach for a batch processing problem with non-identical job sizes. European Journal of Operational Research, 221(3), 533\u2013545.","journal-title":"European Journal of Operational Research"},{"issue":"4","key":"9347_CR5","doi-asserted-by":"publisher","first-page":"764","DOI":"10.1287\/opre.40.4.764","volume":"40","author":"C-Y Lee","year":"1992","unstructured":"Lee, C.-Y., Uzsoy, R., & Martin-Vega, L. A. (1992). Efficient algorithms for scheduling semiconductor burn-in operations. Operations Research, 40(4), 764\u2013775.","journal-title":"Operations Research"},{"issue":"3","key":"9347_CR6","doi-asserted-by":"crossref","first-page":"1376","DOI":"10.1109\/TASE.2019.2946196","volume":"17","author":"Z Zhao","year":"2020","unstructured":"Zhao, Z., Liu, S., Zhou, M., Guo, X., & Qi, L. (2020). Decomposition Method for New Single-Machine Scheduling Problems From Steel Production Systems. IEEE Transactions on Automation Science and Engineering, 17(3), 1376\u20131387.","journal-title":"IEEE Transactions on Automation Science and Engineering"},{"key":"9347_CR7","doi-asserted-by":"crossref","unstructured":"Polyakovskiy, S., Thiruvady, D., & M\u2019Hallah, R. (2020). Just-in-time batch scheduling subject to batch size. In Proceedings of the 2020 genetic and evolutionary computation conference (GECCO \u201920, pp. 228\u2013235). New York, NY: Association for Computing Machinery","DOI":"10.1145\/3377930.3390207"},{"key":"9347_CR8","doi-asserted-by":"crossref","unstructured":"Tang, T.\u00a0Y. & Beck, J.\u00a0C. (2020). CP and Hybrid Models for Two-Stage Batching and Scheduling. In Integration of constraint programming, artificial intelligence, and operations research (Lecture Notes in Computer Science, pp 431\u2013446)","DOI":"10.1007\/978-3-030-58942-4_28"},{"issue":"1","key":"9347_CR9","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1002\/(SICI)1099-1425(199806)1:1<31::AID-JOS4>3.0.CO;2-R","volume":"1","author":"P Brucker","year":"1998","unstructured":"Brucker, P., Gladky, A., Hoogeveen, H., Kovalyov, M. Y., Potts, C. N., Tautenhahn, T., & Van De Velde, S. L. (1998). Scheduling a batching machine. Journal of Scheduling, 1(1), 31\u201354.","journal-title":"Journal of Scheduling"},{"key":"9347_CR10","doi-asserted-by":"crossref","unstructured":"Kosch, S. & Beck, J.\u00a0C. (2014). A new mip model for parallel-batch scheduling with non-identical job sizes. In International Conference on AI and OR techniques in constriant programming for combinatorial optimization problems (pp. 55\u201370). Springer","DOI":"10.1007\/978-3-319-07046-9_5"},{"key":"9347_CR11","doi-asserted-by":"crossref","unstructured":"Trindade, R.\u00a0S., de\u00a0Ara\u00fajo, O.\u00a0C., & Fampa, M. (2020). Arc-flow approach for parallel batch processing machine scheduling with non-identical job sizes. In International Symposium on Combinatorial Optimization (pp. 179\u2013190). Springer","DOI":"10.1007\/978-3-030-53262-8_15"},{"issue":"3\u20134","key":"9347_CR12","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/S0360-8352(01)00009-2","volume":"39","author":"M Azizoglu","year":"2001","unstructured":"Azizoglu, M., & Webster, S. (2001). Scheduling a batch processing machine with incompatible job families. Computers & Industrial Engineering, 39(3\u20134), 325\u2013335.","journal-title":"Computers & Industrial Engineering"},{"issue":"10","key":"9347_CR13","doi-asserted-by":"publisher","first-page":"1720","DOI":"10.1016\/j.cor.2009.12.007","volume":"37","author":"NR Parsa","year":"2010","unstructured":"Parsa, N. R., Karimi, B., & Kashan, A. H. (2010). A branch and price algorithm to minimize makespan on a single batch processing machine with non-identical job sizes. Computers & Operations Research, 37(10), 1720\u20131730.","journal-title":"Computers & Operations Research"},{"issue":"5","key":"9347_CR14","doi-asserted-by":"publisher","first-page":"767","DOI":"10.1007\/s10845-009-0272-z","volume":"22","author":"P Damodaran","year":"2011","unstructured":"Damodaran, P., V\u00e9lez-Gallego, M. C., & Maya, J. (2011). A grasp approach for makespan minimization on parallel batch processing machines. Journal of Intelligent Manufacturing, 22(5), 767\u2013777.","journal-title":"Journal of Intelligent Manufacturing"},{"issue":"8","key":"9347_CR15","doi-asserted-by":"publisher","first-page":"2462","DOI":"10.1080\/00207543.2012.748227","volume":"51","author":"E Cakici","year":"2013","unstructured":"Cakici, E., Mason, S. J., Fowler, J. W., & Geismar, H. N. (2013). Batch scheduling on parallel machines with dynamic job arrivals and incompatible job families. International Journal of Production Research, 51(8), 2462\u20132477.","journal-title":"International Journal of Production Research"},{"issue":"10","key":"9347_CR16","doi-asserted-by":"publisher","first-page":"3016","DOI":"10.1016\/j.cor.2005.11.011","volume":"34","author":"S Malve","year":"2007","unstructured":"Malve, S., & Uzsoy, R. (2007). A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and incompatible job families. Computers & Operations Research, 34(10), 3016\u20133028.","journal-title":"Computers & Operations Research"},{"issue":"5\u20138","key":"9347_CR17","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1007\/s00170-014-6195-7","volume":"75","author":"A Costa","year":"2014","unstructured":"Costa, A., Cappadonna, F. A., & Fichera, S. (2014). A novel genetic algorithm for the hybrid flow shop scheduling with parallel batching and eligibility constraints. The International Journal of Advanced Manufacturing Technology, 75(5\u20138), 833\u2013847.","journal-title":"The International Journal of Advanced Manufacturing Technology"},{"issue":"2","key":"9347_CR18","doi-asserted-by":"publisher","first-page":"765","DOI":"10.1016\/j.asoc.2012.10.021","volume":"13","author":"B Cheng","year":"2013","unstructured":"Cheng, B., Wang, Q., Yang, S., & Hu, X. (2013). An improved ant colony optimization for scheduling identical parallel batching machines with arbitrary job sizes. Applied Soft Computing, 13(2), 765\u2013772.","journal-title":"Applied Soft Computing"},{"key":"9347_CR19","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.cie.2018.06.018","volume":"123","author":"H Zhou","year":"2018","unstructured":"Zhou, H., Pang, J., Chen, P.-K., & Chou, F.-D. (2018). A modified particle swarm optimization algorithm for a batch-processing machine scheduling problem with arbitrary release times and non-identical job sizes. Computers & Industrial Engineering, 123, 67\u201381.","journal-title":"Computers & Industrial Engineering"},{"issue":"1","key":"9347_CR20","doi-asserted-by":"publisher","first-page":"1451","DOI":"10.1016\/j.eswa.2011.08.029","volume":"39","author":"P Damodaran","year":"2012","unstructured":"Damodaran, P., & V\u00e9lez-Gallego, M. C. (2012). A simulated annealing algorithm to minimize makespan of parallel batch processing machines with unequal job ready times. Expert Systems with Applications, 39(1), 1451\u20131458.","journal-title":"Expert Systems with Applications"},{"key":"9347_CR21","doi-asserted-by":"publisher","unstructured":"Lackner, M.-L., Mrkvicka, C., Musliu, N., Walkiewicz, D., & Winter, F. (2022a). Benchmark instances and models for the Oven Scheduling Problem [Data Set]. Zenodo. https:\/\/doi.org\/10.5281\/zenodo.7456938","DOI":"10.5281\/zenodo.7456938"},{"key":"9347_CR22","unstructured":"Lackner, M.-L., Mrkvicka, C., Musliu, N., Walkiewicz, D., & Winter, F. (2021). Minimizing Cumulative Batch Processing Time for an Industrial Oven Scheduling Problem. In 27th International conference on principles and practice of constraint programming (CP 2021), volume 210 of leibniz international proceedings in informatics (LIPIcs) (pp. 37:1\u201337:18). Dagstuhl, Germany: Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik"},{"key":"9347_CR23","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"RL Graham","year":"1979","unstructured":"Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5, 287\u2013326.","journal-title":"Annals of Discrete Mathematics"},{"issue":"7","key":"9347_CR24","doi-asserted-by":"publisher","first-page":"1615","DOI":"10.1080\/00207549408957026","volume":"32","author":"R Uzsoy","year":"1994","unstructured":"Uzsoy, R. (1994). Scheduling a single batch processing machine with non-identical job sizes. The International Journal of Production Research, 32(7), 1615\u20131635.","journal-title":"The International Journal of Production Research"},{"issue":"10","key":"9347_CR25","doi-asserted-by":"publisher","first-page":"2685","DOI":"10.1080\/00207549508904839","volume":"33","author":"R Uzsoy","year":"1995","unstructured":"Uzsoy, R. (1995). Scheduling batch processing machines with incompatible job families. International Journal of Production Research, 33(10), 2685\u20132708.","journal-title":"International Journal of Production Research"},{"key":"9347_CR26","doi-asserted-by":"crossref","unstructured":"Nethercote, N., Stuckey, P. J., Becket, R., Brand, S., Duck, G. J., & Tack, G. (2007). MiniZinc: Towards a Standard CP Modelling Language. In C. Bessi\u00e8re (Ed.), Principles and practice of constraint programming - CP 2007 (Lecture Notes in Computer Science, pp. 529\u2013543). Berlin, Heidelberg: Springer.","DOI":"10.1007\/978-3-540-74970-7_38"},{"key":"9347_CR27","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/978-1-4614-6940-7_15","volume-title":"Search methodologies","author":"K Deb","year":"2014","unstructured":"Deb, K. (2014). Multi-objective optimization. Search methodologies (pp. 403\u2013449). Boston, MA: Springer."},{"key":"9347_CR28","unstructured":"Miettinen, K. (2012). Nonlinear multiobjective optimization (vol. 12). New York: Springer Science & Business Media."},{"issue":"5","key":"9347_CR29","doi-asserted-by":"publisher","first-page":"912","DOI":"10.1016\/j.camwa.2011.11.057","volume":"63","author":"G Chiandussi","year":"2012","unstructured":"Chiandussi, G., Codegone, M., Ferrero, S., & Varesio, F. (2012). Comparison of multi-objective optimization methodologies for engineering applications. Computers & Mathematics with Applications, 63(5), 912\u2013942.","journal-title":"Computers & Mathematics with Applications"},{"issue":"2","key":"9347_CR30","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1007\/s10601-018-9281-x","volume":"23","author":"P Laborie","year":"2018","unstructured":"Laborie, P., Rogerie, J., Shaw, P., & Vil\u00edm, P. (2018). IBM ILOG CP optimizer for scheduling. Constraints, 23(2), 210\u2013250.","journal-title":"Constraints"},{"issue":"4","key":"9347_CR31","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1287\/ijoc.14.4.345.2826","volume":"14","author":"PV Hentenryck","year":"2002","unstructured":"Hentenryck, P. V. (2002). Constraint and integer programming in OPL. INFORMS Journal on Computing, 14(4), 345\u2013372.","journal-title":"INFORMS Journal on Computing"},{"key":"9347_CR32","unstructured":"(2017). IBM ILOG CPLEX Optimization studio, Getting Started with Scheduling in CPLEX Studio. IBM. https:\/\/www.ibm.com\/docs\/en\/SSSA5P_12.8.0\/ilog.odms.studio.help\/pdf\/sched_gs.pdf"},{"key":"9347_CR33","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1016\/j.cie.2016.11.001","volume":"102","author":"AM Ham","year":"2016","unstructured":"Ham, A. M., & Cakici, E. (2016). Flexible job shop scheduling problem with parallel batch processing machines: Mip and cp approaches. Computers & Industrial Engineering, 102, 160\u2013165.","journal-title":"Computers & Industrial Engineering"},{"key":"9347_CR34","doi-asserted-by":"crossref","unstructured":"Belov, G., Stuckey, P.\u00a0J., Tack, G., & Wallace, M. (2016). Improved linearization of constraint programming models. In M. Rueher (Ed.), Principles and Practice of Constraint Programming - 22nd International Conference, CP 2016, September 5-9, 2016, Proceedings, volume 9892 of Lecture Notes in Computer Science (pp 49\u201365). Toulouse, France: Springer.","DOI":"10.1007\/978-3-319-44953-1_4"},{"issue":"2","key":"9347_CR35","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1609\/aimag.v35i2.2539","volume":"35","author":"PJ Stuckey","year":"2014","unstructured":"Stuckey, P. J., Feydy, T., Schutt, A., Tack, G., & Fischer, J. (2014). The minizinc challenge 2008\u20132013. AI Magazine, 35(2), 55\u201360.","journal-title":"AI Magazine"},{"key":"9347_CR36","unstructured":"Zwicker, W. S. (2016). Introduction to the theory of voting. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, & A. D. Procaccia (Eds.), Handbook of computational social choice (chapter 2, pp. 23\u201356). Cambridge: Cambridge University Press."},{"key":"9347_CR37","unstructured":"Lackner, M.-L., Musliu, N., & Winter, F. (2022b). Solving an industrial oven scheduling problem with a simulated annealing approach. In Proceedings of the 13th international conference on the practice and theory of automated timetabling - PATAT 2022 - Volume III (pp 115\u2013120)"},{"key":"9347_CR38","unstructured":"Velez\u00a0Gallego, M.\u00a0C. (2009). Algorithms for scheduling parallel batch processing machines with non-identical job ready times. PhD thesis, Florida: International University"}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-023-09347-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10601-023-09347-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-023-09347-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,3]],"date-time":"2023-08-03T22:08:25Z","timestamp":1691100505000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10601-023-09347-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["9347"],"URL":"https:\/\/doi.org\/10.1007\/s10601-023-09347-2","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"value":"1383-7133","type":"print"},{"value":"1572-9354","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6]]},"assertion":[{"value":"24 March 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 July 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}