基于改进型NSGAII的织造车间多目标大规模动态调度

doi:10.13475/j.fzxb.20210502710

纺织学报 ›› 2022, Vol. 43 ›› Issue (04): 74-83.doi: 10.13475/j.fzxb.20210502710

基于改进型NSGAII的织造车间多目标大规模动态调度

沈春娅¹^,², 雷钧杰¹^,², 汝欣¹^,², 彭来湖¹^,², 胡旭东¹^,²()

1.浙江理工大学机械与自动控制学院, 浙江杭州 310018
2.浙江理工大学浙江省现代纺织装备技术重点实验室, 浙江杭州 310018

收稿日期:2021-05-12 修回日期:2021-11-26 出版日期:2022-04-15 发布日期:2022-04-20
通讯作者: 胡旭东
作者简介:沈春娅(1993—),女,博士生。主要研究方向为智能纺织装备技术。
基金资助:
浙江省公益技术研究计划项目(LGG21E050024);浙江省重点研发计划项目(2019C01038);浙江省博士后科研项目特别资助项目(ZJ2020004);浙江理工大学科研启动基金项目(18022224-Y)

Multi-objective large-scale dynamic scheduling for weaving workshops based on improved NSGAII

SHEN Chunya¹^,², LEI Junjie¹^,², RU Xin¹^,², PENG Laihu¹^,², HU Xudong¹^,²()

1. School of Mechanical Engineering and Automation, Zhejiang Sci-Tech University, Hangzhou, Zhejiang 310018, China
2. Key Laboratory of Modern Textile Machinery & Technology of Zhejiang Province,Zhejiang Sci-Tech University, Hangzhou, Zhejiang 310018, China

Received:2021-05-12 Revised:2021-11-26 Published:2022-04-15 Online:2022-04-20
Contact: HU Xudong

摘要/Abstract

摘要：

织造车间调度规模普遍在300台织机、1 000个织轴以上,遗传算法搜索极易陷入局部最优,针对传统动态调度机制在织造插单、打样等复杂生产场景中适应性不强的问题,提出一种改进NSGAII算法。从织造多织机、多织轴、多产品的大规模调度出发,基于织造和穿经之间独特的逆工序调度关系,构建以逾期损失、最大完工时间和织机空闲时间均最小为目标的织造多目标大规模调度模型。通过改进启发规则的编码方式缩小解空间,设计了一种局部和全局关联优化的贪婪进化算子,避免算法寻优陷入局部最优;并提出基于支配关系评价的动态调度机制,优化算法在生产中动态响应机制差,抗扰动性不高的不足。验证实验证明,改进NSGAII算法在织机调度规模为500台、4 000个织轴时,调度能力仍优于其他算法。

关键词: 织造车间智能调度, NSGAII, 多目标优化, 大规模调度, 动态调度, 启发规则

Abstract:

As the number of looms exceeds 300 with more than 1 000 weaver's beams in the weaving workshop, the genetic algorithm is easy to fall into local optimal solution when solving such large-scale scheduling problems, and the traditional dynamic scheduling mechanism is not adaptable enough for complex production scenarios such as order insertion and proofing. An improved NSGAII algorithm was proposed in the paper. Considering the facts that the scheduling of a large-scale weaving workshop involves large numbers of looms, weaver's beams and products, and the unique inverse process scheduling relationship between weaving and drawing-in, a multi-objective large-scale scheduling model for weaving was constructed, aiming at the minimization of overdue loss, makespan, and idle time of loom. The encoding of heuristic rules was improved to reduce the solution space, and a greedy evolution operator was used in local and global correlation optimization to avoid falling into local optimization. A dynamic scheduling mechanism based on dominance relationship evaluation was adopted to improve the poor dynamic response mechanism and low ability against disturbance during production. Experiments show that the scheduling ability of the algorithm remains superior over other algorithms in a situation where there are 500 looms with 4 000 weaver's beams in a weaving workshop.

Key words: intelligent scheduling of weaving workshop, NSGAII, multi-objective optimization, large-scale scheduling, dynamic scheduling, heuristic rule

中图分类号:

TS111.8

沈春娅, 雷钧杰, 汝欣, 彭来湖, 胡旭东. 基于改进型NSGAII的织造车间多目标大规模动态调度[J]. 纺织学报, 2022, 43(04): 74-83.

SHEN Chunya, LEI Junjie, RU Xin, PENG Laihu, HU Xudong. Multi-objective large-scale dynamic scheduling for weaving workshops based on improved NSGAII[J]. Journal of Textile Research, 2022, 43(04): 74-83.

图/表 8

图1

图2

图3

图4

表1

表2

表3

图5

参考文献 20

[1]	工业和信息化部. 纺织工业发展规划(2016-2020年)[N]. 纺织服装周刊, 2016(38): 10-15.
	Ministry of Industry and Information Technology. Development plan for textile industry(2016-2020)[N]. Textile & Apparel Weekly, 2016(38): 10-15.
