Combination of Local Search Strategies for Rotating Workforce Scheduling Problem

1 Introduction

Workforce scheduling, in general, includes sub-problems which appear in many spheres of life as in industrial plants, hospitals, public transport, airlines companies, universities etc. There are two main variants of workforce schedules: rotating (or cyclic) workforce schedules and non-cyclic workforce schedules. In a rotating workforce schedule all employees have the same basic schedule but start with different offsets. For this problem we have given (for formal definition see [Musliu et al., 2002]): number of employees: n, set of m shifts, length of schedule, temporal requirements, constraints about the sequences of shifts permitted to be assigned to employees (the complement of inadmissible sequences), maximum and minimum length of periods of consecutive shifts and maximum and minimum length of blocks of work days. The aim is to find a cyclic schedule (assignment of shifts to employees) that satisfies the requirement matrix and fulfill all given hard constraints.

Workforce schedules have a impact on the health and satisfaction of employees as well as on their performance at work. Therefore, computerized workforce scheduling has interested researchers for over 30 years. For solving the problem of workforce scheduling, different approaches have been used in the literature. Survey of algorithms used for different workforce scheduling problems is given by Alfares [Alfares, 2004]. Balakrishnan and Wong [Balakrishnan and Wong,

1990] solved a problem of rotating workforce scheduling by modeling it as a network flow problem. Musliu et al [Musliu et al., 2002] proposed and implemented a new method for the generation of rotating workforce schedules, which is based on pruning of search space, by involving the decision maker during the generation of partial solutions. The algorithms has been included in a commercial product called First Class Scheduler, which is already being used by several companies in Europe since 2000. Recently, Musliu [Musliu, 2003] proposed a simple tabu search approach for this problem. In this paper we propose improvement of tabu search technique proposed in [Musliu, 2003] by combination of this technique with random walk and min conflicts heuristic.

2 Combination of Local search strategies

In this paper we propose a combination of tabu search with random walk and min conflicts technique. The combination of tabu search with randomwalk works as follows: For each iteration with probability p randomly the cell (in the schedule) which is in conflict is picked. Another cell is picked in the same column randomly and the contents of two selected cells are swapped. With probability 1-p, the tabu search algorithm is applied.

The random walk strategy in our case picks with probability p, first randomly one cell which is appears in some violated constraint (conflict). The content of this cell is swapped with the content of other cell which is selected randomly in the same column. As described later the solutions during each iteration fulfill always the workforce requirements. This is the reason why we allow the swap of contents of cells only inside of one column.

Further, we consider also combination of tabu search with min-conflicts strategy. The procedure applies standard min conflicts strategy for each iteration with probability p. With probability 1-p, it follows the tabu search algorithm.

The min-conflict strategy for this problem works as follows. Randomly a cell in schedule (variable) which is in a conflict is picked. Further, all solutions are generated which can be obtained by swapping the content of selected cell and other cells in the same column. From the generated neighborhood the solution which minimizes number of conflicts is selected for the next iteration. Note that there is a small difference compare to pure min conflicts heuristic ([Minton et al., 1992]) due to the specifics of this problem. First, in our case not only one variable in conflict changes the value, but two variables (which represents schedule cells in the same column) exchange their contents. Second, with our procedure also a worst solution can be accepted for the next iteration.

Considering generation of neighborhood in tabu search we apply a simple move, which swaps the contents of two elements in the schedule. However, to reduce the neighborhood of the current solution, we only allow those solutions which fulfill workforce requirements, and thus the swapping of elements is done only inside of a particular column (day of schedule). The whole neighborhood of the current solution is obtained by swapping all possible elements (not identical) in all columns of a table. The applied move is denoted as swap(j, i, k), where j represents the column in which the swap of elements should be done, and i, k represent elements in column j that should swap their contents. Additionally, the above described move was extended to swap the blocks of neighborhood cells.

To calculate the fitness of the solution, for each violation of constraint a determined number of points (penalty) is given, based on the constraint and the degree of the constraint violation. The fitness represents the sum of all penalties caused from the violation of constraints. Since the problem we want to solve only has hard constraints, the solution will be found when the fitness of the solution reaches the value 0.

3 Computational results

In this section we report on computational results obtained with the current implementation of local search strategies. For comparison we collected a set of real life problems which can be used further by other researchers to compare their results with ours. The collection of these problems can be found on http://www.dbai.tuwien.ac.at/staff/musliu/benchmarks/. The problems for which we give the results in this paper contains from 7 to 64 groups. Each group can contain one or more employees. The first three examples are benchmark examples we could find in literature with some modification according the definition of problems we solve in this paper. Other 15 examples are real life examples of different size which appeared in different areas in practice. The experiments were performed in a machine Pentum 4, 1,8GHZ, 512 MB RAM. For each problem 10 independent runs were executed. Maximal number of evaluations for each run is 10000000. Note that we experimented with different parameters considering the probability for random walk, length of tabu list and type of tabu. In this paper the best results we could obtain for each strategy are presented.

In the Table 1 a summary of results fo tabu search, tabu search with random walk, and tabu search with min conflicts heuristics is presented. For each problem the average time needed (in seconds) for generation of solution is presented. The column named Sol. (solutions) represents number of solutions found in 10 runs.

3.1 Discussion of results

From the Table 1 we can conclude that tabu search approach is improved with combination of tabu search with random walk considering both the average time needed to find the solutions and also the number of runs in which the solution is found. Combination of tabu search with min conflicts heuristic further improves tabu search considering the the time for which the solution are generated and the number of successful runs. The combination of tabu search with min conflicts strategy proposed in this paper improves the results obtained by FCS, which to our best knowledge is the state of art commercial systems for generation of rotating workforce schedules.