Single machine batch scheduling with deadlines and resource dependent processing times

Edwin Tai Chiu Cheng, Mikhail Y. Kovalyov

Research output: Journal article publicationJournal articleAcademic researchpeer-review

36 Citations (Scopus)

Abstract

We consider the problem of scheduling n jobs on a single machine where each job has a deadline and a processing time that is a linear decreasing function of the amount of a common discrete resource allocated to the job. Jobs may be combined to form batches containing contiguously scheduled jobs. For each batch, a constant set-up time is needed before the first job of the batch is processed. The completion time of each job in a batch coincides with the completion time of the last job in the batch. A schedule specifies the sequence of jobs and the size of each batch, i.e. the number of jobs it contains. The objective is to find simultaneously a resource allocation and a schedule which is feasible with respect to the deadlines so as to minimize the total weighted resource consumption. The problem is shown to be NP-hard even for the special case of common parameters. Two dynamic programming algorithms are presented for the general problem, as well as a fully polynomial approximation scheme.
Original languageEnglish
Pages (from-to)243-249
Number of pages7
JournalOperations Research Letters
Volume17
Issue number5
DOIs
Publication statusPublished - 1 Jan 1995

Keywords

  • Batching
  • Dynamic programming
  • Fully polynomial approximation scheme
  • Resource allocation
  • Single machine scheduling

ASJC Scopus subject areas

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Cite this