[2]	宋代立, 张洁. 蚁群算法求解混合流水车间分批调度问题[J]. 计算机集成制造系统, 2013, 19(7): 1640-1647.
	SONG Daili, ZHANG Jie. Batch scheduling problem of hybrid flow shop based on ant colony algorithm[J]. Computer Integrated Manufacturing Systems, 2013, 19(7): 1640-1647.
[3]	郑小虎, 鲍劲松, 马清文, 等. 基于模拟退火遗传算法的纺纱车间调度系统[J]. 纺织学报, 2020, 41(6): 36-41.
	ZHENG Xiaohu, BAO Jinsong, MA Qingwen, et al. Spinning workshop collaborative scheduling method based onsimulated annealing genetic algorithm[J]. Journal of Textile Research, 2020, 41(6): 36-41.
[4]	韩忠华, 张权, 史海波, 等. 带准备时间的柔性流水车间多序列有限缓冲区排产优化问题[J]. 机械工程学报, 2019, 55(24): 236-252.
	HAN Zhonghua, ZHANG Quan, SHI Haibo, et al. Multi-queue limited buffer scheduling problems in flexible flow shop with setup times[J]. Journal of Mechanical Engineering, 2019, 55(24): 236-252. doi: 10.3901/JME.2019.24.236
[5]	宋存利. 求解混合流水车间调度的改进贪婪遗传算法[J]. 系统工程与电子技术, 2019, 41(5):1079-1086.
	SONG Cunli. Improved greedy genetic algorithm for hybrid flow-shop scheduling problem[J]. Systems Engineering and Electronics, 2019, 41(5): 1079-1086.
[6]	LI J, SANG H, HAN Y, et al. Efficient multi-objective optimization algorithm for hybrid flow shop scheduling problems with setup energy consumptions[J]. Journal of Cleaner Production, 2018, 181:584-598. doi: 10.1016/j.jclepro.2018.02.004
[7]	周炳海, 顾佳颖. 考虑多资源约束的非等效并行机节能调度算法[J]. 东北大学学报(自然科学版), 2019, 40(3): 403-408.
	ZHOU Binghai, GU Jiaying. An energy-saving scheduling algorithm for non-identical parallel machines with multi-resource contraints[J]. Journal of Northeastern University( Natural Science), 2019, 40(3): 403-408.
[8]	卢颖涛. 针织企业染整车间调度方法研究[D]. 上海:东华大学, 2019:34-46.
	LU Yingtao. Research on dyeing production scheduling in dyeing and finishing workshop of knitting com-pany[D]. Shanghai: Donghua University, 2019:34-46.
[9]	刘爱军, 杨育, 邢青松, 等. 柔性作业车间多目标动态调度[J]. 计算机集成制造系统, 2011, 17(12): 2629-2637.
	LIU Aijun, YANG Yu, XING Qingsong, et al. Dynamic scheduling on mulit-objective flexible job shop[J]. Computer Integrated Manufacturing Systems, 2011, 17(12): 2629-2637.
[10]	黎冰, 王静, 顾幸生. 基于改进蚁群算法的多目标Job-shop 动态调度[J]. 华东理工大学学报(自然科学版), 2015, 41(4): 523-528.
	LI Bing, WANG Jing, GU Xingsheng. Multi-objective Job-shop dynamic scheduling based on improved ant colony algorithm[J]. Journal of East China University of Science and Technology(Natural Science Edition), 2015, 41(4): 523-528.
[11]	陈革, 杨建成. 纺织机械概论[M]. 北京: 中国纺织出版社, 2011: 80-82.
	CHEN Ge, YANG Jiancheng. Introduction to textile machinery[M]. Beijing: China Textile & Apparel Press, 2011: 80-82.
[12]	刘爱军, 杨育, 邢青松, 等. 多目标模糊柔性车间调度中的多种群遗传算法[J]. 计算机集成制造系统, 2011, 17(9): 1954-1961.
	LIU Aijun, YANG Yu, XING Qingsong, et al. Multi-population genetic algorithm in multiobjective fuzzy and flexible job shop scheduling[J]. Computer Integrated Manufacturing Systems, 2011, 17(9): 1954-1961.
[13]	周明, 孙树栋. 遗传算法原理及应用[M]. 北京: 国防工业出版, 1999: 15-16.
	ZHOU Ming, SUN Shudong. Genetic algorithms: theory and application[M]. Beijing: National Defense Industry Press, 1999: 15-16.
