The Extended Shift Minimization Personnel Task Scheduling Problem

In workforce scheduling, shift generation is the process of determining the shift structure, along with the tasks to be carried out in particular shifts. Application areas of shift generation include hospitals, retail stores, contact centers, cleaning, home care, guarding, manufacturing and delivery of goods. We present an extension to the Shift Minimization Personnel Task Scheduling Problem that is a problem in which a set of tasks with fixed start and finish times have to be allocated to a heterogeneous workforce. The objective in the SMPTSP is to minimize the number of employees required to carry out the given set of tasks. In the ESMPTSP, another objective is to maximize the number of feasible (shift, employee) pairs. We provide a mathematical formulation of the extended problem. We present an efficient ruin and recreate heuristic along with computational results for existing SMPTSP data sets and to a new data set. The presented heuristic is suitable for application in large real-world scenarios. The new instances, along with our best solutions, have been made available online.

---

1. Preface

---

2. Session: 14th International Workshop on Computational Optimization

---

3. Communication Papers