论文标题
在不确定的工作技能要求下，可用于路由和调度多技能团队的强大优化方法
Robust Optimization Approaches for Routing and Scheduling of Multi-Skilled Teams under Uncertain Job Skill Requirements
论文作者
论文摘要
我们考虑了多技能员工的组合问题和安排，这些员工必须执行不确定资格要求的工作。我们提出了两种建模方法，它们生成解决可能数据变化的解决方案。两种方法都使用预算不确定性的变体，其中资格要求的偏差受限制。在第一种方法中，我们汇总了不确定的限制，以确保作业中存在的工作资格总数不小于最差的案例价值。我们表明，可以事先计算这些值，从而导致与名义模型相比的稳健模型，几乎没有额外的复杂性。在我们的第二种方法中，我们将所有工作的总体资格偏差约束。尽管这种方法更为复杂，但我们表明，通过基于动态程序的对抗性问题使用线性编程公式来得出紧凑的问题制定。在最初为确定性问题版本提供的实例测试床上分析了两种方法的性能。我们的实验显示了在存在数据不确定性的情况下提出的方法的有效性，并揭示了稳健性的价格和增长。
We consider a combined problem of teaming and scheduling of multi-skilled employees that have to perform jobs with uncertain qualification requirements. We propose two modeling approaches that generate solutions that are robust to possible data variations. Both approaches use variants of budgeted uncertainty, where deviations in qualification requirements are bounded by a constraint. In the first approach, we aggregate uncertain constraints to ensure that the total number of job qualifications present at a job is not less than a worst-case value. We show that these values can be computed beforehand, resulting in a robust model with little additional complexity compared with the nominal model. In our second approach, we bound the overall qualification deviation over all jobs. While this approach is more complex, we show that it is still possible to derive a compact problem formulation by using a linear programming formulation for the adversarial problem based on a dynamic program. The performance of both approaches is analyzed on a test bed of instances which were originally provided for a deterministic problem version. Our experiments show the effectiveness of the proposed approaches in the presence of data uncertainty and reveal the price and gain of robustness.
