Batch scheduling of simple linear deteriorating jobs on a single machine to minimize makespan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

40 Citations (Scopus)

Abstract

We consider a scheduling problem in which n jobs are to be processed on a single machine. The jobs are processed in batches and the processing time of each job is a simple linear 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. The objective is to minimize the makespan, i.e., the completion time of the last job. We first show that the problem is strongly NP-hard. Then we show that, if the number of batches is B, the problem remains strongly NP-hard when B ≤ U for a variable U ≥ 2 or B ≥ U for any constant U ≥ 2. For the case of B ≤ U, we present a dynamic programming algorithm that runs in pseudo-polynomial time and a fully polynomial time approximation scheme (FPTAS) for any constant U ≥ 2. Furthermore, we provide an optimal linear time algorithm for the special case where the jobs are subject to a linear precedence constraint, which subsumes the case where all the job growth rates are equal.
Original languageEnglish
Pages (from-to)90-98
Number of pages9
JournalEuropean Journal of Operational Research
Volume202
Issue number1
DOIs
Publication statusPublished - 1 Apr 2010

Keywords

  • Batch scheduling
  • Computational complexity
  • FPTAS
  • Makespan

ASJC Scopus subject areas

  • Management Science and Operations Research
  • Modelling and Simulation
  • Information Systems and Management

Cite this