基于改进注水算法的离散车间任务分配问题研究

doi:10.16182/j.issn1004731x.joss.20-0872

系统仿真学报 ›› 2022, Vol. 34 ›› Issue (4): 768-776.doi: 10.16182/j.issn1004731x.joss.20-0872

基于改进注水算法的离散车间任务分配问题研究

冯开团(), 袁杰()

新疆大学电气工程学院，新疆乌鲁木齐 830047

收稿日期:2020-11-10 修回日期:2021-08-30 出版日期:2022-04-30 发布日期:2022-04-20
通讯作者: 袁杰 E-mail:390890382@qq.com;yuanjie222@126.com
作者简介:冯开团(1996-)，男，硕士生，研究方向为动态任务规划、智能算法优化。E-mail：390890382@qq.com
基金资助:
国家自然科学基金(61863033);新疆维吾尔自治区“天山青年计划”-优秀青年科技人才培养项目(2019Q018)

Research on Discrete Workshop Task Assignment Based on Improved Water Filling Algorithm

Kaituan Feng(), Jie Yuan()

School of Electrical Engineering, Xinjiang University, Urumqi 830047, China

Received:2020-11-10 Revised:2021-08-30 Online:2022-04-30 Published:2022-04-20
Contact: Jie Yuan E-mail:390890382@qq.com;yuanjie222@126.com

摘要/Abstract

摘要：

针对离散车间实时动态任务分配结果欠理想的问题，提出了改进的注水算法。该算法加入了加工速率和费用因子，协调了加工速率和费用以及加工工件之间的关系，实现了不同代价的工件分配，对分配结果进行了调整，满足了离散分配的要求。改进的注水算法能够对临时新增的工件进行实时动态的分配。提出的算法与匈牙利算法、两阶段优化方法以及注水算法进行了对比，实验结果表明，改进的注水算法在加工时间和加工费用上具有一定的优势，其运算复杂度仅与加工中心的数量有关。

关键词: 离散车间调度, 注水算法, 动态任务分配, 匈牙利算法, 两阶段优化方法

Abstract:

Aiming at the unsatisfactory the results of the real-time dynamic task allocation in discrete workshops are not ideal, an improved water filling algorithm is proposed. Compared with the equal cost allocation of the water injection algorithm, the processing rate and cost factors are added to the improved water injection algorithm to coordinate the processing rate, the cost and the workpieces. The allocation of the different cost workpieces is realized and the result is adjusted, which can meet the requirements of discrete distribution. The improved water injection algorithm can dynamically allocate the newly added workpieces in real time. The proposed algorithm is compared with the Hungarian algorithm, the two-stage optimization method and the water filling algorithm. The experimental results show that the improved water filling algorithm has advantages in processing time and processing cost. The computational complexity of the algorithm is only related to the number of machining centers.

Key words: discrete workshop scheduling, water filling algorithm, dynamic task allocation, Hungary algorithm, two-stage optimization method

中图分类号:

TP391.4

冯开团, 袁杰. 基于改进注水算法的离散车间任务分配问题研究[J]. 系统仿真学报, 2022, 34(4): 768-776.

Kaituan Feng, Jie Yuan. Research on Discrete Workshop Task Assignment Based on Improved Water Filling Algorithm[J]. Journal of System Simulation, 2022, 34(4): 768-776.

图/表 17

表1

图1

图2

表2

图3

图4

表3

表4

表5

图5

表6

表7

表8

表9

图6

图7

图8

参考文献 13

1	屈挺, 张凯, 罗浩, 等. 物联网驱动的"生产-物流"动态联动机制、系统及案例[J]. 机械工程学报, 2015, 51(20): 36-44.
	Qu Ting, Zhang Kai, Luo Hao, et al. Internet-of-things Based Dynamic Synchronization of Production and Logistics: Mechanism, System and Case Study[J]. Journal of Mechanical Engineering, 2015, 51(20): 36-44.
2	Yin Chao, Deng Pengcheng, Li Xiaobin. Intelligent Manufacturing Mode for Sophisticated Equipment Assembly Workshop[J]. Journal of Advanced Manufacturing Systems(S0219-6867), 2018, 17(4): 533-549.
3	唐任仲, 胡罗克, 周邦, 等. 基于无线射频识别技术的车间在制品物流状态分析[J]. 计算机集成制造系统, 2014, 20(1): 45-54.
	Tang Renzhong, Hu Luoke, Zhou Bang,et al. Logistics Status Analysis of Work-in-process in the Workshop Based on RFID Technology[J]. Computer Integrated Manufacturing Systems, 2014, 20(1): 45-54.
