A metaheuristic algorithm for project selection and scheduling with due windows and limited inventory capacity

Abstract

Purpose

The purpose of this paper is to provide an effective solution for a complex planning problem encountered in heavy industry. The problem entails selecting a set of projects to produce from a larger set of solicited projects and simultaneously scheduling their production to maximize profit. Each project has a due window inside of which, if accepted, it must be shipped. Additionally, there is a limited inventory buffer where lots produced early are stored. Because scheduling affects which projects may be selected and vice-versa, this is a particularly difficult combinatorial optimization problem.

Design/methodology/approach

The authors develop an algorithm based on the Metaheuristic for Randomized Priority Search (Meta-RaPS) as well as a greedy heuristic and an integer programming (IP) model. The authors then perform computational experiments on a large set of benchmark problems over a wide range of characteristics to compare the performance of each method in terms of solution quality and time required.

Findings

The paper shows that this problem is very difficult to solve using IP, with even small instances unable to be solved optimally. The paper then shows that both proposed algorithms will in seconds often outperform IP by a large margin. Meta-RaPS is particularly robust, consistently producing the best or very near-best solutions.

Practical implications

The Meta-RaPS algorithm developed enables companies facing this problem to achieve higher profits through improved decision making. Moreover, this algorithm is relatively easy to implement.

Originality/value

This research provides an effective solution for a difficult combinatorial optimization problem encountered in heavy industry which has not been previously addressed in the literature.

Citation

Garcia, C. (2014), "A metaheuristic algorithm for project selection and scheduling with due windows and limited inventory capacity", Kybernetes, Vol. 43 No. 9/10, pp. 1483-1499. https://doi.org/10.1108/K-11-2013-0245