面向复杂工程项目型产品作业车间调度问题

黄伟; 阎春平; 王星荣; 许建平

doi:10.13433/j.cnki.1003-8728.20190126

面向复杂工程项目型产品作业车间调度问题

doi: 10.13433/j.cnki.1003-8728.20190126

重庆大学机械工程学院, 重庆 400030

基金项目:

重庆市人工智能技术创新重大主题专项项目 cstc2017rgzn-zdyfX0033

详细信息

作者简介:
黄伟(1993-), 硕士研究生, 研究方向为智能制造系统与装备, huangwei_smile@126.com

通讯作者:
阎春平, 教授, 博士生导师, ycp@cqu.edu.cn

中图分类号: TH164
计量
- 文章访问数: 442
- HTML全文浏览量: 190
- PDF下载量: 23
- 被引次数: 0
出版历程
- 收稿日期: 2019-02-19
- 刊出日期: 2020-03-05

Job Shop Scheduling Problem for Complex Engineering Project Products

College of Mechanical Engineering, Chongqing University, Chongqing 400030, China

摘要

摘要: 针对复杂工程项目型产品作业车间调度问题（CEPP-JSP），在考虑产品生产过程具有成套性、并行性、分散性和高柔性等生产特点的基础上，构建了面向CEPP-JSP的基本生产任务分配和作业中心生产调度的多目标优化模型，提出了改进的非支配排序遗传算法（NSGA-Ⅱ）对优化模型进行求解，从而得到了CEPP-JSP的Pareto综合最优解。最后，以某水轮机公司产品的作业车间调度为例，验证了提出模型和算法的可行性和有效性。
- 复杂工程项目型产品 /
- 车间调度 /
- 非支配排序遗传算法 /
- Pareto最优解
Abstract: Aiming at the complex engineering project products job shop scheduling problem (CEPP-JSP), by considering the characteristics of complete production process, parallelism, decentralization and high flexibility, a multi-objective optimization model for CEPP-JSP basic production task allocation and job center production scheduling is constructed. The improved non-dominated sorting genetic algorithm (NSGA-Ⅱ) is proposed to solve the optimization model and the comprehensive optimal solution of CEPP-JSP is obtained. Finally, the feasibility and validity of the model and algorithm are verified by using an example of workshop scheduling in a hydraulic turbine.
- CEPP /
- scheduling /
- non-dominated sorting genetic algorithm (NSGA-Ⅱ) /
- Pareto optimal solution

HTML全文

图 1 面向复杂工程项目型产品生产过程资源层次分解

下载: 全尺寸图片幻灯片

图 2 NSGA-Ⅱ寻优过程

下载: 全尺寸图片幻灯片

图 3 双层编码方案

下载: 全尺寸图片幻灯片

图 4 改进的NSGA-Ⅱ算法流程

下载: 全尺寸图片幻灯片

图 5 项目执行甘特图

下载: 全尺寸图片幻灯片

图 6 项目分配的Pareto最优解

下载: 全尺寸图片幻灯片

图 7 工件加工顺序甘特图

下载: 全尺寸图片幻灯片

图 8 作业中心调度的Pareto最优解

下载: 全尺寸图片幻灯片

表 1 8×8基准案例测试结果 h

目标	SPT	GA	AL+CGA	PSO+SA	本文
完工时间	19	16	16	15	14
总负荷	91	77	75	75	75
最大负荷	16	14	14	12	12

下载: 导出CSV

表 2 项目处理流程及时间

项目	处理过程	作业中心	作业时间/×10² h
1	1	1	1
	2	[2,3]	[5.5, 6.0]
	3	[2,3]	[6.0, 6.0]
2	1	[2,3]	[7.5, 8.0]
	2	1	5
	3	5	10
3	1	[2,3]	[6.0, 5.5]
	2	4	6.0
	3	5	10

下载: 导出CSV

表 3 项目1流程2作业中心2加工工件及工序

工件类型	工序号	设备号	加工时间/h
1	1	1	12
	2	[2,3,4]	[160,160,165]
	3	[5,6]	[115,120]
	4	[2,4]	[95,90]
	5	[2,3,4]	[145,140,140]
2	1	1	15
	2	[2,3,4]	[55,50,50]
	3	[7,8]	[110,115]
	4	[7,8]	[60,65]
	5	[5,6]	[160,165]
3	1	1	10
	2	[5,6]	[120,115]
	3	[2,3,4]	[135,135,140]
	4	[2,3,4]	[20,18,20]
	5	[2,3,4]	[28,25,25]
4	1	[2,4]	[120,115]
	2	[5,6]	[30,35]
	3	[2,3,4]	[20,20,20]
	4	[7,8]	[65,60]
	5	[2,3,4]	[130,130,135]
