Online scheduling of parallel jobs on two machines is 2-competitive |
| |
| Authors: | J.L. Hurink |
| |
| Affiliation: | University of Twente, P.O. box 217, 7500AE Enschede, The Netherlands |
| |
| Abstract: | We consider online scheduling of parallel jobs on parallel machines. For the problem with two machines and the objective of minimizing the makespan, we show that 2 is a tight lower bound on the competitive ratio. For the problem with m machines, we derive lower bounds using an ILP formulation. |
| |
| Keywords: | Online scheduling Parallel jobs Competitive analysis |
| 本文献已被 ScienceDirect 等数据库收录！ |
