An Integrated Scheduling Algorithm for the Same Equipment Process Sequencing Based on the Root-Subtree Vertical and Horizontal Pre-Scheduling

被引:1
作者
Xie, Zhiqiang [1 ]
Teng, Haikun [1 ]
Ardyanti, Anak Agung Ayu Putri [1 ]
Yu, Xu [2 ]
机构
[1] Harbin Univ Sci & Technol, Harbin 150000, Peoples R China
[2] Qingdao Univ Sci & Technol, Qingdao 266061, Peoples R China
来源
CMES-COMPUTER MODELING IN ENGINEERING & SCIENCES | 2023年 / 134卷 / 01期
基金
中国国家自然科学基金;
关键词
Horizontal and vertical pre-scheduling; the priority of the Root-Subtree; the equipment process pre-start time; the dynamic start time strategy of the equipment process;
D O I
10.32604/cmes.2022.021550
中图分类号
T [工业技术];
学科分类号
08 ;
摘要
Given the existing integrated scheduling algorithms, all processes are ordered and scheduled overall, and these algorithms ignore the influence of the vertical and horizontal characteristics of the product process tree on the product scheduling effect. This paper presents an integrated scheduling algorithm for the same equipment process sequencing based on the Root-Subtree horizontal and vertical pre-scheduling to solve the above problem. Firstly, the tree decomposition method is used to extract the root node to split the process tree into several Root-Subtrees, and the Root-Subtree priority is set from large to small through the optimal completion time of vertical and horizontal pre-scheduling. All Root-Subtree processes on the same equipment are sorted into the stack according to the equipment process pre-start time, and the stack-top processes are combined with the schedulable process set to schedule and dispatch the stack. The start processing time of each process is determined according to the dynamic start processing time strategy of the equipment process, to complete the fusion operation of the Root-Subtree processes under the constraints of the vertical process tree and the horizontal equipment. Then, the root node is retrieved to form a substantial scheduling scheme, which realizes scheduling optimization by mining the vertical and horizontal characteristics of the process tree. Verification by examples shows that, compared with the traditional integrated scheduling algorithms that sort the scheduling processes as an overall, the integrated scheduling algorithm in this paper is better. The proposed algorithm enhances the process scheduling compactness, reduces the length of the idle time of the processing equipment, and optimizes the production scheduling target, which is of universal significance to solve the integrated scheduling problem.
引用
收藏
页码:179 / 200
页数:22
相关论文
共 26 条
[1]   A BRANCH-AND-BOUND ALGORITHM FOR THE JOB-SHOP SCHEDULING PROBLEM [J].
BRUCKER, P ;
JURISCH, B ;
SIEVERS, B .
DISCRETE APPLIED MATHEMATICS, 1994, 49 (1-3) :107-127
[2]  
Brucker P, 2007, MATH METHOD OPER RES, V65, P461, DOI [10.1007/s00186-006-0127-8, 10.1007/S00186-006-0127-8]
[3]  
Chen Min, 2021, ICIIP 2021: 2021 6th International Conference on Intelligent Information Processing, P49, DOI 10.1145/3480571.3480579
[4]   Design and Application of an Improved Genetic Algorithm to a Class Scheduling System [J].
Chen, Xiangliu ;
Yue, Xiao-Guang ;
Li, Rita Yi Man ;
Zhumadillayeva, Ainur ;
Liu, Ruru .
INTERNATIONAL JOURNAL OF EMERGING TECHNOLOGIES IN LEARNING, 2021, 16 (01) :44-59
[5]   A hybrid algorithm for integrated scheduling problem of complex products with tree structure [J].
Gao, Yilong ;
Xie, Zhiqiang ;
Yu, Xu .
MULTIMEDIA TOOLS AND APPLICATIONS, 2020, 79 (43-44) :32285-32304
[6]   Using solvable classes in flowshop scheduling [J].
Gruzlikov, A. M. ;
Kolesov, N. V. ;
Skorodumov, Iu. M. ;
Tolmacheva, M. V. .
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2017, 88 (5-8) :1535-1546
[7]   基于剪枝分层的柔性加工车间调度算法 [J].
桂忠艳 ;
杨静 ;
谢志强 .
控制与决策 , 2017, (11) :1921-1932
[8]   Integrated Scheduling Algorithm of Complex Product with No-wait Constraint Based on Virtual Component [J].
Guo W. ;
Lei Q. ;
Song Y. ;
Lü X. ;
Li L. .
Jixie Gongcheng Xuebao/Journal of Mechanical Engineering, 2020, 56 (04) :246-257
[9]  
Haikun T., 2019, PROC 3 INTWORKSHOP E, P93
[10]  
Hou Liang, 2004, Chinese Journal of Mechanical Engineering, V40, P56, DOI 10.3901/JME.2004.01.056