基于遗传算法的多目标车间调度
|
摘要
针对作业车间调度中应用遗传算法求解存在的早熟问题,对其搜索速度、收敛效果和最优解等方面进行分析研究,给出一种新的混合遗传算法。首先对初始种群进行实数编码,增加解空间中可行解的个数;接着根据距离排列,增加种群的多样性;然后采用拉普拉斯交叉算子和逆转变异,改进算法的搜索效率;最后结合模拟退火算法,并在每一代遗传进化中引入局部搜索,提高了算法的全局寻优能力。通过与其他算法的仿真比较,结果表明新的混合算法能提高多目标车间调度问题的求解速度和质量,并能够找到最佳的调度方案。
Aiming at the premature problem of applying genetic algorithm in job shop scheduling, this paper analyzes and studies its search speed, convergence effect and optimal solution, and presents a new hybrid genetic algorithm. First, the initial population is real-coded to increase the number of feasible solutions in the solution space. Then arrange the population according to the distance to increase the diversity of the population. And the Laplacian crossover operator and inverse transformation are used to improve the search efficiency of the algorithm. Finally, the simulated annealing algorithm is combined, and local search is introduced in each generation of genetic evolution, which improves the global optimization ability of the algorithm. Compared with other algorithms, the results show that the new hybrid algorithm can improve the speed and quality of multi-objective shop scheduling problems and find the best scheduling solution.
Aiming at the premature problem of applying genetic algorithm in job shop scheduling, this paper analyzes and studies its search speed, convergence effect and optimal solution, and presents a new hybrid genetic algorithm. First, the initial population is real-coded to increase the number of feasible solutions in the solution space. Then arrange the population according to the distance to increase the diversity of the population. And the Laplacian crossover operator and inverse transformation are used to improve the search efficiency of the algorithm. Finally, the simulated annealing algorithm is combined, and local search is introduced in each generation of genetic evolution, which improves the global optimization ability of the algorithm. Compared with other algorithms, the results show that the new hybrid algorithm can improve the speed and quality of multi-objective shop scheduling problems and find the best scheduling solution.
引文
[1] 谭艳艳.几种改进的分解类多目标进化算法及其应用[D].西安:西安电子科技大学,2013.
[2] 曹策俊,李从东,杨琴,等.模拟植物生长算法在组合优化问题中的应用:研究进展[J].技术经济,2017,36(5):127-136.
[3] 林仁,周国华.机器柔性度对柔性车间调度影响的研究[J].计算机工程与应用,2015,51(7):18-23.
[4] Wang Han.A two-stage optimization method for energy-saving flexible job-shop scheduling based on energy dynamic characterization [J].Journal of Cleaner Production,2018,188:575-588.
[5] Jamrus Thitipong,Chen-Fu Chien,Mitsuo Gen,et al.Hybrid Particle Swarm Optimization Combined With Genetic Operators for Flexible Job-Shop Scheduling Under Uncertain Processing Time for Semiconductor Manufacturing [J].IEEE Transactions on Semiconductor Manufacturing,2018,31 (1) :32-41.
[6] Wang L,Luo CM,Cai JC.A Variable Interval Rescheduling Strategy for Dynamic Flexible Job Shop Scheduling Problem by Improved Genetic Algorithm [J].Journal Of Advanced Transportation,2017.
[7] XU WX,Wang Q,Bian WB,et al.Improved GA and global random machine selection based on key operation to solve FJSP [J].CIESC Journal,2017,68(3):1073-1080.
[8] Azzouz Ameni,Meriem Ennigrou,Lamjed Ben Said .A hybrid algorithm for flexible job-shop scheduling problem with setup time [J].International Journal of Production Management and Engineering,2017,5(1) :23-30.
[9] 蔡霞,李枚毅,王康,等.基于浮点型编码策略的差分多目标柔性车间调度优化[J].计算机应用研究,2013,30(4):999-1003.
[10] CHANG HC,Liu TK.Optimisation of distributed manufacturing flexible job shop scheduling by using hybrid genetic algorithms [J].Journal of Intelligent Manufacturing,2017,28 (8) :1973-1986.
[11] Deep K,Thakur M.A new crossover operator for real coded genetic algorithms[J].Applied Mathematics & Computation,2007,188(1):895-911.
[12] 刘爱军,杨育,邢青松,等.多目标模糊柔性车间调度中的多种群遗传算法[J].计算机集成制造系统,2011,17(9):1954-1961.
[2] 曹策俊,李从东,杨琴,等.模拟植物生长算法在组合优化问题中的应用:研究进展[J].技术经济,2017,36(5):127-136.
[3] 林仁,周国华.机器柔性度对柔性车间调度影响的研究[J].计算机工程与应用,2015,51(7):18-23.
[4] Wang Han.A two-stage optimization method for energy-saving flexible job-shop scheduling based on energy dynamic characterization [J].Journal of Cleaner Production,2018,188:575-588.
[5] Jamrus Thitipong,Chen-Fu Chien,Mitsuo Gen,et al.Hybrid Particle Swarm Optimization Combined With Genetic Operators for Flexible Job-Shop Scheduling Under Uncertain Processing Time for Semiconductor Manufacturing [J].IEEE Transactions on Semiconductor Manufacturing,2018,31 (1) :32-41.
[6] Wang L,Luo CM,Cai JC.A Variable Interval Rescheduling Strategy for Dynamic Flexible Job Shop Scheduling Problem by Improved Genetic Algorithm [J].Journal Of Advanced Transportation,2017.
[7] XU WX,Wang Q,Bian WB,et al.Improved GA and global random machine selection based on key operation to solve FJSP [J].CIESC Journal,2017,68(3):1073-1080.
[8] Azzouz Ameni,Meriem Ennigrou,Lamjed Ben Said .A hybrid algorithm for flexible job-shop scheduling problem with setup time [J].International Journal of Production Management and Engineering,2017,5(1) :23-30.
[9] 蔡霞,李枚毅,王康,等.基于浮点型编码策略的差分多目标柔性车间调度优化[J].计算机应用研究,2013,30(4):999-1003.
[10] CHANG HC,Liu TK.Optimisation of distributed manufacturing flexible job shop scheduling by using hybrid genetic algorithms [J].Journal of Intelligent Manufacturing,2017,28 (8) :1973-1986.
[11] Deep K,Thakur M.A new crossover operator for real coded genetic algorithms[J].Applied Mathematics & Computation,2007,188(1):895-911.
[12] 刘爱军,杨育,邢青松,等.多目标模糊柔性车间调度中的多种群遗传算法[J].计算机集成制造系统,2011,17(9):1954-1961.