Review on Scheduling Algorithms for MOFJSP

Abstract

Abstract:

A mathematical model and related definitions of MOFJSP were introduced and the related theories and the research fruits of MOFJSP were summarized. The emphasis was focused on review both of the computational intelligent algorithms and the intelligent search methods. Some future research directions and contents of optimization scheduling algorithms were pointed out and suggestions of related researches in the future were proposed.

Key words: multi-objective flexible job-shop scheduling problem(MOFJSP), scheduling, algorithm, review

摘要：

首先，介绍了多目标柔性作业车间调度问题的数学模型和有关定义；其次，总结了相关优化算法理论，汇总了MOFJSP优化算法的研究成果, 重点综述了求解多目标优化问题性能优良的计算智能方法和智能搜索算法；最后，指出MOFJSP优化算法若干有待进一步研究的方向和内容，并为下一步研究提出了建议。

关键词: 多目标柔性作业车间, 调度, 算法, 综述

CLC Number:

TP301

Peng Jiangang, Liu Mingzhou, Zhang Mingxin, Zhang Xi. Review on Scheduling Algorithms for MOFJSP[J]. China Mechanical Engineering, 2014, 25(23): 3244-3254.

彭建刚, 刘明周, 张铭鑫, 张玺. 多目标柔性作业车间调度算法研究综述[J]. 中国机械工程, 2014, 25(23): 3244-3254.

References

