置换流水车间调度问题的中心引力优化算法求解
|
摘要
目前求解置换流水车间调度问题的智能优化算法都是随机型优化方法,存在的一个问题是解的稳定性较差。针对该问题,本文给出一种确定型智能优化算法——中心引力优化算法的求解方法。为处理基本中心引力优化算法对初始解选择要求高的问题,利用低偏差序列生成初始解,提高初始解质量;利用加速度和位置迭代方程更新解的状态;利用两位置交换排序法进行局部搜索,提高算法的优化性能。采用置换流水车间调度问题标准测试算例进行数值实验,并和基本中心引力优化算法、NEH启发式算法、微粒群优化算法和萤火虫算法进行比较。结果表明该算法不仅具有更好的解的稳定性,而且具有更高的计算精度,为置换流水车间调度问题的求解提供了一种可行有效的方法。
The existing intelligent optimization algorithms for permutation flow-shop scheduling problem are all stochastic optimization methods. One problem with these approaches is that they have poor solution stability. In this paper,a method based on central force optimization algorithm which is a deterministic intelligent optimization algorithm is proposed to resolve this problem. The basic algorithm depends upon the choice of the initial solutions. To deal with this problem,low-discrepancy sequences are used to generate initial solutions to improve the quality of initial solutions. The acceleration and position equations are employed to update the solutions. A sorting method to swap two positions in a solution is used to conduct local searches,to enhance the performance of the algorithm. The benchmarks are used to perform numerical experiments. The presented algorithm is compared with basic central force optimization algorithm,NEH heuristic algorithm,particle swarm optimization algorithm,and firefly algorithm. The results demonstrate that the proposed method not only has better solution stability but also higher accuracy. The presented approach provides a feasible and effective way to solve the permutation flowshop scheduling problem.
The existing intelligent optimization algorithms for permutation flow-shop scheduling problem are all stochastic optimization methods. One problem with these approaches is that they have poor solution stability. In this paper,a method based on central force optimization algorithm which is a deterministic intelligent optimization algorithm is proposed to resolve this problem. The basic algorithm depends upon the choice of the initial solutions. To deal with this problem,low-discrepancy sequences are used to generate initial solutions to improve the quality of initial solutions. The acceleration and position equations are employed to update the solutions. A sorting method to swap two positions in a solution is used to conduct local searches,to enhance the performance of the algorithm. The benchmarks are used to perform numerical experiments. The presented algorithm is compared with basic central force optimization algorithm,NEH heuristic algorithm,particle swarm optimization algorithm,and firefly algorithm. The results demonstrate that the proposed method not only has better solution stability but also higher accuracy. The presented approach provides a feasible and effective way to solve the permutation flowshop scheduling problem.
引文
[1]刘长平,叶春明.置换流水车间调度问题的萤火虫算法求解[J].工业工程与管理,2012,17(3):56-59,65.
[2]Garey M R,Johnson D S,Sethi R.The complexity of flowshop and jobshop scheduling[J].Mathematics of Operations Research,1976,1(2):117-129.
[3]刘三阳.置换流水车间调度问题的几种智能算法[D].西安电子科技大学:博士学位论文,2012.
[4]Formato R A.Central force optimization:a new metaheuristic with applications in applied electromagnetics[J].Progress in Electromagnetics Research,2007,77:425-491.
[5]Green R,Wang L,Alam M.Training neural networks using central force optimization and particle swarm optimization:insights and comparisons[J].Expert Systems with Applications,2012,39:555-563.
[6]Haghighi A,Ramos HM.Detection of leakage freshwater and friction factor calibration in drinking networks using central force optimization[J].Water Resource Manage,2012,26:2347-2363.
[7]Roa O,Amaya I,Ramirez F,Correa R.Solution of nonlinear circuits with the central force optimization algorithm[C].Proceedings of the IEEE 4th Colombian Workshop on Circuits and Systems,Barranquilla,2012:1-6.
[8]Chen Y B,Yu J Q,Mei Y S,Wang Y,Su X.Modified central force optimization(MCFO)algorithm for 3D UAV path planning[J].Neurocomputing,2016,171:878-888.
[9]朱高峰,伍铁斌,张艳蕾,成运,刘云连.求解约束优化问题的中心引力优化算法及其工程应用[J].计算机应用研究,2013,30(10):2923-2926,2961.
[10]Liu Y,Tian P.A multi-start central force optimization for global optimization[J].Applied Soft Computing,2015,27:92-98.
[11]Maaranen H,Miettinen K,MkelM M.Quasi-random initial population for genetic algorithms[J].Computers&Mathematics with Applications,2004,47(12):1885-1895.
[12]Formato R A.Central force optimization with variable initial probes and adaptive decision space[J].Applied Mathematics and Computation,2011,217(21):8866-8872.
[13]Carlier J.Scheduling with disjunctive constraints[J].RAIRO-Operations Research,1978,12(4):333-350.
[2]Garey M R,Johnson D S,Sethi R.The complexity of flowshop and jobshop scheduling[J].Mathematics of Operations Research,1976,1(2):117-129.
[3]刘三阳.置换流水车间调度问题的几种智能算法[D].西安电子科技大学:博士学位论文,2012.
[4]Formato R A.Central force optimization:a new metaheuristic with applications in applied electromagnetics[J].Progress in Electromagnetics Research,2007,77:425-491.
[5]Green R,Wang L,Alam M.Training neural networks using central force optimization and particle swarm optimization:insights and comparisons[J].Expert Systems with Applications,2012,39:555-563.
[6]Haghighi A,Ramos HM.Detection of leakage freshwater and friction factor calibration in drinking networks using central force optimization[J].Water Resource Manage,2012,26:2347-2363.
[7]Roa O,Amaya I,Ramirez F,Correa R.Solution of nonlinear circuits with the central force optimization algorithm[C].Proceedings of the IEEE 4th Colombian Workshop on Circuits and Systems,Barranquilla,2012:1-6.
[8]Chen Y B,Yu J Q,Mei Y S,Wang Y,Su X.Modified central force optimization(MCFO)algorithm for 3D UAV path planning[J].Neurocomputing,2016,171:878-888.
[9]朱高峰,伍铁斌,张艳蕾,成运,刘云连.求解约束优化问题的中心引力优化算法及其工程应用[J].计算机应用研究,2013,30(10):2923-2926,2961.
[10]Liu Y,Tian P.A multi-start central force optimization for global optimization[J].Applied Soft Computing,2015,27:92-98.
[11]Maaranen H,Miettinen K,MkelM M.Quasi-random initial population for genetic algorithms[J].Computers&Mathematics with Applications,2004,47(12):1885-1895.
[12]Formato R A.Central force optimization with variable initial probes and adaptive decision space[J].Applied Mathematics and Computation,2011,217(21):8866-8872.
[13]Carlier J.Scheduling with disjunctive constraints[J].RAIRO-Operations Research,1978,12(4):333-350.