Batch scheduling of step deteriorating jobs

M. S. Barketau, Edwin Tai Chiu Cheng, Chi To Ng, Vladimir Kotov, Mikhail Y. Kovalyov

Research output: Journal article publicationJournal articleAcademic researchpeer-review

18 Citations (Scopus)


In this paper we consider the problem of scheduling n jobs on a single machine, where the jobs are processed in batches and the processing time of each job is a step function depending on its waiting time, which is the time between the start of the processing of the batch to which the job belongs and the start of the processing of the job. For job i, if its waiting time is less than a given threshold value D, then it requires a basic processing time ai; otherwise, it requires an extended processing time ai+bi. The objective is to minimize the completion time of the last job. We first show that the problem is NP-hard in the strong sense even if all biare equal, it is NP-hard even if bi=aifor all i, and it is non-approximable in polynomial time with a constant performance guarantee Δ<3/2, unless. We then present O(nlog∈n) and O(n3F-1log∈n/FF) algorithms for the case where all aiare equal and for the case where there are F, F 2, distinct values of ai, respectively. We further propose an O(n2log∈n) approximation algorithm with a performance guarantee for the general problem, where m * is the number of batches in an optimal schedule. All the above results apply or can be easily modified for the corresponding open-end bin packing problem.
Original languageEnglish
Pages (from-to)17-28
Number of pages12
JournalJournal of Scheduling
Issue number1
Publication statusPublished - 1 Feb 2008


  • Batching
  • Deterioration
  • Open-end bin packing
  • Scheduling

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering
  • Management Science and Operations Research


Dive into the research topics of 'Batch scheduling of step deteriorating jobs'. Together they form a unique fingerprint.

Cite this