The shift minimisation personnel task scheduling problem: A new hybrid approach and computational insights

• A new hybrid heuristic approach is presented for a task scheduling problem (SMPTSP).
• The new approach improves upon the state of the art algorithms for the SMPTSP.
• An empirical hardness study investigates the effect of two problem features.
• A new benchmark dataset is generated based on the hardness results.
• The majority of the new instances remain unsolved with the presented approach.

Assigning scheduled tasks to a multi-skilled workforce is a known NP-complete problem with many applications in health care, services, logistics and manufacturing. Optimising the use and composition of costly and scarce resources such as staff has major implications on any organisation׳s health. The present paper introduces a new, versatile two-phase matheuristic approach to the shift minimisation personnel task scheduling problem, which considers assigning tasks to a set of multi-skilled employees, whose working times have been determined beforehand. Computational results show that the new hybrid method is capable of finding, for the first time, optimal solutions for all benchmark instances from the literature, in very limited computation time. The influence of a set of problem instance features on the performance of different algorithms is investigated in order to discover what makes particular problem instances harder than others. These insights are useful when deciding on organisational policies to better manage various operational aspects related to workforce. The empirical hardness results enable to generate hard problem instances. A set of new challenging instances is now available to the academic community.