Improved heuristic for manpower shift planning with modified shift priorities

Consideration is given to a personnel planning problem, termed manpower shift planning (MSP), faced by producers in several process industries, most of which are small- and medium-sized companies. This seeks the minimum manpower needed in each workday shift of a manufacturing facility so that production targets are met within a given time horizon. The problem has been shown to be NP-hard. After positioning MSP within the relevant research field, we propose a new lower bound for its solution. We then study the modification of an existing MSP heuristic with a view to improving its performance. As originally proposed, the heuristic prioritises shifts according to a specific priority index. Since different indices may improve heuristic performance, we define six alternative indices and prove that three are equivalent. A two-phased numerical investigation is used for assessing and ranking the four non-equivalent indices. Results show that heuristic efficiency strongly depends on shift priorities. Moreover, heuristic efficiency improves (even if marginally) for one of the new priority indices. Finally, for all but one of the indices studied, the heuristic clearly outperforms (at a fraction of run time) a popular commercial ILP-optimiser.