Multi‐mode resource‐constrained project scheduling using modified variable neighborhood search heuristic

• Date: 01 January 2020
• Author: Alireza Abbasi,Ripon K. Chakrabortty,Michael J. Ryan
• DOI: http://doi.org/10.1111/itor.12644
• Published date: 01 January 2020

Intl. Trans. in Op. Res. 27 (2020) 138–167

DOI: 10.1111/itor.12644

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Multi-mode resource-constrained project scheduling using

modified variable neighborhood search heuristic

Ripon K. Chakrabortty , Alireza Abbasi and Michael J. Ryan

Capability Systems Centre, School of Engineering and InformationTechnology, University of New South Wales,

Canberra 2600, Australia

E-mail: r.chakrabortty@adfa.edu.au, ripon_ipebuet@yahoo.com[Chakrabortty]; a.abbasi@unsw.edu.au [Abbasi];

m.ryan@adfa.edu.au [Ryan]

Received 3 April 2018; received in revised form 8 February 2019; accepted 12 February 2019

Abstract

This paper aims at providing a fast near-optimum solution to the multi-mode resource-constrained project

scheduling problems (MRCPSPs), for projects with activities that have known deterministic renewable and

nonrenewable resource requirements. The MRCPSP is known to be nondeterministic polynomial-time hard

and has been solved using various exact, heuristic, and meta-heuristic procedures. In this paper, a modified

variable neighborhood search heuristic algorithm is used as an advanced optimization technique that suits

scheduling problems. For the experimental study, we have considered a standard set of 3929 multi-mode

benchmark instances from the project scheduling library with a range of projects comprising 10–30 activities.

Moreover, for a better comparison, this researchalso considers a standard set of 4320 newly developed multi-

mode instances from MMLIB50, MMLIB100, and MMLIB+datasets.With the limit of 50,000 schedules on

these datasets, our proposedalgorithm provides better makespan for 106, 34, and 1601 instances,respectively,

which justifies the efficiency of the proposed algorithm, particularly for projects with a larger number of

activities. The results reportedin this paper can be used as a benchmark for other researchers to compare and

improve.

Keywords:resource constraints; multi-mode RCPSPs; neighborhood search; heuristics

1. Introduction

The elemental scheduling problem in a deterministic project frame is the so-called resource-

constrained project scheduling problem (RCPSP), which consists of determining a baseline schedule

that satisfies both the finish-start and the zero-lag precedence constraints between activities and

the renewable resource constraints, under the objective of minimizing project duration. Scheduling

involves the allocation of given resources to activities while determining the start and completion

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

R.K. Chakrabortty et al. / Intl. Trans. in Op. Res. 27 (2020) 138–167 139

times of those associated activities. Due to scarce resources, the allocationof those resources makes

the solution process more complex and so severalcompromises have to be made to solve the RCPSP

to the desired level of near-optimality (Chakrabortty et al., 2017, 2018b).

The multi-mode resource-constrained project scheduling problem (MRCPSP) is an extension

of the conventional single-mode RCPSP, in which the duration of each task is a function of the

level and type of resources committed to it, and the project interactions that result from the

utilization of shared resources that must be taken into consideration (Zapata et al., 2008). Due to

its applicability, MRCPSP is important and has been gradually paid more attention in diversified

fields. However, MRCPSP is noticeably more complex than single-mode RCPSP, which is itself

nondeterministic polynomial-time hard (NP-hard) (Elloumi and Fortemps, 2010). When there are

at least two nonrenewable resources, the problem of finding a feasible solution is already NP-

complete (Kolisch and Drexl, 1997). According to the classification scheme of Herroelen et al.

(1999), MRCPSP is denoted as m,1T|cpm,disc,mu|Cmax (i.e., mresource types that can be both

renewable and nonrenewable | strict finish and start precedence constraints with zero time-lag,

activities that have multiple execution modes, activity resource requirements are a discrete function

of activity duration | the objective is to minimize project makespan).

In the case of MRCPSPs, when the process allows the choice of modes, further complexity is

added that enlarges the search space for finding the optimize/appropriate resources for activities

(Kyriakidiset al., 2012). There has been a significant number of exact methods, and heuristic, meta-

heuristic, and hyper-heuristic approaches for solving different RCPSPs and MRCPSPs (Elsayed

et al., 2017; Almeida et al., 2019). Among them, the exact methods for MRCPSP include the

“branch and cut” algorithm (Zhu et al., 2006), the “tree-based branch and bound” algorithm

(Hartmann and Drexl, 1998; Cheng et al., 2015), and the “linear programming-based” algorithm

(Kopanos et al., 2014). However, as stated by Sprecher and Drexl (1998), MRCPSP with at least 20

activities and three modes per activity cannot be solved by exact optimization procedures within a

reasonablecomputational time that would be of use in a near-real-time application.This incapability

of exact methods for MRCPSPs leads to the need for research on heuristic and/or meta-heuristic

approaches.

Further,the increasing interest in optimization and operations research formeta-heuristics during

recent years has also resulted in the development of several meta-heuristic solution procedures that

are available for application to the MRCPSP. A wide variety of meta-heuristic strategies, solution

representations, and schedule generation schemes has been proposed to develop the most efficient

algorithms (Van Peteghem and Vanhoucke, 2014). Some very recent heuristic and meta-heuristic

solution procedures for the classical RCPSP and MRCPSPs include the works of Basnet (2016),

Chakrabortty et al. (2014, 2016, 2018a), Cheng and Tran (2016), Damak et al. (2009), Messelis

and De Causmaecker (2014), Palacio and Larrea (2017), Rezaeian et al. (2015), Schnell and Hartl

(2016), Sebt et al. (20175, 2015), Soliman and Elgendi (2014), Wauters et al. (2016), and Zamani

(2017).

In general, a schedule is represented by a validsequence of activities, which satisfies the precedence

constraints. To generate valid sequence of activities, numerous researchers have applied variable

neighborhood search (VNS). Similarly, among heuristic and/or meta-heuristic approaches, VNS

is another very powerful meta-heuristic approach for solving many combinatorial optimization

problems such as the vehicle routing problem (Mouthuy et al., 2015; Monroy-Licht et al., 2017;

Polat, 2017), inventory routing problem (Gruler et al., 2020), and the traveling salesman problem

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation of OperationalResearch Societies