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)

Abstract

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
Volume36
Issue number5
DOIs
Publication statusPublished - 1 Sep 2008

Keywords

  • 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