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

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

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

CLC Number:

TP391.4

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.

Figures/Tables 17

Table 1

Fig. 1

Fig. 2

Table 2

Fig. 3

Fig. 4

Table 3

Table 4

Table 5

Fig. 5

Table 6

Table 7

Table 8

Table 9

Fig. 6

Fig. 7

Fig. 8

References 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

工件	新增工件数	加工中心
工件	新增工件数	M1	M2	M3	M4	M5
T1	100	34	11	13	3	39
T2	150	49	40	38	0	23
T3	150	60	26	43	15	6
T4	100	48	11	8	33	0
T5	150	58	1	0	38	53

工件	加工中心
工件	M1	M2	M3	M4	M5
T1	37	18	53	97	35

工件	加工中心
工件	M1	M2	M3	M4	M5
T1	53	33	33	26	55