Identifying FMS repetitive patterns for efficient search-based scheduling algorithm: A colored Petri net approach

Olatunde T. Baruwa, Miquel A. Piera

Research output: Contribution to journalArticleResearch

28 Citations (Scopus)


© 2014 The Society of Manufacturing Engineers. Published by Elsevier Ltd. All rights reserved. The multiple lot size scheduling problem plays a crucial role in minimizing production and setup costs in order to respond to constant fluctuations in customer demands. However, the computational cost to optimize a scheduling problem increases as the lot size of jobs increases, leading to a scalability problem for most scheduling algorithms. This paper presents an efficient search approach based on colored Petri net (CPN) formalism that addresses the state explosion problem of reachability graphs used for finding the optimal solutions to scheduling problems. To reduce the memory requirements, the proposed approach exploits the structural equivalence found in the reachability graphs of flexible manufacturing systems' (FMS) CPNs to discard states once they are no longer needed to explore the state space. The hypothetical structural equivalence is attributed to the repetitive patterns identified in the execution of manufacturing processes when the lot sizes of jobs are scaled for FMS whose underlying layout configuration is fixed. We present the concept of structural equivalence based on duplicate state detection for FMS of different lot sizes and give sufficient conditions under which the structural equivalence obtained from a few lot size (smaller) instances holds for the same FMS of a larger size. The approach is validated experimentally on different FMS examples which confirm that the behavior of an FMS of any large lot size can be inferred from the FMS of a smaller size. Experimental results indicate that this work performs better than prior search methods and obtains optimal schedules of FMS with large lot sizes. Also, we show that the approach is applicable to FMS problems of similar configurations where the problem size differ by the number of jobs, resources and operations.
Original languageEnglish
Pages (from-to)120-135
JournalJournal of Manufacturing Systems
Publication statusPublished - 1 Jan 2015


  • Colored Petri nets
  • Flexible job shop
  • Flexible manufacturing systems
  • Heuristic search
  • Layered duplicate detection
  • Memory-efficient
  • Reachability graph
  • Scheduling


Dive into the research topics of 'Identifying FMS repetitive patterns for efficient search-based scheduling algorithm: A colored Petri net approach'. Together they form a unique fingerprint.

Cite this