Scheduling Problems for a Class of Hybrid FMS Using T-TPN and Beam Search

Journal of control, automation and electrical systems

article

Cherif, G.¹  Leclercq, E.¹  Lefebvre, D.¹ 

[1] Normandie Université

关键词: Complex discrete event systems;    T-TPN;    Scheduling;    Beam search;   

DOI  :  10.1007/s40313-021-00700-5

学科分类：自动化工程

来源: Springer

【 摘 要 】

This paper is about scheduling problems for a class of flexible manufacturing systems (FMS) that have some operations with total precedence constraints and other operations with full routing flexibility (namely hybrid FMS). The objective is to find a control sequence from an initial state to a reference one in minimal time. For that, a systematic multi-level formalism is introduced to model the hybrid FMS based on the hierarchical structuration of the operations. Transition-timed Petri nets (T-TPN) that behave under earliest firing policy are used for that purpose. Then a new cost function is introduced to estimate the residual time to the reference. This estimation is proved to be a lower bound of the true duration. A modified Beam Search algorithm is proposed that uses the cost function to selectively explore the Petri net (PN) state space. Computational experiments illustrate the efficiency of the approach in comparison with other existing methods.

【 授权许可】

CC BY