| Article ID: | iaor201111635 |
| Volume: | 14 |
| Issue: | 6 |
| Start Page Number: | 571 |
| End Page Number: | 581 |
| Publication Date: | Dec 2011 |
| Journal: | Journal of Scheduling |
| Authors: | Schwiegelshohn Uwe |
| Keywords: | combinatorial optimization, scheduling |
The paper discusses a rarely used metric that is well suited to evaluate online schedules for independent jobs on massively parallel processors. The metric is based on the total weighted completion time objective with the weight being the resource consumption of the job. Although every job contributes to the objective value, the metric exhibits many properties that are similar to the properties of the makespan objective. For this metric, we particularly address nonclairvoyant online scheduling of sequential jobs on parallel identical machines and prove an almost tight competitive factor of 1.25 for nondelay schedules. For the extension of the problem to rigid parallel jobs, we show that no constant competitive factor exists. However, if all jobs are released at time 0, List Scheduling in descending order of the degree of parallelism guarantees an approximation factor of 2.