  This paper studies Makespan Minimization in the secretary model. Formally,
jobs, specified by their processing times, are presented in a uniformly random
order. An online algorithm has to assign each job permanently and irrevocably
to one of m parallel and identical machines such that the expected time it
takes to process them all, the makespan, is minimized. We give two
deterministic algorithms. First, a straightforward adaptation of the
semi-online strategy LightLoad provides a very simple algorithm retaining its
competitive ratio of 1.75. A new and sophisticated algorithm is
1.535-competitive. These competitive ratios are not only obtained in
expectation but, in fact, for all but a very tiny fraction of job orders.
Classically, online makespan minimization only considers the worst-case order.
Here, no competitive ratio below 1.885 for deterministic algorithms and 1.581
using randomization is possible. The best randomized algorithm so far is
1.916-competitive. Our results show that classical worst-case orders are quite
rare and pessimistic for many applications. They also demonstrate the power of
randomization when compared to much stronger deterministic reordering models.
We complement our results by providing first lower bounds. A competitive ratio
obtained on nearly all possible job orders must be at least 1.257. This implies
a lower bound of 1.043 for both deterministic and randomized algorithms in the
general model.
