An evolutionary implicit enumeration procedure for solving the resource-constrained project scheduling problem

An evolutionary implicit enumeration procedure for solving the resource-constrained project scheduling problem

0.00 Avg rating0 Votes
Article ID: iaor20172577
Volume: 24
Issue: 6
Start Page Number: 1525
End Page Number: 1547
Publication Date: Nov 2017
Journal: International Transactions in Operational Research
Authors:
Keywords: project management, heuristics, combinatorial optimization, optimization, heuristics: genetic algorithms
Abstract:

This paper presents a procedure for solving the resource‐constrained project scheduling problem. It consists of an implicit enumeration module and a genetic algorithm. If the procedure is provided access to all of its required computational resources of the problem at hand, it guarantees the optimality of the produced solution. In contrast, and in the case of limited access to computational resources, the procedure gradually moves the root of the search‐tree downward, and consequently prunes part of the search space, trading speed with precision effectively. In the cases where speed has been traded with precision, and the guarantee of optimality has been lost, the final schedule created by the implicit enumeration module is used as a template whose modified instances fill an initial pool of a genetic algorithm to improve the proposed solution. The procedure has been applied to 2040 benchmark instances. The results are promising; whereas for all small‐ and some medium‐sized instances, the procedure has found and guaranteed optimal solutions, for other instances, whose optimal solutions cannot be guaranteed within the limit of computational resources, it has produced high‐quality solutions.

Reviews

Required fields are marked *. Your email address will not be published.