Scheduling of flexible manufacturing systems based on Petri nets and hybrid heuristic search

Abstract

Abstract This paper proposes and evaluates a hybrid search strategy and its application to flexible manufacturing system (FMS) scheduling in a Petri net framework. Petri nets can concisely model multiple lot sizes for each job, the strict precedence constraint, multiple kinds of resources, and concurrent activities. To cope with the complexities for FMS scheduling, this paper presents a hybrid heuristic search strategy, which combines the heuristic A* strategy with the DF strategy based on the execution of the Petri nets. The search scheme can invoke quicker termination conditions, and the quality of the search result is controllable. To demonstrate this, the scheduling results are derived and evaluated through a simple FMS with multiple lot sizes for each job. The algorithm is also applied to a set of randomly generated more complex FMSs with such characteristics as limited buffer sizes, multiple resources, and alternative routings. Keywords: Petri netsManufacturing strategySchedulingHeuristics Acknowledgements The research described in this paper is supported by a grant from the Jiangsu Key Science and Technology Project of China (Project No. BE2002010), the National Research Foundation for the Doctoral Programme of Higher Education of China (Project No. 20050288015), and the Science Innovation Fund of NUST. The authors want to thank Dr Huanxin Henry Xiong at Lucent Technologies, for his helpful suggestions in this research.