“A heuristic approach to schedule reoptimization in the context of interactive optimization”

New publication

David Meignan, “A heuristic approach to schedule reoptimization in the context of interactive optimization”, GECCO’14, pp. 461-468, 2014. DOI: 10.1145/2576768.2598213

Abstract: Optimization models used in planning and scheduling systems are not exempt from inaccuracies. These optimization systems often require an expert to assess solutions and to adjust them before taking decisions. However, adjusting a solution computed by an optimization procedure is difficult, especially because of the cascading effect. A small modification in a candidate solution may require to modify a large part of the solution. This obstacle to the adjustment of a solution can be overcome by interactive reoptimization. In this paper we analyze the impact of the cascading effect on a shift-scheduling problem and propose an efficient heuristic approach for reoptimizing solutions. The proposed approach is a local-search metaheuristic that has been adapted to the reoptimization. This approach is evaluated on a set of problem instances on which additional preferences are generated to simulate desired adjustments of a decision maker. Experimental results indicate that, even with a small perturbation, the cascading effect is manifest and cannot be efficiently tackled by applying recovery actions. Moreover, results show that the proposed reoptimization method provides significant cost gains within a short time while keeping a level of simplicity and modularity adequate for an implementation in a decision support system.

Article accepted at GECCO’2014 and nominated for best paper award

geccoCoverThe article “A heuristic approach to schedule reoptimization in the context of interactive optimization” (author: David Meignan), has been accepted at the next GECCO conference to be held in Vancouver (Canada). The paper has been nominated for a best paper award in the track “Evolutionary Combinatorial Optimization and Metaheuristics”.

“Praise (by Günther Raidl and Thomas Stützle): This paper proposes a new heuristic approach to the re-optimization of schedules, which is a task that frequently arises in practical situations, where experts assess and adjust solutions before taking final decisions. A detailed experimental study clearly establishes the effectiveness and the adequacy of the proposed approach.”

Press release on the website of the University of Osnabrück

Logo_UOSThe University of Osnabrück has published a “press release” announcing the project. The text in German is available here (Pressemitteilungen, Nr. 104/2013), and below is an English version.

New research project in Computer Science at the University of Osnabrück

The DFG has approved the funding of a research project on interactive optimization to Dr. David Meignan. The project will be conducted at the Institute of Computer Science of the University of Osnabrück for a period of two years. This project involves several collaborators in different countries: Dr. David Meignan (Principal investigator, University of Osnabrück, Germany), Pr. Sigrid Knust, Pr. Joachim Hertzberg, and Dipl.-Systemwiss. Florian Bruns (University of Osnabrück, Germany), Dr. Jean-Marc Frayret, and Pr. Gilles Pesant (Polytechnique Montréal, Canada), Pr. Abderrafiâa Koukam, and Pr. Vincent Hilaire (University of Technology of Belfort-Montbéliard, France).

The project funded by the DFG is the continuation of an initial study conducted since April 2012 by Dr. David Meignan and Pr. Sigrid Knust. This work on interactive optimization has been awarded by a grant from Google within the “Google Focused Grant Program on Mathematical Optimization and Combinatorial Optimization” in 2012.

Interactive optimization is the combination of combinatorial optimization methods with expertize of a human operator or user. Over the years, Operation Research has produced numbers of successful computational approaches and software tools for solving hard combinatorial optimization problems of practical significance. However, in several application domains there is still a large gap between research and application of advanced optimization methods, in particular for decision support tools. Interactive optimization is an active and promising paradigm to fill this gap between research and application.

The objectives of this project entitled “Interactive metaheuristics for optimization-based decision support systems” is to develop efficient and practical models, algorithms and software tools for the design of interactive optimisation methods for decision support systems. Two optimization problems have been identified for evaluating the proposed approach. The first one is a staff scheduling problem, whose objective is to determine satisfactory schedules for employees according to workload, legal constraints and staff preferences. The second optimization problem concerns the planning of operation in intermodal transportation.

More information:
Dr. David Meignan
Universität Osnabrück
Fachbereich 6, Mathematik/Informatik
Albrechtstr. 28
49076 Osnabrück
Office: 31/320
Telephone: +49 (0) 541 969-2509
Fax: +49 (0) 541 969-2799
Email: dmeignan [ at ] uos.de
Website: http://www.lalea.fr