In this paper, we study the open shop scheduling problem with blocking and deadlocks. First, we develop a new Petri net class that extends the well-known S³R nets to handle the features of open shop systems. Next, we establish necessary conditions for deadlock-free operation based on the properties of a particular structural siphon. Then, we implement a graph search algorithm that intelligently explores the net reachability graph and uses a search strategy based on a double filtering mechanism and new evaluation functions. We conducted computational tests on a set of classical instances adapted from the literature. The quality of the solutions was established with a lower bound calculated with the aforementioned siphon. The results show the validity of the approach: the proposed algorithm found solutions with values that were very close to the lower bound in most cases.

In this paper we propose the GAPN (genetic algorithms and Petri nets) approach, which combines the modelling power of Petri nets with the optimisation capability of genetic algorithms (GAs) for manufacturing systems scheduling. This approach uses both Petri nets to formulate the scheduling problem and GAs for scheduling. Its primary advantage is its ability to model a wide variety of manufacturing systems with no modifications either in the net structure or in the chromosomal representation. In this paper we tested the performance on both classical scheduling problems and on a real life setting of a manufacturer of car seat covers. In particular, such a manufacturing system involves features such as complex project-like routings, assembly operations, and workstations with unrelated parallel machines. The implementation of the algorithm at the company is also discussed. Experiments show the validity of the proposed approach.