Title: Approximation techniques for average completion time scheduling
Abstract: We consider the problem of nonpreemptive scheduling to minimize average (weighted) completion time, allowing for release dates, parallel machines, and precedence constraints. Recent work has led to constant-factor approximations for this problem, based on solving a preemptive or linear programming relaxation and then using the solution to get an ordering on the jobs. We introduce several new techniques which generalize this basic paradigm. We use these ideas to obtain improved approximation algorithms for one-machine scheduling to minimize average completion time with release dates. In the process, we obtain an optimal randomized on-line algorithm for the same problem that beats a lower bound for deterministic on-line algorithms. We consider extensions to the case of parallel machine scheduling, and for this we introduce two new ideas: first, we show that a preemptive one-machine relaxation is a powerful tool for designing parallel machine scheduling algorithms that simultaneously produce good approximations and have small running times; second, we show that a non-greedy {open_quotes}rounding{close_quotes} of the relaxation yields better approximations than a greedy one. We also prove a general theorem relating the value of one-machine relaxations to that of the schedules obtained for the original m-machine problems. This theorem applies even when there are precedencemore » constraints on the jobs. We apply this result to precedence graphs such as in-trees, out-trees, and series- parallel graphs; these are of particular interest in compiler applications that partly motivated our work.« less
Publication Year: 1997
Publication Date: 1997-01-05
Language: en
Type: article
Access and Citation
Cited By Count: 81
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot