{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:42:02Z","timestamp":1740145322015,"version":"3.37.3"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,6,11]],"date-time":"2020-06-11T00:00:00Z","timestamp":1591833600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,6,11]],"date-time":"2020-06-11T00:00:00Z","timestamp":1591833600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Szechenyi 2020","award":["EFOP-3.6.1-16-2016-00015"],"award-info":[{"award-number":["EFOP-3.6.1-16-2016-00015"]}]},{"name":"DFG grant","award":["FU860\/1-1"],"award-info":[{"award-number":["FU860\/1-1"]}]},{"DOI":"10.13039\/501100011019","name":"NKFIH","doi-asserted-by":"crossref","award":["SNN 129364"],"award-info":[{"award-number":["SNN 129364"]}],"id":[{"id":"10.13039\/501100011019","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cent Eur J Oper Res"],"published-print":{"date-parts":[[2021,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We deal with a very complex and hard scheduling problem. Two types of products are processed by a heterogeneous resource set, where resources have different operating capabilities and setup times are considered. The processing of the products follows different workflows, allowing also assembly lines. The complexity of the problem arises from having a huge number of products from both types. The goal is to process all products in minimum time, i.e., the makespan is to be minimized. We consider a special case, where there are two job types on four different tasks, and four types of machines. Some of the machines are multi-purpose and some operations can be processed by different machine types. The processing time of an operation may depend also on the machine that processes it. The problem is very difficult to solve even in this special setting. Because of the complexity of the problem an exact solver would require too much running time. We propose a compound method where a heuristic is combined with an exact solver. Our proposed heuristic is composed of several phases applying different smart strategies. In order to reduce the computational complexity of the exact approach, we exploit the makespan determined by the heuristic as an upper bound for the time horizon, which has a direct influence on the instance size used in the exact approach. We demonstrate the efficiency of our combined method on multiple problem classes. With the help of the heuristic the exact solver is able to obtain an optimal solution in a much shorter amount of time.<\/jats:p>","DOI":"10.1007\/s10100-020-00689-3","type":"journal-article","created":{"date-parts":[[2020,6,11]],"date-time":"2020-06-11T22:02:39Z","timestamp":1591912959000},"page":"1079-1113","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["A new heuristic and an exact approach for a production planning problem"],"prefix":"10.1007","volume":"29","author":[{"given":"Peter","family":"Auer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gy\u00f6rgy","family":"D\u00f3sa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9609-1538","authenticated-orcid":false,"given":"Tibor","family":"Dulai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Armin","family":"F\u00fcgenschuh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peggy","family":"N\u00e4ser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ronald","family":"Ortner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"\u00c1gnes","family":"Werner-Stark","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,6,11]]},"reference":[{"issue":"3","key":"689_CR1","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1016\/j.ejor.2014.09.030","volume":"241","author":"C Almeder","year":"2015","unstructured":"Almeder C, Klabjan D, Traxler R, Almada-Lobo B (2015) Lead time considerations for the multi-level capacitated lot-sizing problem. Eur J Oper Res 241(3):727\u2013738","journal-title":"Eur J Oper Res"},{"key":"689_CR2","volume-title":"Tecnomatix plant simulation","author":"S Bangsow","year":"2015","unstructured":"Bangsow S (2015) Tecnomatix plant simulation. Springer, Cham"},{"key":"689_CR3","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF02023073","volume":"41","author":"P Brandimarte","year":"1993","unstructured":"Brandimarte P (1993) Routing and scheduling in a flexible job shop by tabu search. Ann Oper Res 41:157\u2013183. https:\/\/doi.org\/10.1007\/BF02023073","journal-title":"Ann Oper Res"},{"key":"689_CR4","volume-title":"Handbook of combinatorial optimization","author":"B Chen","year":"1998","unstructured":"Chen B, Potts C, Woeginger G (1998) A review of machine scheduling: complexity, algorithms and approximability. In: Du D-Z, Pardalos P (eds) Handbook of combinatorial optimization, vol 3. Kluwer Academic Publishers, Dordrecht"},{"issue":"4","key":"689_CR5","doi-asserted-by":"publisher","first-page":"1005","DOI":"10.1287\/moor.1050.0158","volume":"30","author":"JR Correa","year":"2005","unstructured":"Correa JR, Schulz AS (2005) Single-machine scheduling with precedence constraints. Math Oper Res 30(4):1005\u20131021","journal-title":"Math Oper Res"},{"issue":"1","key":"689_CR6","doi-asserted-by":"publisher","first-page":"66","DOI":"10.2507\/IJSIMM13(1)6.260","volume":"13","author":"M Debevec","year":"2014","unstructured":"Debevec M, Simic M, Herakovic N (2014) Virtual factory as an advanced approach for production process optimization. Int J Simul Model 13(1):66\u201378","journal-title":"Int J Simul Model"},{"key":"689_CR7","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/s10845-007-0026-8","volume":"18","author":"P Fattahi","year":"2007","unstructured":"Fattahi P, Saidi-Mehrabad M, Jolai F (2007) Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. J Intell Manuf 18:331\u2013342. https:\/\/doi.org\/10.1007\/s10845-007-0026-8","journal-title":"J Intell Manuf"},{"key":"689_CR8","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/s10479-005-3446-x","volume":"139","author":"C Floudas","year":"2005","unstructured":"Floudas C, Lin X (2005) Mixed integer linear programming in process scheduling: modeling, algorithms, and applications. Annals OR 139:131\u2013162. https:\/\/doi.org\/10.1007\/s10479-005-3446-x","journal-title":"Annals OR"},{"key":"689_CR9","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.cor.2014.08.022","volume":"54","author":"C Gicquel","year":"2015","unstructured":"Gicquel C, Minoux M (2015) Multi-product valid inequalities for the discrete lot-sizing and scheduling problem. Comput Oper Res 54:12\u201320","journal-title":"Comput Oper Res"},{"key":"689_CR10","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.orl.2008.10.001","volume":"37","author":"C Gicquel","year":"2009","unstructured":"Gicquel C, Minoux M, Dallery Y (2009) On the discrete lot-sizing and scheduling problem with sequence-dependent changeover times. Oper Res Lett 37:32\u201336","journal-title":"Oper Res Lett"},{"key":"689_CR11","doi-asserted-by":"crossref","unstructured":"Hassan M, Kacem I, Martin S, Osman IM (2016) Unrelated parallel machine scheduling problem with precedence constraints: polyhedral analysis and branch-and-cut. In: Cerulli R, Fujishige S, Mahjoub A (eds) Combinatorial optimization ISCO 2016 Lecture Notes in Computer Science, vol 9849, pp 308\u2013319","DOI":"10.1007\/978-3-319-45587-7_27"},{"issue":"3","key":"689_CR12","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1016\/S0377-2217(96)00247-0","volume":"102","author":"J Herrmann","year":"1997","unstructured":"Herrmann J, Proth J, Sauer N (1997) Heuristics for unrelated machine scheduling with precedence constraints. Eur J Oper Res 102(3):528\u2013537","journal-title":"Eur J Oper Res"},{"key":"689_CR13","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/BF01719451","volume":"15","author":"J Hurink","year":"1994","unstructured":"Hurink J, Jurisch B, Thole M (1994) Tabu search for the job-shop scheduling problem with multi-purpose machines. Oper-Res-Spektrum 15:205\u2013215","journal-title":"Oper-Res-Spektrum"},{"issue":"4","key":"689_CR14","first-page":"60","volume":"6","author":"S Klos","year":"2015","unstructured":"Klos S, Trebuna P (2015) Using computer simulation method to improve throughput of production systems by buffers and workers allocation. Manag Prod Eng Rev 6(4):60\u201369","journal-title":"Manag Prod Eng Rev"},{"key":"689_CR15","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/j.cor.2016.04.006","volume":"73","author":"WY Ku","year":"2016","unstructured":"Ku WY, Beck C (2016) Mixed integer programming models for job shop scheduling: a computational analysis. Comput Oper Res 73:165\u2013173","journal-title":"Comput Oper Res"},{"key":"689_CR16","doi-asserted-by":"crossref","unstructured":"Kumar VSA, Marathe MV, Parthasarathy S, Srinivasan A (2005) Scheduling on unrelated machines under tree-like precedence constraints. In: Chekuri C et al (eds) APPROX and RANDOM 2005, LNCS, vol 3624, pp 146\u2013157","DOI":"10.1007\/11538462_13"},{"issue":"6","key":"689_CR17","doi-asserted-by":"publisher","first-page":"1146","DOI":"10.4304\/jsw.6.6.1146-1153","volume":"6","author":"C Liu","year":"2011","unstructured":"Liu C, Yang S (2011) A heuristic serial schedule algorithm for unrelated parallel machine scheduling with precedence constraints. J Softw 6(6):1146\u20131153","journal-title":"J Softw"},{"key":"689_CR18","doi-asserted-by":"publisher","unstructured":"Najid N, Dauz\u00e8-P\u00e9r\u00e8s S, Zaidat A (2002) A modified simulated annealing method for flexible job shop scheduling problem, vol 5, p 6. https:\/\/doi.org\/10.1109\/ICSMC.2002.1176334","DOI":"10.1109\/ICSMC.2002.1176334"},{"issue":"10","key":"689_CR19","doi-asserted-by":"publisher","first-page":"3202","DOI":"10.1016\/j.cor.2007.02.014","volume":"35","author":"F Pezzella","year":"2008","unstructured":"Pezzella F, Morganti G, Ciaschetti G (2008) A genetic algorithm for the flexible job-shop scheduling problem. Comput Oper Res 35(10):3202\u20133212. https:\/\/doi.org\/10.1016\/j.cor.2007.02.014","journal-title":"Comput Oper Res"},{"key":"689_CR20","volume-title":"Production planning by mixed integer programming","author":"Y Pochet","year":"2006","unstructured":"Pochet Y, Wolsey LA (2006) Production planning by mixed integer programming. Springer, New York"},{"key":"689_CR21","doi-asserted-by":"publisher","first-page":"1250","DOI":"10.1016\/j.cor.2006.07.015","volume":"35","author":"PL Rocha","year":"2008","unstructured":"Rocha PL, Ravetti MG, Mateus GR, Pardalos PM (2008) Exact algorithms for a scheduling problem with unrelated parallel machines and sequence and machine-dependent setup times. Comput Oper Res 35:1250\u20131264","journal-title":"Comput Oper Res"},{"key":"689_CR22","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/s00170-005-0375-4","volume":"32","author":"M Saidi-Mehrabad","year":"2007","unstructured":"Saidi-Mehrabad M, Fattahi P (2007) Flexible job shop scheduling with tabu search algorithms. Int J Adv Manuf Technol 32:563\u2013570. https:\/\/doi.org\/10.1007\/s00170-005-0375-4","journal-title":"Int J Adv Manuf Technol"},{"key":"689_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58614-9","volume-title":"Production planning and scheduling in flexible assembly systems","author":"T Sawik","year":"1999","unstructured":"Sawik T (1999) Production planning and scheduling in flexible assembly systems. Springer, Berlin"},{"key":"689_CR24","doi-asserted-by":"publisher","unstructured":"Wan X, Yan H (2016) An algorithm for assembly job shop scheduling problem. In: 2nd International Conference on Electronics, Network and Computer Engineering (ICENCE 2016). Atlantis Press. https:\/\/doi.org\/10.2991\/icence-16.2016.48","DOI":"10.2991\/icence-16.2016.48"}],"container-title":["Central European Journal of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10100-020-00689-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10100-020-00689-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10100-020-00689-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,28]],"date-time":"2021-06-28T11:40:57Z","timestamp":1624880457000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10100-020-00689-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,11]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["689"],"URL":"https:\/\/doi.org\/10.1007\/s10100-020-00689-3","relation":{},"ISSN":["1435-246X","1613-9178"],"issn-type":[{"type":"print","value":"1435-246X"},{"type":"electronic","value":"1613-9178"}],"subject":[],"published":{"date-parts":[[2020,6,11]]},"assertion":[{"value":"11 June 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}