Heuristics for large scale labour scheduling problems in retail sector

Labour scheduling in an organization is described as the process of producing optimized timetables for employees. During this process, the work regulations associated with the relevant workplace agreements must be observed and individual work preferences should be accommodated. The problem is further complicated by having many non-standard shift patterns with varying start and end times, and shifts of differing lengths. Generating all possible shift combinations results in a very large problem size and, consequently, the computational time needed to find an optimal schedule may become too excessive to be of any practical value. This paper proposes eight heuristics for generating candidate shifts. Our extensive analysis identified several patterns in intraday labour demand, ranging from a simple flat demand to a mixed fluctuating demand. Accordingly, a number of heuristics were developed for these different demand patterns, and an integer programming model was constructed to test their performance. Our computational analysis on small-scale test problems showed promising results by some of the heuristics in improving computational efficiency, without compromising the solution quality. The results indicated that a combination of some of these heuristics would be useful for the general case in which demand does not necessarily follow any specific pattern.