Single-machine batch scheduling with job processing time compatibility

Shisheng Li, Edwin Tai Chiu Cheng, Chi To Ng, Jinjiang Yuan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

5 Citations (Scopus)


We consider scheduling problems with job processing time compatibility on a single unbounded batch machine. Each job's processing time is characterized by an interval. Any number of jobs can be processed in a batch under the condition that the processing time intervals of the jobs in the same batch have a nonempty intersection. The processing time of a batch is given by the left endpoint of the intersection of the processing time intervals of the jobs in the batch. For the makespan minimization problem with individual job release dates, we design a pseudo-polynomial dynamic programming algorithm for the case where the number of distinct release dates is fixed. We also present a class of online algorithms that are 2-competitive and a polynomial-time approximation scheme for the case where the number of release dates is arbitrary. For the problem to minimize the weighted number of tardy jobs under a common due date, we show that it is binary NP-hard and provide a polynomial-time algorithm when the jobs have a common weight.
Original languageEnglish
Pages (from-to)57-66
Number of pages10
JournalTheoretical Computer Science
Publication statusPublished - 1 Jan 2015


  • Approximation algorithm
  • Batch machine
  • Compatibility
  • Release date

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this