基于混沌量子算法和MAGTD的多目标FJSP求解策略

doi:10.12005/orms.2017.0003

运筹与管理 ›› 2017, Vol. 26 ›› Issue (1): 18-24.DOI: 10.12005/orms.2017.0003

基于混沌量子算法和MAGTD的多目标FJSP求解策略

宁涛^1,2, 王旭坪¹, 焦璇¹

1.大连理工大学系统工程研究所,辽宁大连116023;
2.大连交通大学软件学院,辽宁大连116045

收稿日期:2014-11-03 出版日期:2017-01-20
作者简介:宁涛(1979- ),男,山东蓬莱人,副教授,硕士生导师,研究方向:计算机集成制造、车间调度;王旭坪(1962- ),男,辽宁锦州人,教授,博士生导师,研究方向:车间调度管理、突发事件与应急管理;焦璇(1986- ),女,吉林长春人,讲师,研究方向:计算机集成制造、车间调度。
基金资助:
国家自然科学基金重点资助项目(71531002);国家自然科学基金项目(71471025);辽宁省社科规划基金一般项目(L16BGL008);辽宁省博士启动基金项目(L201601244)

Study on Multi-objective Flexible Job Shop Scheduling Basedon Chaos Quantum Optimization and MAGTD

NING Tao^1,2, WANG Xu-ping¹, JIAO Xuan¹

1.Institute of systems engineering, Dalian University of Technology, Dalian 116023, China;
2.Institute of Software, Dalian Jiaotong University, Dalian 116045, China

Received:2014-11-03 Online:2017-01-20

摘要/Abstract

摘要： 针对多目标环境下柔性作业车间的调度问题,以最小化最大完工时间和惩罚值为目标,建立调度问题的数学模型,提出了基于混沌理论的量子粒子群算法。针对实际生产交货期不确定的特点,在量子粒子群算法基础上,提出引入混沌机制建立初始群的方法;利用混沌机制的遍历性,提出混沌局部优化策略;为获取最优调度方案提出了引入多指标加权灰靶选择策略。通过典型基准算例和对比测试,验证了所提出的算法获得最满意调度方案的可行性和求解多目标柔性作业车间调度问题的有效性。

关键词: 柔性作业车间调度, 量子粒子群算法, 混沌机制, 多指标加权灰靶策略

