Scheduling jobs with release dates on parallel batch processing machines

Research output: Journal article publicationJournal articleAcademic researchpeer-review

14 Citations (Scopus)


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
Issue number8
Publication statusPublished - 28 Apr 2009


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

ASJC Scopus subject areas

  • Applied Mathematics
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Scheduling jobs with release dates on parallel batch processing machines'. Together they form a unique fingerprint.

Cite this