多目标置换流水车间调度的改进食物链算法

摘要/Abstract

摘要：

针对目标函数为最小化最大完成时间和总延迟时间的多目标置换流水车间调度问题，提出了一种改进的食物链算法。该算法在食物链算法的基础上，引入基于Pareto最优解的快速非支配性排序和个体拥挤距离计算，增强了算法的寻优性能。对OR-Library三个典型算例的优化比较表明，该算法在解的质量上明显超越NSGA-Ⅱ算法。

关键词: 置换流水车间调度, 多目标优化, 食物链算法, Pareto最优解

Abstract:

An improved food chain algorithm was proposed for permutation flow shop scheduling with multiple objectives of minimizing makespan and total tardiness. Fast non-dominated sorting and crowded distance estimation were introduced into the food chain algorithm to improve the optimization ability based on Pareto optimal solutions. Three typical OR-Library examples were selected to conduct comparison. Numerical results show that the designed algorithm can obtain much better solutions than NSGA-Ⅱ.

Key words: permutation flow shop scheduling, multi-objective optimization, food chain algorithm, Pareto optimal solution

中图分类号:

F406.2

陈可嘉, 周晓敏. 多目标置换流水车间调度的改进食物链算法[J]. 中国机械工程, 2015, 26(3): 348-353,360.

Chen Kejia, Zhou Xiaomin. Improved Food Chain Algorithm for Multi-objective Permutation Flow Shop Scheduling[J]. China Mechanical Engineering, 2015, 26(3): 348-353,360.

参考文献

[1]Ishibuchi H, Murata T. A Multi-objective Genetic Local Search Algorithm and Its Application to Flowshop Scheduling[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 1998, 28(3): 392-403.
[2]Ravindran D, Haq A N, Selvakumar S J, et al. Flow Shop Scheduling with Multiple Objective of Minimizing Makespan and Total Flow Time[J]. International Journal of Advanced Manufacturing Technology, 2005, 25(9/10): 1007-1012.
[3]Yagmahan B, Yenisey M M. A Multi-objective Ant Colony System Algorithm for Flow Shop Scheduling Problem[J]. Expert Systems with Applications, 2010, 37(2): 1361-1368.
[4]Lee C K M, Lin D, Ho W, et al. Design of a Genetic Algorithm for Bi-objective Flow Shop Scheduling Problems with Re-entrant Jobs[J]. International Journal of Advanced Manufacturing Technology, 2011, 56(9/12): 1105-1113.
[5]Pasupathy T, Rajendran C, Suresh R K. A Multi-objective Genetic Algorithm for Scheduling in Flow Shops to Minimize the Makespan and Total Flow Time of Jobs[J]. International Journal of Advanced Manufacturing Technology, 2006, 27(7/8): 804-815.
[6]Lemesre J, Dhaenens C, Talbi E G. An Exact Parallel Method for a Bi-objective Permutation Flowshop Problem[J]. European Journal of Operational Research, 2007, 177(3): 1641-1655.
[7]Qian B, Wang L, Huang D X, et al. An Effective Hybrid DE-based Algorithm for Multi-objective Flow Shop Scheduling with Limited Buffers[J]. Computers & Operations Research, 2009, 36(1): 209-233.
[8]Dubois-Lacoste J, López-Ibáez M, Stützle T. A Hybrid TP+PLS Algorithm for Bi-objective Flow-shop Scheduling Problems[J]. Computers & Operations Research, 2011, 38(8): 1219-1236.
[9]Arroyo J E C, de Souza Pereira A A. A GRASP Heuristic for the Multi-objective Permutation Flowshop Scheduling Problem[J]. International Journal of Advanced Manufacturing Technology, 2011, 55(5/8): 741-753.
[10]杨开兵, 刘晓冰. 带调整时间的多目标流水车间调度的优化算法[J]. 工业工程与管理, 2008, 13(5): 1-5.
Yang Kaibing, Liu Xiaobing. Optimization Algorithm for Multi-objective Flow Shop Scheduling with Setup Times[J]. Industrial Engineering and Management, 2008, 13(5): 1-5.
[11]董兴业, 黄厚宽, 陈萍. 多目标同顺序流水作业的局部搜索算法[J]. 计算机集成制造系统, 2008, 14(3): 535-542.
Dong Xingye, Huang Houkuan, Chen Ping. Local Search Algorithm for Multi-objective Permutation Flowshop Sequencing Problem[J]. Computer Integrated Manufacturing Systems, 2008, 14(3): 535-542.
[12]秦艳. 改进交叉策略的GA在流水车间多目标调度中的应用[J]. 现代制造工程, 2010(12): 29-32.
Qin Yan. Application of GA with Improved Crossover Operators in Multi-objective Flow Shop Scheduling[J]. Modern Manufacturing Engineering, 2010(12): 29-32.
[13]喻海飞, 汪定伟. 食物链算法及其在供应链计划中的应用[J]. 系统仿真学报, 2005, 17(5): 1195-1198.
Yu Haifei, Wang Dingwei. Food-chain Algorithm and Application to Supply-chain Planning[J]. Journal of System Simulation, 2005, 17(5): 1195-1198.
[14]喻海飞, 汪定伟. 食物链算法及其在分销网络优化中的应用[J]. 东北大学学报(自然科学版), 2006, 27(2): 146-149.
Yu Haifei, Wang Dingwei. Food-chain Algorithm and Its Application to Optimizing Distribution Network[J]. Journal of Northeastern University (Natural Science), 2006, 27(2): 146-149.
[15]Zitzler E. Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications[M]. Aachen: Shaker Verlag, 1999.
[16]Deb K, Pratap A, Agarwal S, Meyarivan T. A Fast and Elitist Multiobjective Genetic Algorithm：NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197.
[17]Beasley J E. OR-Library. (2012-06-12)[2013-09-13]. http://people.brunel.ac.uk/~mastjjb/jeb/info.html.
[18]师瑞峰, 周泓, 上官春霞. 混合递进多目标进化算法及其在flow shop排序中的应用[J]. 系统工程理论与实践, 2006, 26(8): 101-108.
Shi Ruifeng, Zhou Hong, Shangguan Chunxia. A Hybrid Escalating Multi-objective Evolutionary Algorithm with Its Application to Flow Shop Problems[J]. Systems Engineering-Theory & Practice, 2006, 26(8): 101-108.