Journal of Textile Research ›› 2022, Vol. 43 ›› Issue (04): 74-83.doi: 10.13475/j.fzxb.20210502710

• Textile Engineering • Previous Articles     Next Articles

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 Online:2022-04-15 Published:2022-04-20
  • Contact: HU Xudong E-mail:xdhu@zstu.edu.cn

RichHTML

8

PDF (PC)

59

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

CLC Number: 

  • TS111.8

Fig.1

Process flow of weaving workshop"

Fig.2

Relationship between overdue time and loss"

Fig.3

Dynamic scheduling flow chart"

Fig.4

Frontier solution set distribution. (a)Case a; (b)Case b; (c)Case c;(d)Case d"

Tab.1

Comparison of C index results"

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

Tab.2

Three algorithms of experimental results statistics"

组别 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

Tab.3

Drawing-in process scheduling"

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

Fig.5

Weaving process is rescheduled Gantt chart"

[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] SHAO Jingfeng, SHI Xiaomin. Multi-objective optimization of spinning process parameters based on nondominated sorting genetic algorithm II [J]. Journal of Textile Research, 2022, 43(01): 80-88.
[2] XIE Ziang, DU Jinsong, ZHAO Guohua. Adaptive dynamic scheduling of garment hanging production line [J]. Journal of Textile Research, 2020, 41(10): 144-149.
[3] ZHENG Xiaohu, BAO Jinsong, MA Qingwen, ZHOU Heng, ZHANG Liangshan. Spinning workshop collaborative scheduling method based on simulated annealing genetic algorithm [J]. Journal of Textile Research, 2020, 41(06): 36-41.
[4] MO Shuai, FENG Zhanyong, TANG Wenjie, DANG Heyu, ZOU Zhenxing. Performance optimization of elastic spindle pipe based on neural network and genetic algorithm [J]. Journal of Textile Research, 2020, 41(04): 161-166.
[5] MENG Shuo, PAN Ruru, GAO Weidong, WANG Jing'an, ZHOU Lijun. Research on weaving scheduling using main objective evolutionary genetic algorithm [J]. Journal of Textile Research, 2019, 40(08): 169-174.
[6] . Influence of joint clearances of coupling shaft system on pile height in tufting machine [J]. JOURNAL OF TEXTILE RESEARCH, 2016, 37(08): 132-137.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
京ICP备14006648号
Copyright 2021 © Editorial office of Journal of Textile Research
Supported by Beijing Magtech Co.Ltd