Shift scheduling and rostering with same shift-type and weekend-off fairness constraints in call centres

Based on the actual operational situation of call centres, this paper incorporates the constraints of the same shift-type within a week and the fairness of weekends-off into scheduling. Utilising the progressive decomposition structure of the same shift-type constraint, this paper constructs an integer programming model for multi-week scheduling optimisation problem of call centre agents. We first analyse the maximum lower bound of the problem and prove the optimality of its relaxation problem. Then we propose a two-stage algorithm which combines a constructive heuristic with neighbourhood search incorporating simulated annealing. Experimental results show that the integer programming model is only suitable for achieving optimal solutions for small-scale problems, while our two-stage algorithm can obtain (sub-)optimal solutions for large-scale problems. The impact of employment policy on labour costs is also discussed. [Received: 21 March 2023; Accepted: 12 November 2023]