[1]Conway R N, Maxwel W L, Miller L W. Theory of Scheduling[M].New York:Dover Publications INC,2003.
[2]Jain A S, Meeran S. Deterministic Job-shop Scheduling: Past, Present and Future[J].European Journal of Operational Research, 1999,113 (2):390-434.
[3]Blazewicz J,Finke G,Haopt G.New Trends in Machine Scheduling[J].European Journal of Operational Research, 1988,37:303-317.
[4]Andries P E.计算智能导论[M].2版.北京:清华大学出版社,2010.
[5]公茂果,焦李成,杨咚咚,等.进化多目标优化算法研究[J].软件学报,2009,20(2):271-289.
Gong Maoguo,Jiao Licheng,Yang Dongdong,et al. Research on Evolutionary Multi-objective Optimization Algorithms[J].Journal of Software,2009,20(2):271-289.
[6]Abdullah K,David W C,Alice E S.Multi-objective Optimization Using Genetic Algorithms: a Tutorial[J]. Reliability Engineering and System Safety,2006,91: 992-1007.
[7]Liu A J,Yang Y,Liang X D, et al. Fuzzy and Dynamic Flexible Job-shop Scheduling with Multi-object and Multi-constraints[C]//Proceedings of the 2010 International Conference on Mechanical,Industrial,and Manufacturing Technologies(MIMT 2010). Sanya,China:331-336.
[8]Xiong J,Xing L N,Chen Y W. Robust Scheduling for Multi-objective Flexible Job-shop Problems with Random Machine Breakdowns[J]. International Journal of Production Economics, 2012,141(1):112-126.
[9]Xing L N, Chen Y W, Yang K W. Multi-objective Flexible Job Shop Schedule: Design and Evaluation by Simulation Modeling[J]. Applied Soft Computing,2009,9(1):362-376.
[10]Montazeri M, Wassehove L N. Analysis of Scheduling Rules of an FMS[J]. Int. J. Prod. Res.,1990,28(4):785-802.
[11]Zhou Defan,Jiang Jingang, Luo Chunling, et al. Multi-objective Flexible Job-shop Scheduling Method Study Based on the Integration Algorithm of GA-BP[J]. International Journal of Digital Content Technology and Its Applications, 2013,7(2):109-116.
[12]Holland J H.Adaptation in Natural and Artificial Systems[M]. Cambridge:MIT Press,1992.
[13]Wu Xiuli,Li Shujian. Mass Variety and Small Batch Scheduling in the Flexible Job Shop[J]. Proceedings of the 2009 2nd International Conference on Biomedical Engineering and Informatics,2009,1/4:2207-2213.
[14]吴秀丽,孙树栋,余建军,等.多目标柔性作业车间调度优化研究[J].计算机集成制造系统,2006,12(5):731-736.
Wu Xiuli,Sun Shudong,Yu Jianjun, et al.Research on Multi-objective Optimization for Flexible Job Shop Scheduling[J].Computer Integrated Manufacturing Systems, 2006,12(5):731-736.
[15]陈华平,谷峰,卢冰原,等.自适应多目标遗传算法在柔性工作车间调度中的应用[J].系统仿真学报,2006,18(8):2271-2288.
Chen Huaping,Gu Feng,Lu Bingyuan, et al.Aplication of Self-adaptive Multi-objective Genetic Algorithm in Flexible Job Shop Scheduling[J].Journal of System Simulation,2006,18(8): 2271-2288.
[16]刘爱军,杨育,邢青松,等.柔性作业车间多目标动态调度[J].计算机集成制造系统,2011,17(12):2629-2637.
Liu Aijun,Yang Yu,Xing Qingsong,et al. Dynamic Scheduling on Multi-objective Flexible Job Shop[J].Computer Integrated Manufacturing Systems, 2011,17(12):2629-2637.
[17]Li J Q,Pan Q K,Xie S X. A Hybrid Variable Neighborhood Search Algorithm for Solving Multi-objective Flexible Job Shop Problems[J].Computer Science and Information Systems, 2010,7(4): 907-930.
[18]Zhang Guohui,Gao Liang,Shi Yang. A Novel Variable Neighborhood Genetic Algorithm for Multi-objective Flexible Job-shop Scheduling Problems[J].Materials and Product Technologies: Advanced Materials Research,2010,118/120: 369-373.
[19]Wang Xiaojuan,Li Wenfeng,Zhang Ying.An Improved Multi-objective Genetic Algorithm for Fuzzy Flexible Job-shop Scheduling Problem[J].International Journal of Computer Applications in Technology.2013,47(2/3):280-288.
[20]刘爱军,杨育,程文明,等.复杂制造环境下的改进非支配排序遗传算法[J].计算机集成制造系统,2012,18(11):2446-2458.
Liu Aijun,Yang Yu,Cheng Wenming,et al. Improved NSGA for Complex Manufacturing Environment[J].Computer Integrated Manufacturing Systems,2012,18(11):2446-2458.
[21]张超勇,董星,王晓娟,等.基于改进非支配排序遗传算法的多目标柔性作业车间调度[J].机械工程学报,2010,46(11):156-164.
Zhang Chaoyong,Dong Xing,Wang Xiaojuan,et al. Improved NSGA-Ⅱ for the Multi-objective Flexible Job-shop Scheduling Problem[J]. Journal of Mechanical Engineering, 2010,46(11):156-164.
[22]Frutos M, Olivera A C, Tohme F. A Memetic Algorithm Based on a NSGAII Scheme for the Flexible Job-shop Scheduling Problem[J].Annals of Operations Research, 2010, 181(1): 745-765.
[23]Zeng Qiang,Yang Yu,Cheng Bo, et al. Research on Multi-objective Optimization for Equal Batch Splitting FJSP under Parallel and Sequence Shift Mode[J].Journal of System Simulation,2012,24(5):1046-1052.
[24]曾强,杨育,沈玲,等.基于准时交货的批量生产FJSP多目标优化[J].计算机集成制造系统,2011,17(8):1780-1789.
Zeng Qiang,Yang Yu,Shen Ling, et al. Multi-objective Optimization for Batch Production FJSP Based on Just in Time Delivery[J]. Computer Integrated Manufacturing Systems, 2011,17(8):1780-1789.
[25]曾强,杨育,王小磊,等.基于多规则设备分配及工序排序的FJSP多目标集成优化方法[J].计算机集成制造系统,2011, 17(5):980-989.
Zeng Qiang,Yang Yu,Wang Xiaolei, et al.Integrated Multi-objective Optimization Method for FJSP Based on Multiple Rule Machine Assignment and Job Sequencing[J].Computer Integrated Manufacturing Systems, 2011,17(5):980-989.
[26]曾强,杨育,王小磊,等.并行机作业车间等量分批多目标优化调度[J].计算机集成制造系统,2011,17(4):816-825.
Zeng Qiang,Yang Yu,Wang Xiaolei, et al. Multi-objective Optimization Method for Equal Lot Scheduling Problem of Job Shop with Parallel Machines[J].Computer Integrated Manufacturing Systems,2011,17(4):816-825.
[27]Lung R I,Chira C,Dumitrescu D.An Agent-based Collaborative Evolutionary Model for Multimodal Optimization[C]//Proceedings of the 2008 GECCO Conference Companion on Genetic and Evolutionary Computation.Atlanta, 2008: 1969-1976.
[28]刘爱军,杨育,邢青松,等.多目标模糊柔性车间调度中的多种群遗传算法[J].计算机集成制造系统,2011,17(9):1954-1961.
Liu Aijun,Yang Yu,Xing Qingsong, et al. Multi-population Genetic Algorithm in Multi-objective Fuzzy and Flexible Job Shop Scheduling[J]. Computer Integrated Manufacturing Systems,2011,17(9):1954-1961.
[29]薛锋,王慈光,牟峰.基于信息熵和混沌理论的遗传-蚁群协同优化算法[J].控制与决策, 2011,26(1):44-48.
Xue Feng,Wang Ciguang,Mu Feng. Genetic and Ant Colony Collaborative Optimization Algorithm Based on Information Entropy and Chaos Theory[J].Control and Decision,2011, 26(1):44-48.
[30]张敬敏,张有华,李霞.多目标柔性作业车间调度问题的混合差分算法[J].计算机工程与应用,2011,47(20):245-248.
Zhang Jingmin,Zhang Youhua,Li Xia. Hybrid Differential Evolution Algorithm for Solving Multi-objective Flexible Job-shop Scheduling Problem[J].Computer Engineering and Applications,2011,47(20):245-248.
[31]Grobler J, Engelbrecht A,Kok S, et al. Metaheuristics for the Multi-objective FJSP with Sequence-dependent Set-up Times, Auxiliary Resources and Machine Down Time[J].Annals of Operations Research,2010,180(1):165-196.
[32]白俊杰,龚毅光,王宁生,等.多目标柔性作业车间分批优化调度[J]. 计算机集成制造系统, 2010,16(2):396-403.
Bai Junjie,Gong Yiguang,Wang Ningsheng, et al. Multi-objective Flexible Job Shop Scheduling with Lot-splitting[J]. Computer Integrated Manufacturing Systems, 2010, 16(2): 396-403.
[33]Ghasem M,Mehdi M. A Pareto Approach to Multi-objective Flexible Job-shop Scheduling Problem Using Particle Swarm Optimization and Local Search[J].Int. J. Production Economics, 2011,129:14-22.
[34]Liu Hongbo,Abraham A, Wang Zuwen.A Multi-swarm approach to Multi-objective Flexible Job-shop Scheduling Problems[J]. Fundamenta Informaticae, 2009,95(4): 465-489.
[35]Mostaghim S,Teich J. Strategies for Finding Good Local Guides in Multi-objective Particle Swarm Optimization[C]//Proceedings of the 2003 IEEE Swarm Intelligence Symposium (SIS 03). Indianapolis,2003:26-33.
[36]Tripathi P K,Bandyopadhyay S,Pal Sankar K. Multi-objective Particle Swarm Optimization with Time Variant Inertia and Acceleration Coefficients[J]. Information Sciences,2007,177(22):5033-5049.
[37]Xia Weijun, Wu Zhiming.An Effective Hybrid Optimization Approach for Multi-objective Flexible Job-shop Scheduling Problems[J]. Computers & Industrial Engineering, 2005,48: 409-425.
[38]Shao Xinyu,Liu Weiqi,Liu Qiong, et al.Hybrid Discrete Particle Swarm Optimization for Multi-objective Flexible Job-shop Scheduling Problem[J].International Journal of Advanced Manufacturing Technology,2013,67( 9/12):2885-2901.
[39]张静,王万良,徐新黎,等.混合粒子群算法求解多目标柔性作业车间调度问题[J].控制理论与应用,2012,29(6):715-722.
Zhang Jing,Wang Wanliang,Xu Xinli,et al. Hybrid Particle-swarm Optimization for Multi-objective Flexible Job-shop Scheduling Problem[J]. Control Theory & Applications, 2012, 29(6):715-722.
[40]Xing Lining, Chen Yingwu, Yang Kewei.Double Layer Aco Algorithm for the Multi-objective FJSSP[J]. New Generation Computing, 2008,26:313-327.
[41]Luo Delin,Chen Haiping,Wu Shunxiang, et al. Hybrid Ant Colony Multi-objective Optimization for Flexible Job Shop Scheduling Problems[J]. Journal of Internet Technology,2010, 11(3):361-369.
[42]Li Li,Wang Keqi.Multi-objective Flexible Job Shop Schedule Based on Improved Ant Colony Algorithm[C]//ICIA: 2009 International Conference on Information and Automation.Zhuhai, 2009:1158-1162.
[43]Zhang Weicun,Zheng Pi’e,Wu Xiaodan. Ant Colony and Particle Swarm Optimization Algorithm-based Solution to Multi-objective Flexible Job-shop Scheduling Problems[J]. Journal of Computer Applications,2007,27(4):936-941.
[44]施进发,焦合军,陈涛.交货期惩罚下柔性车间调度多目标Pareto优化研究[J].机械工程学报,2012,48(12):184-192.
Shi Jinfa,Jiao Hejun,Chen Tao.Multi-objective Pareto Optimization on Flexible Job-shop Scheduling Problem about Due Punishment[J]. Journal of Mechanical Engineering, 2012, 48(12):184-192.
[45]Liouane N,Saad I,Borne P. Ant System and Fuzzy Controller for Multi-objective Optimization of the Flexible Job Shop Scheduling Problems[J].Studies in Informatics and Control, 2007,16(2):217-226.
[46]Li Junqing,Pan Quanke,Xie Shengxian.An Effective Shuffled Frog-leaping Algorithm for Multi-objective Flexible Job Shop Scheduling Problems[J].Applied Mathematics and Computation,2012,218(18): 9353-9371.
[47]Li Junqing,Pan Quanke.Chemical-reaction Optimization for Flexible Job-shop Scheduling Problems with Maintenance Activity[J]. Applied Soft Computing,2012,12:2896-2912.
[48]Li Junqing,Pan Quanke.Chemical-reaction Optimization for Solving Fuzzy Job-shop Scheduling Problem with Flexible Maintenance Activities[J].Int. J. Production Economics, 2013,145:4-17.
[49]Lu Hong.Stretching Technique-based Clonal Selection Algorithm for Flexible Job-shop Scheduling[C]//Proceedings of the 2009 International Conference on Computational Intelligence and Natural Computing.Wuhan,2009:111-114.
[50]Wang Xiaojuan,Gao Liang,Zhang Chaoyong, et al.A Multi-objective Genetic Algorithm Based on Immune and Entropy Principle for Flexible Job-shop Scheduling Problem[J]. International Journal of Advanced Manufacturing Technology, 2010, 51(5/8): 757-767.
[51]Zhang Jingmin,Zhang Youhua,Qin Peng.Immune Clonal Differential Evolution Algorithm for Multi-objective Flexible Job-shop Scheduling Problem[C]//Proceedings of the 2010 International Conference on Artificial Intelligence and Education (ICAIE 2010). Hangzhou, 2010:73-77.
[52]赵韩,高先圣,姜康,等.基于免疫遗传算法的多目标柔性作业车间调度研究[J].系统仿真学报,2008, 20(22):6163-6168.
Zhao Han,Gao Xiansheng,Jiang Kang,et al.Study of Multi-objective Flexible Job Shop Scheduling Based on Immune Genetic Algorithm[J]. Journal of System Simulation,2008, 20(22):6163-6168.
[53]余建军,孙树栋,郝京辉.免疫算法求解多目标柔性作业车间调度研究[J].计算机集成制造系统,2006,12(10):1643-1650.
Yu Jianjun,Sun Shudong,Hao Jinghui.Multi-objective Flexible Job-shop Scheduling Based on Immune Algorithm[J]. Computer Integrated Manufacturing Systems, 2006,12(10): 1643-1650.
[54]Zadeh L A.Fuzzy Sets[J].Information and Control,1965, 8(3): 338-353.
[55]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:1309-1318.
[56]Low C,Yip Y,Wu T H.Modelling and Heuristics of FMS Scheduling with Multiple Objectives[J].Computers & Operations Research,2006,33(3):674-694.
[57]Li Junqing,Pan Quanke,Xie Shengxian,et al.A Hybrid Pareto-based Tabu Search for Multi-objective Flexible Job Shop Scheduling Problem with E/T Penalty[J].Advences in Swarm Intelligence, Proceedings:Lecture Notes in Computer Science, 2010,6145:620-627.
[58]李俊青,潘全科,王玉亭.多目标柔性车间调度的Pareto混合禁忌搜索算法[J].计算机集成制造系统, 2010,16(7):1419-1426.
Li Junqing,Pan Quanke,Wang Yuting. Hybrid Pareto-based Tabu Search Algorithm for Solving the Multi-objective Flexible Job Shop Scheduling Problem[J]. Computer Integrated Manufacturing Systems, 2010,16(7): 1419-1426.
[59]Li Junqing,Pan Quanke,Liang YunChia.An Effective Hybrid Tabu Search Algorithm for Multi-objective Flexible Job-shop Scheduling Problems[J].Computers & Industrial Engineering, 2010, 59:647-662.
[60]Gao K Z,Suganthan P N,Chua T J.Pareto-based Discrete Harmony Search Algorithm for Flexible Job Shop Scheduling[C]//2012 12th International Conference on Intelligence Systems Design and Applications(ISDA).Kochi,2012: 953-956.
[61]Kirkpatrick S C,Gelatt C D Jr,Vecchi M P.Optimization by Simulated Annealing[J].Science,1983,220(4598):671-680.
[62]Liu H B,Abraham A,Choi O,et al. Variable Neighborhood Particle Swarm Optimization for Multi-objective Flexible Jobshop Scheduling Problems[J]. Lect. Notes Comput. Sci., 2006,4247:197-204.
[63]Ho N B,Tay J C.Solving Multiple-objective Flexible Job Shop Problems By Evolution and Local Search[J].IEEE Transations on Systems Man and Cybernetics Part C-Applications and Reviews,2008,38(5): 674-685.
[64]Penev K, Littlefair G. Free Search-a Comparative Analysis[J]. Information Sciences,2005,172(1/2):173-193.