Rostering for a restaurant

We present a heuristic algorithm for preparing weekly employee schedules, The algorithm ensures that employees are not assigned to periods when they are unavailable, or more than one shift per day, or a night shift followed by a morning shift. It attempts as far as possible to satisfy constraints on the required number of employees per period, the minimum and maximum number of shifts per week for each employee, at least one supervisor on duty at all times, and at most one trainee on duty at all times. The algorithm consists of an initial construction heuristic followed by tabu search. We describe the design of a scheduling application that implements the heuristic algorithm for a restaurant franchise.