|Table of Contents|

Improved DRSGA for flexible job shop scheduling


Research Field:
Publishing date:


Improved DRSGA for flexible job shop scheduling
Zhao XiaoqiangHe Hao
College of Electrical Engineering and Information Engineering,Lanzhou University of Technology,Lanzhou 730050,China
flexible job shop scheduling dynamic random search genetic algorithm efficiency coefficient method sequence machine allocation double-layer chromosome encoding scheme variable influence space evaluation method contest rules
To solve the problems of flexible job shop scheduling that it is difficult to determine the weight and the scheduling efficiency is poor,an improved dynamic random search genetic algorithm(DRSGA)is proposed here.All minimized job completing time and total machine loading are translated into single minimized objective by the efficiency coefficient method.A double-layer chromosome encoding scheme is adopted based on sequence crossover and machine allocation crossover.A variable influence space evaluation method is used to guarantee the uniform distribution of non-inferior solutions,and the diversity of population is maintained.A dynamic random search(DRS)method and contest rules are employed to adjust key process orders and obtain the optimal scheduling scheme.The improved DRSGA is compared with the vector evaluated genetic algorithm(VEGA),the improved genetic algorithm(IMGA)and the hybrid genetic algorithm(HGA).The simulation results indicate that the average time of the optimal solution of the improved DRSGA is shorter than the other three algorithms for 41~257 s.


[1] Garey M,Johnson D,Sethi R.The complexity of flow shop and job-shop schedules[J].Mathematics of Operations Research,1976,1(2):117-129.
[3]杨晓梅,曾建潮.遗传算法求解柔性job shop调度问题[J].控制与决策,2004,19(10):1197-1200.
Yang Xiaomei,Zeng Jianchao.Solving flexible job shop scheduling problem using genetic algorithm[J].Control and Decision,2004,19(10):1197-1200.
Peng Jiangang,Liu Mingzhou,Zhang Xi,et al.Rescheduling algorithm based on uncertain processing time of operations for a flexible job-shop[J].China Mechanical Engineering,2014,6(17):2320-2326.
Liu Yuefan,Zhu Xing.Solving flexible job shop scheduling problem based on an improved genetic algorithm[J].Journal of Dalian Jiaotong University,2015,36(4):101-104.
Ren Xiaoli.Improving CGA by LSO for multiple-objective job shop scheduling problem[J].Computer Applications and Software,2015,32(3):60-64.
[7]Hamzacebi C,Kutay F.Continuous functions minimization by dynamic random search technique[J].Applied Mathematical Modelling,2007,31(10):2189-2198.
[8]Pan Quanke,Wang Ling,Gao Liang,et al.Differential evolution algorithm based on blocks on critical path for job shop scheduling problems[J].Journal of Mechanical Engineering,2010,46(22); 182-188.
Zhang Chaoyong,Rao Yunqing,Liu Xiangjun,et al.An improved genetic algorithm for the job shop scheduling problem[J].China Mechanical Engineering,2004,15(23):2149-2153.
[10]Zhang Guohui,Shao Xinyu,Li Peigen,et al.An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem[J].Computers & Industrial Engineering,2009,56(4):1309-1318.
[11]Knowles J,Corne D.On metrics for comparing nondominated sets[C]//Proceedings of the Congress on Evolutionary Computation(CEC-2002).New York,NY,USA:IEEE,2002:711-716.
[12]Kacem I,Hammadi S,Borne P.Pareto-optimality approach for flexible job-shop scheduling problems:Hybridization of evolutionary algorithms and fuzzy logic[J].Mathematics & Computers in Simulation,2002,60(3-5):245-276.


Last Update: 2016-06-30