Title: A novel discrete particle swarm optimisation for scheduling projects with resource-constraints

Authors: Shih-Chieh Chen; Chiung-Fen Cheng; Ching-Chiuan Lin

Addresses: Department of Multimedia Game Design, Overseas Chinese University, Taiwan ' Department of Multimedia Game Design, Overseas Chinese University, Taiwan ' Department of Information Technology, Overseas Chinese University, Taiwan

Abstract: The objective of resource-constrained project scheduling problem (RCPSP) is to schedule the operating start time of each activity in a project subject to resource constraints and precedence constraints such that the makespan of this project is minimised. Being an NP-hard problem, evolutionary algorithms are proposed to solve RCPSP. Particle swarm optimisation (PSO) is a nature-inspired algorithm to solve optimisation problems that is performed by the movements of particles, presented by real-valued vectors, along the trajectories in the solution space of an optimisation problem to search the optimal solution. Such a mechanism and representation of particles are difficult to apply PSO to solve discrete combinatorial optimisation problems. Therefore, in this paper, we propose a novel discrete particle swarm optimisation (DPSO) algorithm to solve RCPSP. A new problem-based similarity measure of permutations, the position representation, the direction and velocity of movement representation of permutations in the solution space are also proposed in DPSO such that the particles can search the optimal solution in a discrete solution space. The computational results show that DPSO is compatible to other state-of-the-art algorithms in solving RCPSP.

Keywords: resourced-constrained project scheduling; particle swarm optimisation; PSO; similarity measure; evolutionary algorithm.

DOI: 10.1504/IJCPS.2018.093078

International Journal of Cognitive Performance Support, 2018 Vol.1 No.2, pp.103 - 116

Received: 06 Oct 2015
Accepted: 13 Dec 2015
Published online: 09 Jul 2018 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article