Scheduling in the Random-Oder Model.

Abstract:  We study Online Makespan Minimization, one of the most basic scheduling problems, in the random-order model. Here jobs of a given input arrive in a uniformly chosen random order as opposed to the classical adversarial model, which considers worst-case orders. The random-order model originates from the Secretary Problem and has received quite some research interest over the last years.

For scheduling, the random-order model provides beyond worst-case guarantees while still not being overly pessimistic. Furthermore, it leads to a stronger performance measure, which considers ‘nearly worst-case’ orders. Recent results on Makespan Minimization in the random-order model outperform classical lower bounds, even using this stronger measure. This proves formally that classical worst-case sequences are highly order-reliant and should therefore be rare in practical applications.

In this talk we discuss the role of random-order arrival for Makespan Minimization. We compare recent random-order bounds with various classical online and semi-online guarantees, and introduce key techniques, which allow to profit from random-order arrival. These techniques should be relevant for further research on Random-Order Makespan Minimization and related problems.

Posted on Mar 29, 2021 in ACGO, Seminars