Sequencing jobs with random processing times to minimize weighted completion time variance

The authors examine the problem of sequencing a set of jobs on a single machine, where each job has a random processing time and is associated with a known, job-dependent weight. The objective is to minimize the expectation of the weighted variance of job completion times. They establish the NP-completeness of this problem, and further show that the problem under some compatible conditions is NP-complete in the ordinary sense. The authors introduce the concept of a W-shaped solution for the problem and find that an optimal W-shaped sequence exists under the compatible conditions. They propose an exact algorithm, based on this W-shaped property, which can generate an optimal solution in pseudopolynomial time.