The unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan

J. J. Yuan, Z. H. Liu, Chi To Ng, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

33 Citations (Scopus)

Abstract

In this paper we consider the unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan. We show that this problem is strongly NP-hard, and give an O(n(n/m+1)m) time dynamic programming algorithm and an O(mkk+1P2k-1) time dynamic programming algorithm, where n is the number of jobs, m is the number of families, k is the number of distinct release dates and P is the sum of the processing times of all families. We further give a heuristic with a performance ratio 2. We also give a polynomial-time approximation scheme for the problem.
Original languageEnglish
Pages (from-to)199-212
Number of pages14
JournalTheoretical Computer Science
Volume320
Issue number2-3
DOIs
Publication statusPublished - 14 Jun 2004

Keywords

  • Batching
  • Family
  • Makespan
  • Scheduling

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this