Reverse Order and Greedy Integrated Scheduling Algorithm Considering Dynamic Time Urgency Degree of the Process Sequences

CAO Wangcheng; XIE Zhiqiang; PEI Lirong

doi:10.11999/JEIT211455

Volume 44 Issue 5

May 2022

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2022 > 44(5): 1572-1580

CAO Wangcheng, XIE Zhiqiang, PEI Lirong. Reverse Order and Greedy Integrated Scheduling Algorithm Considering Dynamic Time Urgency Degree of the Process Sequences[J]. Journal of Electronics & Information Technology, 2022, 44(5): 1572-1580. doi: 10.11999/JEIT211455

Citation:

CAO Wangcheng, XIE Zhiqiang, PEI Lirong. Reverse Order and Greedy Integrated Scheduling Algorithm Considering Dynamic Time Urgency Degree of the Process Sequences[J]. Journal of Electronics & Information Technology, 2022, 44(5): 1572-1580. doi: 10.11999/JEIT211455

Citation:

PDF( 2161 KB)

Reverse Order and Greedy Integrated Scheduling Algorithm Considering Dynamic Time Urgency Degree of the Process Sequences

doi: 10.11999/JEIT211455

1.
College of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China
2.
Department of Computer Science and Technology, Mudanjiang Normal University, Mudanjiang 157011, China

Funds: The Key Science and Technology Projects of Heilongjiang Provincial Education Department (1355ZD004), The National Natural Science Foundation of China (61772160)

Received Date: 2021-12-08
Rev Recd Date: 2022-03-26

Available Online: 2022-04-22

Publish Date: 2022-05-25

Abstract

Abstract

For the general integrated scheduling problem of tree structured complex single product machining and assembling, a reverse order and greedy integrated scheduling algorithm is proposed by considering dynamic TUD (Time Urgency Degree) of the process sequences. The strategy of process sorting is put forward, and the TUD of process sequence is defined. The process tree is reversed using leaf alignment, according to the order from leaf to root, the scheduling order of leaf nodes in the same layer is determined layer by layer from large to small according to the dynamic TUD values of the process sequences to which the leaf nodes belong. The sorted leaf nodes are put into the queue in turn. Finally, the elements in the queue are reversed. A reverse order and greedy scheduling strategy is proposed. Each time, a single process is taken as a unit to conduct trial scheduling at the quasi-scheduling time point in the required equipment. Quasi-scheduling scheme set of the process is obtained, and the quasi-scheduling scheme with the minimum end time is selected, and if it is not unique, the scheme is selected to machine the process as early as possible. A case shows that the proposed algorithm optimizes the general integrated scheduling results and has high efficiency.
- Integrated scheduling,
- Machining and assembling,
- Time Urgency Degree (TUD),
- Reverse order,
- Greedy

FullText(HTML)

References(15)

References

