A New Model For Completion Time Variance Problem With Job-Dependent Weights And Controllable Processing Times

We consider a new model for scheduling n jobs on a single machine. Each job requires a processing time pi, which may be compressed at an additional cost, and is associated with a weight Wi. The objective is to minimize the weighted variance of completion times and the total cost incurred from the compression of processing times. This is the WCTV problem with controllable processing times. The WCTV problem with equal weight and with noncontrollable processing times has been shown to be NP-hard. In this paper, we describe optimality properties, and we propose a heuristic algorithm to solve the problem. Computational results are reported that demonstrate the effectiveness of the algorithm.