Hybrid discrete shuffled frog leaping algorithm for the scheduling problem of flexible assembly systems
LI Xiao-ling
FENG Yan-xiang
ZHANG Guang-hui
DUAN Hao-hao
Abstract：This paper addresses the scheduling problem in flexible assembly systems(FAS)without intermediate buffer-s.In such systems,deadlock may occur when multiple jobs compete for limited shared resources under inappropriate allocation.To solve the scheduling problem of deadlock-prone FAS,Petri nets are used to model it,and a hybrid discrete shuffled frog leaping algorithm(HDSFLA)is proposed to minimize the maximum completion time,i.e.,makespan.Firstly,a novel encoding and decoding method is proposed,in which an individual is encoded as a complete transition sequence and can be decoded into a sequence of jobs and operations.Then,in order to guarantee the feasibility of each individual,an individual modification method and an improved individual modification method based on the-earliest-firing-time are de-veloped,through which an unfeasible solution can be repaired into a feasible one.Furthermore,based on the characteristics of the encoding method,a crossover operation is designed to generate new individuals for the next generation.In addition,to balance the global exploration and local exploitation capabilities of the proposed algorithm,a local search method based on swap and insert operators is developed and imbedded into the algorithm.Experimental tests on different instances and comparisons with other algorithms are conducted to demonstrate the effectiveness of HDSFLA.
Keywords：flexible assembly systemsdeadlockPetri netsschedulinghybrid discrete shuffled frog leaping algorithm
Publication Date：2025-04-30
Online Publishing Date：2025-08-15(First online date of this platform, not the publication date of the document)
Pages：11( 816-826 )