A heuristic approach to schedule reoptimization in the context of interactive optimization
A heuristic approach to schedule reoptimization in the context of interactive optimization
复制标题
DOI：
10.1145/2576768.2598213
复制
发表时间：
2014-07
期刊：
影响因子：
--
通讯作者：
D. Meignan
中科院分区：
文献类型：
--
作者：
D. Meignan
计划和调度系统中使用的优化模型也不能幸免于不准确。这些优化系统通常需要专家来评估解决方案，并在做出决策之前对其进行调整。然而，调整通过优化过程计算的解是困难的，尤其是因为级联效应。候选解决方案中的一小部分修改可能需要修改解决方案的大部分。这种解决方案调整的障碍可以通过交互式重新优化来克服。本文分析了层叠效应对换班调度问题的影响，并提出了一种高效的启发式方法来重新优化解。该方法是一种局部搜索的元启发式算法，已适应于重新优化。这种方法是在一组问题实例上进行评估的，在这些实例上生成了额外的偏好，以模拟决策者所需的调整。实验结果表明，即使有很小的扰动，级联效应也是明显的，不能通过施加恢复作用来有效地解决。此外，结果表明，所提出的再优化方法在短时间内提供了显著的成本收益，同时保持了足够的简单性和模块化程度，足以在决策支持系统中实现。
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.