|
|||||
|
|
On-line scheduling to minimize average completion time revisited |
|
| Authors: | Nicole Megow Andreas S Schulz |
| Affiliation: | a Institut für Mathematik, Technische Universität Berlin, Sekr. MA 6-1, Strasse des 17. Juni 136, Berlin 10623, Germany b Sloan School of Management, Massachusetts Institute of Technology, Office E53-361, 77 Massachusetts Avenue, Cambridge, MA 02139-4307, USA |
| Abstract: | 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 than the previously best-known deterministic on-line algorithms. |
| Keywords: | Scheduling On-line algorithm Approximation algorithm Competitive analysis |
| 本文献已被 ScienceDirect 等数据库收录！ | |