A SIMULATED ANNEALING APPROACH TO THE SOLUTION OF FLEXIBLE LABOR SCHEDULING PROBLEMS

This paper presents a new solution approach to the discontinuous labou r tour scheduling problem where the objective is to minimize the numbe r of full-time employees required to satisfy forecast demand. Previous heuristic approaches have often limited the number of allowable tours by restricting labour scheduling flexibility in terms of shift length , shift start-times, days-off, meal-break placement, and other factors . These restrictions were essential to the tractability of the heurist ic approaches but often resulted in solutions that contained a substan tial amount of excess labour. In this study, we relaxed many of the re strictions on scheduling flexibility assumed in previous studies. The resulting problem environment contained more than two billion allowabl e tours, precluding the use of previous heuristic methods. Consequentl y, we developed a simulated annealing heuristic for solving the proble m. An important facet of this new approach is an 'intelligent' improve ment routine which eliminates the need for long run-times typically as sociated with simulated annealing algorithms. The simulated annealing framework does not rely on a special problem structure and our impleme ntation rapidly converged to near-optimal solutions for all problems i n the test environment.