Title :
A hybrid genetic algorithm for the resource constrained multi-project scheduling problem
Author :
Li, Jinghua ; Liu, Wenjian
Author_Institution :
Sch. of Mechatronics Eng., Harbin Inst. of Technol.
Abstract :
Due to the widespread availability of the Internet, large scale distributed projects in manufacturing are becoming popular. Besides resource constraints, there exist precedence constraints among activities within each project. This paper presents a hybrid genetic algorithm to solve the resource-constrained multi-project scheduling problem (RCMPSP), which is well known NP-hard problem. Objectives described in this paper are to minimize total project time of multiple projects. The chromosome representation of the problem is based on activity lists. The proposed algorithm was operated in two phases. In the first phase, the feasible schedules are constructed as the initialization of the algorithm by permutation based simulation and priority rules. In the second phase, this feasible schedule was optimized by genetic algorithm, thus a better approximate solution was obtained. Finally, after comparing several different algorithms, the validity of proposed algorithm is shown by a practical example
Keywords :
PERT; critical path analysis; genetic algorithms; manufacturing resources planning; minimisation; scheduling; Internet; NP-hard problem; chromosome representation; genetic algorithm; large scale distributed manufacturing project; project time minimization; resource constrained multiproject scheduling problem; Availability; Genetic algorithms; Job shop scheduling; Large-scale systems; Mathematical model; Mechatronics; NP-hard problem; Processor scheduling; Resource management; Space exploration;
Conference_Titel :
Emerging Technologies and Factory Automation, 2005. ETFA 2005. 10th IEEE Conference on
Conference_Location :
Catania
Print_ISBN :
0-7803-9401-1
DOI :
10.1109/ETFA.2005.1612707