An Approach With Nested Partition For Two Kinds Of Resource-Constrained Project Scheduling Problem

Classic resource-constrained project scheduling problem and progress paymentproblem are universal and tough problem that contractor convinces in project. How toschedule project under constrained resource to minimum the project makespan and howto schedule project as well as decide the payment schema negotiating with client tomaximize its net present value is the most concerned problem for contractor and winattention from scholars all the time.Nested partition is applied in this paper to solve the two kinds ofresource-constrained project scheduling problem. First, relevant time factors involved ineach activity is computed by critical path method to get the initial searching space. Thenthe activity is selected and its range is partitioned to get the sub searching region.Sampling is executed in each sub region respectively and serial schedule and parallelschedule are used in sampling method. The most promising region is estimated byselecting the sub region that most possibly get the best solution and the other isaggregated as the surrounding region of the iteration. If the iteration depth is bigger than1, sampling is executed in the surrounding region of the last iteration. Comparing thepromise index of promising region of this iteration and surrounding region of last region,if the promising region is better, move on, else backtracking operation is executed. Sincenested partition is open and flexible, different strategies are set according to thecharacteristics of two problems.Comparatively the result achieved by nested partition is good and better than mostheuristic algorithm which is especially obvious in the large scale instance. It is alsoimproved in computing time especially in large scale instance and instance that issampling in serial schedule. Solution of the two problems would provide importantdecision support for contractor to reasonably schedule activities and decide paymentschema with client as well as well as determination of the factors in the payment.