A best possible online algorithm for scheduling equal-length jobs on two machines with chain precedence constraints
| Autor: | Wenhua Li, Junling Yuan, Jinjiang Yuan |
|---|---|
| Rok vydání: | 2012 |
| Předmět: |
Mathematical optimization
General Computer Science Competitive analysis Job shop scheduling Computer science Distributed computing Equal-length jobs Fair-share scheduling Competitive ratio Theoretical Computer Science Scheduling (computing) Chain precedence constraints Online algorithm Computer Science(all) Parallel-machine scheduling |
| Zdroj: | Theoretical Computer Science. 457:174-180 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2012.07.009 |
| Popis: | We consider the online scheduling on two identical parallel machines with chain precedence constraints to minimize makespan, where jobs arrive over time and have identical processing times. For this online scheduling problem, Huo and Leung [Y. Huo and J.Y.-T. Leung, Online scheduling of precedence constrained tasks, SIAM Journal on Computing, 34 (2005), 743–762] proved that it is impossible to have an online algorithm of a competitive ratio 1. We provide a best possible online algorithm of competitive ratio 13−12. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect