Multi-Agent Optimization For Preemptive Resource-Constrained Project Scheduling Problem

The research subject of this paper is related to one of the extension issues of classic resource-constrained project scheduling problem, namely one-time preemptive resource-constrained project scheduling problem, abbreviated as 1_PRCPSP. In real projects, some of the activities may be preempted because the resources are not in place in time or due to the needs of other activities should be met first; anyway, too many such preemptions would not be allowed. This is the background of the preemptive resource-constrained project scheduling problem (PRCPSP).1_PRCPSP is a special issue of PRCPSP, in which the activities are allowed to be interrupted not more than once.Like RCPSP,1_PRCPSP is an NP-hard problem, which makes it become an important research direction to use intelligent optimization. We have exlpored the solving approaches from the perspective of multi-agent optimization based on previous studies. Specifically, our research methods include particle swarm optimization (PSO), ant colony optimization (ACO) and multi-agent optimization (MAO). PSO and ACO are both belong to swarm intelligent optimization, as well as a kind of MAO.PSO is first used in problem solving, and the corresponding algorithm is denoted by 1PRCPSP_PSO. We design four coding methods, including an activity list based encoding, a priority value based encoding, an activity list and preemptive point based encoding, and a priority value and preemptive point based encoding. The serial schedule generation scheme (SSGS) and the one-preemption serial schedule generation scheme are adopted for decoding, while the ideology of peak crossover operator (PX) plays an important role in the particle update mechanism. Computational experiments on the standard RCPSP data sets from PSPLIB show that our 1PRCPSP_PSO not only has good convergence, but also can obtain competitive results.Second, we apply ACO on 1_PRCPSP and design the 1PRCPSP_ACO. The algorithm also draws on the ideology from peak crossover, in which we design a peak path pheromone enhancement mechanism that an additional enhancement operating would be imposed to the peak path of the best solution in current generation. Algorithm 1_SSGS is used to transfer the an ant's path into a feasible schedule. Similarly, we use RCPSP data sets in PSPLIB to assess the convergence and effectiveness of the algorithm.Finally, we propose a 1PRCPSP_MAS architecture and the corresponding optimization 1PRCPSP_MAO. The 1PRCPSP_MAS architecture contains two types of agents:activity agents which are responsible for resource requests and implemention of their activities, and a schedule agent which is in charge of resource allocation and project scheduling. The activity agents and the schedule agent carry out resource allocation and project scheduling through negotiation mechanism; and they achieve the optimal solution of the problem through an iterative improvement process. Different with the former two algorithms,1PRCPSP_MAO has two features of both simulation and optimization. Mechanism for negotiation between agents, is designed to simulate the situation that, in real project, communications often occur among persons in charge or departments to resolve conflict or to change project plans; and iterative improvement process makes the algorithm to have a function of problem optimization.The results of this paper are of theoretical and practical significance, which enrich the research methods of preemptive resource-constrained project scheduling problems, while expand the applications of particle swarm optimization, ant colony optimization and multi-agent optimization. The multi-agent system we designed can be applied to decision making in project schedule management, providing a multi-agent system based simulation and optimization method for project overall assessment in project planning phase.