Greedy heuristic algorithms for manpower shift planning

Consideration is given to a particular personnel planning problem faced by a food manufacturing company. This problem, referred to herein as manpower shift planning (MSP), seeks for the minimum workforce needed to work in each available workday shift over a given planning horizon in order to complete predetermined production objectives associated with individual production lines. We formulate MSP as an integer linear program, whose structure allows us to conjecture that it is an NP-Complete problem. We then propose two greedy heuristic algorithms for solving MSP, one for single and another for multiple workday shifts. Using results from a standard ILP optimiser together with a lower bound developed for the MSP solution, we test the performance of the multi-shift heuristic for a variety of operating environments. The results demonstrate very satisfactory performance in terms of both solution time and quality. The paper is concluded with a discussion on the results and proposals for further research.