Interactive optimization for shift scheduling

Although studied interactive methods can be applied to diverse problems, the application domain on which interactive methods are evaluated during the project is personnel scheduling and more precisely shift scheduling. We provide here a short introduction on this optimization problem and give details on the initial problem model that has been used in our study.

Shift scheduling

Shift scheduling is the task of assigning employees to shifts (e.g. Early shift 7:00-15:00, late shift 15:00-22:00) for a given planning period [Burke et al. 2004, Ernst et al. 2004]. The result, illustrated in Figure 1, is the definition of employees’ schedules. Some of the constraints that are generally considered for shift scheduling made the problem complex (See [Lau 1996] and [Brucker et al. 2011] for complexity results).

schedule

Figure 1. A shift scheduling problem with a candidate solution.

Selected references on shift scheduling

[Brucker et al. 2011] P. Brucker, R. Qu, and E. Burke. “Personnel scheduling: Models and complexity”. European Journal of Operational Research, 210(3):467-473, 2011.

[Burke et al. 2004] E. K. Burke, P. D. Causmaecker, G. V. Berghe, and H. V. Landeghem. “The state of the art of nurse rostering”. Journal of Scheduling, 7:441–499, 2004.

[Ernst et al. 2004] A. T. Ernst, H. Jiang, M. Krishnamoorthy, and D. Sier. “Staff scheduling and rostering: A review of applications, methods and models”. European Journal of Operational Research, 153(1):3–27, 2004.

[Lau 1996] H. C. Lau. “On the complexity of manpower shift scheduling”. Computers and Operations Research, 23(1):93-102, 1996.

What makes shift scheduling a promising application for interactive optimization?

Interactive optimization has a strong potential for solving shift scheduling problems for different reasons. First, staff planning problems are generally difficult to model because a lot of criteria are taken into account for making a decision on staff planning. Those criteria cover a multitude of aspects, from simple demand and economic aspects, to more complex criteria such as comfort or fairness in assignments. In addition, shift scheduling problems are generally difficult to solve. Finally, it is often necessary for a decision maker to solve such a problem on a regular basis (every weeks or months). In this context, interactive optimization can be useful for refining the problem model and also for adjusting the performance of an optimization procedure.

The INRC2010 problem model

There are several shift scheduling models and benchmarks in the literature (see for instance [Smet et al. 2013]). The INRC2010 benchmark has been proposed for a competition held in 2010, the International Nurse Rostering Competition [Haspeslagh et al. 2012]. This benchmark has been selected for our study because 1) the model contains a reasonable set of realistic constraints, 2) results are available in the literature, and 3) the dataset is composed of various instances of different size and characteristics. The optimization model for the INRC2010 benchmark contain the following constraints:

Hard constraints:

  • Exact demand coverage
  • Unique shift assignment of employees per day

Soft constraints:

  • Maximum and minimum number of assignments within the planning horizon
  • Maximum and minimum number of consecutive working days
  • Skill requirements
  • Unwanted consecutive working shifts (patterns of 2 or 3 days)
  • Day-off and shift-off requests
  • Complete working weekends
  • Identical shifts during weekends
  • Maximum and minimum number of consecutive free days
  • Maximum and minimum number of consecutive working weekends

The benchmark data are available here. The Figure 2 represents the data structure used for each instance. Note that some fields are not used by the instances.

INRC_data_structure

Figure 2. Data structure for INRC2010 problem instances (based on the XML schema file of the INRC2010 benchmark).

Selected references on shift scheduling benchmarks and INRC2010 model

[Haspeslagh et al. 2014] S. Haspeslagh, P. De Causmaecker, A. Schaerf, and M. Stølevik, “The first international nurse rostering competition 2010″, Annals of Operations Research, 218:221-236, 2014.

[Meignan 2014] D. Meignan, “A Heuristic Approach to Schedule Reoptimization in the Context of Interactive Optimization”, Genetic and Evolutionary Computation Conference,  461-468, 2014.

[Smet et al. 2013] P. Smet, P. De Causmaecker, B. Bilgin, G. Van den Berghe, “Nurse Rostering: A Complex Example of Personnel Scheduling with Perspectives”, Automated Scheduling and Planning, Studies in Computational Intelligence, 505:129-153, 2013.