Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/13324
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
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.
URI: http://hdl.handle.net/10397/13324
ISSN: 0167-6377
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

31
Last Week
1
Last month
0
Citations as of Apr 30, 2016

Page view(s)

44
Last Week
0
Last month
Checked on Jun 25, 2017

Google ScholarTM

Check



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