A genetic algorithm for the project scheduling with the resource constraints

• Autorzy: Klimek M.
• Języki publikacji: EN

Abstrakty

EN

The resource-constrained project scheduling problem (RCPSP) has received the attention of many researchers because it can be applied in a wide variety of real production and construction projects. This paper presents a genetic algorithm (GA) solving the RCPSP with the objective function of minimizing makespan. Standard genetic algorithm has to be adapted for project scheduling with precedence constraints. Therefore, an initial population was generated by a random procedure which produces feasible solutions (permutation of jobs fulfilling precedence constraints). Besides, all implemented genetic operators have taken sequential relationships in a project into consideration. Finally, we have demonstrated the performance and accuracy of the proposed algorithm. Computational experiments were performed using a set of 960 standard problem instances from Project Scheduling Problem LIBrary (PSPLIB) presented by Kolisch and Sprecher [1]. We used 480 problems consisting of 30 jobs and 480 90-activity instances. We have tested effectiveness of various combinations of parameters, genetic operators to find the best configuration of GA. The computational results validate the good effectiveness of our genetic algorithm.

Słowa kluczowe

EN

genetic algorithm; project scheduling; resource constraints; RCPSP

• Wydawca: Wydawnictwo UMCS
• Czasopismo: Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica
• Rocznik: 2010
• Tom: Vol. 10, no. 1
• Strony: 117--130
• Opis fizyczny: Bibliogr. 11 poz., rys., tab.

Twórcy

autor

Klimek M.

• The Institute of Computer Science, State School of Higher Vocational Education, Sidorska 102, 21-500 Biala Podlaska, Poland

Bibliografia

• [1] Kolisch R., Sprecher A., PSPLIB – a project scheduling library, European Journal of Operational Research 96 (1997): 205.
• [2] Błażewicz J., Lenstra J., Kan A. R., Scheduling subject to resource constraints – classification and complexity, Discrete Applied Mathematics 5 (1983): 11.
• [3] Herroelen W., De Reyck B., Demeulemeester E., Resource constrained scheduling: a survey of recent developments, Computers and Operations Research 25 (1998).
• [4] Kelley J. E. Jr., The critical-path method: resources planning and scheduling, Muth J. F., Thompson G. L. (Industrial Scheduling, Prentice-Hall, New Jersey, 1963): 347.
• [5] Kolisch R., Serial and parallel resource-constrained project scheduling methods revisited: theory and computation, European Journal of Operational Research 90 (1996): 320.
• [6] Holland J.H., Adaptation in natural and artificial systems (University of Michigan Press, Ann Arbor, 1975).
• [7] Michalewicz Z., Genetic algorithms + data structures = evolution programs (Springer-Verlag, 1992).
• [8] Kolisch R., Hartmann S., Heuristic algorithms for solving the resource-constrained project scheduling problem: classification and computational analysis, Handbook on Recent Advances in Project Scheduling: Recent Models, Algorithms and Applications, J. Weglarz (Kluwer Academic Publishers, 1999): 147.
• [9] Kostrubiec A., Metody generowania sasiedztwa w metaheurystycznych metodach harmonogramowania projektów. Inżynieria systemów zarzadzania. Ilościowe metody wspomagania decyzji w systemach produkcji (Wydawnictwo Politechniki Gdańskiej, Gdańsk, 2005): 45.
• [10] Bierwirth C., Mattfeld D.C., Production scheduling and rescheduling with genetic algorithms, Evolutionary Computation 7 (1999): 1.
• [11] Kolisch R., Hartmann S., Experimental investigation of heuristics for resource constrained project scheduling: an update, European Journal of Operational Research 174 (2006): 23.