Robust Online Algorithms for Scheduling and Packing Problems

点击翻译按钮获取中文摘要

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.