Taming the State-space Explosion in the Makespan Optimization of Flexible Manufacturing Systems

João Bastos; Jeroen Voeten; Sander Stuijk; Ramon Schiffelers; Henk Corporaal

doi:10.1145/3426194

Taming the State-space Explosion in the Makespan Optimization of Flexible Manufacturing Systems

João Bastos, Jeroen Voeten, Sander Stuijk, Ramon Schiffelers, Henk Corporaal

Research output: Contribution to journal › Article › Academic › peer-review

2 Citations (Scopus)

61 Downloads (Pure)

Abstract

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.

Original language	English
Article number	15
Number of pages	26
Journal	ACM Transactions on Cyber-Physical Systems
Volume	5
Issue number	2
DOIs	https://doi.org/10.1145/3426194
Publication status	Published - 4 Jan 2021

Funding

This research is supported by the Dutch NWO-TTW, carried out as part of the Robust Cyber-Physical Systems (RCPS) program, project number 12694. Research leading to these results has received funding from the EU ECSEL Joint Undertaking under grant agreement no 826452 (project Arrowhead Tools). The proofs for all Lemmas and Theorems can be found in an Appendix provided with the supplementary material. Authors’ addresses: J. Bastos, J. Voeten, S. Stuijk, and H. Corporaal, TUe Department of Electrical Engineering, Eindhoven University of Technology, 5612AP Eindhoven, The Netherlands; emails: [email protected], {j.p.m.voeten, s.stuijk, h.corporaal}@tue.nl; R. Schiffelers, ASML Veldhoven, The Netherlands; email: [email protected]. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. © 2021 Association for Computing Machinery. 2378-962X/2021/01-ART15 $15.00 https://doi.org/10.1145/3426194

Keywords

Flexible manufactoring systems
formal specification
makespan optimization
max plus linear systems

Access to Document

10.1145/3426194

published versionFinal published version, 1.45 MB

Cite this

@article{2c6b0c5a67d64c21b3db5718f9533ef0,

title = "Taming the State-space Explosion in the Makespan Optimization of Flexible Manufacturing Systems",

abstract = "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.",

keywords = "Flexible manufactoring systems, formal specification, makespan optimization, max plus linear systems",

author = "Jo{\~a}o Bastos and Jeroen Voeten and Sander Stuijk and Ramon Schiffelers and Henk Corporaal",

note = "Funding Information: This research is supported by the Dutch NWO-TTW, carried out as part of the Robust Cyber-Physical Systems (RCPS) program, project number 12694. Research leading to these results has received funding from the EU ECSEL Joint Undertaking under grant agreement no 826452 (project Arrowhead Tools). The proofs for all Lemmas and Theorems can be found in an Appendix provided with the supplementary material. Authors{\textquoteright} addresses: J. Bastos, J. Voeten, S. Stuijk, and H. Corporaal, TUe Department of Electrical Engineering, Eindhoven University of Technology, 5612AP Eindhoven, The Netherlands; emails: [email protected], {j.p.m.voeten, s.stuijk, h.corporaal}@tue.nl; R. Schiffelers, ASML Veldhoven, The Netherlands; email: [email protected]. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. {\textcopyright} 2021 Association for Computing Machinery. 2378-962X/2021/01-ART15 $15.00 https://doi.org/10.1145/3426194 Publisher Copyright: {\textcopyright} 2021 ACM.",

year = "2021",

month = jan,

day = "4",

doi = "10.1145/3426194",

language = "English",

volume = "5",

journal = "ACM Transactions on Cyber-Physical Systems",

issn = "2378-962X",

publisher = "Association for Computing Machinery, Inc",

number = "2",

}

TY - JOUR

T1 - Taming the State-space Explosion in the Makespan Optimization of Flexible Manufacturing Systems

AU - Bastos, João

AU - Voeten, Jeroen

AU - Stuijk, Sander

AU - Schiffelers, Ramon

AU - Corporaal, Henk

N1 - Funding Information: This research is supported by the Dutch NWO-TTW, carried out as part of the Robust Cyber-Physical Systems (RCPS) program, project number 12694. Research leading to these results has received funding from the EU ECSEL Joint Undertaking under grant agreement no 826452 (project Arrowhead Tools). The proofs for all Lemmas and Theorems can be found in an Appendix provided with the supplementary material. Authors’ addresses: J. Bastos, J. Voeten, S. Stuijk, and H. Corporaal, TUe Department of Electrical Engineering, Eindhoven University of Technology, 5612AP Eindhoven, The Netherlands; emails: [email protected], {j.p.m.voeten, s.stuijk, h.corporaal}@tue.nl; R. Schiffelers, ASML Veldhoven, The Netherlands; email: [email protected]. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. © 2021 Association for Computing Machinery. 2378-962X/2021/01-ART15 $15.00 https://doi.org/10.1145/3426194 Publisher Copyright: © 2021 ACM.

PY - 2021/1/4

Y1 - 2021/1/4

N2 - 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.

AB - 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.

KW - Flexible manufactoring systems

KW - formal specification

KW - makespan optimization

KW - max plus linear systems

UR - http://www.scopus.com/inward/record.url?scp=85100442203&partnerID=8YFLogxK

U2 - 10.1145/3426194

DO - 10.1145/3426194

M3 - Article

AN - SCOPUS:85100442203

SN - 2378-962X

VL - 5

JO - ACM Transactions on Cyber-Physical Systems

JF - ACM Transactions on Cyber-Physical Systems

IS - 2

M1 - 15

ER -

Taming the State-space Explosion in the Makespan Optimization of Flexible Manufacturing Systems

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this