Scheduling problems form a very large class of optimization problems encountered in several industries and organizations of widely different kinds. The particular problem that we consider is a staff scheduling problem, which consists of assigning activities to employees by taking into account workload requirements and different other constraints (legal, economic, organizational and social). Staff scheduling are NP-hard, heuristics are often used to deal with large scale practical problems. In this paper, we focus on activities duration constraints which make the problem difficult to solve.We propose a Tabu Search (TS) approach to deal with the specific staff scheduling problem taking into account workload and activities duration constraints. Computational results show the effectiveness of the proposed approach comparing CPLEX solver.
Mots clés : Tabu search, Scheduling problem, Integer linear programming