Finite automata decomposition for flexible manufacturing systems control and scheduling

Houshang Darabi, Mohsen A. Jafari, Shomit S. Manapure

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


Despite the efforts in scheduling and control of flexible manufacturing systems (FMSs) with resource constraints, the current pool of scheduling techniques faces two major drawbacks: modeling and complexity. Modeling is the task of converting the FMS data to a set of information, ready to be processed by a scheduling algorithm. Complexity has a direct relation with the amount of effort required to execute a scheduling algorithm successfully on the information set generated in the modeling phase. In this paper, we use Finite Automata (FA) theory to develop a modeling formalism and its accompanying scheduling algorithm for control and scheduling of FMS with resource constraints. While the FA-based modeling is completely automatic and does not need any human-designer interference, its related algorithm is both effective and efficient. We use IDEF3 standard to capture the FMS activities and resource data. We propose a three-step procedure. In the first step, the IDEF3 data set is converted to a finite automaton, preserving the activity precedence relationships. In the second step, the resulted finite automaton is decomposed to smaller (in size) scheduling problems that can be independently optimized. In the third step, a heuristic scheduling algorithm is used to handle each problem separately. We applied the developed procedure to 100 problems. The results are satisfactory and promising.

Original languageEnglish (US)
Pages (from-to)168-175
Number of pages8
JournalIEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews
Issue number2
StatePublished - May 2003

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Software
  • Information Systems
  • Human-Computer Interaction
  • Computer Science Applications
  • Electrical and Electronic Engineering


  • FMS scheduling
  • Finite automata decomposition
  • Finite automata modeling
  • IDEF3 standard

Fingerprint Dive into the research topics of 'Finite automata decomposition for flexible manufacturing systems control and scheduling'. Together they form a unique fingerprint.

Cite this