Affordable Access

Publisher Website

Single machine batch scheduling with deadlines and resource dependent processing times

Elsevier B.V.
Publication Date
DOI: 10.1016/0167-6377(95)00011-8
  • Single Machine Scheduling
  • Batching
  • Resource Allocation
  • Dynamic Programming
  • Fully Polynomial Approximation Scheme
  • Computer Science


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.

There are no comments yet on this publication. Be the first to share your thoughts.