Approximation schemes for minimizing total (weighted) completion time with release dates on a batch machine

Research output: Journal article publicationJournal articleAcademic researchpeer-review

16 Citations (Scopus)

Abstract

A batch machine is a machine that can process a number of jobs simultaneously as a batch, and the processing time of a batch is equal to the longest processing time of the jobs assigned to it. In this paper, we present a polynomial time approximation scheme (PTAS) for scheduling a batch machine to minimize the total completion time with job release dates. Also, we present a fully polynomial time approximation scheme (FPTAS) for scheduling an unbounded batch machine, which can process an arbitrary number of jobs simultaneously, to minimize the total weighted completion time with job release dates.
Original languageEnglish
Pages (from-to)288-298
Number of pages11
JournalTheoretical Computer Science
Volume347
Issue number1-2
DOIs
Publication statusPublished - 30 Nov 2005

Keywords

  • Approximation scheme
  • Batch processing
  • Scheduling

ASJC Scopus subject areas

  • Computational Theory and Mathematics

Cite this