Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/11228
Title: Minimizing completion time variance with compressible processing times
Authors: Ng, CT 
Cai, X
Cheng, TCE 
Lam, SS
Keywords: Completion time variance
Compressible processing times
Scheduling
Issue Date: 2005
Publisher: Springer
Source: Journal of global optimization, 2005, v. 31, no. 2, p. 333-352 How to cite?
Journal: Journal of global optimization 
Abstract: We introduce a new formulation of the standard completion time variance (CTV) problem with n jobs and one machine in which the job sequence and the processing times of the jobs are all decision variables. The processing time of job i (i=1, ⋯, n) can be compressed by an amount within [li ui] which however will incur a compression cost. The compression cost is a general convex non-decreasing function of the amount of the job processing time compressed. The objective is to minimize a weighted combination of the completion time variance and the total compression cost. We show that under an agreeable condition on the bounds of the processing time compressions a pseudo-polynomial algorithm can be derived to find an optimal solution for the problem. Based on the pseudo-polynomial time algorithm two heuristic algorithms H1 and H2 are proposed for the general problem. The relative errors of both heuristic algorithms are guaranteed to be no more than δ where δ is a measure of deviation from the agreeable condition. While H1 can find an optimal solution for the agreeable problem H2 is dominant for solving the general problem. We also derive a tight lower bound for the optimal solution of the general problem. The performance of H2 is evaluated by complete enumeration for small n and by comparison with this tight lower bound for large n. Computational results (with n up to 80) are reported which show that the heuristic algorithm H2 in general can efficiently yield near optimal solutions when n is large.
URI: http://hdl.handle.net/10397/11228
ISSN: 0925-5001
EISSN: 1573-2916
DOI: 10.1007/s10898-004-5703-y
Appears in Collections:Conference Paper

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

SCOPUSTM   
Citations

13
Last Week
0
Last month
0
Citations as of Sep 10, 2017

WEB OF SCIENCETM
Citations

9
Last Week
0
Last month
0
Citations as of Sep 13, 2017

Page view(s)

68
Last Week
1
Last month
Checked on Sep 17, 2017

Google ScholarTM

Check

Altmetric



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