Open Access

ARTICLE

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

by Zhiqiang Xie^1,*, Haikun Teng¹, Anak Agung Ayu Putri Ardyanti¹, Xu Yu²

1 Harbin University of Science and Technology, Harbin, 150000, China
2 Qingdao University of Science and Technology, Qingdao, 266061, China

* Corresponding Author: Zhiqiang Xie. Email:

Computer Modeling in Engineering & Sciences 2023, 134(1), 179-200. https://doi.org/10.32604/cmes.2022.021550

Received 20 January 2022; Accepted 16 March 2022; Issue published 24 August 2022

Abstract

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.

---

Keywords

---