Single-machine batch scheduling of linear deteriorating jobs

Min Ji, Qinyun Yang, Danli Yao, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

5 Citations (Scopus)


We consider the problem of scheduling jobs in batches on a single machine where the processing time of each job is a simple increasing linear function of its waiting time, i.e., the time between the starting time of processing the batch to which the job belongs and the starting time of processing of the job. The objective is to minimize the sum of the total job flow time and the batching cost. We first show that the case with a given number of batches is strongly NP-hard and we present a fully polynomial-time approximation scheme (FPTAS) for this case. We then show that the case with an arbitrary number of batches is also strongly NP-hard and there is no polynomial-time approximation algorithm with a constant upper bound for this case unless P= NP.
Original languageEnglish
Pages (from-to)36-49
Number of pages14
JournalTheoretical Computer Science
Publication statusPublished - 17 May 2015


  • Batch
  • Deteriorating jobs
  • Non-approximability
  • NP-hardness
  • Scheduling

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this