Special cases of online parallel job scheduling

Johann L. Hurink, J.J. Paulus

Research output: Book/ReportReportProfessional

46 Downloads (Pure)


In this paper we consider the online scheduling of jobs, which require processing on a number of machines simultaneously. These jobs are presented to a decision maker one by one, where the next job becomes known as soon as the current job is scheduled. The objective is to minimize the makespan. For the problem with three machines we give a 2.8-competitive algorithm, improving upon the 3-competitive greedy algorithm. For the special case with arbitrary number of machines, where the jobs appear in non-increasing order of machine requirement, we give a 2.4815-competitive algorithm, improving the 2.75-competitive greedy algorithm.
Original languageUndefined
Place of PublicationEindhoven
PublisherBETA Research School for Operations Management and Logistics
Number of pages20
ISBN (Print)9789038612188
Publication statusPublished - 26 Nov 2007

Publication series

NameBeta working papers
PublisherBeta Research School for Operations Management and Logistics
ISSN (Print)1386-9213


  • METIS-245844
  • EWI-11536
  • IR-64518

Cite this