Scheduling Regular and Temporary Employees with Qualifications in a Casino

We consider a workforce scheduling problem that arises when scheduling the employees of a casino for a prescribed time period. Given a set of tasks for each day, we are looking for a sequence of tasks and days off for each employee. All sequences have to observe (hard) legal and contractual constraints as well as (soft) in-house restrictions. The overall objective is to minimize violations of the soft restrictions and evenly distribute attractive tasks among employees. Apart from regular employees, we have to take into account temporary employees, where each employee is characterized by a certain set of skills.First, we consider an exact solution procedure based on a minimum-cost multicommodity network flow formulation, which can be solved by means of column generation and branch-and-bound techniques. For large problem instances we propose a local search algorithm. An initial solution is obtained by successively solving several assignment problems. Two Hill Climbing procedures are used to improve the initial solution.