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

Banafsheh Namiranian, Ryerson University

Date of Award

2005

Degree Type

Thesis

Degree Name

Master of Applied Science (MASc)

Department

Mechanical Engineering

First Advisor

Saeed Zolfaghari

Second Advisor

Ahmed El-bouri

Abstract

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.