{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T15:20:31Z","timestamp":1759332031488,"version":"3.37.3"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,11,2]],"date-time":"2020-11-02T00:00:00Z","timestamp":1604275200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,11,2]],"date-time":"2020-11-02T00:00:00Z","timestamp":1604275200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"NWO","award":["12694"],"award-info":[{"award-number":["12694"]}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["826452"],"award-info":[{"award-number":["826452"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Event Dyn Syst"],"published-print":{"date-parts":[[2021,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>One of the challenges in the design of supervisors with optimal throughput for manufacturing systems is the presence of behavior outside the control of the supervisor. Uncontrollable behavior is typically encountered in the presence of (user) inputs, external disturbances, and exceptional behavior. This paper introduces an approach for the modeling and synthesis of a throughput-optimal supervisor for manufacturing systems with partially-controllable behavior on two abstraction levels. Extended finite automata are used to model the high abstraction level in terms of system activities, where uncontrollability is modeled by the presence of uncontrollable activities. In the lower abstraction level, activities are modeled as directed acyclic graphs that define the constituent actions and dependencies between them. System feedback from the lower abstraction level, including timing, is captured using variables in the extended finite automata of the higher abstraction level. For throughput optimization, game-theoretic methods are employed on the state space of the synthesized supervisor to determine a guarantee to the lower-bound system performance. This result is also used in a new method to automatically compute a throughput-optimal controller that is robust to the uncontrollable behavior.<\/jats:p>","DOI":"10.1007\/s10626-020-00325-x","type":"journal-article","created":{"date-parts":[[2020,11,2]],"date-time":"2020-11-02T17:03:40Z","timestamp":1604336620000},"page":"103-135","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Supervisor synthesis and throughput optimization of partially-controllable manufacturing systems"],"prefix":"10.1007","volume":"31","author":[{"given":"Berend Jan Christiaan","family":"van Putten","sequence":"first","affiliation":[]},{"given":"Bram","family":"van der Sanden","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9283-4074","authenticated-orcid":false,"given":"Michel","family":"Reniers","sequence":"additional","affiliation":[]},{"given":"Jeroen","family":"Voeten","sequence":"additional","affiliation":[]},{"given":"Ramon","family":"Schiffelers","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,11,2]]},"reference":[{"issue":"2","key":"325_CR1","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1016\/j.tcs.2005.11.018","volume":"354","author":"Y Abdedda\u00efm","year":"2006","unstructured":"Abdedda\u00efm Y, Asarin E, Maler O (2006) Scheduling with timed automata. Theor Comput Sci 354(2):272\u2013300. https:\/\/doi.org\/10.1016\/j.tcs.2005.11.018. ISSN 03043975","journal-title":"Theor Comput Sci"},{"issue":"2","key":"325_CR2","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1109\/JSYST.2008.923193","volume":"2","author":"A Aybar","year":"2008","unstructured":"Aybar A, Iftar A (2008) Deadlock avoidance controller design for timed Petri nets using stretching. IEEE Syst J 2(2):178\u2013188. https:\/\/doi.org\/10.1109\/JSYST.2008.923193. ISSN 19379234","journal-title":"IEEE Syst J"},{"key":"325_CR3","doi-asserted-by":"crossref","unstructured":"Baeten JCM, van de Mortel-Fronczak JM, Rooda JE (2016) Integration of supervisory control synthesis in model-based systems engineering. In: Dimirovski GM (ed) Complex systems: relationships between control, communications and computing, pp 39\u201358","DOI":"10.1007\/978-3-319-28860-4_2"},{"key":"325_CR4","doi-asserted-by":"publisher","unstructured":"Basile F, Chiacchio P, Giua A (2002) Optimal Petri net monitor design. In: Caillaud B, Darondeau P, Lavagno L, Xie X (eds) Synthesis and control of discrete event systems. https:\/\/doi.org\/10.1007\/978-1-4757-6656-1_9. ISBN 978-1-4757-6656-1. Springer, Boston, pp 141\u2013153","DOI":"10.1007\/978-1-4757-6656-1_9"},{"key":"325_CR5","unstructured":"Behrmann G, Cougnard A, David A, Fleury E, Larsen KG, Lime D (2007) Uppaal-tiga: time for playing games! In: Damm W, Hermanns H (eds) Computer aided verification. ISBN 978-3-540-73368-3. Springer, Berlin, pp 121\u2013125"},{"key":"325_CR6","unstructured":"Bloem R, Greimel K, Henzinger TA, Jobstmann B (2009) Synthesizing robust systems. In: Formal methods in computer-aided design. ISBN 9781424449668, pp 85\u201392"},{"issue":"2","key":"325_CR7","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s10703-010-0105-x","volume":"38","author":"L Brim","year":"2011","unstructured":"Brim L, Chaloupka J, Doyen L, Gentilini R, Raskin JF (2011) Faster algorithms for mean-payoff games. Form Methods Syst Des 38(2):97\u2013118. https:\/\/doi.org\/10.1007\/s10703-010-0105-x. ISSN 09259856","journal-title":"Form Methods Syst Des"},{"key":"325_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-68612-7","volume-title":"Introduction to discrete event systems","author":"CG Cassandras","year":"2008","unstructured":"Cassandras CG, Lafortune S (2008) Introduction to discrete event systems. Springer, Berlin"},{"key":"325_CR9","doi-asserted-by":"publisher","unstructured":"Chen Y-L, Lin F (2000) Modeling of discrete event systems using finite state machines with parameters. In: Proceedings of the IEEE international conference on control applications, CCA\u201900. https:\/\/doi.org\/10.1109\/CCA.2000.897591. ISBN 0780365623, pp 941\u2013946","DOI":"10.1109\/CCA.2000.897591"},{"issue":"4","key":"325_CR10","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/1027084.1027085","volume":"9","author":"A Dasdan","year":"2004","unstructured":"Dasdan A (2004) Experimental analysis of the fastest optimum cycle ratio and mean algorithms. ACM Trans Des Autom Electron Syst 9(4):385\u2013418. https:\/\/doi.org\/10.1145\/1027084.1027085. ISSN 10844309","journal-title":"ACM Trans Des Autom Electron Syst"},{"key":"325_CR11","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/s10626-015-0223-0","volume":"27","author":"R Ehlers","year":"2017","unstructured":"Ehlers R, Lafortune S, Tripakis S, Vardi MY (2017) Supervisory control and reactive synthesis: a comparative introduction. Discrete Event Dyn Syst 27:209\u2013260","journal-title":"Discrete Event Dyn Syst"},{"key":"325_CR12","unstructured":"Estefan JA (2008) Survey of model-based systems engineering (MBSE) methodologies. Technical report, INCOSE MBSE Initiative"},{"issue":"6","key":"325_CR13","doi-asserted-by":"publisher","first-page":"1449","DOI":"10.1109\/TAC.2008.927679","volume":"53","author":"L Feng","year":"2008","unstructured":"Feng L, Wonham WM (2008) Supervisory control architecture for discrete-event systems. IEEE Trans Autom Control 53(6):1449\u20131461","journal-title":"IEEE Trans Autom Control"},{"issue":"2","key":"325_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1880050.1880052","volume":"10","author":"M Geilen","year":"2010","unstructured":"Geilen M (2010) Synchronous dataflow scenarios. ACM Trans Embed Comput Syst 10(2):1\u201331. https:\/\/doi.org\/10.1145\/1880050.1880052. ISSN 15399087","journal-title":"ACM Trans Embed Comput Syst"},{"key":"325_CR15","doi-asserted-by":"publisher","unstructured":"Geilen M, Stuijk S (2010) Worst-case performance analysis of Synchronous Dataflow scenarios. In: International conference on hardware\/software codesign and system synthesis (CODES+ISSS). https:\/\/doi.org\/10.1145\/1878961.1878985. ISBN 978-1-6055-8905-3, pp 125\u2013134","DOI":"10.1145\/1878961.1878985"},{"issue":"2","key":"325_CR16","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"PE Hart","year":"1968","unstructured":"Hart PE, Nilsson NJ, Raphael B (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cybern 4 (2):100\u2013107. https:\/\/doi.org\/10.1109\/TSSC.1968.300136. ISSN 0536-1567","journal-title":"IEEE Trans Syst Sci Cybern"},{"issue":"7","key":"325_CR17","doi-asserted-by":"publisher","first-page":"1592","DOI":"10.1109\/TAC.2008.927800","volume":"53","author":"J Huang","year":"2008","unstructured":"Huang J, Kumar R (2008) Optimal nonblocking directed control of discrete event systems. IEEE Trans Autom Control 53(7):1592\u20131603. https:\/\/doi.org\/10.1109\/TAC.2008.927800. ISSN 0018-9286","journal-title":"IEEE Trans Autom Control"},{"key":"325_CR18","doi-asserted-by":"crossref","unstructured":"Hulgaard H, Burns SM (1995) Efficient timing analysis of a class of Petri nets. In: Wolper P (ed) Computer aided verification. ISBN 978-3-540-49413-3. Springer, Berlin, pp 423\u2013436","DOI":"10.1007\/3-540-60045-0_67"},{"key":"325_CR19","unstructured":"Kempf J-F, Bozga M, Maler O (2013) As soon as probable: optimal scheduling under stochastic uncertainty. In: Piterman N, Smolka SA (eds) Tools and algorithms for the construction and analysis of systems. ISBN 978-3-642-36742-7. Springer, Berlin, pp 385\u2013400"},{"key":"325_CR20","doi-asserted-by":"publisher","unstructured":"Kobetski A, Richardsson J, \u00c5kesson K, Fabian M (2007) Minimization of expected cycle time in manufacturing cells with uncontrollable behavior. In: 2007 IEEE International conference on automation science and engineering. https:\/\/doi.org\/10.1109\/COASE.2007.4341802, pp 14\u201319","DOI":"10.1109\/COASE.2007.4341802"},{"key":"325_CR21","doi-asserted-by":"crossref","unstructured":"Komenda J, Masopust T, van Schuppen JH (2016) Control of an engineering-structured multilevel discrete-event system. In: 13th International workshop on discrete event systems, pp 103\u2013108","DOI":"10.1109\/WODES.2016.7497833"},{"key":"325_CR22","first-page":"109","volume-title":"Synthesis with incomplete information","author":"O Kupferman","year":"2000","unstructured":"Kupferman O, Vardi MY (2000) Synthesis with incomplete information. Kluwer Academic Publishers, Dordrecht, pp 109\u2013127"},{"issue":"4","key":"325_CR23","doi-asserted-by":"publisher","first-page":"54","DOI":"10.3390\/pr5040054","volume":"5","author":"D Lefebvre","year":"2017","unstructured":"Lefebvre D (2017) Dynamical scheduling and robust control in uncertain environments with Petri nets for DESs. Processes 5(4):54. https:\/\/doi.org\/10.3390\/pr5040054. ISSN 2227-9717. http:\/\/www.mdpi.com\/2227-9717\/5\/4\/54","journal-title":"Processes"},{"issue":"1","key":"325_CR24","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s10626-015-0217-y","volume":"26","author":"S Mohajerani","year":"2016","unstructured":"Mohajerani S, Malik R, Fabian M (2016) A framework for compositional nonblocking verification of extended finite-state machines. Discrete Event Dyn Syst 26(1):33\u201384. https:\/\/doi.org\/10.1007\/s10626-015-0217-y","journal-title":"Discrete Event Dyn Syst"},{"issue":"3","key":"325_CR25","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1109\/9.847725","volume":"45","author":"JO Moody","year":"2000","unstructured":"Moody JO, Antsaklis PJ (2000) Petri net supervisors for DES with uncontrollable and unobservable transitions. IEEE Trans Autom Control 45(3):462\u2013476. https:\/\/doi.org\/10.1109\/9.847725. ISSN 00189286","journal-title":"IEEE Trans Autom Control"},{"key":"325_CR26","doi-asserted-by":"crossref","unstructured":"Ni\u00f1o-Mora J (2008) Stochastic scheduling. In: Encyclopedia of optimization. Springer, pp 3818\u20133824","DOI":"10.1007\/978-0-387-74759-0_665"},{"issue":"3","key":"325_CR27","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1109\/TASE.2011.2124457","volume":"8","author":"L Ouedraogo","year":"2011","unstructured":"Ouedraogo L, Kumar R, Malik R, \u00c5kesson K (2011) Nonblocking and safe control of discrete-event systems modeled as extended finite automata. IEEE Trans Autom Sci Eng 8(3):560\u2013569. https:\/\/doi.org\/10.1109\/TASE.2011.2124457","journal-title":"IEEE Trans Autom Sci Eng"},{"key":"325_CR28","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1016\/j.ins.2015.08.056","volume":"329","author":"PN Pena","year":"2016","unstructured":"Pena PN, Costa TA, Silva RS, Takahashi RHC (2016) Control of flexible manufacturing systems under model uncertainty using supervisory control theory and evolutionary computation schedule synthesis. Inf Sci 329:491\u2013502. https:\/\/doi.org\/10.1016\/j.ins.2015.08.056. ISSN 0020-0255. http:\/\/www.sciencedirect.com\/science\/article\/pii\/S002002551500691X","journal-title":"Inf Sci"},{"issue":"1","key":"325_CR29","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1137\/0325013","volume":"25","author":"PJ Ramadge","year":"1987","unstructured":"Ramadge PJ, Wonham WM (1987) Supervisory control of a class of discrete event processes. SIAM J Control Optim 25(1):206\u2013230. https:\/\/doi.org\/10.1137\/0325013. ISSN 0363-0129","journal-title":"SIAM J Control Optim"},{"key":"325_CR30","doi-asserted-by":"crossref","unstructured":"Raman V, Donz\u00e9 A, Sadigh D, Murray RM, Seshia SA (2015) Reactive synthesis from signal temporal logic specifications. In: Proceedings of the 18th international conference on hybrid systems: computation and control, HSCC\u201915, Seattle, WA, USA, April 14\u201316, 2015, pp 239\u2013248","DOI":"10.1145\/2728606.2728628"},{"key":"325_CR31","doi-asserted-by":"crossref","unstructured":"Skelin M, Geilen M (2018) It\u2019s a matter of time: modeling and analysis of time dependent systems using scenario-aware dataflow. In: 2018 16th ACM\/IEEE international conference on formal methods and models for system design (MEMOCODE), pp 1\u201311","DOI":"10.1109\/MEMCOD.2018.8556996"},{"key":"325_CR32","doi-asserted-by":"crossref","unstructured":"Sk\u00f6ldstam M, \u00c5kesson K, Fabian M (2007) Modeling of discrete event systems using finite automata with variables. In: 46th IEEE conference on decision and control, CDC 2007, New Orleans, LA, USA, December 12\u201314, 2007, pp 3387\u20133392","DOI":"10.1109\/CDC.2007.4434894"},{"key":"325_CR33","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/j.procir.2017.01.036","volume":"60","author":"C Steimer","year":"2017","unstructured":"Steimer C, Fischer J, Aurich JC (2017) Model-based design process for the early phases of manufacturing system planning using SysML. Procedia CIRP 60:163\u2013168. https:\/\/doi.org\/10.1016\/j.procir.2017.01.036. ISSN 22128271","journal-title":"Procedia CIRP"},{"issue":"1","key":"325_CR34","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1109\/TAC.2011.2157391","volume":"57","author":"R Su","year":"2012","unstructured":"Su R, van Schuppen JH, Rooda JE (2012) The synthesis of time optimal supervisors by using heaps-of-pieces. IEEE Trans Autom Control 57 (1):105\u2013118. https:\/\/doi.org\/10.1109\/TAC.2011.2157391. ISSN 0018-9286","journal-title":"IEEE Trans Autom Control"},{"key":"325_CR35","doi-asserted-by":"publisher","unstructured":"van Beek DA, Fokkink W, Hendriks D, Hofkamp A, Markovski J, van de Mortel-Fronczak JM, MA Reniers (2014) CIF 3: model-based engineering of supervisory controllers. In: Tools and algorithms for the construction and analysis of systems\u201420th international conference, TACAS 2014. https:\/\/doi.org\/10.1007\/978-3-642-54862-8_48, pp 575\u2013580","DOI":"10.1007\/978-3-642-54862-8_48"},{"key":"325_CR36","unstructured":"van der Sanden B (2018) Performance analysis and optimization of supervisory controllers. PhD thesis, Eindhoven University of Technology"},{"key":"325_CR37","doi-asserted-by":"crossref","unstructured":"van der Sanden B, Bastos J, Voeten J, Geilen M, Reniers M, Basten T, Jacobs J, Schiffelers R (2016) Compositional specification of functionality and timing of manufacturing systems. In: 2016 Forum on specification and design languages (FDL), Bremen","DOI":"10.1109\/FDL.2016.7880372"},{"key":"325_CR38","unstructured":"van Putten BJC (2018) Tackling uncontrollability in the specification and performance of manufacturing systems. Master\u2019s thesis, Eindhoven University of Technology"},{"key":"325_CR39","unstructured":"Voronov A, \u00c5kesson K (2009) Verification of supervisory control properties of finite automata extended with variables. Technical report, Chalmers University of Technology. http:\/\/publications.lib.chalmers.se\/records\/fulltext\/94442.pdf"},{"key":"325_CR40","unstructured":"Wang J (1998) Timed Petri nets: theory and application. The International Series on Discrete Event Dynamic Systems. Springer US. ISBN 9780792382706"},{"issue":"10","key":"325_CR41","doi-asserted-by":"publisher","first-page":"1125","DOI":"10.1109\/9.58555","volume":"35","author":"H Zhong","year":"1990","unstructured":"Zhong H, Wonham WM (1990) On the consistency of hierrchical supervisoion in discrete-event systems. IEEE Trans Autom Control 35(10):1125\u20131134","journal-title":"IEEE Trans Autom Control"}],"container-title":["Discrete Event Dynamic Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10626-020-00325-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10626-020-00325-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10626-020-00325-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,26]],"date-time":"2022-11-26T06:28:17Z","timestamp":1669444097000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10626-020-00325-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,2]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["325"],"URL":"https:\/\/doi.org\/10.1007\/s10626-020-00325-x","relation":{},"ISSN":["0924-6703","1573-7594"],"issn-type":[{"type":"print","value":"0924-6703"},{"type":"electronic","value":"1573-7594"}],"subject":[],"published":{"date-parts":[[2020,11,2]]},"assertion":[{"value":"24 June 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 August 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 November 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}