5	1	[5,6]	[42,45]
	2	[2,3,4]	[55,50,55]
	3	[2,3,4]	[55,55,52]
	4	[7,8]	[50,50]
	5	[2,3,4]	[56,56,56]

下载: 导出CSV

表 4 目标函数值迭代寻优过程

迭代次数	Q_max/h	C_end/h	Q/h
1	395	570	231
2	383	565	233.125
3	395	547	233.5
4	395	540	231
5	395	540	233.5
6	395	522	233.5
7	395	522	233.5
8	395	522	233.5
9	395	522	233.5
10	395	522	233.5
11	395	522	233.5
⋮	⋮	⋮	⋮
50	395	522	233.5
⋮	⋮	⋮	⋮
109	395	522	233.5
110	395	522	233.5
120	395	522	233.5

下载: 导出CSV

表 5 结果比对分析

类别	Q_max/h	C_end/h	Q/h	交货期
本文	395	522	233.5	满足
经验	500	550	215	延迟或提前很久

下载: 导出CSV

参考文献(21)

[1]	杨超, 陆志强.项目拆分和多项目调度集成决策模型与算法[J].计算机集成制造系统, 2018, 24(3):550-557 http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt201803002 Yang C, Lu Z Q. Integrated decision making model and algorithm of project splitting and multi-project scheduling[J]. Computer Integrated Manufacturing Systems, 2018, 24(3):550-557(in Chinese) http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt201803002
[2]	程序, 吴澄.一种复杂项目调度问题的混合智能算法[J].计算机集成制造系统, 2006, 12(4):585-589 doi: 10.3969/j.issn.1006-5911.2006.04.019 Cheng X, Wu C. Hybrid algorithm for complex project scheduling[J]. Computer Integrated Manufacturing Systems, 2006, 12(4):585-589(in Chinese) doi: 10.3969/j.issn.1006-5911.2006.04.019
[3]	施国强, 李伯虎, 柴旭东.不确定条件下复杂产品开发项目调度模型研究[J].计算机集成制造系统, 2007, 13(10):1909-1913, 1920 doi: 10.3969/j.issn.1006-5911.2007.10.006 Shi G Q, Li B H, Chai X D. Modeling of uncertain project scheduling for complex product development[J]. Computer Integrated Manufacturing Systems, 2007, 13(10):1909-1913, 1920(in Chinese) doi: 10.3969/j.issn.1006-5911.2007.10.006
[4]	Gholizadeh-Tayyar S, Dupont L, Lamothe J, et al. Modeling a generalized resource constrained multi project scheduling problem integrated with a forward-backward supply chain planning[J]. IFAC-PapersOnLine, 2016, 49(12):1283-1288 doi: 10.1016/j.ifacol.2016.07.700
[5]	万峰, 刘检华, 宁汝新, 等.面向复杂产品装配过程的可视化生产调度技术[J].计算机集成制造系统, 2013, 19(4):755-765 http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt201304011 Wan F, Liu J H, Ning R X, et al. Visual production scheduling technology for the complex product assembly process[J]. Computer Integrated Manufacturing Systems, 2013, 19(4):755-765(in Chinese) http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt201304011
[6]	吴锋, 刘文煌.手工装配作业下的一种调度策略与控制方法[J].清华大学学报, 1998, 38(2):58-61 doi: 10.3321/j.issn:1000-0054.1998.02.016 Wu F, Liu W H. Scheduling strategy and control methods for the manual assembly process[J]. Journal of Tsinghua University, 1998, 38(2): 58-61(in Chinese) doi: 10.3321/j.issn:1000-0054.1998.02.016
[7]	刘检华, 白书清, 段华, 等.面向手工装配的计算机辅助装配过程控制方法[J].计算机集成制造系统, 2009, 15(12):2391-2398 http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt200912015 Liu J H, Bai S Q, Duan H, et al. Computer aided assembly process control method for manual assembly[J]. Computer Integrated Manufacturing Systems, 2009, 15(12):2391-2398(in Chinese) http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt200912015
[8]	王雷, 蔡劲草, 石鑫.基于改进遗传算法的多目标柔性作业车间节能调度问题[J].南京理工大学学报, 2017, 41(4):494-502 http://d.old.wanfangdata.com.cn/Periodical/njlgdxxb201704015 Wang L, Cai J C, Shi X. Multi-objective flexible job shop energy-saving scheduling problem based on improved genetic algorithm[J]. Journal of Nanjing University of Science and Technology, 2017, 41(4):494-502(in Chinese) http://d.old.wanfangdata.com.cn/Periodical/njlgdxxb201704015
[9]	Xu Y, Wang L, Wang S Y, et al. An effective teaching- learning-based optimization algorithm for the flexible job-shop scheduling problem with fuzzy processing time[J]. Neurocomputing, 2015, 148:260-268 doi: 10.1016/j.neucom.2013.10.042
[10]	Chen M, Li J L. Genetic algorithm combined with gradient information for flexible job-shop scheduling problem with different varieties and small batches[C]//Proceedings of the 3rd International Conference on Mechatronics and Mechanical Engineering. MATEC Web of Conferences. Shanghai, China, 2017: 10001
[11]	张超勇, 董星, 王晓娟, 等.基于改进非支配排序遗传算法的多目标柔性作业车间调度[J].机械工程学报, 2010, 46(11):156-164 http://d.old.wanfangdata.com.cn/Periodical/jxgcxb201011024 Zhang C Y, Dong X, Wang X J, et al. Improved NSGA-Ⅱ for the multi-objective flexible job-shop scheduling problem[J]. Journal of Mechanical Engineering, 2010, 46(11):156-164(in Chinese) http://d.old.wanfangdata.com.cn/Periodical/jxgcxb201011024
[12]	魏巍, 谭建荣, 冯毅雄, 等.柔性工作车间调度问题的多目标优化方法研究[J].计算机集成制造系统, 2009, 15(8):1592-1598 http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt200908020 Wei W, Tan J R, Feng Y X, et al. Multi-objective optimization method research on flexible job shop scheduling problem[J]. Computer Integrated Manufacturing Systems, 2009, 15(8):1592-1598(in Chinese) http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt200908020
[13]	吴秀丽, 孙树栋, 余建军, 等.多目标柔性作业车间调度优化研究[J].计算机集成制造系统, 2006, 12(5):731-736 doi: 10.3969/j.issn.1006-5911.2006.05.016 Wu X l, Sun S D, Yu J J, et al. Research on multi-objective optimization for flexible job shop scheduling[J]. Computer Integrated Manufacturing Systems, 2006, 12(5):731-736(in Chinese) doi: 10.3969/j.issn.1006-5911.2006.05.016
[14]	薄洪光.基于数据和扰动辨识的生产调度优化理论[M].北京:科学出版社, 2013 Bo H G. Production scheduling optimization theory based on data and disturbance identification[M]. Beijing: Science Press, 2013(in Chinese)
[15]	Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197 doi: 10.1109/4235.996017
[16]	Srinivas N, Deb K. Multi-objective function optimization using non-dominated sorting genetic algorithms[J]. IEEE Transactions on Evolutionary Computation, 1995, 2(3):221-248 http://d.old.wanfangdata.com.cn/Periodical/xtgcydzjs201704013
[17]	陈鸿海, 蒋增强, 左乐, 等.基于近亲变异NSGA-Ⅱ算法的多目标柔性作业车间调度[J].农业机械学报, 2015, 46(4):344-350 http://d.old.wanfangdata.com.cn/Periodical/nyjxxb201504051 Chen H H, Jiang Z Q, Zuo L, et al. Multi-objective flexible job-shop scheduling problem based on NSGA-Ⅱ with close relative variation[J]. Transactions of the Chinese Society for Agricultural Machinery, 2015, 46(4):344-350(in Chinese) http://d.old.wanfangdata.com.cn/Periodical/nyjxxb201504051
[18]	肖海宁, 楼佩煌, 严伟国, 等.柔性作业车间中机床与自动导引车在线调度方法[J].农业机械学报, 2013, 44(4):280-286 http://d.old.wanfangdata.com.cn/Periodical/nyjxxb201304048 Xiao H N, Lou P H, Yan W G, et al. On-line scheduling method for simultaneous scheduling of machines and automated guided vehicles in flexible job shop[J]. Transactions of the Chinese Society for Agricultural Machinery, 2013, 44(4):280-286(in Chinese) http://d.old.wanfangdata.com.cn/Periodical/nyjxxb201304048
[19]	Kacem I, Hammadi S, Borne P. Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 2002, 32(1):1-13 doi: 10.1109/TSMCC.2002.1009117
[20]	刘爱军, 杨育, 程文明, 等.复杂制造环境下的改进非支配排序遗传算法[J].计算机集成制造系统, 2012, 18(11):2446-2458 http://www.cnki.com.cn/Article/CJFDTotal-JSJJ201211014.htm Liu A J, Yang Y, Cheng W M, et al. Improved NSGA for complex manufacturing environment[J]. Computer Integrated Manufacturing Systems, 2012, 18(11):2446-2458(in Chinese) http://www.cnki.com.cn/Article/CJFDTotal-JSJJ201211014.htm
[21]	Xia W J, Wu Z M. An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems[J]. Computers & Industrial Engineering, 2005, 48(2):409-425 doi: 10.1016-j.cie.2005.01.018/