State Space-Based Hybrid Heuristic Search Algorithm for Scheduling Deadlock-Prone Automated Manufacturing Systems

This work addresses the scheduling problem of deadlock-prone automated manufacturing systems (AMSs) modeled by a class of Petri nets called systems of simple sequential processes with resources (S3PRs), and proposes a novel hybrid heuristic search (HHS) algorithm to minimize the makespan. First, based on place-timed Petri net models of AMSs, a timed state space (TSS) composed of timed states is defined. TSS-based breadth-first search and A* algorithms are developed, through which the optimal solutions for small-scale problems can be obtained. Then, in order to effectively solve the scheduling problems of AMSs with different scales, TSS is condensed, and HHS is designed to search the condensed state space (CSS). In HHS, a duplicate detection policy is proposed for ensuring that only one transition path is reserved for each state in CSS. A pruning policy is proposed for pruning unpromising states to achieve the goal of searching a small part of CSS only, and three different cost estimation functions are developed for evaluating states. A hybrid search strategy is defined to achieve high search efficiency and find better solutions. The integration of the proposed duplicate detection policy, pruning policy, and hybrid search strategy ensures the high optimization performance and computational efficiency of HHS. Experimental results on benchmark AMS instances demonstrate the superiority of the proposed algorithm over the existing ones. The applicability of HHS in solving different industrial problems and manufacturing scheduling problems is also verified. Note to Practitioners—Automated manufacturing systems (AMSs) are computer-controlled manufacturing systems. They exhibit a high degree of resources sharing and route flexibility and can be highly adaptable to various production plans. Solving their scheduling problems is of great significance to manufacturers. When designing a scheduling algorithm for such systems, engineers face two challenges: how to deal with deadlocks caused by jobs competing for limited resources, and how to maintain high solution ability when solving large-scale problems. Existing algorithms for scheduling deadlock-prone AMSs have to rely on specific deadlock handling strategies to ensure their feasibility, and are unable to find high-quality solutions for large-scale problems. This article presents a hybrid heuristic search (HHS) algorithm for minimizing the makespan of deadlock-prone AMSs, in which a duplicate detection policy, a pruning policy, and a hybrid search strategy are specially designed. The combination of these policies ensure that HHS can find a high-quality solution in a short computation time, even if no deadlock handling strategy is used in the algorithm. Experimental tests and comparisons show that HHS significantly outperforms existing algorithms. The proposed HHS can be applied to other AMS scheduling problems, and can be used as an online or real-time scheduling method due to its high computational efficiency.