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

Johann L. Hurink, J.J. Paulus

Research output: Book/ReportReportProfessional

86 Downloads (Pure)

Abstract

We consider online scheduling of parallel jobs on parallel machines. For the problem with two machines and the objective of minimizing the makespan, $P2|online-list,m_j|C_{max}$, we show that 2 is a lower bound on the competitive ratio of any online algorithm. Thereby we not only improve the existing lower bound of $1+\sqrt{2/3}$, but also close the gap with the trivial upper bound of 2. For the problem with m machines, $Pm|online-list,m_j |C_{max}$, we derive lower bounds using an ILP formulation. Futhermore, we show that with the presented construction no lower bound greater than 2.5 can be obtained.
Original languageUndefined
Place of PublicationEnschede
PublisherBETA Research School for Operations Management and Logistics
Number of pages13
Publication statusPublished - Feb 2007

Publication series

NameBeta working papers
PublisherBeta Research School for Operations Management and Logistics, University of Twente
No.2/WP-200
ISSN (Print)1386-9213

Keywords

  • IR-67006
  • METIS-242069
  • EWI-9514

Cite this

Hurink, J. L., & Paulus, J. J. (2007). Online scheduling of parallel jobs on two machines is 2-competitive. (Beta working papers; No. 2/WP-200). Enschede: BETA Research School for Operations Management and Logistics.