A dissimilarities balance model for a multi-skilled multi-location food safety inspector scheduling problem

In this work, we examine a staff scheduling problem in a governmental food safety center that is responsible for the surveillance of imported food at an international airport. In addition to the fact that the staff have different levels of efficiency and have different preference for work shifts, the Operations Manager of the food safety center would like to balance the dissimilarities of workers in order to provide unbiased work schedules for staff members. We adopt a two-phase approach, where the first phase is to schedule the work shifts of food safety inspectors (including rest days and shift types) with schedule fairness and staff preference taken into account and the second phase is to best-fit them to tasks in terms of skill-matches and create diversity of team formations. We also provide polyhedral results and devise valid inequalities for the two formulations. For the first-phase problem, we relax some constraints of the fairness criteria to reduce the problem size to reduce computational effort. We derive an upper bound for the objective value of the relaxation and provide computational results to show that the solutions devised from our proposed methodology are of good quality. For the second-phase problem, we develop a shift-by-shift assignment heuristic to obtain an upper bound for the maximum number of times any pair of workers is assigned to the same shift at the same location. We propose an enumeration algorithm, that solves the problems for fixed values of this number until an optimality condition holds or the problem is infeasible. Computational results show that our proposed approach can produce solutions of good quality in a much shorter period of time, compared with a standalone commercial solver.