Online scheduling of parallel jobs on two machines is 2-competitive

Share/Save/Bookmark

Hurink, J.L. and Paulus, J.J. (2008) Online scheduling of parallel jobs on two machines is 2-competitive. Operations Research Letters, 36 (1). pp. 51-56. ISSN 0167-6377

[img] PDF
Restricted to UT campus only
: Request a copy
151kB
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.
Item Type:Article
Copyright:© 2008 Elsevier
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/62089
Official URL:http://dx.doi.org/10.1016/j.orl.2007.06.001
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 250858