论文标题
通过多面体不确定性可回收可恢复的稳健单机调度
Recoverable Robust Single Machine Scheduling with Polyhedral Uncertainty
论文作者
论文摘要
本文考虑了在多面体不确定性下可回收的鲁棒单机调度问题，目的是最大程度地减少总流动时间。在这种情况下，决策者必须根据不确定的工作处理时间确定第一阶段时间表。然后，遵循这些处理时间的实现，他们可以选择交换最多的Delta分离对工作的位置，以获得第二阶段的时间表。 在进一步详细介绍增量子问题之前，我们首先使用一般可回收的鲁棒框架来提出这个调度问题。我们证明了最大重量匹配问题的一般结果，表明对于特定形式的边缘权重，匹配的多层可以完全以多种方式约束。我们使用此结果来得出完整问题的基于匹配的紧凑配方。对增量问题的进一步分析会导致基于分配的紧凑配方。预算不确定性集的计算结果比较了我们提出的三种紧凑模型的相对强度。
This paper considers a recoverable robust single-machine scheduling problem under polyhedral uncertainty with the objective of minimising the total flow time. In this setting, a decision-maker must determine a first-stage schedule subject to the uncertain job processing times. Then following the realisation of these processing times, they have the option to swap the positions of up to Delta disjoint pairs of jobs to obtain a second-stage schedule. We first formulate this scheduling problem using a general recoverable robust framework, before we examine the incremental subproblem in further detail. We prove a general result for max-weight matching problems, showing that for edge weights of a specific form, the matching polytope can be fully characterised by polynomially many constraints. We use this result to derive a matching-based compact formulation for the full problem. Further analysis of the incremental problem leads to an additional assignment-based compact formulation. Computational results on budgeted uncertainty sets compare the relative strengths of the three compact models we propose.
