1. ¹Kuwait University, Safat, Kuwait
2. ²Virginia Polytechnic Institute & State University, Blacksburg, VA, USA

Correspondence: SM Al-Yakoob, Department of Mathematics & Computer Science, Kuwait University, PO Box 5969, Safat 13060, Kuwait. E-mail: salem@al-yakoob.com

Received 1 May 2005; Accepted 1 June 2006; Published online 18 October 2006.

Abstract

This paper is concerned with the problem of assigning employees to a number of work centres taking into account employees' expressed preferences for specific shifts, off-days, and work centres. This particular problem is faced by the Kuwait National Petroleum Corporation that hires a firm to prepare schedules for assigning employees to about 86 stations distributed all over Kuwait. The number of variables in a mixed-integer programming model formulated for this problem is overwhelming, and hence, a direct solution to even the continuous relaxation of this model for relatively large-scale instances is inconceivable. However, we demonstrate that a column generation method, which exploits the special structures of the model, can readily solve the continuous relaxation of the model. Based on this column generation construct, we develop an effective heuristic to solve the problem. Computational results indicate that the proposed approach can facilitate the generation of good-quality schedules for even large-scale problem instances in a reasonable time.