A comparison of some heuristics to improve shift generation in the labour scheduling problem

The use of part-time personnel with different skills and time-availability has risen dramatically over the last few decades. This fact, especially in service-oriented organizations with great demand fluctuations, makes the labour scheduling problem complicated. The Integer Programming (IP) technique is a common tool for assigning employees to right shifts but, due to its large size in this particular type of problem, the IP model cannot be solved optimally within a reasonable time. In order to reduce the problem size and, subsequently, the computational time, one approach is to reduce the number of decision variables which are defined as shifts in the labour scheduling problem. This thesis presents eight different heuristics to generate a smaller set of shifts instead of exhaustively generating all possible shifts. With the aid of statistical analysis, the proposed algorithims are compared, and the best heuristic in terms of efficiency and effectiveness is introduced.