Clonal Selection Optimization for Multi-Mode Resource Constrained Project Scheduling Problem
PAN Xiao-Ying, LIU Fang, JIAO Li-Cheng
Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education, Institute of Intelligent Information Processing, Xidian University, Xi'an 710071
Abstract Based on the analysis of the characteristics of project optimization scheduling, a clonal selection algorithm for multi-mode resource constrained project scheduling problem (CSA-MRCPSP) is proposed. It is used to obtain the optimal scheduling sequences so that the duration of the project is minimized. Some strategies are adopted such as schedule encoding, semi-random initialization, and restricted mutation operator. CSA-MRCPSP synthesizes the characteristics of project scheduling global search, diversity, and no prone to premature in immune clonal selection. Thus the cost is reduced with the optimal solution being found. The experimental results on PSPLEB show CSA-MRCPSP has good performance and it can find optimal solution in reasonable time for most instances. Furthermore, compared with other heuristic methods, CSA-MRCPSP also has some advantages, including higher optimal proportion and lower average deviation.
[1] Brucker P, Knust S, Schoo A, et al. A Branch and Bound Algorithm for Resource-Constrained Project Scheduling Problem. European Journal of Operational Research, 1998, 107(2): 272-288 [2] Mingozzi A, Maniezzo V, Ricciardelli S, et al. An Exact Algorithm for the Resource-Constrained Project Scheduling Problem Based on a New Mathematical Formulation. Management Science, 1998, 44(5): 714-729 [3] Sprecher A, Drexl A. Multi-Mode Resource-Constrained Project Scheduling by a Simple, General and Powerful Sequencing Algorithm. European Journal of Operational Research, 1998, 107(2): 431-450 [4] JóZefowska J, Mika M. Simulated Annealing for Multi-Mode Resource-Constrained Project Scheduling. Annals of Operations Research, 2001, 102(1): 137-155 [5] Bouleimen K, Lecocq H. A New Efficient Simulated Annealing Algorithm for the Resource-Constrained Project Scheduling Problem and Its Multiple Mode Version. European Journal of Operational Research, 2003, 149(2): 268-281 [6] Hartmann S. Project Scheduling with Multiple Modes: A Genetic Algorithm. Annals of Operations Research, 2001, 102(1/2/3/4): 111-135 [7] Kolisch R, Hartmann S. Experimental Investigation of Heuristics for Resource-Constrained Project Scheduling: An Update. European Journal of Operational Research, 2006, 174(1): 23-37 [8] Jiao Licheng, Du Haifeng. Development and Prospect of the Artificial Immune System. Acta Electronica Sinica, 2003, 31(10): 1540-1548 (in Chinese) (焦李成,杜海峰.人工免疫系统进展与展望.电子学报, 2003, 31(10): 1540-1548) [9] Project Scheduling Problem Library: PSPLIB [DB/OL]. [2007-10-27]. http://129.187.106.231/psplib/ [10] Liu Shixin, Wang Mengguang, Nie Yiyong. Optimization Algorithm for Solving Multi-Mode Resource-Constrained Project Scheduling Problem. Journal of Systems Engineering, 2001, 16(1): 55-60 (in Chinese) (刘士新,王梦光,聂义勇.多执行模式资源受限工程调度问题的优化算法.系统工程学报, 2001, 16(1): 55-60)
2008, Vol. 21 
