Minimizing completion time variance with compressible processing times

Chi To Ng, X. Cai, Edwin Tai Chiu Cheng, S. S. Lam

Research output: Journal article publicationJournal articleAcademic researchpeer-review

15 Citations (Scopus)


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 [liui] 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.
Original languageEnglish
Pages (from-to)333-352
Number of pages20
JournalJournal of Global Optimization
Issue number2
Publication statusPublished - 1 Feb 2005


  • Completion time variance
  • Compressible processing times
  • Scheduling

ASJC Scopus subject areas

  • Applied Mathematics
  • Control and Optimization
  • Management Science and Operations Research
  • Global and Planetary Change


Dive into the research topics of 'Minimizing completion time variance with compressible processing times'. Together they form a unique fingerprint.

Cite this