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

• 纺织工程 • 上一篇    下一篇

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

沈春娅1,2, 雷钧杰1,2, 汝欣1,2, 彭来湖1,2, 胡旭东1,2()   

  1. 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 Chunya1,2, LEI Junjie1,2, RU Xin1,2, PENG Laihu1,2, HU Xudong1,2()   

  1. 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

摘要:

织造车间调度规模普遍在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

图1

织造车间工艺流程"

图2

逾期时间与损失的关系"

图3

动态调度流程图"

图4

前沿解集分布"

表1

C指标结果对比"

案例 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

表2

3种算法的实验结果统计"

组别 m n 算法目标值/h 算法计算耗时/s
近视算法 H-NSGAII_G NSGAII_3 近视
算法
H-NSGAII_G NSGAII_3
f1 f2 f3 f1 f2 f3 f1 f2 f3
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
a1 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
b1 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
c1 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

表3

穿经工序调度"

织轴
编号
初始调度 再调度
穿经机
编号
开始时
间/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

图5

织造工序再调度甘特图"

[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.
[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.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!