Minimizing sum of completion times for batch scheduling of jobs with deteriorating processing times

Joseph Y T Leung, Chi To Ng, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

33 Citations (Scopus)


We consider the problem of scheduling n jobs on m ≥ 1 parallel and identical machines, where the jobs are processed in batches and the processing time of each job is a step function of its waiting time; i.e., 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 each job i, if its waiting time is less than a given threshold D, then it requires a basic processing time pi= ai; otherwise, it requires an extended processing time pi= ai+ bi. The objective is to minimize the sum of completion times; i.e., ∑i = 1nCi, where Ciis the completion time of job i. We first show that the problem is NP-hard in the strong sense even if there is a single machine and bi= b for all 1 ≤ i ≤ n. We then show that the problem is solvable in polynomial time if ai= a for all 1 ≤ i ≤ n. Our algorithm runs in O(n2) time. Finally, we give an approximation algorithm for the special case where bi≤ D for all 1 ≤ i ≤ n, and show that it has a performance guarantee of 2.
Original languageEnglish
Pages (from-to)1090-1099
Number of pages10
JournalEuropean Journal of Operational Research
Issue number3
Publication statusPublished - 16 Jun 2008


  • Batch scheduling
  • Deteriorating processing times
  • Performance guarantee
  • Strong NP-hardness
  • Sum of completion times

ASJC Scopus subject areas

  • Information Systems and Management
  • Management Science and Operations Research
  • Statistics, Probability and Uncertainty
  • Applied Mathematics
  • Modelling and Simulation
  • Transportation

Cite this