| Autor: |
Gerhard J. Woeginger, Bo Chen, André van Vliet |
| Jazyk: |
angličtina |
| Rok vydání: |
1994 |
| Předmět: |
|
| Zdroj: |
Operations Research Letters, 16(4), 221-230. Elsevier |
| ISSN: |
0167-6377 |
| DOI: |
10.1016/0167-6377(94)90071-x |
| Popis: |
We investigate the problem of on-line scheduling a set of independent jobs on m parallel and identical machines with the objective of minimizing the overall finishing time. In this note, we are mainly interested in the cases where m is small. We derive results on the inevitable worst-case deviations from the optimum as encountered by any on-line algorithm. For m = 2 and m = 3, Graham's List Scheduling heuristic is known to be best possible. For m = 4, we will derive almost matching upper and lower bounds on the best possible worst-case guarantee for any on-line algorithm. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
