A rolling planning horizon heuristic for scheduling agents with different qualifications

• We model the tour scheduling problem for check-in agents from ground-handling agencies.
• We provide a MIP model that includes multiskilled agents and flexible contracts.
• We propose a rolling planning horizon-based heuristic to solve this problem.
• The proposed heuristic can even solve complex instances from real-world cases.
• More qualified agents provide more scheduling flexibility albeit possibly at higher costs.

This paper presents an optimization model for the tour scheduling problem for agents with multiple skills and flexible contracts in check-in counters at airports. The objective is to minimize the total assignment costs subject to demand fulfillment and labor regulations. In order to solve this problem we develop a rolling planning horizon-based heuristic. Our heuristic is robust and provides near-optimal schedules within reasonable computation time for real-world cases, although the parameter selection is important to its performance. In addition, we discuss the impact of the skill distribution on the scheduling costs for several instances.