The bounded single-machine parallel-batching scheduling problem with family jobs and release dates to minimize makespan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

21 Citations (Scopus)

Abstract

We consider the problem of scheduling family jobs with release dates on a bounded batching machine to minimize the makespan. A polynomial-time approximation scheme for the identical job size model and an approximation algorithm with a worst-case ratio of frac(5, 2) for the non-identical job size model will be derived.
Original languageEnglish
Pages (from-to)61-66
Number of pages6
JournalOperations Research Letters
Volume36
Issue number1
DOIs
Publication statusPublished - 1 Jan 2008

Keywords

  • Approximation algorithm
  • Batching
  • Family
  • Single-machine scheduling
  • 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