{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,3]],"date-time":"2025-10-03T17:51:30Z","timestamp":1759513890197,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T00:00:00Z","timestamp":1609718400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"crossref","award":["12694"],"award-info":[{"award-number":["12694"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100006339","name":"ASML","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100006339","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003005","name":"Technische Universiteit Eindhoven","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003005","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Cyber-Phys. Syst."],"published-print":{"date-parts":[[2021,4,30]]},"abstract":"<jats:p>This article presents a modular automaton-based framework to specify flexible manufacturing systems and to optimize the makespan of product batches. The Batch Makespan Optimization (BMO) problem is NP-Hard and optimization can therefore take prohibitively long, depending on the size of the state-space induced by the specification. To tame the state-space explosion problem, we develop an algebra based on automata equivalence and inclusion relations that consider both behavior and structure. The algebra allows us to systematically relate the languages induced by the automata, their state-space sizes, and their solutions to the BMO problem. Further, we introduce a novel constraint-based approach to systematically prune the state-space based on the the notions of nonpermutation-repulsiveness and permutation-attractiveness. We prove that constraining a nonpermutation-repulsing automaton with a permutation-attracting constraint always reduces the state-space. This approach allows us to (i) compute optimal solutions of the BMO problem when the (additional) constraints are taken into account and (ii) compute bounds for the (original) BMO problem (without using the constraints). We demonstrate the effectiveness of our approach by optimizing an industrial wafer handling controller.<\/jats:p>","DOI":"10.1145\/3426194","type":"journal-article","created":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T14:32:32Z","timestamp":1609770752000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Taming the State-space Explosion in the Makespan Optimization of Flexible Manufacturing Systems"],"prefix":"10.1145","volume":"5","author":[{"given":"Jo\u00e3o","family":"Bastos","sequence":"first","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeroen","family":"Voeten","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sander","family":"Stuijk","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ramon","family":"Schiffelers","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology and ASML Veldhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Henk","family":"Corporaal","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,1,4]]},"reference":[{"volume-title":"Max-plus algebra. Disc. Math. Applic. 39 (11","year":"2006","author":"Akian Marianne","key":"e_1_2_2_1_1"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1111\/itor.12199"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2016.05.036"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2006.06.060"},{"volume-title":"Geert Jan Olsder, and Jean-Pierre Quadrat","year":"2001","author":"Baccelli Francois","key":"e_1_2_2_5_1"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3207719.3207728"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cie.2015.12.007"},{"volume-title":"Stepwise Refinement of Distributed Systems Models, Formalisms, Correctness, J. W. de Bakker, W.-P","author":"Brinksma Ed","key":"e_1_2_2_8_1"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SEAA.2012.20"},{"volume-title":"Handbook of Semiconductor Manufacturing Technology","author":"Doering Robert","key":"e_1_2_2_10_1","doi-asserted-by":"crossref","DOI":"10.1201\/9781420017663"},{"key":"e_1_2_2_11_1","doi-asserted-by":"crossref","unstructured":"Twan Basten et al. 2020. Scenarios in the Design of Flexible Manufacturing Systems. Springer International Publishing Cham 181--224. DOI:https:\/\/doi.org\/10.1007\/978-3-030-20343-6_9.  Twan Basten et al. 2020. Scenarios in the Design of Flexible Manufacturing Systems. Springer International Publishing Cham 181--224. DOI:https:\/\/doi.org\/10.1007\/978-3-030-20343-6_9.","DOI":"10.1007\/978-3-030-20343-6_9"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10626-012-0130-6"},{"volume-title":"Geert Jan Olsder, and Jacob van der Woude","year":"2006","author":"Heidergott Bernd","key":"e_1_2_2_13_1"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90114-7"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0325013"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijproman.2014.07.003"},{"volume-title":"Proceedings of the International Conference on Tools and Algorithms for the Construction and Analysis of Systems.","author":"van Beek Dirk A.","key":"e_1_2_2_18_1"},{"volume-title":"Proceedings of the Forum on Specification and Design Languages.","author":"van der Sanden B.","key":"e_1_2_2_19_1"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSD.2018.00007"},{"volume-title":"Proceedings of the Design, Automation Test in Europe Conference Exhibition (DATE\u201916)","author":"van Pinxten J.","key":"e_1_2_2_21_1"},{"key":"e_1_2_2_22_1","first-page":"5s","article-title":"Online scheduling of 2-re-entrant flexible manufacturing systems","volume":"16","author":"van Pinxten Joost","year":"2017","journal-title":"ACM Trans. Embed. Comput. Syst."}],"container-title":["ACM Transactions on Cyber-Physical Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3426194","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3426194","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:31:33Z","timestamp":1750195893000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3426194"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,4]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,4,30]]}},"alternative-id":["10.1145\/3426194"],"URL":"https:\/\/doi.org\/10.1145\/3426194","relation":{},"ISSN":["2378-962X","2378-9638"],"issn-type":[{"type":"print","value":"2378-962X"},{"type":"electronic","value":"2378-9638"}],"subject":[],"published":{"date-parts":[[2021,1,4]]},"assertion":[{"value":"2019-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}