A branch-and-bound embedded genetic algorithm for resource-constrained project scheduling problem with resource transfer
- PDF / 822,102 Bytes
- 35 Pages / 439.37 x 666.142 pts Page_size
- 16 Downloads / 224 Views
A branch-and-bound embedded genetic algorithm for resource-constrained project scheduling problem with resource transfer time of aircraft moving assembly line Yifei Ren1
· Zhiqiang Lu1
· Xinyi Liu1
Received: 13 April 2019 / Accepted: 31 January 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract Motivated by the resource transfer time between different stations in the aircraft moving assembly line, this study addresses the resource-constrained project scheduling problem with resource transfer time, which aims at minimizing the makespan of the project while respecting precedence relations and resource constraints. We assume that the resource transfer time is known and deterministic in advance. The resource transfer time and the precedence of activities are coupled with each other, which means that the transfer time of resource changes according to the precedence of activities, while the transfer time affects the decision of the precedence of activities at the same time. We present a linear mathematical model for the problem and propose a branchand-bound embedded genetic algorithm with a new precedence-based coding method which adapts to the structure of the problem. A series of experimental tests reveal that the branch-and-bound embedded genetic algorithm outperforms the existing algorithm proposed in the literature in finding high quality solutions. Keywords Project scheduling · Resource transfer time · Branch-and-bound · Genetic algorithm · Aircraft moving assembly line
B
Zhiqiang Lu [email protected] Yifei Ren [email protected] Xinyi Liu [email protected]
1
School of Mechanical Engineering, Tongji University, Caoan Road 4800, Mechanical Building A443, Shanghai City 201804, People’s Republic of China
123
Y. Ren et al.
1 Introduction Aircraft moving assembly line has initiated a modern aircraft assembly process which is being adopted by aviation giants as its high efficiency, high quality stability and continuous production according to various market demand rates. Aircraft assembly line production is a complex project involving job operation, resource allocation and so on, which is similar with project scheduling problem. In addition, the intention of the aircraft moving assembly line is to assemble an aircraft with the highest efficiency under the constant resources. As a result, we abstract the aircraft assembly line production scheduling problem as resource-constrained project scheduling problem (RCPSP) and search for further optimization methods to reduce the makespan of the aircraft assembly line. RCPSP has been studied extensively in the past few decades, the common RCPSP aims at minimizing the makespan of the project subject to precedence constraints and resource constraints, and is known to be NP-hard [4]. Meanwhile, the extensions of RCPSP such as multi-mode problems [6, 13, 46], multi-project problems [23, 24, 41], multi-skill problems [1, 33, 45] and so on are also considered. Currently, various branch-and-bound algorithms to solve RCPSP have been propos
Data Loading...
