Research On Shop Scheduling Approaches Based On Gene Expression Programming

With the increasingly fierce competition in manufacturing industry,shop scheduling,which is a core problem in manufacturing enterprises,is attracting more and more concerns in both academy and industry.Gene Expression Programming(GEP)is an evolutionary algorithm designed for learning,which is capable of extracting domain knowledges from different problem domains.This paper focuses on applications of GEP in shop scheduling from various perspectives,covering direct and indirect approaches.In view of a more efficient problem solving,a hybrid algorithm is proposed based on GEP and Biogeography-Based Optimization(BBO),combining the good exploration ablitiy of GEP and strong exploitation ability of BBO.The regression benchmark results show that proposed Biogeography-Based Gene Expression Programming(BBGEP)is superior to the original GEP in terms of convergence and solution quality.Further,a scheduling rule mining framework is proposed based on BBGEP.The framework ultilizes BBGEP to learn from different kinds of scheduling scenarios,searching for scheduling rules which are suitable for different shop types respectively.The obtained rules are then applied into scheduling for problem solving.The numeric experiments show that proposed framework can be applied in permutation flow shop scheduling problem(PFSP)and dynamic flexible job shop scheduling problem(DFJSP)effectively.Next,a hyper-herusitic(HH)based on BBGEP for scheduling problems is proposed.The HH framework uses BBGEP as high level heuristic to guide the search in the algorithm searching space,controlling the execution of low level heuristics and solution updates.The proposed HH can be applied directly for scheduling problems.The numeric experiment shows that the proposed BBGEP-HH is capable of solving PFSP and FJSP with sequence dependent setup times and performs better than Genetic Algorithm and Grey Wolf Optimizer.At last,the paper presents a real world surface mount technology(SMT)shop scheduling case and BBGEP-HH is applied to solve this problem.The case study shows that proposed BBGEP-HH permforms reasonablely well,which further proves the vadality of this approach.