[1]	WANG Zhen, ZHANG Xiaohuan, CAO Yuxiao, et al. An integrated scheduling algorithm for multi-device-processes with the strategy of exchanging adjacent parallel processes of the same device[J]. EURASIP Journal on Wireless Communications and Networking, 2021, 2021(1): 104. doi: 10.1186/s13638-021-01989-1
[2]	苑迎春, 李小平, 王茜, 等. 基于逆向分层的网格工作流调度算法[J]. 计算机学报, 2008, 31(2): 282–290. doi: 10.3321/j.issn:0254-4164.2008.02.012 YUAN Yingchun, LI Xiaoping, WANG Qian, et al. Bottom level based heuristic for workflow scheduling in grids[J]. Chinese Journal of Computers, 2008, 31(2): 282–290. doi: 10.3321/j.issn:0254-4164.2008.02.012
[3]	苑迎春, 李小平, 王茜. 基于串归约的网格工作流费用优化方法[J]. 计算机研究与发展, 2008, 45(2): 246–253. YUAN Yingchun, LI Xiaoping, and WANG Qian. Cost optimization heuristics for grid workflows scheduling based on serial reduction[J]. Journal of Computer Research and Development, 2008, 45(2): 246–253.
[4]	苑迎春, 李小平, 王茜, 等. 成本约束的网格工作流时间优化方法[J]. 计算机研究与发展, 2009, 46(2): 194–201. YUAN Yingchun, LI Xiaoping, WANG Qian, et al. Time optimization heuristics for scheduling budget-constrained grid workflows[J]. Journal of Computer Research and Development, 2009, 46(2): 194–201.
[5]	LI Xiaoping, QIAN Lihua, and RUIZ R. Cloud workflow scheduling with deadlines and time slot availability[J]. IEEE Transactions on Services Computing, 2018, 11(2): 329–340. doi: 10.1109/TSC.2016.2518187
[6]	LI Xiaoping, YU Wei, RUIZ R, et al. Energy-aware cloud workflow applications scheduling with geo-distributed data[J]. IEEE Transactions on Services Computing, 2022, 15(2): 891–903. doi: 10.1109/TSC.2020.2965106
[7]	LI Xiaoping, CHEN Fuchao, RUIZ R, et al. MapReduce task scheduling in heterogeneous geo-distributed data centers[J]. IEEE Transactions on Services Computing, To be published.
[8]	李克强. 政府工作报告-2021年3月5日在第十三届全国人民代表大会第四次会议上[EB/OL]. http://www.gov.cn/gongbao/content/2021/content_5593438.htm?ivk_sa=1024320u, 2021. LI Keqiang. Government work report - at the fourth session of the 13th National People's Congress on March 5, 2021[EB/OL]. http://www.gov.cn/gongbao/content/2021/content_5593438.htm?ivk_sa=1024320u, 2021.
[9]	GAO Yilong, XIE Zhiqiang, YANG Dan, et al. Flexible integrated scheduling algorithm based on remaining work probability selection coding[J]. Expert Systems, 2021, 38(4): e12683. doi: 10.1111/exsy.12683
[10]	谢志强, 辛宇, 杨静. 可回退抢占的设备驱动综合调度算法[J]. 自动化学报, 2011, 37(11): 1332–1343. doi: 10.3724/SP.J.1004.2011.01332 XIE Zhiqiang, XIN Yu, and YANG Jing. Machine-driven integrated scheduling algorithm with rollback-preemptive[J]. Acta Automatica Sinica, 2011, 37(11): 1332–1343. doi: 10.3724/SP.J.1004.2011.01332
[11]	谢志强, 杨静, 周勇, 等. 基于工序集的动态关键路径多产品制造调度算法[J]. 计算机学报, 2011, 34(2): 406–412. doi: 10.3724/SP.J.1016.2011.00406 XIE Zhiqiang, YANG Jing, ZHOU Yong, et al. Dynamic critical paths multi-product manufacturing scheduling algorithm based on operation set[J]. Chinese Journal of Computers, 2011, 34(2): 406–412. doi: 10.3724/SP.J.1016.2011.00406
[12]	张雍达, 宋嘉. 工业4.0时代的智能制造[J]. 中国工业和信息化, 2021(9): 32–34. doi: 10.19609/j.cnki.cn10-1299/f.2021.09.002 ZHANG Yongda and SONG Jia. Intelligent manufacturing in the industrial 4.0 era[J]. China Industry &Information Technology, 2021(9): 32–34. doi: 10.19609/j.cnki.cn10-1299/f.2021.09.002
[13]	谢志强, 张晓欢, 高一龙, 等. 考虑串行工序紧密度的择时综合调度算法[J]. 机械工程学报, 2018, 54(6): 191–202. doi: 10.3901/JME.2018.06.191 XIE Zhiqiang, ZHANG Xiaohuan, GAO Yilong, et al. Time-selective integrated scheduling algorithm considering the compactness of serial processes[J]. Journal of Mechanical Engineering, 2018, 54(6): 191–202. doi: 10.3901/JME.2018.06.191
[14]	谢志强, 张晓欢, 辛宇, 等. 考虑后续工序的择时综合调度算法[J]. 自动化学报, 2018, 44(2): 344–362. doi: 10.16383/j.aas.2018.c160562 XIE Zhiqiang, ZHANG Xiaohuan, XIN Yu, et al. Time-selective integrated scheduling algorithm considering posterior processes[J]. Acta Automatica Sinica, 2018, 44(2): 344–362. doi: 10.16383/j.aas.2018.c160562
[15]	WANG Zhen, ZHANG Xiaohuan, and PENG Gang. An improved integrated scheduling algorithm with process sequence time-selective strategy[J]. Complexity, 2021, 2021: 5570575. doi: 10.1155/2021/5570575