Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/15758
Title: Single-machine scheduling with trade-off between number of tardy jobs and resource allocation
Authors: Cheng, TCE 
Chen, ZL
Li, CL 
Keywords: Resource allocation
Scheduling
Sequencing
Time-cost trade-offs
Issue Date: 1996
Publisher: North-Holland
Source: Operations research letters, 1996, v. 19, no. 5, p. 237-242 How to cite?
Journal: Operations research letters 
Abstract: We consider a single-machine scheduling problem in which job processing times are controllable through the allocation of a limited resource. The amount of resource consumption of a job is assumed to be linearly related to the job processing time. The performance criteria are the total resource consumption and the number of tardy jobs. Our objective is to construct the trade-off curve between the total amount of resource consumed and the number of tardy jobs. An NP-hardness proof is presented for the problem of minimizing the total amount of allocated resource subject to a limited number of tardy jobs. A pseudo-polynomial-time dynamic programming algorithm is proposed for constructing the trade-off curve. This dynamic program can be generalized to the case where the job processing time is a decreasing function of the amount of allocated resource.
URI: http://hdl.handle.net/10397/15758
ISSN: 0167-6377
EISSN: 1872-7468
DOI: 10.1016/S0167-6377(96)00035-1
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

23
Last Week
0
Last month
0
Citations as of Nov 3, 2017

WEB OF SCIENCETM
Citations

20
Last Week
0
Last month
0
Citations as of Nov 10, 2017

Page view(s)

73
Last Week
1
Last month
Checked on Nov 12, 2017

Google ScholarTM

Check

Altmetric



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