A hybrid algorithm for integrated scheduling problem of complex products with tree structure
- PDF / 2,846,344 Bytes
- 20 Pages / 439.642 x 666.49 pts Page_size
- 97 Downloads / 205 Views
A hybrid algorithm for integrated scheduling problem of complex products with tree structure Yilong Gao1 · Zhiqiang Xie1
· Xu Yu2
Received: 25 October 2019 / Revised: 20 July 2020 / Accepted: 28 July 2020 / © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Due to the poor design of encoding methods or evolutionary operators in previous genetic-algorithm-based integrated scheduling algorithms, this paper proposes an integrated scheduling algorithm based on a hybrid genetic algorithm and tabu search. Firstly, an encoding method based on a dynamic schedulable operation set is proposed. This method cannot only reflect the priority constraints among operations, but also avoid the problems of imposing constraints and missing solution space in previous division encoding method. Secondly, a decoding method based on machine idle time driving is presented to handle the scheduling order of operations on different machines. Then, two different discrete crossover and mutation operators are designed to ensure the legitimacy of the processing sequence of the same machine. Finally, a local search strategy based on tabu search is shown to enhance the search capability for superior solutions. The algorithm is tested by the randomly generated instances, and the experimental results indicate that the proposed algorithm is effective and can achieve satisfactory performance. Keywords Processing · Assembly · Tree-structured product · Integrated scheduling problem · Hybrid algorithm
1 Introduction The production scheduling problem is a typical non-deterministic polynomial (NP) hard problem. It usually treats processing [6, 7] and assembly [9, 11] as two independent stages. The final product is assembled by a series of components, and these components may be parts or sub-assemblies (SUAs) which have been previously assembled. However, with the increase of people’s demand for personalized customized products, if the traditional production method of “processing first and assembly later” is followed, the inherent parallel Zhiqiang Xie
[email protected] 1
School of Computer Science and Technology, Harbin University of Science and Technology, Harbin, 150080, China
2
School of Information Science and Technology, Qingdao University of Science and Technology, Qingdao, 266061, China
Multimedia Tools and Applications
relationship among operations of the complex product will inevitably be broken, affecting the entire product manufacturing cycle. Therefore, in this paper, we investigate the integrated scheduling problem [20] of complex products with a tree structure. It is different from the previous flow shop scheduling problem [8, 16] and the job shop scheduling problem [18, 28], because we consider the processing and assembly of parts at the same time. In other words, in this production system, it involves not only machines used for parts processing but also machines used for assembling parts. The scheduling object of this problem is a complex product with tree structure as shown in Fig. 1. It can be see
Data Loading...
