Petri Nets and Deadlock-Free Scheduling of Open Shop Manufacturing Systems
针对带阻塞和死锁的开放车间调度问题，提出一种扩展的Petri网模型，并基于结构信标建立无死锁必要条件，设计双过滤机制和图搜索算法，在经典实例上找到接近下界的解。
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 S3R 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.