Journal of Jilin University(Engineering and Technology Edition) ›› 2021, Vol. 51 ›› Issue (3): 900-909.doi: 10.13229/j.cnki.jdxbgxb20200063

Previous Articles     Next Articles

Multi⁃objective flow shop optimal scheduling considering worker's load

Bao-feng SUN1(),Xin-xin REN1,Zai-si ZHENG1,2,Guo-yi Li1   

  1. 1.College of Transportation，Jilin University，Changchun 130022，China
    2.Department of Product，FAW-Volkswagen Auntomobile Co. ，Ltd. ，Changchun 130011，China
  • Received:2020-02-06 Online:2021-05-01 Published:2021-05-07

RICH HTML

 1   

PDF (PC)

294

Abstract:

To solve the problem of workers' load imbalance in the flow shop scheduling， a dual-objective optimization scheduling model is proposed in this paper with the minimum delay time and the workers' workload standard deviation. A NSGA-II based on two-gene chromosome coding is designed to obtain Pareto-optimal solutions. Two embedded heuristic rules， the earliest due date （EDD） rule and the shortest processing time （SPT） rule， are introduced together with NSGA-II to form the NSGA-II-EDD and NSGA-II-SPT for comparison. Computation experimental analysis shows that NSGA-II performs better in case of evaluation indexes with the average non-dominated solutions N， error ratio ER，spacing evaluation index S and Pareto front span K， but is worse in operation time T.

Key words: computer application, flow shop scheduling, multi-objective optimization, worker's load, two-gene chromosome coding, NSGA-II algorithm

CLC Number: 

  • TP29

Fig.1

Distribution of processing tasks"

Table 1

Weekly order production time"

工件号工序一工序二工序三工序四交货期
166867965296
261806464538
356856965550
452856273272
558668170275
655787967558
759648163267
869778466296
967867568296
1070787764289
1165627479280
1269758579308
1355736679546
1468858579317
1559698369280
1657636677263
1767718561284
1866658569570
1952866975564
2068788673305

Table 2

Team, worker and process"

班组名称工序一工序二工序三工序四
16787
26877
36777
47888

Table 3

Partial worker basic information table"

工序人员编号身高/cm体重/kg年龄BMRRMRm
一1159553264112
2172724368124
3177622872123
4179593274119
5170633376117
6162623570116
二1172652870125
2167523267114
3164532963112
4162623374124
5167582876110
6169604375119
7172592972126
三1174673269123
2176632265119
3168642663104
4172692761106
5164592572103
6158623364112
7163632967109
8157593662114

Table 4

Model basic parameters"

参数符号数值
低负荷延误概率λ10.064
高负荷延误概率λ20.104
单位时间工人能量阈值E10.056
经验参数β7.02

Fig.2

Solution of the algorithm NSGA-II"

Table 5

Result of frontier solution"

订单规模运行时间/sPareto
Tσ
903.2308.44
1004.34012.55
4.1111.53
5.2310.39
15.4110.31
1105.121.1147.66
5.5723.65
16.6917.41
34.3116.91
38.2315.85
67.4914.58
71.3214.51
72.4114.49
80.9913.08
107.5312.79
1206.3881.0423.49
140.3423.02
140.3518.46
162.2014.93
219.4814.49
272.3113.53
281.8813.15
464.7412.83
523.8512.82
528.5712.48

Fig.3

Iteration curve trend of target value"

Fig.4

Comparison of the number of non-dominated solutions in the frontier of Pareto"

Fig.5

Comparison of the error ratio (ER) in Pareto frontier solution"

Fig.6

Comparison of spacing evaluation index inPareto frontier solution"

Fig.7

Comparison of the frontier span"

Fig.8

Comparison of running time"