4	尹超, 高玲, 李孝斌. 基于复杂网络理论的离散制造车间生产物流网络建模与分析[J]. 计算机集成制造系统,2020, 26(8): 2157-2169.
	Yin Chao, Gao Ling, Li Xiaobin. Modeling and Analysis of Production Logistics Network in Discrete Manufacturing Workshop Based on Complex Network Theory [J]. Computer Integrated Manufacturing Systems, 2020, 26(8): 2157-2169.
5	单鑫, 王艳, 纪志成. 基于参数知识鸽群算法的离散车间能效优化[J]. 系统仿真学报, 2017, 29(9): 2140-2149.
	Shan Xin, Wang Yan, Ji Zhicheng. Energy Efficiency Optimization for Discrete Workshop Based on Parametric Knowledge Pigeon Swarm Algorithm[J]. Journal of System Simulation, 2017, 29(9): 2140-2149.
6	张富强, 付颖斌. 制造物联驱动的工序物流动态规划框架[J]. 计算机集成制造系统, 2016, 22(5): 1315-1322.
	Zhang Fuqiang, Fu Yingbin. Dynamic Planning Architecture for Process Logistics Driven by Internet of Manufacturing Things[J]. Computer Integrated Manufacturing Systems, 2016, 22(5): 1315-1322.
7	Frieze Alan, Pegden Wesley, Tkocz Tomasz. On Random Multi-Dimensional Assignment Problems[J]. Discrete Applied Mathematics(S0166-218X), 2020, 287(1): 1-9.
8	Qin Yichen, Zhang J H, Chan Felix T S, et al. A Two-Stage Optimization Approach for Aircraft Hangar Maintenance Planning and Staff Assignment Problems under MRO Outsourcing Mode[J]. Computer & Industrial Engineering(S0360-8352), 2020, 146(1): 1-57.
9	Yang R, Kwak K S, Zhou Z. Distributed Water-Filling Algorithm for Direct-Sequence Ultra Wideband Cognitive Radio Network with Limit on Aggregate Power Emission[J]. IET Communications (S1751-8628), 2010, 4(12): 1404-1414.
10	Noor Shahida M K, Nordin Rosdiadee, Ismail Mahamod. Improved Water-Filling Power Allocation for Energy-Efficient Massive MIMO Downlink Transmissions[J]. International Journal of Electronics and Telecommunications (S2081-8491), 2017, 63(1): 79-84.
11	Sharma Sunil, Sahu O P. An Improved Iterative Water Filling Algorithm in Multiuser DSL Environment[J]. Wireless Personal Communications(S0929-6212), 2017, 94(3): 675-684.
12	赵力, 孙献璞, 张海林. 一种用于离散比特分配的改进注水算法[J]. 电子与信息学报, 2010, 32(3): 638-642.
	Zhao Li, Sun Xianpu, Zhang Hailin. An Improved Water-filling Algorithm for Discrete Bit Allocation [J]. Journal of Electronics & Information Technology, 2010, 32(3): 638-642.
13	Ramakrishna Reddy K, Meikandasivam S. Optimal Distribution of Plug-In-Electric Vehicle's Storage Capacity Using Water Filling Algorithm for Load Flattening and Vehicle Prioritization Using ANFIS[J].Electric Power Systems Research (S0378-7796), 2018, 165(1): 120-133.

工件	新增工件数	加工中心
工件	新增工件数	M1	M2	M3
T1	100	20, 18, 9	25, 15, 9	11, 20, 19
T2	200	30, 15, 13	15, 20, 17	21, 16, 13
T3	300	40, 13, 6	38, 10, 8	45, 8, 5

工件	新增工件数	加工中心
工件	新增工件数	M1	M2	M3	M4	M5
T1	100	30, 27, 8	18, 11, 19	50, 10, 6	99, 5, 2	13, 17, 4
T2	150	51, 10, 4	32, 12, 11	44, 11, 8	69, 8, 15	73, 8, 5
T3	150	33, 17, 8	32, 7, 11	18, 7, 13	67, 10, 9	79, 8, 7
T4	100	21, 18, 18	39, 10, 15	54, 7, 8	41, 10, 9	63, 6, 7
T5	150	11, 19, 9	39, 18, 13	74, 9, 10	59, 11, 5	23, 19, 9