[14]	DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGAII[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197. doi: 10.1109/4235.996017
[15]	BLICKLE Tobias, THIELE Lothar. A comparison of selection schemes used in evolutionary algorithms[J]. Evolutionary Computation, 1996, 4(4): 361-394. doi: 10.1162/evco.1996.4.4.361
[16]	AGRAWAL R B, DEB K, AGRAWAL R B. Simulated binary crossover for continuous search space[J]. Complex Systems, 2000, 9(3): 115-148.
[17]	DEB K, GOYAL M. A combined genetic adaptive search (geneas) for engineering design[J]. Computer Science and Informatics, 1999, 26:30-45.
[18]	ZITZLER E. Evolutionary algorithms for multiobjective optimization: methods and applications[D]. Swiss: Swiss Federal Institute of Technology, 1999:1-56.
[19]	RAMAMRITHAM K, STANKOVIC J A, SHIAH P F. Efficient scheduling algorithms for real-time multiprocessor systems[J]. IEEE Transactions on Parallel and Distributed Systems, 1990, 1(2): 184-194. doi: 10.1109/71.80146
[20]	宾雪莲, 杨玉海, 金士尧. 一种基于分组与适当选取策略的实时多处理器系统的动态调度算法[J]. 计算机学报, 2006(1): 81-91.
	BIN Xuelian, YANG Yuhai, JIN Shiyao. A new dynamic scheduling algorithm for real-time multiprocessor systems based on grouping and properly choosing policies[J]. Chinese Journal of Computers, 2006(1): 81-91.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

案例	C(NSGAII,NSGAII_G)	C(NSGAII_G,NSGAII)
a	0.159 090 909	0.698 630 137
b	0	0.805 194 805
c	0	0.957 446 809
d	0	0.861 111 111

组别	m	n	算法目标值/h									算法计算耗时/s
			近视算法			H-NSGAII_G			NSGAII_3			近视算法	H-NSGAII_G	NSGAII_3
			f₁	f₂	f₃	f₁	f₂	f₃	f₁	f₂	f₃	近视算法	H-NSGAII_G	NSGAII_3
	6	14	0	467	52	0	466	46	0	455	37	0.12	51.93	75.42
	6	28	0	826	90	0	763	66	0	747	61	0.35	164.00	159.11
a₁	6	42	0	1 120	128	0	1 040	94	0	1 072	80	0.54	173.98	177.48
	6	56	0	1 467	164	0	1 427	112	0	1 461	106	0.98	270.36	343.97
	6	70	0	1 784	200	0	1 757	142	0	1 795	142	1.38	667.45	565.75
	100	245	0	487	3 271	0	495	2 739	0	770	2 907	3.22	753.62	723.12
	100	490	0	839	3 992	0	828	3 430	1 222	1 586	5 068	4.43	2 218.81	2 358.66
b₁	100	735	0	1 202	4 697	0	1 176	3 823	9 624	2 799	5 398	4.69	3 765.43	3 566.62
	100	980	0	1 625	5 394	0	1 571	4 202	34 064	4 721	8 755	5.12	4 518.52	4 587.94
	100	1 225	0	1 951	6 121	0	1 921	4 695	55 462	5 510	9 521	5.76	6 024.72	6 125.72
c₁	500	4 000	0	2 163	390 486	0	1 537	70 403	98 764	7 655	460 485	22.24	23 154.20	28 743.60

基于改进型NSGAII的织造车间多目标大规模动态调度

Multi-objective large-scale dynamic scheduling for weaving workshops based on improved NSGAII

RichHTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 20

相关文章 5

Metrics

本文评价

推荐阅读 0

织轴编号	初始调度			再调度
织轴编号	穿经机编号	开始时间/h	结束时间/h	穿经机编号	开始时间/h	结束时间/h
1	1	0	1.1	—	—	—
2	2	0	1.1	—	—	—
…	…	…	…	—	—	—
14	2	3.30	4.45	—	—	—
15	2	4.45	5.56	—	—	—
16	2	123.15	124.26	—	—	—
17	1	137.52	138.63	—	—	—
23	1	138.63	139.75	—	—	—
26	2	138.62	139.74	—	—	—
71	—	—	—	1	238.00	239.13
20	—	—	—	2	242.13	243.24
21	—	—	—	1	314.00	315.11
22	—	—	—	2	389.22	390.33
24	—	—	—	1	435.60	436.72
28	—	—	—	2	436.60	437.72
29	2	226.07	227.19	1	545.78	546.90

[1]	谢子昂, 杜劲松, 赵国华. 衬衫吊挂流水线的自适应动态调度[J]. 纺织学报, 2020, 41(10): 144-149.
[2]	郑小虎, 鲍劲松, 马清文, 周衡, 张良山. 基于模拟退火遗传算法的纺纱车间调度系统[J]. 纺织学报, 2020, 41(06): 36-41.
[3]	莫帅, 冯战勇, 唐文杰, 党合玉, 邹振兴. 基于神经网络和遗传算法的锭子弹性管性能优化[J]. 纺织学报, 2020, 41(04): 161-166.
[4]	孟朔, 潘如如, 高卫东, 王静安, 周利军. 采用主目标进化遗传算法的织造排程研究[J]. 纺织学报, 2019, 40(08): 169-174.
[5]	黄双郗欣甫徐洋孙以泽. 簇绒地毯织机耦联轴系的铰链间隙对毯面绒高的影响[J]. 纺织学报, 2016, 37(08): 132-137.