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

34 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)

Fingerprint

Dive into the research topics of 'The unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan'. Together they form a unique fingerprint.
  • Outstanding Natural Sciences Paper Award

    Yuan, J.J. (Recipient), Liu, Z.H. (Recipient), Ng, Chi To (Recipient) & Cheng, Edwin Tai Chiu (Recipient), Jul 2006

    Prize: Prize (research)

  • Outstanding Science and Technology Paper Award

    Yuan, J.J. (Recipient), Liu, Z.H. (Recipient), Ng, Chi To (Recipient) & Cheng, Edwin Tai Chiu (Recipient), Aug 2006

    Prize: Prize (research)

Cite this