Model And Optimization Algorithms Research On A Special Resource-constrained Project Scheduling Problem

Being closed related to production cost and efficiency, project scheduling problem plays an important role in enterprise production. Given the variety of the production processes, the classic resource-constrained project scheduling problem (RCPSP) is not appropriate, so a new project scheduling problem model is proposed in this paper: special resource-constrained project scheduling problem (SRCPSP). On the basis of RCPSP, SRCPSP, which is proposed to solve the pratical situation, introduces the concepts of sites and jobs, adds the constraints of sites for jobs and renewable resources, and sets the objective to be minizing both the total flowtime and the total deviation time.Given the fact that the traditional RCPSP is NP-Hard, and the discussed problem is more complex, the use of heuristic alogrithm is an inevitable choice. First, a serial-schedule-generated-scheme heuristic is proposed to solve the SRCPSP, with three priority rules used for choosing the sites, renewable resources and operations. The experiments show that the heuristic algorithm can generate an initial feasible solution in a reasonable time. Next, meta-heuristic algorithms are used to optimize the initial solution. Iterated local search algorithm is firstly tested in this paper, with the anlysis of the representation of solutions, the structure of neighborhood, and the strategy of pertuation. But the experiments show that the iterated local search is not appropriate for SRCPSP, on account of the high time cost of the job moving between sites. Considering that the scheduling of operations is substantially assigning approritate site and resource, randomly assigning sites and resources for operations are tested in the paper. The results show that randomly selecting sites can optimize the solution. Therefore, max-min ant system (MMAS) is adopted in selecting sites and experiments are conducted to determine the value of parameters. The experiments show that using MMAS to optimize the selecting of sites is effective. And this method is stably better than randomly selecting sites on the condition of generating the same amount of solutions.So, with regard to the SRCPSP model proposed in this paper, the proposed MMAS-based optimization algorithm is effective, and the proper selecting of the site for the jobs plays a key role in the optimizaition of the problem.