吉林大学学报(工学版) ›› 2021, Vol. 51 ›› Issue (3): 900-909.doi: 10.13229/j.cnki.jdxbgxb20200063

• 交通运输工程·土木工程 • 上一篇    下一篇

考虑工人负荷的多目标流水车间优化调度

孙宝凤1(),任欣欣1,郑再思1,2,李国一1   

  1. 1.吉林大学 交通学院,长春 130022
    2.一汽-大众汽车有限公司 生产部,长春 130011
  • 收稿日期:2020-02-06 出版日期:2021-05-01 发布日期:2021-05-07
  • 作者简介:孙宝凤(1970-),女,教授,博士. 研究方向:物流系统规划与仿真优化. E-mail:sunbf@jlu.edu.cn
  • 基金资助:
    国家自然科学基金项目(61873109);吉林省交通运输科技项目(20160112)

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

摘要:

针对流水车间工人负荷不平衡的现象,构建了工件总延误时间和工人作业分配标准差最小化的双目标优化调度模型。设计了基于两段式染色体编码的NSGA-II算法,获得了模型的Pareto最优解集。引入两种嵌入启发式规则:交货期最接近(EDD)规则和加工时间最短(SPT)规则,形成了NSGA-II-EDD和NSGA-II-SPT两种对比情境。算例分析表明:NSGA-II算法的Pareto解的平均个数N、Pareto前沿解误差比ER、Pareto前沿解空间评价指标S、Pareto前沿跨度K比NSGA-II-EDD和NSGA-II-SPT的性能好,在算法运算时间T上性能较差。

关键词: 计算机应用, 流水车间调度, 多目标优化, 工人负荷, 两段式染色体编码, NSGA-II算法

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

中图分类号: 

  • TP29

图1

加工任务分配关系图"

表1

周订单各工序加工时间 (min)"

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

表2

班组、工人和工序配置情况 (configuration 人)"

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

表3

部分员工基本信息表"

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

表4

模型基本参数"

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

图2

NSGA-II算法的解的情况"

表5

前沿解求解结果"

订单规模运行时间/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

图3

目标值迭代曲线趋势"

图4

Pareto前沿非支配解的数量对比"

图5

Pareto 前沿解误差比比较"

图6

Pareto前沿解空间评价指标比较"

图7

Pareto前沿跨度比较"

图8

运行时间比较"

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] 王淑敏,陈伟. 基于连续密度隐马尔可夫模型的矿下异常行为识别算法[J]. 吉林大学学报(工学版), 2021, 51(3): 1067-1072.
[2] 刘元宁,吴迪,朱晓冬,张齐贤,李双双,郭书君,王超. 基于YOLOv3改进的用户界面组件检测算法[J]. 吉林大学学报(工学版), 2021, 51(3): 1026-1033.
[3] 朱小龙,谢忠. 基于机器学习的地理空间数据抽取算法[J]. 吉林大学学报(工学版), 2021, 51(3): 1011-1016.
[4] 欧阳丹彤,刘扬,刘杰. 故障响应指导下基于测试集的故障诊断方法[J]. 吉林大学学报(工学版), 2021, 51(3): 1017-1025.
[5] 钱榕,张茹,张克君,金鑫,葛诗靓,江晟. 融合全局和局部特征的胶囊图神经网络[J]. 吉林大学学报(工学版), 2021, 51(3): 1048-1054.
[6] 沈淑涛,尼玛扎西. 基于区块链技术的双混沌可识篡改图像加密方法[J]. 吉林大学学报(工学版), 2021, 51(3): 1055-1059.
[7] 顾天奇,胡晨捷,涂毅,林述温. 基于移动最小二乘法的稳健重构方法[J]. 吉林大学学报(工学版), 2021, 51(2): 685-691.
[8] 许骞艺,秦贵和,孙铭会,孟诚训. 基于改进的ResNeSt驾驶员头部状态分类算法[J]. 吉林大学学报(工学版), 2021, 51(2): 704-711.
[9] 魏晓辉,周长宝,沈笑先,刘圆圆,童群超. 机器学习加速CALYPSO结构预测的可行性[J]. 吉林大学学报(工学版), 2021, 51(2): 667-676.
[10] 黄继承,沈成,纪爱敏,李显旺,张彬,田昆鹏,刘浩鲁. 工业大麻收割机切割⁃输送关键部件作业参数优化[J]. 吉林大学学报(工学版), 2021, 51(2): 772-780.
[11] 周炳海,吴琼. 基于多目标的机器人装配线平衡算法[J]. 吉林大学学报(工学版), 2021, 51(2): 720-727.
[12] 方明,陈文强. 结合残差网络及目标掩膜的人脸微表情识别[J]. 吉林大学学报(工学版), 2021, 51(1): 303-313.
[13] 宋元,周丹媛,石文昌. 增强OpenStack Swift云存储系统安全功能的方法[J]. 吉林大学学报(工学版), 2021, 51(1): 314-322.
[14] 王小玉,胡鑫豪,韩昌林. 基于生成对抗网络的人脸铅笔画算法[J]. 吉林大学学报(工学版), 2021, 51(1): 285-292.
[15] 车翔玖,董有政. 基于多尺度信息融合的图像识别改进算法[J]. 吉林大学学报(工学版), 2020, 50(5): 1747-1754.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!