A Permutation-Based Bees Algorithm for Solving Resource-Constrained Project Scheduling Problem

A Permutation-Based Bees Algorithm for Solving Resource-Constrained Project Scheduling Problem

Mohamed Amine Nemmich (Department of Computer Science, University Mustapha Stambouli of Mascara, Mascara, Algeria), Fatima Debbat (Department of Computer Science, University Mustapha Stambouli of Mascara, Mascara, Algeria) and Mohamed Slimane (Université de Tours, Laboratoire d'Informatique Fondamentale et Appliquée de Tours (LIFAT), Tours, France)
Copyright: © 2019 |Pages: 24
DOI: 10.4018/IJSIR.2019100101

Abstract

In this article, a novel Permutation-based Bees Algorithm (PBA) is proposed for the resource-constrained project scheduling problem (RCPSP) which is widely applied in advanced manufacturing, production planning, and project management. The PBA is a modification of existing Bees Algorithm (BA) adapted for solving combinatorial optimization problems by changing some of the algorithm's core concepts. The algorithm treats the solutions of RCPSP as bee swarms and employs the activity-list representation and moves operators for the bees, in association with the serial scheduling generation scheme (Serial SGS), to execute the intelligent updating process of the swarms to search for better solutions. The performance of the proposed approach is analysed across various problem complexities associated with J30, J60 and J120 full instance sets of PSPLIB and compared with other approaches from the literature. Simulation results demonstrate that the proposed PBA provides an effective and efficient approach for solving RCPSP.
Article Preview
Top

Introduction

Scheduling is a decision-making process that deals with the allocation of resources to tasks over given time periods with the all constraints provided (Baker, 1974). It is also considered as the optimization of a problem, with the goal of optimizing one or more objectives. Scheduling is widely used on a regular basis in many manufacturing and service industries. Often, the process includes some limitations like the capacity of vehicles, working time of employees, limited funds etc. Scheduling problems differ markedly from case to case (Đumić, Šišejković, Čorić, & Jakobović, 2018).

One of the most intractable classical combinatorial optimization problems in the context of scheduling is resource constrained project scheduling problem (RCPSP). It was proved to be strongly NP-hard (Blazewicz, Lenstra, & Kan, 1983). The main objective is to schedule the activities such that the project completion time (makespan) can be minimized, while involving precedence (temporal) and resources constraints (Chen, 2011).

As an active research area, the RCPSP has a wide range of applications in logistics, manufacturing and project management (Bukata, Šůcha, & Hanzálek, 2015). It is also at the core of many project scheduling problems arising in a variety of industries and other applications, which include software development, rolling ingots production in aluminium industry, medical research scheduling, sports league scheduling, audit scheduling, scheduling of port operations, market research interviewers scheduling, assembly shop scheduling, instruction scheduling for parallel processors, batch production scheduling, employee scheduling, school and university timetabling, and resource-constrained scheduling for disaster and recovery, among many others (Riley & Rego, 2018).

Many real-life problems can be formulated as RCPSP, and due to its complexity, RCPSP became a very attractive field for researchers either in scheduling field or in operations research. Numerous numbers of researches have proposed various approaches which can be dispatched into three main classes: deterministic (or exact), heuristics and meta-heuristic methods (Hartmann & Briskorn, 2010).

Exact approaches have been explored firstly to solve the RCPSP such as Integer Programming, Implicit Enumeration, Branch-and-bound, Dynamic Programming (Đumić et al. 2018). Exact approaches are typically used to solve relatively small-sized instances optimally since the execution time needed increases impractically with the size of the problem (Akbari, Zeighami, & Akbari, 2012). Therefore, heuristics or a meta-heuristic would be more suitable for the large-sized problems in a satisfactory manner. These methods find the optimal or near optimal schedule in reasonable amount of time and memory space (Đumić et al., 2018).

Several heuristics approaches have been developed and try to provide good solutions by considering two main components, namely the Priority Rule based heuristics and Schedule Generation Scheme (SGS) (Fahmy, Hassan, & Bassioni, 2014). Priority rules are particularly useful in cases where cheaper, more intuitive solutions are preferred over optimality, something that is commonly seen in smaller manufacturing environments. Priority rules are mainly used to arrange the activities list in an order which will generate a good solution. Various priority rules have been proposed such as: latest start time (LST), latest finish time (LFT), resource scheduling method (RSM), improved resource scheduling method (IRSM), worst case sack (WCS), shortest processing time (SPT), minimum slack (MSLK), most immediate successors (MIS), most total successors (MTS), least float per successor (LFS), greatest rank positional weight (GRPW), most total successors (MTS), longest path following (LPF), and random (Rand) (Kolisch & Hartmann, 1999). The schedule generation scheme (SGS) is used to create a schedule depending on priority rule. There are two different types of SGS: Serial SGS based on activity incrementation, and Parallel SGS based on time incrementation (Kolisch & Hartmann, 1999). Priority based-methods can solve large-sized RCPSP problem within acceptable time, but they are hard to adapt to the constraints of problems dynamically (Chen, 2011).

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
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