A new Hybrid Filtered Beam Search algorithm for deadlock-free scheduling of flexible manufacturing systems using Petri Nets
Computers & Industrial Engineering, (June 2017)DOI: 10.1016/j.cie.2017.04.034
Abstract
A fast and efficient Beam Search strategy based on Petri Nets for FMS scheduling. A Double filtering mechanisms that reduce the search space and computational time. A learning mechanism based on upper bounds for improving the search. New best solutions on classical deadlock-prone instances of FMS. This paper presents a new Hybrid Filtered Beam Search algorithm for deadlock-free scheduling of flexible manufacturing systems. The proposed algorithm uses a diversification/intensification strategy that aims to selectively explore the state space of a Timed Place Petri Net that represents the dynamics of the system. The exploration strategy is based on a double filtering mechanism that limits the number of markings that can be expanded at each level of the search tree. The algorithm, which was tested on several benchmark instances from the literature, not only produces good quality schedules but it is also efficient in terms of memory requirements and computational time. In addition, the algorithm requires little tune-up and produces consistent results. Computational experiments show the effectiveness of the algorithm in comparison with other recent and state of the art methods.