改进NSGA算法求解多目标柔性车间作业调度问题
|
摘要
在多目标柔性车间作业调度问题的研究中,求解算法与多目标处理至关重要。因此,基于非支配排序遗传算法提出了改进遗传算法求解该问题,设计了相应的矩阵编码、交叉算子,改进了非劣前沿分级方法,并提出了基于Pareto等级的自适应变异算子以及精英保留策略。实例计算表明,该算法可以利用传统遗传算法全局搜索能力的同时可以防止早熟现象的发生。改进非劣前沿分级方法可以快速得到Pareto最优解集,进一步减小了计算复杂度,而且可以根据种群的多样性改变变异概率,有利于保持种群多样性、发掘潜力个体。
During the evaluation process of the job-shop scheduling problem, the algorithm and multi-objective optimization are very important. Therefore, an improved genetic algorithm based on NSGA is proposed and the corresponding matrix coding, decoding and crossover operators are designed. To reduce the computational complexity and improve the performance of the algorithm, a novel non-dominated sorting method, adaptive mutation operators and elite retention strategies are introduced. The simulation experiments show that this non-dominated sorting method can get the Pareto optimal solutions quickly and correctly by dividing the whole population into three parts. This algorithm can make full use of the global searching ability of traditional genetic algorithm, prevent the occurrence of precocious phenomenon, and change the mutation probability according to the diversity of the population.
During the evaluation process of the job-shop scheduling problem, the algorithm and multi-objective optimization are very important. Therefore, an improved genetic algorithm based on NSGA is proposed and the corresponding matrix coding, decoding and crossover operators are designed. To reduce the computational complexity and improve the performance of the algorithm, a novel non-dominated sorting method, adaptive mutation operators and elite retention strategies are introduced. The simulation experiments show that this non-dominated sorting method can get the Pareto optimal solutions quickly and correctly by dividing the whole population into three parts. This algorithm can make full use of the global searching ability of traditional genetic algorithm, prevent the occurrence of precocious phenomenon, and change the mutation probability according to the diversity of the population.
引文
[1]薛宏全,魏生民,张鹏,等.基于多种群蚁群算法的柔性作业车间调度研究[J].计算机工程与应用,2013,49(24):243-248.
[2]王凌,邓瑾,王圣尧.分布式车间调度优化算法研究综述[J].控制与决策,2016,31(1):1-11.
[3]施文章,韩伟,戴睿闻.模拟退火下布谷鸟算法求解车间作业调度问题[J].计算机工程与应用,2017,53(17):249-253.
[4] Mokhtari H,Hasani A.An energy efficient muti-objective optimization for flexible job shop scheduling problem[J].Comput Chem Eng,2017,104(2):339-352.
[5]屈迟文,傅彦铭,罗明山,等.求解柔性作业车间调度问题的鸟群算法[J].计算机工程与应用,2018,54(17):249-257.
[6] Amjad M K,Butt S I,Kousar R,et al.Recent research trends in genetic algorithm based flexible job shop scheduling problems[J].Mathematical Problems in Engineering,2018(8):1-32.
[7] Li X,Gao L.An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem[J].Int J Prod Econ,2016,174:93-110.
[8] Chen M,Li J.Genetic algorithm combined with gradient information for flexible job-shop scheduling problem with different varieties and small batches[C]//Proceedings of2016 the 3rd International Conference on Mechatronics and Mechanical Engineering,2017.
[9] Cinar D,Oliveira J A,Topcu Y I,et al.A priority-based genetic algorithm for a flexible job shop scheduling problem[J].Journal of Industrial&Management Optimization,2017,12(4):1391-1415.
[10] Liu A,Fowler J,Pfund M.Dynamic co-ordinated scheduling in the supply chain considering flexible routes[J].International Journal of Production Research,2016,54(1):322-335.
[11] Liu A,Pfund M,Fowler J.Scheduling optimization of task allocation in integrated manufacturing system based on task decomposition[J].Journal of Systems Engineering and Electronics,2016,27(2):422-433.
[12] Liu A,Liu H,Tsai S B,et al.Using a hybrid model on joint scheduling of berths and quay cranes—from a sustainable perspective[J].Sustainability,2018,10(6):1-15.
[13]李峥峰.多时间因素作业车间调度问题的研究与工程应用[D].武汉:华中科技大学,2010.
[14]刘林,郑江.改进生物地理学算法求解柔性作业调度问题[J].计算机工程与应用,2016,52(18):228-234.
[15]马邦雄,叶春明.基于改进量子猫群算法的流水车间调度研究[J].计算机工程与应用,2015,51(17):34-37.
[16]张华军,赵金,罗慧,等.基于个人偏好的多目标优化问题目标权重计算方法[J].控制与决策,2014,29(8):1471-1476.
[17] Srinivas N,Deb K.Muilti-objective optimization using nondominated sorting in genetic algorithms[J].Evolutionary Computation,1994,2(3),221-248.
[18] Deb K,Agrawal S,Pratap A,et al.A fast elitist nondominated sorting genetic algorithm for multi-objective optimization:NSGA-II[M].Berlin Heidelberg:Springer,2000:849-858.
[19]张超勇,董星,王晓娟,等.基于改进非支配排序遗传算法的多目标柔性作业车间调度[J].机械工程学报,2010,46(11):156-164.
[20]刘晓霞,谢里阳,陶泽,等.柔性作业车间多目标调度优化研究[J].东北大学学报(自然科学版),2008,29(3):362-365.
[21]张超勇,饶运清,李培根,等.柔性作业车间调度问题的两级遗传算法[J].机械工程学报,2007,43(4):119-124.
[2]王凌,邓瑾,王圣尧.分布式车间调度优化算法研究综述[J].控制与决策,2016,31(1):1-11.
[3]施文章,韩伟,戴睿闻.模拟退火下布谷鸟算法求解车间作业调度问题[J].计算机工程与应用,2017,53(17):249-253.
[4] Mokhtari H,Hasani A.An energy efficient muti-objective optimization for flexible job shop scheduling problem[J].Comput Chem Eng,2017,104(2):339-352.
[5]屈迟文,傅彦铭,罗明山,等.求解柔性作业车间调度问题的鸟群算法[J].计算机工程与应用,2018,54(17):249-257.
[6] Amjad M K,Butt S I,Kousar R,et al.Recent research trends in genetic algorithm based flexible job shop scheduling problems[J].Mathematical Problems in Engineering,2018(8):1-32.
[7] Li X,Gao L.An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem[J].Int J Prod Econ,2016,174:93-110.
[8] Chen M,Li J.Genetic algorithm combined with gradient information for flexible job-shop scheduling problem with different varieties and small batches[C]//Proceedings of2016 the 3rd International Conference on Mechatronics and Mechanical Engineering,2017.
[9] Cinar D,Oliveira J A,Topcu Y I,et al.A priority-based genetic algorithm for a flexible job shop scheduling problem[J].Journal of Industrial&Management Optimization,2017,12(4):1391-1415.
[10] Liu A,Fowler J,Pfund M.Dynamic co-ordinated scheduling in the supply chain considering flexible routes[J].International Journal of Production Research,2016,54(1):322-335.
[11] Liu A,Pfund M,Fowler J.Scheduling optimization of task allocation in integrated manufacturing system based on task decomposition[J].Journal of Systems Engineering and Electronics,2016,27(2):422-433.
[12] Liu A,Liu H,Tsai S B,et al.Using a hybrid model on joint scheduling of berths and quay cranes—from a sustainable perspective[J].Sustainability,2018,10(6):1-15.
[13]李峥峰.多时间因素作业车间调度问题的研究与工程应用[D].武汉:华中科技大学,2010.
[14]刘林,郑江.改进生物地理学算法求解柔性作业调度问题[J].计算机工程与应用,2016,52(18):228-234.
[15]马邦雄,叶春明.基于改进量子猫群算法的流水车间调度研究[J].计算机工程与应用,2015,51(17):34-37.
[16]张华军,赵金,罗慧,等.基于个人偏好的多目标优化问题目标权重计算方法[J].控制与决策,2014,29(8):1471-1476.
[17] Srinivas N,Deb K.Muilti-objective optimization using nondominated sorting in genetic algorithms[J].Evolutionary Computation,1994,2(3),221-248.
[18] Deb K,Agrawal S,Pratap A,et al.A fast elitist nondominated sorting genetic algorithm for multi-objective optimization:NSGA-II[M].Berlin Heidelberg:Springer,2000:849-858.
[19]张超勇,董星,王晓娟,等.基于改进非支配排序遗传算法的多目标柔性作业车间调度[J].机械工程学报,2010,46(11):156-164.
[20]刘晓霞,谢里阳,陶泽,等.柔性作业车间多目标调度优化研究[J].东北大学学报(自然科学版),2008,29(3):362-365.
[21]张超勇,饶运清,李培根,等.柔性作业车间调度问题的两级遗传算法[J].机械工程学报,2007,43(4):119-124.