A Simulated Annealing Approach to the Solution of Flexible Labour Scheduling Problems
作者:
BruscoMichael J.,
JacobsLarry W.,
期刊:
Journal of the Operational Research Society
(Taylor Available online 1993)
卷期:
Volume 44,
issue 12
页码: 1191-1200
ISSN:0160-5682
年代: 1993
DOI:10.1057/jors.1993.198
出版商: Taylor&Francis
关键词: Labour Scheduling;Heuristics;Simulated Annealing
数据来源: Taylor
摘要:
AbstractThis paper presents a new solution approach to the discontinuous labour tour scheduling problem where the objective is to minimize the number 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 heuristic approaches but often resulted in solutions that contained a substantial amount of excess labour. In this study, we relaxed many of the restrictions on scheduling flexibility assumed in previous studies. The resulting problem environment contained more than two billion allowable tours, precluding the use of previous heuristic methods. Consequently, we developed a simulated annealing heuristic for solving the problem. An important facet of this new approach is an‘intelligent’improvement routine which eliminates the need for long run-times typically associated with simulated annealing algorithms. The simulated annealing framework does not rely on a special problem structure and our implementation rapidly converged to near-optimal solutions for all problems in the test environment.
点击下载:
PDF (4368KB)
返 回