Robust Online Algorithms for Scheduling and Packing Problems

本研究项目的目标是为基本的包装和调度问题设计鲁棒的在线算法；例如，在相同和统一的机器上调度，以及箱和条形包装问题。虽然存在这些问题的离线变体的近似算法和方案，它们产生接近最优解的解，但这在经典的在线设置中是不可能的。例如，在相同机器上调度的情况下，不存在竞争比大于1.88的在线算法。在实际应用的激励下，研究社区研究了几个有趣的模型，其中实际的时间表可以在新工作到来时改变。事实上，工作岗位的迁移受到所谓迁移因子\beta的限制。如果一个执行时间为p_j的新作业到达，则允许它重新调度总执行时间为\beta p_j的一组作业。有趣的是所谓的鲁棒在线算法，它具有恒定的迁移因子。我们的重点是研究算法的保证竞争比和使用的迁移因子之间的权衡。我们想解决几个悬而未决的问题。我们项目的其他目标包括开发（整数）线性规划(I) lp敏感性分析的基础技术，探索鲁棒近似方案使用的迁移因子的下界，以及研究具有小迁移因子的简单在线算法是否可以在没有迁移的情况下胜过在线问题的下界。

The goal of this research project is the design of robust online algorithms for fundamental packing and scheduling problems; e.g. scheduling on identical and uniform machines and bin and strip packing problems. While there are approximation algorithms and schemes for the offline variants of these problems which generate solutions close to the optimum ones, this is not possible in the classical online setting. For example in the case of scheduling on identical machines there does not exist an online algorithm with competitive ratio better than 1.88. Motivated by practical applications several interesting models have been studied in the research community where the actual schedule can be changed when a new job arrives. In fact the migration of jobs is limited by the so called migration factor \beta. If a new job with execution time p_j arrives, it is allowed to reschedule a set of jobs with total execution time \beta p_j. Interesting are so called robust online algorithms which have a constant migration factor. Our focus is to study the trade off between the guaranteed competitive ratio of the algorithm and the used migration factor. We want to solve several open questions. Other goals of our project include the development of underlying techniques of the sensitivity analysis of (integer) linear programs (I)LPs, the exploration of lower bounds of the migration factor used by robust approximation schemes, and studying whether simple online algorithms with small migration factor can beat the lower bounds for the online problems without migration.