On the Minimization of Completion Time Variance with a Bicriteria Extension

1992/12/01 by Prabuddha De, Jay B. Ghosh, Charles E. Wells · 1 citation
Engineering · Computer Science · #Scheduling and Optimization Algorithms #Optimization and Search Problems #Advanced Control Systems Optimization

paper · doi:10.1287/opre.40.6.1148

Abstract

We discuss a single-machine scheduling problem where the objective is to minimize the variance of job completion times. To date, the problem has not been solved in polynomial time. This paper presents a dynamic programming algorithm that is pseudopolynomial in complexity. We also propose a fully polynomial approximation scheme and derive a lower bound that is useful in its implementation. Furthermore, we show that the dynamic programming solution is easy to extend to a bicriteria version of the problem in which it is desired to simultaneously minimize the mean completion time.

Cited by

• A Wolfe Line Search Algorithm for Vector Optimization

Related

• An FPTAS of Minimizing Total Weighted Completion Time on Single Machine with Position Constraint
• Scheduling with regular performance measures and optional job rejection on a single machine
• Approximate Total Weighted Completion Time with Convex Controllable Processing Times
• Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines
• Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations