A Multi-Agent Optimization Method for Preemptive Resource-Constrained Project Scheduling

A Multi-Agent Optimization Method for Preemptive Resource-Constrained Project Scheduling

Yongyi Shou (School of Management, Zhejiang University, Hangzhou, China), Wenjin Hu (Zhejiang University, Hangzhou, China), Changtao Lai (Zhejiang University, Hangzhou, China) and Ying Ying (Zhejiang University, Hangzhou, China)
Copyright: © 2019 |Pages: 13
DOI: 10.4018/IJITPM.2019010102

Abstract

A multi-agent optimization method is proposed to solve the preemptive resource-constrained project scheduling problem in which activities are allowed to be preempted no more than once. The proposed method involves a multi-agent system, a negotiation process, and two types of agents (activity agents and schedule agent). The activity agents and the schedule agent negotiate with each other to allocate resources and optimize the project schedule. Computational experiments were conducted using the standard project scheduling problem sets. Compared with prior studies, results of the proposed method are competitive in terms of project makespan. The method can be extended to other preemptive resource-constrained project scheduling problems.
Article Preview
Top

1. 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.

Complete Article List

Search this Journal:
Reset
Open Access Articles
Volume 12: 4 Issues (2021): Forthcoming, Available for Pre-Order
Volume 11: 4 Issues (2020): 2 Released, 2 Forthcoming
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing