Research On Flexible Resource-Constrained Project Scheduling Problem Based On Hybrid Genetic Algorithm

With the development of the project more and more complex,efficient and reasonable project scheduling in the project management is more and more important,so it is of great practical significance to research the algorithm to solve the problem of project scheduling problem.Flexible Resource-constrained Project Scheduling Problem(FRCPSP)is a kind of problem which is very close to the reality project development.Flexible resources represent resources with multiple skills.There are two kinds of constraints in this kind of problem: task execution order constraint and flexible resource constraint.The objective of the problem is to give the resource allocation and the starting time of each task in the project under the constraint condition in order to reach the goal of the shortest project duration.FRCPSP is NP-hard problem.Nowadays,the research on the algorithm to solve this problem is mainly focused on the heuristic algorithm.In order to be more close to the actual project development,the milestone task is added to the traditional FRCPSP,and the corresponding mathematical model is established.Genetic Algorithm(GA)has a very good effect in solving the problem of project scheduling.A hybrid genetic algorithm(HGA)is designed to solve FRCPSP based on Chaos Particle Swarm Optimization(CPSO)and GA.CPSO is used to optimize the initial population of the algorithm to reduce the number of genetic algorithm iterations and to generate new individual to update populations when the population size changes.This paper further studies the characteristics of flexible resource allocation and designs a flexible resource allocation strategy based on maximum flow model and Ford-Fulkerson algorithm,which can make full use of idle resources for task scheduling.Finally,the revised example of Project Scheduling Problem Library(PSPLIB)is used to test the HGA program,and compare the performance of different algorithms in order to verify the effectiveness of the HGA.The HGA is applied to the actual system.