Online Makespan Minimization with Parallel Schedules

• Published in: Algorithmica 2017-06, Vol.78 (2), p.492-520
• Main Authors: Albers, Susanne, Hellwig, Matthias
• Format: Article
• Language: English
• Subjects: Algorithm Analysis and Problem Complexity; Algorithms; Augmentation; Completion time; Computer Science; Computer Systems Organization and Communication Networks; Data Structures and Information Theory; Job shops; Mathematical models; Mathematics of Computing; Microprocessors; Optimization; Parallel processing; Production scheduling; Schedules; Scheduling; Theory of Computation; Universe
• ISSN: 0178-4617; 1432-0541
• DOI: 10.1007/s00453-016-0172-5

Online makespan minimization is a classical problem in which a sequence of jobs σ = J 1 , … , J n has to be scheduled on m identical parallel machines so as to minimize the maximum completion time of any job. In this paper we investigate the problem with an essentially new model of resource augmentation. More specifically, an online algorithm is allowed to build several schedules in parallel while processing σ . At the end of the scheduling process the best schedule is selected. This model can be viewed as providing an online algorithm with extra space, which is invested to maintain multiple solutions. The setting is of particular interest in parallel processing environments where each processor can maintain a single or a small set of solutions. As a main result we develop a ( 4 / 3 + ε ) -competitive algorithm, for any 0 < ε ≤ 1 , that uses a constant number of schedules. The constant is equal to 1 / ε O ( log ( 1 / ε ) ) . We also give a ( 1 + ε ) -competitive algorithm, for any 0 < ε ≤ 1 , that builds a polynomial number of ( m / ε ) O ( log ( 1 / ε ) / ε ) schedules. This value depends on m but is independent of the input σ . The performance guarantees are nearly best possible. We show that any algorithm that achieves a competitiveness smaller than 4 / 3 must construct Ω ( m ) schedules. Our algorithms make use of novel guessing schemes that (1) predict the optimum makespan of a job sequence σ to within a factor of 1 + ε and (2) guess the job processing times and their frequencies in σ . In (2) we have to sparsify the universe of all guesses so as to reduce the number of schedules to a constant. We remark that the competitive ratios achieved using parallel schedules are considerably smaller than those in the standard problem without resource augmentation. Furthermore they are at least as good and in most cases better than the ratios obtained with other means of resource augmentation for makespan minimization.