Title: Heuristic solutions for the economic manpower shift planning problem

Authors: Andreas C. Nearchou; Athanasios G. Lagodimos

Addresses: Department of Business Administration, University of Patras, 26 500, Patras, Greece ' Department of Business Administration, University of Piraeus, GR-185 34 Piraeus, Greece

Abstract: Consideration is given to the economic manpower shift planning (EMSP) problem, a capacity planning problem which seeks the workforce needed in each workday shift over a given planning horizon in order to complete a specific set of jobs at minimum cost. Since the problem has been shown to be NP-hard, we establish an optimal solution lower bound and develop heuristic algorithms for its solution. Specifically, two greedy algorithms and one meta-heuristic algorithm are developed. The meta-heuristic, which constitutes a hybrid genetic algorithm, combines the advantages of a micro-genetic algorithm (µGA) for fast solutions evolution with a variable neighbourhood search (VNS) technique for improving these solutions. Experiments over three different operating environments were performed to assess the heuristics efficiency. Comparative results from a standard integer linear programming optimiser and the lower bound proposed here show the meta-heuristic to perform very well in terms of solution quality and CPU-time requirements, particularly for large-sized problems (where it clearly outperforms both greedy algorithms). [Received 25 February 2011; Revised 24 September 2011, 15 January 2012, 13 March 2012; Accepted 26 March 2012]

Keywords: maintenance; economic manpower shift planning; combinatorial optimisation; evolutionary algorithms; labour; personnel; metaheuristics; staffing; population-based heuristics; capacity planning; genetic algorithms; neighbourhood search; greedy algorithms; work shifts.

DOI: 10.1504/EJIE.2013.058390

European Journal of Industrial Engineering, 2013 Vol.7 No.6, pp.657 - 686

Published online: 28 Feb 2014 *

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