Optimization And Application Research On Resource-Constrained Project Scheduling Problem Based On The Genetic Algorithm

Resource-Constrained Project Scheduling Problem(RCPSP) is an important Scheduling Problem. It focused on studying reasonable arrangement of starting and finishing time of activity in the project when program purpose is satisfied under conditions of timing and resource constrain to optimize some management purpose, such as shortest construction period, smallest cost and resource leveling. Theoretically,this problem belongs to NP-hard. Various models and many combinatorial optimization problems are special situation of RCPSP.Besides, RCPSP is widely used in construction, software and manufacturing industry. Therefore, research on RCPSP has important theoretical and realistic significance. The paper mainly studies the following contents:(1) As for classic RCPSP, the paper designs a new intelligent optimization algorithm---teaching genetic algorithm for classic resource-constrained program by combining genetic algorithm and teaching-learning algorithm. This algorithm designed a twice crossover operation-based on two-stage search fast algorithm in teaching algorithm.Once cross happens between students and teachers. The crossover operation proceeds between students with crossover probability. The crossover operation design makes teaching genetic algorithm jump out of local optimization effectively to gain better scheduling plan. The experiment verifies effectiveness of algorithm by scheduling problem of classic resource constraint program in standard database PSPLIB.(2) In practical program scheduling, activities of program have one or more execution mode in operation. Each mode represents a resource requirement amount and corresponding combination of sustaining time.Different duration has different resource requirement. It has practical significance to take Resource-Constrained Project Scheduling Problem with multi-processing mode as expansion of classic RCPSP. The paperproposes hybrid genetic algorithm against MRCPSP. Before calculating,the algorithm has to preprocess data in program, then creates original group based on topological sorting and at last designs mutation operation based on neighborhood search to improve local search capability of genetic algorithm. The experiment part tests benchmark problems such as J18 and J20 in standard database, verifying the effectiveness of the algorithm.(3)Theory and algorithm serve for practice and provide practical solutions for program management in modern program. To verify whether hybrid genetic algorithm proposed in the paper can be applied to concrete practice, it make case study against MRCPSP. The result shows that intelligent algorithm not only enriches solutions of multi-processing mode RCPSP but also expands application field of genetic algorithm.