Efficient deadlock control policies are very important in the operation of flexible manufacturing systems (FMS). This work focuses on deadlock control problems for a general class of FMS. They have three interesting characteristics from the application point of view. First, flexible routes of parts and assembly operations are allowed. Second, the number of parts of the same type in a product may be more than one. Third, an operation may require multiple resources. To characterize such FMS, a Petri net model that can well deal with all FMS characteristics is developed. Based on it, this work proposes a Banker's algorithm-like deadlock avoidance policy. The proposed policy is proved to be polynomial in the model size. Moreover, experimental results indicate its effectiveness and superiority over the state-of-the-art policies.

Deadlock-free scheduling and control is critical for optimizing the performance of flexible assembly systems (FASs). Based on the Petri net models of FASs, this paper integrates a deadlock prevention policy with local search and develops a novel deadlock-free scheduling algorithm. A solution of the scheduling problem is coded as a chromosome representation that is a permutation with repetition of parts. By using the deadlock prevention policy, a repairing algorithm (RA) is developed to repair unfeasible chromosomes. A perturbation strategy based on estimation of distribution algorithm is developed to escape from local optima. Moreover, to improve population diversity, an acceptance criterion (AC) based on Pareto dominance is proposed. The chromosome representation, RA, perturbation strategy, and AC together support the cooperative aspect of local search for scheduling problems strongly.

This work investigates a scheduling problem of deadlock-prone flexible manufacturing systems modeled by place-timed Petri nets. It proposes an anytime branch and bound (AB&B) algorithm for it to minimize system makespan based on the branch tree of a net model and a highly permissive deadlock controller. The proposed algorithm searches a sequence of transitions in the branch tree that evolves the model from the initial marking to the final one. In order to prune the branch tree and increase search speed, this work develops two pruning rules, a lower bound of makespan, and a novel branching strategy. Their usage ensures AB&B’s high search efficiency. Experimental results demonstrate that the proposed algorithm surpasses the state-of-the-art ones. Note to Practitioners —In practice, scheduling is one of the most important issues for production managers to address. Existing approaches to deadlock-prone flexible manufacturing system (FMS) scheduling have multiparameters. Their settings can impact the scheduling results greatly. Since their turning is a challenging task, it is difficult to find the best parameter settings. This article proposes an anytime branch and bound (AB&B) algorithm for minimizing the makespan of deadlock-prone FMSs. It has only one parameter, i.e., maximal CPU time, which needs no turning. When it is highly tight, AB&B can output a feasible and decent schedule. If it is larger and larger, AB&B can output a better and better schedule. Comparison studies show that AB&B outclasses existing ones significantly. It is suitable for real-time scheduling cases in which satisfied schedules must be offered in a very short time.

The real-time traffic control of railway networks imposes safety constraints and authorizes movements of trains. This work deals with it by focusing on conflict and deadlock avoidance problems. A place-timed Petri net model is developed for a railway network. Based on it, a conflict avoidance method is presented to ensure that safety principles in railway networks are respected. Also, a polynomial deadlock avoidance policy based on the Banker’s algorithm is proposed. It authorizes the movement of trains between block sections and stations. The proposed conflict avoidance method and deadlock avoidance policy together ensure a railway network to be conflict-free and deadlock-free. Experimental results show that they are effective and efficient.

This article proposes hybrid branch and bound algorithms to minimise the makespan for the two-stage assembly scheduling problem with separated setup times. In the studied problem, there are multiple machines at the first stage, each of which produces a component of a job. When all components are available, a single assembly machine at the second stage completes the job. Existing algorithms are based on the state space search and hence suffer from the state space explosion problem. In order to reduce the search space, lower and upper bounds for a partial schedule are proposed. Also, a heuristic function and a dominance rule are developed to guide the search process. Moreover, accelerated factors are introduced to increase the speed of the search. Experimental results indicate that our algorithms outperform an existing method, and can find the optimal or near-optimal schedules in a short time for all tested problems with up to ten thousand jobs and nine first-stage machines.