Rollout Algorithm For Preemptive Project Scheduling With The Constraints Of Time Windows On Resources

Resource Constrained Project Scheduling Problem mainly study the problem that the activity can not be split and the resources only have a skill as well as the resource canget in the whole time. With the development of society, project and resourcecharacteristics have gradually changing. Some of the key characteristics of resourceshave time window, the resource possessed multi-skill, and the activities allow thediscontinuous, the activities can be properly broken up.In this paper, Preemptive Project Scheduling Problem with the Constraints of TimeWindows on Resources and Preemptive Project Scheduling Problem with the Constraintsof Time Windows on Multi-Skill Resources are studied separately. Firstly the integerprogramming model is established, and then Rollout algorithm based on priority rule isdesigned to solve the problem according to the model. In the case of single skill, directlyproviding a summary of skills and demand, to determine whether meet the resourceconstraint,while in the case of multi-skill, the greedy strategy is proposed to determinewhether meet the resource constraints, and finally the case is used to test theperformance of the algorithm, through designing the resource skills matrix and resourcetime window, the110cases in PSPLIB is changed to the Preemptive Project SchedulingProblem with the Constraints of Time Windows on multi-skill Resources. Through testthe different proportion of multi skill, multi skill and the time window to analysis thesensitivity of the parameter.Experimental results show that in the small scale of the problem, the Rolloutalgorithm could find optimal solution with large probability while the split time of theactivity is less than the CPLEX software; in the massive scale of the problems, CPLEXsoftware can not solve the problem while the proposed algorithm can find the solution ina short time. Meanwhile, split feature of the activities and multi-skill character ofresource could shorten duration of the project. Finally, sensitivity parameter is largewhen the proportion of single skill resources is large while small when the proportion ismedium or massive.