An improved on-line algorithm for scheduling on two unrestrictive parallel batch processing machines

Research output: Journal article publicationJournal articleAcademic researchpeer-review

20 Citations (Scopus)


We consider the problem of on-line scheduling a set of n jobs on two parallel batch processing machines. The objective is to minimize the makespan. We provide an algorithm for the problem that is better than one given in the literature, improving the competitive ratio from frac(3, 2) to sqrt(2).
Original languageEnglish
Pages (from-to)584-588
Number of pages5
JournalOperations Research Letters
Issue number5
Publication statusPublished - 1 Sep 2008


  • Batch
  • Competitive ratio
  • On-line scheduling
  • Parallel machines
  • Worst-case analysis

ASJC Scopus subject areas

  • Management Science and Operations Research
  • Statistics, Probability and Uncertainty
  • Discrete Mathematics and Combinatorics
  • Modelling and Simulation

Cite this