Single machine batch scheduling problem with family setup times 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

16 Citations (Scopus)

Abstract

In this paper we consider the single machine batch scheduling problem with family setup times and release dates to minimize makespan. We show that this problem is strongly NP-hard, and give an O(n (m-n+1)m) time dynamic programming algorithm and an O(mkkP2k-1) time dynamic programming algorithm for the problem, 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 setup times of all the families and the processing times of all the jobs. We further give a heuristic with a performance ratio 2. We also give a polynomial-time approximation scheme (PTAS) for the problem.
Original languageEnglish
Pages (from-to)499-513
Number of pages15
JournalJournal of Scheduling
Volume9
Issue number6
DOIs
Publication statusPublished - 1 Dec 2006

Keywords

  • Batching
  • Family
  • Makespan
  • Release dates
  • Scheduling

ASJC Scopus subject areas

  • Software
  • Engineering(all)
  • Management Science and Operations Research
  • Artificial Intelligence

Cite this