Article Preview
Top1. Introduction
The preemptive resource-constrained project scheduling problem (PRCPSP) is an important sub-problem of the resource-constrained project scheduling problem (RCPSP). The classic RCPSP is based on some assumptions, one of which is that activities are non-preemptive (Moukrim, Quilliot, & Toussaint, 2015; Cheng, Fowler, Kempf, & Mason, 2015). However, in project management practices, some activities may be preempted for the reason that resources are not in place in time or have to be re-allocated for other high-priority activities. Therefore, the PRCPSP has been proposed to relax the non-preemption assumption (Zhu, Li, & Shen, 2011). The PRCPSP allows temporary release of resources in the ongoing process, i.e., an activity can be suspended in order to release its resources for other activities, which makes project scheduling more flexible. In this paper, we mainly focus on the so called 1_PRCPSP, in which activities cannot be interrupted more than once (Ballestín, Valls, & Quintanilla, 2008).
The PRCPSP is a typical NP-hard problem. Exact methods (e.g., branch-and-bound procedure and linear programming-based algorithms) can achieve the optimal solutions of the problem but are not efficient in solving large scale problems (Buddhakulsomsiri & Kim, 2006). Hence, swarm intelligent optimization (SIO) methods (e.g., particle swarm optimization and ant colony optimization) have been adopted to solve the PRCPSP (Demeulemeester & Herroelen, 1996; Damay, Quilliot, & Sanlaville, 2007; Shou, Li, & Lai, 2015). Swarm intelligent optimization methods find the best solutions through interaction and evolution of a population of simple agents. To some extent, swarm intelligent optimization methods can be regarded as agent-based methods, and have been demonstrated to be effective for project scheduling (Ballestín, Valls, & Quintanilla, 2009; Van Peteghem & Vanhoucke, 2010; Fink & Homberger, 2013; Han et al., 2013; Shou et al., 2015). An agent in these methods represents a self-contained problem-solving entity, and is characterized with autonomy, social ability, responsiveness, self-learning and proactiveness (Shou, Xiang, Li, & Yao, 2014). The interactions such as cooperation, coordination and negotiation among these agents contribute to the solution diversity and rapid convergence (Jennings, Sycara, & Wooldridge, 1998; Xie & Liu, 2009).
We propose a multi-agent optimization (MAO) method to solve the 1_PRCPSP. A multi-agent system is established to provide a framework which includes an agent interaction system and a basic service platform. In the multi-agent system, the MAO method consists of two types of agents: activity agents that are responsible for the resource requests and activity implementation, and a schedule agent that is responsible for the resource allocation and project scheduling. Activity agents and the schedule agent negotiate with each other to do resource allocation and project scheduling, and conduct scheduling optimization through an iterative improvement process.
The remainder of this paper is organized as follows. In Section 2, we present the preemptive resource-constrained project scheduling problem and its mathematical model. Section 3 develops a multi-agent optimization method for the 1_PRCPSP. Computational experiments and results are given in Section 4. Section 5 concludes this paper.