The staff scheduling problem is a critical problem in the call center (or, more generally, customer contact center) industry. Even the simplest variations of this problem are known to be NPcomplete (Garey and Johnson 1978). Although staff scheduling has long been an important operations research problem, scheduling has recently become an important component of an emerging class of business software applications known as workforce management software. The need for effective workforce management systems has been driven primarily by the recent, rapid growth of the call center--customer contact center industry, in which efficient deployment of human resources is of crucial, strategic importance. Traditionally, in this industry, staff scheduling has been performed using ad hoc methods and operations research techniques (Cleveland and Mayben 1997).