Scheduling on Identical Machines: How Good is LPT in an On-Line Setting

摘要

The authors consider a parallel machine scheduling problem where jobs arrive overtime. A set of independent jobs has to be scheduled on m identical machines, where preemption is not allowed and the number of jobs is unknown in advance. The authors deal with the problem of minimizing the makspan, which is the time by which all jobs have been finished. They propose and analyze the following on-line LPT algorithm: At any time, a machine becomes available for processing, schedule an available job with the largest processing time. The authors prove that this algorithm has a performance guarantee of 3.2. Furthermore, they show that any on-line algorithm will have a performance bound of at least 1.3473.