Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/21402
Title: Scheduling to minimize the total compression and late costs
Authors: Cheng, TCE 
Chen, ZL
Li, CL
Lin, BMT
Keywords: Approximation schemes
Computational complexity
Dynamic programming
Scheduling
Sequencing
Issue Date: 1998
Publisher: John Wiley & Sons
Source: Naval research logistics, 1998, v. 45, no. 1, p. 67-82 How to cite?
Journal: Naval research logistics 
Abstract: We consider a single-machine scheduling model in which the job processing times are controllable variables with linear costs. The objective is to minimize the sum of the cost incurred in compressing job processing times and the cost associated with the number of late jobs. The problem is shown to be NP-hard even when the due dates of all jobs are identical. We present a dynamic programming solution algorithm and a fully polynomial approximation scheme for the problem. Several efficient heuristics are proposed for solving the problem. Computational experiments demonstrate that the heuristics are capable of producing near-optimal solutions quickly.
URI: http://hdl.handle.net/10397/21402
ISSN: 0894-069X
EISSN: 1520-6750
DOI: 10.1002/(SICI)1520-6750(199802)45:1<67
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

16
Last Week
0
Last month
Citations as of Feb 9, 2018

Page view(s)

63
Last Week
3
Last month
Citations as of Feb 18, 2018

Google ScholarTM

Check

Altmetric


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