𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximation Techniques for Average Completion Time Scheduling

✍ Scribed by Chekuri, C.; Motwani, R.; Natarajan, B.; Stein, C.

Book ID
118180453
Publisher
Society for Industrial and Applied Mathematics
Year
2001
Tongue
English
Weight
229 KB
Volume
31
Category
Article
ISSN
0097-5397

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On-line scheduling to minimize average c
On-line scheduling to minimize average completion time revisited
✍ Nicole Megow; Andreas S Schulz πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 192 KB

We consider the scheduling problem of minimizing the average-weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith's ratio rule yield smaller competitive ratios

A fully combinatorial 2-approximation al
A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion time
✍ N.N. Pisaruk πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 217 KB

We study the problem of scheduling a single machine with the precedence relation on the set of jobs to minimize average weighted completion time. The problem is strongly NP-hard. The ΓΏrst combinatorial 2-approximation algorithm for this scheduling problem was developed by the author in 1992 (in fact