1 Pinedo M L. Scheduling: Theory, Algorithm, and Systems[M]. 5th ed. New York: Springer, 2015.
2 Pan Quan-ke, Wang Ling, Li Jun-qing, et al. A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimization[J]. Journal of Intelligent Manufacturing, 2014, 45:42-56.
3 周炳海,彭涛. 混流装配线准时化物料配送调度优化[J].吉林大学学报:工学版,2017,47(4): 1253-1261.
Zhou Bing-hai, Peng Tao. Optimal schedule of just-in-time part distribution for mixed-model assembly lines[J]. Journal of Jilin University(Engineering and Technology Edition), 2017,47(4): 1253-1261.
4 陈海鹏,邱际伦,邱峰,等. 基于Pi演算的前沿调度算法并行性建模及实现[J]. 吉林大学学报:工学版,2019,49(1):242-247.
Chen Hai-peng, Qiu Ji-lun, Qiu Feng, et al. Modeling and implementation of frontier scheduling parallelism algorithm based on Pi calculus[J]. Journal of Jilin University(Engineering and Technology Edition), 2019,49(1):242-247.
5 陆志强,张思源,崔维伟. 集成预防性维护和流水线调度的鲁棒性优化研究[J]. 自动化学报,2015,41(5):906-913.
Lu Zhi-qiang, Zhang Si-yuan, Cui Wei-wei. Integrating production scheduling and maintenance policy for robustness in flow shop problems[J]. Acta Automatica Sinica, 2015,41(5):906-913.
6 Rock H. The three-machine no-wait flow shop is NP-complete[J]. Journal of the Acm, 1984, 31(2): 336-345.
7 Li P H, Fan Z J, Zhou J. Optimizing and simulating production line balance based on human factors[J]. Applied Mechanics and Materials, 2012(214): 495-499.
8 吴瑕. 基于人因的混流装配系统复杂性优化研究[D]. 天津:天津大学管理学院,2012.
Wu Xia. Optimization of assembly complexity in mixed-model assembly systems based on human factors[D]. Tianjin: School of Management, Tianjin University, 2012.
9 Battini D, Delorme X, Dolgui A, et al. Ergonomics in assembly line balancing based on energy expenditure: a multi-objective model[J]. International Journal of Production Research, 2015, 54(3):824-845.
10 Sun X Y, Zhao L, Zhang P F, et al. Enhanced NSGA-II with evolving directions prediction for interval multi-objective optimization[J]. Swarm and Evolutionary Computation, 2019,49:124-133.
11 Sundararghavan P S, Kunnathur A S, Viswanathan I. Minimizing makespan in parallel flowshops[J]. Journal of the Operational Research Society, 1997, 48(8): 834-842.
12 Marichelvam M K, Prabaharan T. Performance evaluation of an improved hybrid genetic scatter search (IHGSS) algorithm for multistage hybrid flow shop scheduling problems with missing operations[J]. International Journal of Industrial and Systems Engineering, 2014,16(1):120-141.
13 Rosenberg R S. Stimulation of genetic populations with biochemical properties: I. The model[J]. Mathematical Biosciences, 1970,7(3/4):223-257.
14 Zhou B H, Liu W L. Energy-efficient multi-objective scheduling algorithm for hybrid flow shop with fuzzy processing time[J]. Journal of Systems and Control Engineering, 2019, 233(10):1282-1297.
15 Azadeh A, Shoja B M, Ghanei S, et al. A multi-objective optimization problem for multi-state series-parallel systems: a two-stage flow-shop manufacturing system[J]. Reliability Engineering & System Safety, 2015, 136:62-74.
16 Zelazny D, Pempera J. Solving multi-objective permutation flowshop scheduling problem using CUDA[C]∥2015 20th International Conference on Methods and Models in Automation and Robotics (MMAR), Miedzyzdroje, Poland,2015:347-352.
17 Srinivas N, Deb K. Multi-objetive function optimization using non-dominated sorting genetic algorithms[J]. Evolutionary Computation, 1995,2:221-248.
18 Wang H F, Fu Y P, Huang M, et al. A NSGA-II based memetic algorithm for multiobjective parallel flowshop scheduling problem[J]. Computer & Industrial Engineering,2017,113:185-194.
19 Deb K, Amrit P, Sameer A, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation,2002,6(2): 182-197.
20 石英,王秀红,祁丽霞,等. 人因工程学[M]. 北京: 清华大学出版社,2011:103-104.
[1] Shu-min WANG,Wei CHEN. Algorithm for identifying abnormal behavior in underground mines based on continuous density hidden Markov model [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(3): 1067-1072.
[2] Yuan-ning LIU,Di WU,Xiao-dong ZHU,Qi-xian ZHANG,Shuang-shuang LI,Shu-jun GUO,Chao WANG. User interface components detection algorithm based on improved YOLOv3 [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(3): 1026-1033.
[3] Xiao-long ZHU,Zhong XIE. Geospatial data extraction algorithm based on machine learning [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(3): 1011-1016.
[4] Dan-tong OUYANG,Yang LIU,Jie LIU. Fault diagnosis method based on test set under fault response guidance [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(3): 1017-1025.
[5] Rong QIAN,Ru ZHANG,Ke-jun ZHANG,Xin JIN,Shi-liang GE,Sheng JIANG. Capsule graph neural network based on global and local features fusion [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(3): 1048-1054.
[6] Shu-tao SHEN,Zha-xi NIMA. Double chaos identifiable tampering image encryption method based on blockchain technology [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(3): 1055-1059.
[7] Tian-qi GU,Chen-jie HU,Yi TU,Shu-wen LIN. Robust reconstruction method based on moving least squares algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(2): 685-691.
[8] Qian-yi XU,Gui-he QIN,Ming-hui SUN,Cheng-xun MENG. Classification of drivers' head status based on improved ResNeSt [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(2): 704-711.
[9] Xiao-hui WEI,Chang-bao ZHOU,Xiao-xian SHEN,Yuan-yuan LIU,Qun-chao TONG. Accelerating CALYPSO structure prediction with machine learning [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(2): 667-676.
[10] Ji-cheng HUANG,Cheng SHEN,Ai-min JI,Xian-wang LI,Bin ZHANG,Kun-peng TIAN,Hao-lu LIU. Optimization of cutting⁃conveying key working parameters of hemp harvester [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(2): 772-780.
[11] Bing-hai ZHOU,Qiong WU. Balancing and bi⁃objective optimization of robotic assemble lines [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(2): 720-727.
[12] Ming FANG,Wen-qiang CHEN. Face micro-expression recognition based on ResNet with object mask [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(1): 303-313.
[13] Yuan SONG,Dan-yuan ZHOU,Wen-chang SHI. Method to enhance security function of OpenStack Swift cloud storage system [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(1): 314-322.
[14] Xiao-yu WANG,Xin-hao HU,Chang-lin HAN. Face pencil drawing algorithms based on generative adversarial network [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(1): 285-292.
[15] Xiang-jiu CHE,You-zheng DONG. Improved image recognition algorithm based on multi⁃scale information fusion [J]. Journal of Jilin University(Engineering and Technology Edition), 2020, 50(5): 1747-1754.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd