Research On The Resource-Constrained Project Scheduling Problem With Its Application

Within the classical resource-constrained project scheduling problem(RCPSP),the activities of a project have to be scheduled such that the makespan(cost,etc.) of the project is minimized.RCPSP continues to be an active area of research attracting in recent years increasing interest from researchers and practitioners in the search for better solution procedures.The purpose of this paper is to introduce some new optimization algorithms to solve three kinds of RCPSP:classical RCPSP,preemptive RCPSP and resource-constrained multi-project scheduling problem(RCMPSP).To solve the classical RCPSP,we introduce a particle swarm optimization(PSO) with dynamic inertia weight to adjust the inertia weight with the fitness of particles.Three PSO procedures based on different solution representations are propsed—Priority Value Based Particle Swarm Optimization(PVPSO),Priority Rule Based Particle Swarm Optimization (PRPSO),and Permutation Based Particle Swarm Optimization(PEPSO).PVPSO employs a new initialization method in which the heuristic information is added to the classical randomized method to improve the performance of the algorithm.PRPSO searches the optimal combination of priority rules based on PSO.PEPSO adopts the one-point crossover technique into the updating of particles,and makes use of a local search to help the particle escape the local optimum.Numerical results obtained from the PSPLIB show that these PSOs yields better results than several heuristic procedures presented in the literatureThis paper provides the PSOs for the preemptive RCPSP.The experiments on Patterson show that the acitivity splitting can short the makespan of project.This paper develops a new wiest's justification in which the activity splitting is applied to predict whether the schedule could be improved.The new Wiest's justification with prediction(PWiest) was applied to improve the performance of algorithms,such as priority-rule heuristic method,particle swarm optimization and ant colony system and so on,for classic RCPSP,and the algorithms are approved with these experiments on PSPLIB.Finally,the paper studies resource-constrained multi-project scheduling problem (RCMPSP) in which each project has a priority.For RCMPSP without coupling sets,we propose a topological travel optimization algorithm in which various influence factors are considered(such as resources constraints,successors,critical-path-activity-first,etc.).For RCMPSP with coupling sets,we present an uncouple method to deal with the coupling sets in DSM,which is used to represent the coupling relations between activities.The algorithms have been applied to the development of the Ship Design Plan Management System of Dalian Heavy Industry Ship Yard.