Combinatorial versus Priority Based Optimization in Resource Constrained Project Scheduling Problems by Nature Inspired Metaheuristics

Abstract

This paper explores the behavior of the Flower Pollination Algorithm (FPA) and Particle Swarm Optimization (PSO) metaheuristic algorithm in resolving Resource Constrained Project Scheduling Problems (RCPSP) that can model certain practical issues in distributed applications. A RCPSP type problem has at the input a set of activities between which there are precedence relationships and for whose execution it is necessary to allocate resources that are limited. The solution determines the order of execution of the activities with respect to the precedence relations between them and the allocation of the available resources so that the total duration is minimal. The experimental results showed that a near optimal solution can be obtained faster than with other traditional algorithms, mainly for optimization problems in the continuous space. Two versions of FPA and PSO were used, namely combinatorial and priority based optimization. Because during evolution the individuals’ position changes do not guarantee the precedence order preservation, a new tasks reordering procedure is proposed in this paper.

Keywords

• biological information theory
• evolutionary computation
• optimization
• particle swarm optimization
• scheduling algorithms