The latest results of the "Interactive Metaheuristics" project have been presented at GECCO'14. The corresponding article, entitled "A heuristic approach to schedule reoptimization in the context of interactive optimization" [Meignan 2014], shows the potential benefits of an interactive reoptimization approach.
Shift scheduling
In the paper we propose a reoptimization approach for a shift scheduling problem. 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). In our study we considered the model of the shift scheduling problem that has been proposed for the International Nurse Rostering Competition held in 2010 (INRC 2010) [Haspeslagh et al. 2012].
If the manager proceeds by manual adjustment, it will be difficult to obtain a good result. As illustrated in Figure 2, a change can deteriorate a solution, and it is difficult to properly adjust the entire solution. The objective of interactive reoptimization is to overcome this difficulty and provide a mechanism for adjusting a solution while minimizing the impact on the cost of the solution. In the proposed reoptimization approach, the adjustment of a solution is an iterative process in which the user specifies preferences on a current candidate solution, and then a procedure re-optimizes the solution to integrate the preferences. The process is iterated until a satisfactory solution is obtained. For the modification of a planning, instead of manually changing the assignments, the manager indicates some preferences as illustrated in Figure 3. The solution is then reoptimized to introduce the preferences.
First, in comparison to the optimization step, the reoptimization starts with a candidate solution. This initial solution may facilitate the search for a reoptimized solution assuming that only few preferences have been defined by the user of the system.
In addition, the reoptimization must take into account the preferences of the user in addition to the initial objectives and constraints of the optimization problem.
Next, the computation time for re-optimizing is generally shorter than for the optimization step. Considering the interaction context, reoptimization should last a few seconds to allow the user exploring different alternatives.
Finally, the changes which result from the reoptimization should be minimized in order to maintain the consistency of user preferences. If possible, the reoptimized solution should be similar to the initial solution because the preferences of the decision maker have been expressed on the basis of the initial solution. With a completely different reoptimized solution the preferences expressed on the initial solution may lose their meaning. Minimizing the changes in the reoptimized solution should also favors the convergence toward a satisfactory solution for the user.
The reoptimization procedure proposed in the article has been designed and implemented to meet these specific requirements:
In the paper, we provide some results supporting the fact that reoptimization is of practical significance. We considered reoptimization problems in which 5 or 10 assignment preferences are defined over 280 potential shift slots. The reoptimization procedure with ILS has been compared to "pure" local-search procedures. We observed significant gaps in the number of preference satisfied and solution cost reached between the pure local-search procedures and the ILS procedure. Figure 4 illustrates this comparison with an actual result.
The first solution in Figure 4 is the initial solution to be reoptimized. 5 assignment preferences are defined and represented as red crosses. The second solution is obtained with ILS in 2 seconds of computation. 4 preferences have been satisfied, and a cost of 28 has been reached. The third solution is obtained with a hill-climbing procedure based on the 1-swap neighborhood. The number of satisfied preferences is 3, and the cost is 30. The solution obtained with ILS satisfies more preferences than the local-search procedure and reaches a better cost. This result might look trivial, but it clearly shows that the reoptimization cannot be easily handled manually or with a simple recovery procedure. Even for a small number of user preferences, the reoptimization necessitates a global optimization approach.
Additional results are detailed in the paper, including the performance of ILS against state of the art methods, and results on the impact of the distance constraint.
[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. DOI: 10.1016/j.ejor.2010.11.017
[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.
[Haspeslagh et al. 2012] S. Haspeslagh, P. D. Causmaecker, A. Schaerf, and M. Stølevik. The first international nurse rostering competition 2010. Annals of Operations Research, Online. DOI: 10.1007/s10479-012-1062-0, 2012.
[Lau 1996] H. C. Lau. On the complexity of manpower shift scheduling. Computers and Operations Research, 23(1):93-102, 1996. DOI: 10.1016/0305-0548(94)00094-O
[Meignan 2014] D. Meignan, D. A Heuristic Approach to Schedule Reoptimization in the Context of Interactive Optimization. In Genetic and Evolutionary Computation Conference, 461-468, 2014. DOI: 10.1145/2576768.2598213
Figure 1. A shift scheduling problem with a candidate solution.
Reoptimization in the context of a decision support system
In practice, a model of an optimization problem such as the INRC model is likely to contain some inaccuracies. Consequently, a candidate solution provided by an optimization system based on this model may require some adjustments for being realistic. Let's take the case of a manager that uses an optimization system for determining the planning of the employees of his department. The system provides a candidate solution (planning for all employees); however, the manager knows that it is inappropriate for some employees to work on specific shifts. As a concrete example, arduous tasks that are scheduled on specific time slots may be too hard for young recruits. This constraint is not present in the optimization model and the manager has to adjust the planning to reflect it.
Figure 2. Manual adjustment of a candidate solution. The change results in multiple unsatisfied constraints that are difficult to solve manually.
If the manager proceeds by manual adjustment, it will be difficult to obtain a good result. As illustrated in Figure 2, a change can deteriorate a solution, and it is difficult to properly adjust the entire solution. The objective of interactive reoptimization is to overcome this difficulty and provide a mechanism for adjusting a solution while minimizing the impact on the cost of the solution. In the proposed reoptimization approach, the adjustment of a solution is an iterative process in which the user specifies preferences on a current candidate solution, and then a procedure re-optimizes the solution to integrate the preferences. The process is iterated until a satisfactory solution is obtained. For the modification of a planning, instead of manually changing the assignments, the manager indicates some preferences as illustrated in Figure 3. The solution is then reoptimized to introduce the preferences.
Figure 3. Definition of an assignment preference with the resulting solution obtained by reoptimization. Changes in the reoptimized solution are indicated in yellow.
Optimization versus reoptimization
A reoptimization procedure differs from an optimization procedure on several aspects.First, in comparison to the optimization step, the reoptimization starts with a candidate solution. This initial solution may facilitate the search for a reoptimized solution assuming that only few preferences have been defined by the user of the system.
In addition, the reoptimization must take into account the preferences of the user in addition to the initial objectives and constraints of the optimization problem.
Next, the computation time for re-optimizing is generally shorter than for the optimization step. Considering the interaction context, reoptimization should last a few seconds to allow the user exploring different alternatives.
Finally, the changes which result from the reoptimization should be minimized in order to maintain the consistency of user preferences. If possible, the reoptimized solution should be similar to the initial solution because the preferences of the decision maker have been expressed on the basis of the initial solution. With a completely different reoptimized solution the preferences expressed on the initial solution may lose their meaning. Minimizing the changes in the reoptimized solution should also favors the convergence toward a satisfactory solution for the user.
The reoptimization procedure proposed in the article has been designed and implemented to meet these specific requirements:
- An Iterated Local-Search (ILS) procedure is used for both optimization and reoptimization steps. For the reoptimization, the ILS starts with the initial candidate solution.
- In order to obtain good performance in a few seconds, the ILS procedure exploits high-level parallelism (multi-thread strategy) and delta-evaluation of solutions for local-search.
- The problem model used for the reoptimization integrates a soft constraint in order to satisfy the preferences defined by the user.
- Another soft constraint has been integrated to minimize the distance between the initial solution and the reoptimized solution.
Is reoptimization really difficult?
An important question of the study is to evaluate the practical significance of the reoptimization problem. In terms of complexity, the reoptimization problem has the same complexity as the optimization problem [Ausiello at al. 2007]. However, since the reoptimization may start with a good initial solution and only few preferences may be defined, it may not be necessary to use in practice a global optimization procedure.In the paper, we provide some results supporting the fact that reoptimization is of practical significance. We considered reoptimization problems in which 5 or 10 assignment preferences are defined over 280 potential shift slots. The reoptimization procedure with ILS has been compared to "pure" local-search procedures. We observed significant gaps in the number of preference satisfied and solution cost reached between the pure local-search procedures and the ILS procedure. Figure 4 illustrates this comparison with an actual result.
Figure 4. Comparison between ILS and a local-search procedure. The solution obtained with ILS satisfies more preferences than the local-search procedure and reaches a better cost.
The first solution in Figure 4 is the initial solution to be reoptimized. 5 assignment preferences are defined and represented as red crosses. The second solution is obtained with ILS in 2 seconds of computation. 4 preferences have been satisfied, and a cost of 28 has been reached. The third solution is obtained with a hill-climbing procedure based on the 1-swap neighborhood. The number of satisfied preferences is 3, and the cost is 30. The solution obtained with ILS satisfies more preferences than the local-search procedure and reaches a better cost. This result might look trivial, but it clearly shows that the reoptimization cannot be easily handled manually or with a simple recovery procedure. Even for a small number of user preferences, the reoptimization necessitates a global optimization approach.
Additional results are detailed in the paper, including the performance of ILS against state of the art methods, and results on the impact of the distance constraint.
References
[Ausiello et al. 2007] G. Ausiello, V. Bonifaci, and B. Escoffier. Computability in Context: Computation and Logic in the Real World, chapter Complexity and Approximation in Reoptimization, pp. 101–129. Imperial College Press, 2007.[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. DOI: 10.1016/j.ejor.2010.11.017
[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.
[Haspeslagh et al. 2012] S. Haspeslagh, P. D. Causmaecker, A. Schaerf, and M. Stølevik. The first international nurse rostering competition 2010. Annals of Operations Research, Online. DOI: 10.1007/s10479-012-1062-0, 2012.
[Lau 1996] H. C. Lau. On the complexity of manpower shift scheduling. Computers and Operations Research, 23(1):93-102, 1996. DOI: 10.1016/0305-0548(94)00094-O
[Meignan 2014] D. Meignan, D. A Heuristic Approach to Schedule Reoptimization in the Context of Interactive Optimization. In Genetic and Evolutionary Computation Conference, 461-468, 2014. DOI: 10.1145/2576768.2598213
