Scheduling complex production systems with blocking using Petri Nets and beam a search: A heavy truck repair shop

This paper illustrates the combined use of Petri Nets (PNs) and Beam A search to address the scheduling of operations into a Heavy truck repair shop, in which there is no spaces to keep jobs in process. This problem has been modeled as an Open Shop Problem with consideration of blocking conditions. The PN allows a formal representation of the manufacturing system as well as the constraints related with the blocking condition were instantaneous swapping operations between resources is not allowed, while the Beam A Search looks for a good schedule through the reachability graph provided by the PN. As part of the modeling stage, a MILP (Mixed Integer Linear Programming) formulation is proposed to establish upper bounds values. The goal pursued was the minimization of the makespan. The experimental stage was carried out on well known instances for open shop and their performance were measure against the upper bound values resulting from the MILP formulation as well as two different functions alternatives to estimate, for each node, the expected time to reach the final state of the system. The obtained results and the time in which they are obtained, confirm the relevance of the used approach for production scheduling in such complex manufacturing systems.