Research on Model and Algorithm for Uncertain RCPSP with Job Reworking

To address the problems, that are the extension of project duration and the waste of idle resources, caused by changes which job reworking bring to the schedule, this paper constructed a mathematical model with objective function, the minimum sum of total project duration and deviation between planned starting time and actual starting time of jobs, and proposes a kind of reactive scheduling algorithm to solve the problem. Firstly, as the unqualified job is supposed to be restored, the reworking job is inserted after it and a new project network is formed of reworking job and unexecuted jobs. Secondly, in order to reduce the idle waste of resources, the parallel SGS algorithm based on the job combination is used to arrange the jobs and obtain the feasible scheduling plan. Then, the scheduling result is further optimized by improved cuckoo search algorithm with adaptive step-size. Finally, the effectiveness of the algorithm was tested on sets of benchmark instances of different scales from PSPLIB. The instance verification shows that the algorithm proposed in this paper has obvious advantages in optimizing project duration compared with other algorithms, and the resource utilization rate of project can reach to 90.64%.