Please use this identifier to cite or link to this item:
Title: Single machine batch scheduling with deadlines and resource dependent processing times
Authors: Cheng, TCE 
Kovalyov, MY
Keywords: Batching
Dynamic programming
Fully polynomial approximation scheme
Resource allocation
Single machine scheduling
Issue Date: 1995
Publisher: North-Holland
Source: Operations research letters, 1995, v. 17, no. 5, p. 243-249 How to cite?
Journal: Operations research letters 
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.
ISSN: 0167-6377
EISSN: 1872-7468
Appears in Collections:Journal/Magazine Article

View full-text via PolyU eLinks SFX Query
Show full item record


Last Week
Last month
Citations as of Jan 16, 2019

Page view(s)

Last Week
Last month
Citations as of Jan 14, 2019

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.