Optimal Online Algorithms for Minimax Resource Scheduling
Brady Hunsaker, Anton J. Kleywegt, Martin W. P. Savelsbergh, Craig A. Tovey · SIAM Journal on Discrete Mathematics · 2003
We consider a very general online scheduling problem with an objective to minimize the maximum level of resource allocated. We find a simple characterization of an optimal deterministic online algorithm. We develop further results for the two, more specific problems of single resource scheduling and hierarchical line balancing. We determine how to compute optimal online algorithms for both problems using linear programming and integer programming, respectively. We show that randomized algorithms can outperform deterministic algorithms, but only if the amount of work done is a nonconcave function of resource allocation.