Open AccessA genetic algorithm for mode identity and the resource constrained project scheduling problem
Author(s) -
Behrouz Afshar-Nadjafi,
Amir Rahimi,
Hamid Karimi
Publication year - 2012
Publication title -
scientia iranica
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.299
H-Index - 51
eISSN - 2345-3605
pISSN - 1026-3098
DOI - 10.1016/j.scient.2012.11.011
Subject(s) - job shop scheduling , computer science , mathematical optimization , scheduling (production processes) , genetic algorithm scheduling , dynamic priority scheduling , genetic algorithm , algorithm , fair share scheduling , flow shop scheduling , mathematics , schedule , operating system
The Multi-mode Resource Constrained Project Scheduling Problem (MRCPSP) is one of the most important problems in the context of project scheduling. This paper involves a Mode identity and Resource Constrained Project Scheduling Problem (MIRCPSP) to minimize the project makespan. This problem is a more realistic model and a general case of a multi-mode resource constrained project scheduling problem in which the set of project activities is partitioned into disjoint subsets, while all activities forming one subset have to be processed in the same mode. The problem formed in this way is NP-hard, forcing us to develop a meta-heuristic algorithm, namely, the Genetic Algorithm (GA), to obtain a global optimum solution or at least a satisfying one. In addition, the Taguchi experimental design is employed as a statistical optimization technique to calibrate the effective parameters of GA in order to have a robust algorithm. The meta-heuristic algorithm is compared with an exact branch and bound procedure on the basis of a computational experiment performed on a data set constructed by the ProGen/πx project generator. Obtained results show that the performance of the proposed genetic algorithm is quite satisfactory