Heuristic Research On A Resource Constrained Project Scheduling Problem

According to the production requirements of a certain enterprise, a special resource-constrained project scheduling problem (RCPSP) is proposed by adding the site concept and some special relationships between tasks on the classical RCPSP. The objective of this problem model is minimizing makespan. This model is put forward first time in the past research and has the important research value. Then a constructive heuristic algorithm is presented for solving the new model which is proposed by us.First of all, this paper introduces the influence among resources, products, sites and tasks in detail after adding the site concept and describes the differences in constraints with RCPSP according to the analysis of the actual situation. Secondly, we propose a special resource-constrained project scheduling problem (SRCPSP) based on sufficient constraints and elaborate SRCPSP’s objective. In the proposed problem model, the constraints of sites for jobs and the constraints among different renewable resources are added. Finally, a constructive heuristic algorithm, based on the serial scheduling generation scheme, is presented for SRCPSP. In the algorithm, three heuristic rules are used for the selection of the site for a job, the assignment of the renewable resources for an operation and the choice of the operation preferred to be scheduled, respectively. As for the site selection, the one which is available earlier and the most operations can be scheduled on is superior. While for the assignment of the renewable resources, the earliest available and the most capable ones are preferred. For the choice of the operation, the rule of smallest completion time is applied. The method to solve the possible deadlock during the construction is also designed.In the end, we design an experiment and describe the practical instances about the experiment. And experimental results on three practical instances show that the proposed algorithm can construct reasonable solutions for the instances in negligible time, saving a lot of human costs and achieving better solutions.