A Hybrid Genetic Algorithm For Resource-Constrain Project Scheduling Problems

The resource-constrained project scheduling problem (RCPSP) is to schedule the activities such that precedence and resource constraints are satisfied while optimizing some managerial objective. The problem is a typical NP-hard problem. And many well-known optimization problems are the special cases of RCPSP. Thus the researches in this area are very important in both theory analysis and practical applications. This paper studies the improved genetic algorithm for solving resource-constrained project scheduling problem.Fistly. combined the dual-evolution structure of Cultural Algorithm (CA) with the evolution advantage of multi-agent evolutionary algorithm and flexible encoding genetic algorithm, multi-agent cultural genetic algorithm (MACGA) is proposed to solve resource-constrained project scheduling problem. The algorithm sets the population space and belief space. And the agent in each space increases its energy through the operators such as competitive and cooperation with the environment and the self-study operator. The interaction of two spaces is by the acceptance operation and impact operation with synchronous transmission mode regularly.In order to test the interoperability of algorithms, number of standard test functions are calculated with several kinds of algorithms. Test results show that MACGA not only can effectively out of local optimum, but also improve the efficiency of the algorithm convergence.Secondly, the improved algorithms are applied to the classical resource-constrained project scheduling problem. Algorithm uses the decimal encoding.The violation of activity precedence that exists within potential genetics can well be detected by using the activity matrix.The resource conflict among activities of projects can be avoided by means of preempt-based resources assignment. The standard PSPLIB problems of the classical RCPSP are used as simulation example to verify the validity and effectiveness of the algorithm.Lastly, taking into account that the actual project work is often in a variety of implementation models. the algorithm is applied to the multi-mode resource-constrained project scheduling problem. Owes to resource requirements and execution time in each mode is different, and different execution time corresponding to different resource inputs, two-dimensional coding is used, and the various operations is defined in the algorithm.The simulation results of the standard PSPLIB problems with multi-mode resource- constrained project scheduling problem show that the algorithm not only possesses the global convergence but also the higher convergent speed. It is an effective algorithm for large scale scheduling problem.