Article ID Journal Published Year Pages File Type
1143200 Operations Research Letters 2008 6 Pages PDF
Abstract

We consider online scheduling of parallel jobs on parallel machines. For the problem with two machines and the objective of minimizing the makespan, we show that 2 is a tight lower bound on the competitive ratio. For the problem with m machines, we derive lower bounds using an ILP formulation.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
Online scheduling of parallel jobs on two machines is 2-competitive
Authors
, ,