A Dynamic Search Termination Scheme for Retail Labour

Integer programming is a common approach for assigning employees to different shifts in a retail labour scheduling problem. Due to the size of some real life problems, it may not be possible to solve them optimally within a reasonable amount of time. Hence, in practice, one may be satisfied if the solution reaches an acceptable gap from the best bound, a 2% gap for example. This gap is the difference between the current best solution and the theoretically best possible solution that can be found. However, an analysis of several real life labour scheduling problems reveals that, for some cases, a reasonable gap (e.g. 5%) can be found quickly but will take several hours or more to find a 2% gap. In large schedules, with several hundreds of employees, this difference in solution quality can hardly be noticed from the retail store manager's perspective. The difference between the times needed to generate schedules, on the other hand, is noticeable. Therefore, this paper presents a dynamic termination scheme that can be used to prevent long search processes that do not yield recognizable/practical improvements. The scheme is tested on 13 real life problems and results show an average of 55% reduction in search time.