基于Pareto优化的离散自由搜索算法求解多目标柔性作业车间调度问题

摘要/Abstract

摘要：

针对多目标柔性作业车间调度问题搜索空间的离散性和求解算法的收敛性，提出一种基于Pareto优化的离散自由搜索算法来求解多目标柔性作业车间调度问题。在建立基于Markov链数学模型的基础上，证明了算法以概率1收敛；引入首达最优解期望时间来分析算法收敛速度，并分析了算法时间复杂度。采用基于工序排序和机器分配的个体表达方式，在多目标柔性作业车间离散域，利用自由搜索算法在邻域小步幅精确搜索和在全局空间大步幅勘测进行寻优；通过自由搜索算法自适应赋予个体各异辨别能力和Pareto优化概念来比较个体优劣性，不仅保留优化个体，而且使个体寻优方向沿多目标柔性作业车间调度问题Pareto前沿逼近。通过对搜索过程中产生的伪调度方案进行可行性判定，以确保调度方案可行。采用10×10FJSP和8×8FJSP问题的实例进行寻优测试，验证了所提算法的可行性和有效性。

关键词: 多目标柔性作业车间调度问题, 自由搜索, Markov链, Pareto优化

Abstract:

A discrete free search algorithm based on Pareto-optimality was proposed for solving multi-objective flexible job-shop scheduling problem. The convergence with probability one of the proposed algorithm was demonstrated based on Markov chain and the convergence rate was analyzed based on expected first hitting time. The computational complexity of algorithm was also analyzed. Individuals of algorithm were represented based on job operation and machine assignment, and updated either with small precise steps for local search or with large steps for global exploration in discrete domain. The individuals were compared through adaptive sensibility and Pareto-optimality concept. The proposed algorithm was to retain the optimization individuals, and to guide individuals taking exploration walks towards Pareto-optimality front of multi-objective flexible job-shop scheduling problem. The feasibility and effectiveness of the proposed algorithm were verified by both 10×10FJSP and 8×8FJSP instance.

Key words: multi-objective flexible job-shop scheduling problem, free search, Markov chain, Pareto-optimality

中图分类号:

TH186

彭建刚, 刘明周, 张玺, 张铭鑫, 葛茂根. 基于Pareto优化的离散自由搜索算法求解多目标柔性作业车间调度问题[J]. 中国机械工程, 2015, 26(5): 620-626.

Peng Jiangang, Liu Mingzhou, Zhang Xi, Zhang Mingxin, Ge Maogen. Discrete Free Search Based on Pareto-optimality for Multi-objective Flexible Job-shop Scheduling Problem[J]. China Mechanical Engineering, 2015, 26(5): 620-626.

参考文献

[1]Blazewicz J,Finke G,Haopt G.New Trends in Machine Scheduling[J].European Journal of Operational Research,1988, 37: 303-317.
[2]鞠全勇,朱剑英.多目标批量生产柔性作业车间优化调度[J].机械工程学报,2007,43(8):148-154.
Ju Quanyong,Zhu Jianying.Multi-objective Flexible Job Shop Scheduling of Batch Production[J].Chinese Journal of Mechanical, 2007,43(8):148-154.
[3]张超勇,董星,王晓娟,等.基于改进非支配排序遗传算法的多目标柔性作业车间调度[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.
[4]王云,谭建荣,冯毅雄,等.基于SPEA的多目标柔性作业车间调度方法[J].中国机械工程,2010, 21(10):1167-1172.
Wang Yun,Tan Jianrong,Feng Yixiong, et al. Multi-objective Flexible Job-shop Scheduling Based on Strength Pareto Evolutionary Algorithm[J]. China Mechanical Engineering, 2010, 21(10):1167-1172.
[5]Kacem I, Hammadi S, Borne P.Pareto-optimality Approach for Flexible Job-shop Scheduling Problems: Hybridization of Evolutionary Algorithms and Fuzzy Logic[J]. Mathematics and Computers in Simulation, 2002,60: 245– 276.
[6]张静,王万良,徐新黎,等.混合粒子群算法求解多目标柔性作业车间调度问题[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.
[7]Li Junqing, Pan Quanke, Gao Kaizhou. Pareto-based Discrete Artificial Bee Colony Algorithm for Multi-objective Flexible Job Shop Scheduling Problems[J]. International Journal of Advanced Manufacturing Technology, 2011, 55: 1159-1169.
[8]Penev K, Littlefair G. Free Search-a Comparative Analysis[J]. Information Sciences,2005,172(1/2):173-193.
[9]潘全科,王文宏,朱剑英,等.基于粒子群优化和变邻域搜索的混合调度算法[J].计算机集成制造系统, 2007,13(2): 323- 328.
Pan Quanke, Wang Wenhong, Zhu Jianying, et al.Hybrid Heuristics Based on Particle Swarm Optimization and Variable Neighborhood Search for Job Shop Scheduling[J].Computer Integrated Manufacturing Systems, 2007,13(2):323-328.
[10]Anghinolfi D,Paolucci M.A New Discrete Particle Swarm Optimization Approach for the Single-machine Total Weighted Tardiness Scheduling Problem with Sequence- dependent Setup Times[J]. European Journal of Operational Research, 2009, 193:73-85.
[11]公茂果,焦李成,杨咚咚,等.进化多目标优化算法研究[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.
[12]张文修,梁怡.遗传算法的数学基础[M].西安:西安交通大学出版社,2000.
[13]Rudolph G, Agapie A.Convergence Properties of Some Multi-objective Evolutionary Algorithms[C]//Proceedings of on IEEE Conference Evolutionary Computation.Piscataway, New Jersey, 2000:1010-1016.
[14]胡迪鹤.随机环境中的马尔可夫过程[M].北京:高等教育出版社,2011.
[15]黄翰,郝志峰,吴春国,等.蚁群算法的收敛速度分析[J].计算机学报,2007,30(8): 1344-1353.
Huang Han,Hao Zhifeng,Wu Chunguo,et al. The Convergence Speed of Ant Colony Optimization[J]. Chinese Journal of Computers, 2007,30(8):1344-1353.
[16]Yu Yang,Zhou Zhihua.A New Approach to Estimating the Expected First Hitting Time of Evolutionary Algorithms[J]. Artificial Intelligence,2008,172:1809-1832.
[17]Deb K, Pratap A, Agarwal S, et al. A Fast and Elitist Multi- objective Genetic Algorithms:NSGA-Ⅱ[J].IEEE Trans.on Evolutionary Computation,2002,6(2):182-197.
[18]Kacem I,Hammadi S,Borne P.Approach by Localization and Multi-objective Evolutionary Optimization for Flexible Job-shop Scheduling Problems[J].IEEE Transaction Systems, Man,and Cybernetics-Part C,Applications and Reviews, 2002, 32(1):1-13.
[19]张国辉,高亮,李培根,等.改进遗传算法求解柔性作业车间调度问题[J].机械工程学报,2009,45(7):145-151.
Zhang Guohui,Gao Liang,Li Peigen, et al. Improved Genetic Algorithm for the Flexible Job-shop Scheduling Problem[J]. Journal of Mechanical Engineering, 2009, 45(7): 145-151.
[20]李俊青,潘全科,王玉亭.多目标柔性车间调度的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.
[21]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.