{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T10:59:08Z","timestamp":1780052348323,"version":"3.53.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T00:00:00Z","timestamp":1649116800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T00:00:00Z","timestamp":1649116800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006012","name":"Christian Doppler Forschungsgesellschaft","doi-asserted-by":"publisher","award":["Christian Doppler Laboratory for Artificial Intelligence and Optimization for Planning and Scheduling"],"award-info":[{"award-number":["Christian Doppler Laboratory for Artificial Intelligence and Optimization for Planning and Scheduling"]}],"id":[{"id":"10.13039\/501100006012","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we introduce a new problem in the field of production planning, called the production leveling problem. The task is to assign orders to production periods such that the load in each period and for each product type is balanced, capacity limits are not exceeded, and the orders\u2019 priorities are taken into account. Production leveling is an important intermediate step between long-term planning and the final scheduling of orders within a production period, as it is responsible for selecting good subsets of orders to be scheduled within each period. We provide a formal model of the problem and study its computational complexity. As an exact method for solving moderately sized instances, we introduce a mixed integer programming (MIP) formulation. For solving large problem instances, metaheuristic local search is investigated. A greedy heuristic and two neighborhood structures for local search are proposed in order to apply them using simulated annealing. Furthermore, three possible extensions that arise from the application in practice are described and implemented, both within the MIP model and within simulated annealing. We make publicly available a set of realistic problem instances from the industry as well as from random instance generators. The experimental evaluation on our test sets shows that the proposed MIP model is well suited for solving instances with up to 250 orders. Simulated annealing produces solutions with less than <jats:inline-formula><jats:alternatives><jats:tex-math>$$3\\%$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>3<\/mml:mn>\n                    <mml:mo>%<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> average optimality gap on small instances, and scales well up to thousands of orders and dozens of periods and product types. The metaheuristic method presented herein is already being successfully used in the industry.<\/jats:p>","DOI":"10.1007\/s10951-022-00721-1","type":"journal-article","created":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T13:10:16Z","timestamp":1649164216000},"page":"339-370","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Exact and meta-heuristic approaches for the production leveling problem"],"prefix":"10.1007","volume":"25","author":[{"given":"Johannes","family":"Vass","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9916-9011","authenticated-orcid":false,"given":"Marie-Louise","family":"Lackner","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christoph","family":"Mrkvicka","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3992-8637","authenticated-orcid":false,"given":"Nysret","family":"Musliu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1012-1258","authenticated-orcid":false,"given":"Felix","family":"Winter","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,4,5]]},"reference":[{"issue":"1","key":"721_CR1","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1002\/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J","volume":"1","author":"N Alon","year":"1998","unstructured":"Alon, N., Azar, Y., Woeginger, G. J., & Yadid, T. (1998). Approximation schemes for scheduling on parallel machines. Journal of Scheduling, 1(1), 55\u201366.","journal-title":"Journal of Scheduling"},{"issue":"2","key":"721_CR2","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1016\/j.cie.2010.11.002","volume":"60","author":"N Boysen","year":"2011","unstructured":"Boysen, N., & Fliedner, M. (2011). Scheduling aircraft landings to balance workload of ground staff. Computers & Industrial Engineering, 60(2), 206\u2013217.","journal-title":"Computers & Industrial Engineering"},{"issue":"2","key":"721_CR3","doi-asserted-by":"publisher","first-page":"674","DOI":"10.1016\/j.ejor.2006.10.010","volume":"183","author":"N Boysen","year":"2007","unstructured":"Boysen, N., Fliedner, M., & Scholl, A. (2007). A classification of assembly line balancing problems. European Journal of Operational Research, 183(2), 674\u2013693.","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"721_CR4","doi-asserted-by":"publisher","first-page":"818","DOI":"10.1016\/j.ejor.2008.06.038","volume":"197","author":"N Boysen","year":"2009","unstructured":"Boysen, N., Fliedner, M., & Scholl, A. (2009). The product rate variation problem and its relevance in real world mixed-model assembly lines. European Journal of Operational Research, 197(2), 818\u2013824.","journal-title":"European Journal of Operational Research"},{"key":"721_CR5","unstructured":"Castro, C., & Manzano, S. (2001). Variable and value ordering when solving balanced academic curriculum problems. In Proceedings of 6th Workshop of the ERCIM WG on Constraints.."},{"issue":"1","key":"721_CR6","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/s10732-011-9158-2","volume":"18","author":"M Chiarandini","year":"2012","unstructured":"Chiarandini, M., Di Gaspero, L., Gualandi, S., & Schaerf, A. (2012). The balanced academic curriculum problem revisited. Journal of Heuristics, 18(1), 119\u2013148.","journal-title":"Journal of Heuristics"},{"issue":"4","key":"721_CR7","first-page":"31","volume":"35","author":"BJ Coleman","year":"1994","unstructured":"Coleman, B. J., & Vaghefi, M. R. (1994). Heijunka (?): A key to the toyota production system. Production and Inventory Management Journal, 35(4), 31.","journal-title":"Production and Inventory Management Journal"},{"key":"721_CR8","doi-asserted-by":"crossref","unstructured":"Deb, K. (2014). Multi-objective optimization. In Search methodologies, (pp. 403\u2013449), Springer .","DOI":"10.1007\/978-1-4614-6940-7_15"},{"key":"721_CR9","doi-asserted-by":"crossref","unstructured":"Di\u00a0Gaspero, L., & Schaerf, A. (2008). Hybrid local search techniques for the generalized balanced academic curriculum problem. In M.\u00a0J. Blesa, C.\u00a0Blum, C.\u00a0Cotta, A.\u00a0J. Fern\u00e1ndez, J.\u00a0E. Gallardo, A.\u00a0Roli, and M.\u00a0Sampels, (Eds.), Hybrid Metaheuristics, 5th International Workshop, HM 2008, M\u00e1laga, Spain, October 8-9, 2008. Proceedings, volume 5296 of Lecture Notes in Computer Science, pp. 146\u2013157. Springer .","DOI":"10.1007\/978-3-540-88439-2_11"},{"key":"721_CR10","doi-asserted-by":"crossref","unstructured":"Flajolet, P., & Sedgewick, R. (2009). Analytic combinatorics. Cambridge University Press.","DOI":"10.1017\/CBO9780511801655"},{"key":"721_CR11","unstructured":"Garey, M. R., & Johnson, D. S. (1979). Computers and intractability (Vol. 174). W. H."},{"key":"721_CR12","unstructured":"Gurobi\u00a0Optimization, L. (2019). Gurobi optimizer reference manual . URL http:\/\/www.gurobi.com."},{"issue":"4598","key":"721_CR13","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671\u2013680.","journal-title":"Science"},{"issue":"3","key":"721_CR14","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/0377-2217(93)90215-9","volume":"66","author":"W Kubiak","year":"1993","unstructured":"Kubiak, W. (1993). Minimizing variation of production rates in just-in-time systems: A survey. European Journal of Operational Research, 66(3), 259\u2013271.","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"721_CR15","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1287\/msom.1070.0178","volume":"10","author":"W Kubiak","year":"2008","unstructured":"Kubiak, W., & Yavuz, M. (2008). Just-in-time smoothing through batching. Manufacturing & Service Operations Management, 10(3), 506\u2013518.","journal-title":"Manufacturing & Service Operations Management"},{"key":"721_CR16","unstructured":"Lackner, M.-L., Vass, J., & Musliu, N. (2019). Extended Complexity Results for the Production Leveling Problem. Technical Report CD-TR 2019\/2."},{"key":"721_CR17","unstructured":"Lindauer, M., Eggensperger, K., Feurer, M., Falkner, S., Biedenkapp, A., & Hutter, F. (2019) SMAC v3: Algorithm configuration in python. URL https:\/\/github.com\/automl\/SMAC3."},{"key":"721_CR18","unstructured":"Miettinen, K. (2012). Nonlinear multiobjective optimization (Vol. 12). Springer Science & Business Media."},{"issue":"2","key":"721_CR19","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1287\/mnsc.35.2.192","volume":"35","author":"J Miltenburg","year":"1989","unstructured":"Miltenburg, J. (1989). Level schedules for mixed-model assembly lines in just-in-time production systems. Management Science, 35(2), 192\u2013207.","journal-title":"Management Science"},{"key":"721_CR20","doi-asserted-by":"crossref","unstructured":"Mullinax, C., & Lawley, M. (2002). Assigning patients to nurses in neonatal intensive care. Journal of the Operational Research Society, 53(1), 25\u201335.","DOI":"10.1057\/palgrave\/jors\/2601265"},{"key":"721_CR21","unstructured":"Ohno, T., & Rosen, C. B. (1998). Toyota production system: Beyond large-scale production. Productivity Press."},{"issue":"10","key":"721_CR22","doi-asserted-by":"publisher","first-page":"1059","DOI":"10.1080\/0740817X.2012.763002","volume":"45","author":"P Punnakitikashem","year":"2013","unstructured":"Punnakitikashem, P., Rosenberber, J. M., & Buckley-Behan, D. F. (2013). A stochastic programming approach for integrated nurse staffing and assignment. IIE Transactions, 45(10), 1059\u20131076.","journal-title":"IIE Transactions"},{"key":"721_CR23","unstructured":"Schaus, P. (2009). Solving balancing and bin-packing problems with constraint programming. PhD thesis, UCL - Universit\u00e9 Catholique de Louvain. URL https:\/\/dial.uclouvain.be\/pr\/boreal\/en\/object\/boreal%3A23871."},{"key":"721_CR24","doi-asserted-by":"crossref","unstructured":"Schaus, P., Hentenryck, P.\u00a0V., & R\u00e9gin, J.-C. (May 2009). Scalable load balancing in nurse to patient assignment problems. In W.\u00a0J.\u00a0v. Hoeve and J.\u00a0N. Hooker (Eds.) Integration of AI and OR Techniques in Constraint rogramming for Combinatorial Optimization Problems, 6th International Conference, CPAIOR 2009, Pittsburgh, PA, USA, May 27-31, 2009, Proceedings, volume 5547 of Lecture Notes in Computer Science, pp. 248\u2013262. Springer .","DOI":"10.1007\/978-3-642-01929-6_19"},{"key":"721_CR25","unstructured":"Schreiber, E.\u00a0L. (2014). Optimal multi-way number partitioning. PhD thesis, University of California."},{"key":"721_CR26","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1016\/j.cor.2016.03.008","volume":"73","author":"S Schwerdfeger","year":"2016","unstructured":"Schwerdfeger, S., & Walter, R. (2016). A fast and effective subset sum based improvement procedure for workload balancing on identical parallel machines. Computers & Operations Research, 73, 84\u201391.","journal-title":"Computers & Operations Research"},{"key":"721_CR27","unstructured":"Skiena, S. .\u00a0S. (1998). The algorithm design manual. Springer Science & Business Media."},{"key":"721_CR28","unstructured":"Vass, J. (2019). Exact and metaheuristic approaches for the production leveling problem. Master\u2019s thesis, TU Wien, https:\/\/repositum.tuwien.at\/handle\/20.500.12708\/6542."},{"key":"721_CR29","unstructured":"Vass, J., Musliu, N., & Winter, F. (2020). Solving the production leveling problem with order-splitting and resource constraints. In Proceedings of the 13th International Conference on the Practice and Theory of Automated Timetabling - PATAT 2021: Volume I, pp. 261\u2013284. PATAT ."},{"key":"721_CR30","doi-asserted-by":"crossref","unstructured":"Vazirani, V. V. (2003). Approximation algorithms. Springer-Verlag.","DOI":"10.1007\/978-3-662-04565-7"},{"issue":"5","key":"721_CR31","doi-asserted-by":"publisher","first-page":"842","DOI":"10.1287\/opre.24.5.842","volume":"24","author":"DM Warner","year":"1976","unstructured":"Warner, D. M. (1976). Scheduling nursing personnel according to nursing preference: A mathematical programming approach. Operations Research, 24(5), 842\u2013856.","journal-title":"Operations Research"},{"key":"721_CR32","doi-asserted-by":"crossref","unstructured":"Yavuz, M., & Tufekci, S. (2006). A bounded dynamic programming solution to the batching problem in mixed-model just-in-time manufacturing systems. International Journal of Production Economics, 103(2), 841\u2013862.","DOI":"10.1016\/j.ijpe.2006.01.006"},{"key":"721_CR33","doi-asserted-by":"crossref","unstructured":"Yavuz, M., & Tufekci, S. (2006). Dynamic programming solution to the batching problem in just-in-time flow-shops. Computers & Industrial Engineering, 51(3), 416\u2013432.","DOI":"10.1016\/j.cie.2006.08.005"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-022-00721-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-022-00721-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-022-00721-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,7]],"date-time":"2022-07-07T10:35:37Z","timestamp":1657190137000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-022-00721-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,5]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["721"],"URL":"https:\/\/doi.org\/10.1007\/s10951-022-00721-1","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,5]]},"assertion":[{"value":"22 December 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 April 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}