|Table of Contents|

Improved DRSGA for flexible job shop scheduling

《南京理工大学学报》(自然科学版)[ISSN:1005-9830/CN:32-1397/N]

Issue:
2016年03期
Page:
297-
Research Field:
Publishing date:

Info

Title:
Improved DRSGA for flexible job shop scheduling
Author(s):
Zhao XiaoqiangHe Hao
College of Electrical Engineering and Information Engineering,Lanzhou University of Technology,Lanzhou 730050,China
Keywords:
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
PACS:
TP301
DOI:
10.14177/j.cnki.32-1397n.2016.40.03.008
Abstract:
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.

References:

[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.
[2]张文修,梁怡.遗传算法的数学基础[M].西安:西安交通大学出版社,2000.
[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.
[4]彭建刚,刘明周,张玺,等.工序加工时间不确定的柔性作业车间重调度算法[J].中国机械工程,2014,6(17):2320-2326.
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.
[5]刘月凡,朱星.改进的遗传算法求解柔性作业车间调度问题[J].大连交通大学学报,2015,36(4):101-104.
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.
[6]任晓莉.LSO改进CGA解决多目标作业车间调度问题[J].计算机应用与软件,2015,32(3):60-64.
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.
[9]张超勇,饶运清,刘向军,等.基于POX交叉的遗传算法求解Job-Shop调度问题[J].中国机械工程,2004,15(23):2149-2153.
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.

Memo

Memo:
-
Last Update: 2016-06-30