  Makespan minimization on identical machines is a fundamental problem in
online scheduling. The goal is to assign a sequence of jobs to $m$ identical
parallel machines so as to minimize the maximum completion time of any job.
Already in the 1960s, Graham showed that Greedy is $(2-1/m)$-competitive. The
best deterministic online algorithm currently known achieves a competitive
ratio of 1.9201. No deterministic online strategy can obtain a competitiveness
smaller than 1.88.
  In this paper, we study online makespan minimization in the popular
random-order model, where the jobs of a given input arrive as a random
permutation. It is known that Greedy does not attain a competitive factor
asymptotically smaller than 2 in this setting. We present the first improved
performance guarantees. Specifically, we develop a deterministic online
algorithm that achieves a competitive ratio of 1.8478. The result relies on a
new analysis approach. We identify a set of properties that a random
permutation of the input jobs satisfies with high probability. Then we conduct
a worst-case analysis of our algorithm, for the respective class of
permutations. The analysis implies that the stated competitiveness holds not
only in expectation but with high probability. Moreover, it provides
mathematical evidence that job sequences leading to higher performance ratios
are extremely rare, pathological inputs. We complement the results by lower
bounds, for the random-order model. We show that no deterministic online
algorithm can achieve a competitive ratio smaller than 4/3. Moreover, no
deterministic online algorithm can attain a competitiveness smaller than 3/2
with high probability.
