Research And Scheduling Algorithm Implementation For The Site-based And Resource-constrained Project Scheduling Problem

The resource-constrained project scheduling problem (RCPSP) studies the schedule of a set of tasks which must satisfy the precedence and resource constraints. The main target of RCPSP is minimizing the Makespan. There are a category of problems in real production systems or service organizations, which have many additional sites with different types compared to RCPSP. All tasks should be scheduled at specific sites, resources can only serve part of sites, products or movable resources will spend some time to move from on site to another, and the target of such problem is also to minimize the Makespan. The current RCPSP studies rarely consider the site constraints thus cannot be directly used in solving the site-based problems. In this paper, we propose a new method to solve the site-based and resource-constrained project scheduling problem (SRCPSP).Firstly, we present various extensions of the constraints in RCPSP, analysis the site constraints, and describe the constraints between sites and resources, sites and products, and sites and tasks. Combining with the precedence and the site constraints, we give the definition of the same-site task, and prove its property that all the same-site tasks have to be scheduled at one site. Based on the same-site tasks, we present the definitions of Sub-net (SN) and Combined Sub-nets (CSN), and a process is proposed to compute the SN and CSN. Then the model of SRCPSP is proposed by combing the site constraints with the RCPSP model.Secondly, in order to obtain the correct scheduling results of SRCPSP with an acceptable time, we propose two rule-based heuristic scheduling algorithms, which are the Sub-net Based Search (SNBS) algorithm and the Combined Sub-net Based Search (CSNBS) algorithm. What’s more, we present all flowcharts of the SNBS and CSNBS, which can clearly illustrate the both.Finally, by using the project scheduling simulation platform, we generate two test instances, which can be used to verify the effectiveness and correctness of the SNBS and CSNBS algorithms. The experimental results show that the efficiency of SNBS is better than that of CSNBS, but the Makespan of CSNBS is smaller than that of SNBS. Besides, both SNBS and CSNBS are much better than the manual scheduling results on the both instances.