Abstract: In order to solve the flexible job-shop scheduling(FJSP problem in the multi objective environment, the simulation model is established aiming at minimizing the makespan and penalty, and an improved chaos quantum particle swarm optimization(IQPSO)algorithm is proposed. On the basis of the characteristics of the production delivery time in actual production, we introduce the method of initializing population with chaos mechanism. To update the quantum individual, we propose a novel method to improve the quantum rotating angle. The chaos local optimization strategy using the ergodicity of chaos mechanism is proposed. The multi-attribute decision model based on weighted grey target strategy is introduced to select the most satisfied schedule scheme. The feasibility of the proposed algorithm and the validity of solving the multi-objective FJSP are verified through the classical example and a mechanical mould job-shop scheduling.

Key words: flexible job-shop scheduling, quantum particle swarm optimization, chaos mechanism, multi-attribute grey target decision

中图分类号:

TH186
TP18

宁涛, 王旭坪, 焦璇. 基于混沌量子算法和MAGTD的多目标FJSP求解策略[J]. 运筹与管理, 2017, 26(1): 18-24.

NING Tao, WANG Xu-ping, JIAO Xuan. Study on Multi-objective Flexible Job Shop Scheduling Basedon Chaos Quantum Optimization and MAGTD[J]. Operations Research and Management Science, 2017, 26(1): 18-24.

参考文献

[1]Pinedo M. Scheduling theory, algorithms, and system,2nd,prentice Hall[M]. Upper Saddle River, New Jersey, 2002.
[2]梁旭,刘鹏飞,黄明.一种混合生产形态下的多订单调度遗传算法[J].计算机集成制造系统,2012,18(10):2217-2223.
[3]Bucker P, Schlie R. Job-shop scheduling with multi-purpose machines[J]. Computing, 1990, 45(4): 369-375.
[4]刘晓冰,焦璇,宁涛等.基于双链量子遗传算法的柔性作业车间调度[J].计算机集成制造系统,2015, 21(2):495-502.
[5]Deng Guanlong, Gu X S. A hybrid discrete differential evolution algorithm for the no-idle permutation flow shop scheduling problem with makespan criterion[J]. Computers & Operations Research, 2012,39(9): 2152-2160.
[6]Mokhtarl H, Abadi I N K, Cheraghalikhania. A multi-objective flow shop scheduling with resource-de-pendent processing times: trade-off between makespan and cost of resources[J]. International Journal of Production Research, 2011, 49(19): 5851-5875.
[7]赵诗奎,方水量,顾新建.基于极限调度完工时间最小化的机器选择及FJSP求解[J].计算机集成制造系统,2014,20(4):854-865.
[8]马雪丽,黄学文,曹德弼.集成化车间作业计划动态关键路径编制算法[J].计算机集成制造系统,2013,19 (9):2178-2186.
[9]宁涛.混合量子算法在车辆路径问题中应用的研究[D].大连:大连海事大学,2013.
[10]彭建刚,刘明周,张铭鑫,等.基于改进非支配排序的云模型进化多目标柔性作业车间调度[J].机械工程学报,2014,50(12):198-205.
[11]于晓义,孙树栋,褚崴.基于并行协同进化遗传算法的多协作车间计划调度[J].计算机集成制造系统,2008,14(5):991-1000.
[12]刘爱军,杨育,邢青松,等.多目标模糊柔性车间调度中的多种群遗传算法[J].计算机集成制造系统,2011,17(9):1954-1961.
[13]张静,王万良,徐新黎,等.基于改进粒子群算法求解柔性作业车间批量调度问题[J].控制与决策,2012,27(4):35-40.
[14]姜洋,孙伟,丁秋雷,等.考虑行为主体的单机调度干扰管理模型[J].机械工程学报,2013,49(14):191-198.
[15]汪双喜,张超勇,刘琼,等.不同再调度周期下的柔性作业车间动态调度研究[J].计算机集成制造系统,2014,7(14):1-14.
[16]施进发,焦合军,陈涛.交货期惩罚下柔性车间调度多目标Pareto优化研究[J].机械工程学报,2012,48(12):188-196.
[17]党耀国,刘思峰,王正新,等.灰色预测与决策模型研究[M].北京:科学出版社,2009.
[18]Brandimarte P. Routing and scheduling in a flexible job shop by tuba search[J]. Ann Oper Res,1993, 41(3): 157-183.
[19]Zhang G H, Shao X Y, Li P G, Gao L. An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem[J]. Comp Ind Eng, 2009, 53(4): 1309-1318.
[20]Bagheri A, Zandith M, Mahdavi I, Yanzdanni M. An artificial immune algorithm for the flexible job-shop scheduling problem[J]. Fut Gen Comp System, 2010, 26(4): 533-541.
[21]王云,冯毅雄,谭建荣,等.柔性作业车间分批调度多目标优化方法[J].浙江大学学报,2011,45(4):719-726.
[22]彭建刚,刘明周,张明鑫等.基于改进非支配排序的云模型进化多目标柔性作业车间调度[J].机械工程学报,2014,50(12):198-205.

基于混沌量子算法和MAGTD的多目标FJSP求解策略

Study on Multi-objective Flexible Job Shop Scheduling Basedon Chaos Quantum Optimization and MAGTD

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

[1]	马龙, 卢才武, 顾清华. 金属矿山企业生产计划优化方法[J]. 运筹与管理, 2020, 29(9): 34-42.
[2]	田旻,张光军,刘人境. 粒子群遗传混合算法求解考虑传输时间的FJSP[J]. 运筹与管理, 2019, 28(4): 78-88.
[3]	张国辉. DBR理论求解柔性作业车间调度问题[J]. 运筹与管理, 2016, 25(1): 53-58.