工件	加工中心	工件	加工中心
T1	M5	T4	M4
T2	M2	T5	M1
T3	M3

工件	加工中心	工件	加工中心
T1	M4	T4	M3
T2	M1	T5	M2
T3	M5

工件	新增工件数	加工中心
工件	新增工件数	M1	M2	M3	M4	M5
T1	100	23	35	2	0	40
T2	150	33	52	40	14	11
T3	150	42	43	57	8	0
T4	100	43	25	9	23	0
T5	150	60	31	0	11	48

基于改进注水算法的离散车间任务分配问题研究

Research on Discrete Workshop Task Assignment Based on Improved Water Filling Algorithm

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 17

参考文献 13

相关文章 15

编辑推荐

Metrics

本文评价

算法名称	加工费用(元)	加工时间/h	加工中心空闲时间/h
改进的注水算法	5 870	54.21	6.69
注水算法	6 790	55.42	12.03
匈牙利算法	6 250	57.71	17.36
两阶段优化方法	4 600	76.37	29.30

[1]	周维, 刘宇翔, 廖广平, 马鑫. 结合交并比损失的孪生网络目标跟踪算法研究[J]. 系统仿真学报, 2022, 34(9): 1956-1967.
[2]	张思贤, 杨艺, 张猛, 米鹏博. 高效的多特征自适应相关滤波跟踪器[J]. 系统仿真学报, 2022, 34(8): 1864-1873.
[3]	张子迎, 周华. 强化结构的数字壁画病害修复算法研究[J]. 系统仿真学报, 2022, 34(7): 1524-1531.
[4]	上官晋太, 党雅文, 连玮. 非刚体图像配准中一种改进的点匹配方法[J]. 系统仿真学报, 2022, 34(7): 1482-1489.
[5]	周培培, 侯幸林. 一种用于图像融合的无监督深度神经网络[J]. 系统仿真学报, 2022, 34(6): 1267-1274.
[6]	曹建芳, 贾一鸣, 闫敏敏, 田晓东. 稳定增强生成对抗网络在壁画的超分辨率重建[J]. 系统仿真学报, 2022, 34(5): 1076-1089.
[7]	宁小娟, 李洁茹, 高凡, 王映辉. 基于最佳几何约束和RANSAC的特征匹配算法[J]. 系统仿真学报, 2022, 34(4): 727-734.
[8]	杨敬辉, 刘德康, 杜万和, 邢立宁. 基于图像特征的双目测距系统的研究[J]. 系统仿真学报, 2022, 34(3): 624-632.
[9]	王语童, 马世伟, 杨元睿, 陈超宇. 多机器人组合最大覆盖面积寻优及预测方法[J]. 系统仿真学报, 2022, 34(1): 86-92.
[10]	刘茂山, 纪志成, 王艳, 王建锋. 核块对角表达子空间聚类及收敛性分析[J]. 系统仿真学报, 2021, 33(11): 2533-2544.
[11]	霍志浩, 金炜东, 唐鹏. 融合自监督学习的单帧图像运动视差关键点估计[J]. 系统仿真学报, 2021, 33(11): 2753-2759.
[12]	胡蕾, 王足根, 陈田, 张永梅. 一种改进的SRGAN红外图像超分辨率重建算法[J]. 系统仿真学报, 2021, 33(9): 2109-2118.
[13]	李新利, 邹昌铭, 杨国田, 刘禾. 基于生成式对抗网络的发票图像超分辨率研究[J]. 系统仿真学报, 2021, 33(6): 1307-1314.
[14]	柳有权, 裴雪, 李婉, 刘正雄. 基于邻近目标置信度评估的视觉目标跟踪与定位[J]. 系统仿真学报, 2020, 32(7): 1294-1300.
[15]	汤雯洁, 李若桐, 邓雪松, 司伟鑫, 王琼. ICP优化下的B样条四维CT图像弹性配准方法[J]. 系统仿真学报, 2020, 32(7): 1301-1311.