Abstract
The problem of nonpreemptive scheduling to minimize average (weighted) completion time, allowing for release dates, parallel machines, and precedence constraints is considered. New techniques are introduced which generalize recent approaches based on linear programming relaxation. An optimal randomized online algorithm is obtained for the same problem which beats a lower bound for deterministic online algorithms. The problem is extended to the case of parallel machine scheduling. In this case, the efficiencies of preemptive one-machine relaxation and non-greedy `rounding' of the relaxation are demonstrated. A general theorem relating the value of one-machine relaxations to the value of schedules obtained for n-machine problems is proven.
| Original language | English (US) |
|---|---|
| Pages | 609-618 |
| Number of pages | 10 |
| State | Published - 1997 |
| Externally published | Yes |
| Event | Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA, USA Duration: Jan 5 1997 → Jan 7 1997 |
Other
| Other | Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms |
|---|---|
| City | New Orleans, LA, USA |
| Period | 1/5/97 → 1/7/97 |
ASJC Scopus subject areas
- Software
- Mathematics(all)