Scheduling jobs with release dates on parallel batch processing machines

Research output: Journal article publicationJournal articleAcademic researchpeer-review

12 Citations (Scopus)

Abstract

In this paper we consider the problem of scheduling jobs with release dates on parallel unbounded batch processing machines to minimize the maximum lateness. We show that the case where the jobs have deadlines is strongly NP-hard. We develop a polynomial-time approximation scheme for the problem to minimize the maximum delivery completion time, which is equivalent to minimizing the maximum lateness from the optimization viewpoint.
Original languageEnglish
Pages (from-to)1825-1830
Number of pages6
JournalDiscrete Applied Mathematics
Volume157
Issue number8
DOIs
Publication statusPublished - 28 Apr 2009

Keywords

  • Computational Complexity
  • Parallel batch processing machines
  • PTAS
  • Release dates
  • Scheduling

ASJC Scopus subject areas

  • Applied Mathematics
  • Discrete Mathematics and Combinatorics

Cite this