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

Johann L. Hurink, J.J. Paulus

Research output: Contribution to journalArticleAcademicpeer-review

23 Citations (Scopus)


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.
Original languageUndefined
Article number10.1016/j.orl.2007.06.001
Pages (from-to)51-56
Number of pages6
JournalOperations research letters
Issue number1
Publication statusPublished - Jan 2008


  • EWI-11663
  • IR-62089
  • METIS-250858

Cite this