Please use this identifier to cite or link to this item:
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
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.
ISSN: 0925-5001
EISSN: 1573-2916
DOI: 10.1007/s10898-004-5703-y
Appears in Collections:Conference Paper

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


Last Week
Last month
Citations as of Nov 6, 2018


Last Week
Last month
Citations as of Nov 14, 2018

Page view(s)

Last Week
Last month
Citations as of Nov 12, 2018

Google ScholarTM



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