Job Completion Time Variance Minimization on Identical Parallel Machines

Abstract

The paper addresses the problem of scheduling n jobs on m identical parallel machines so as to minimize the job completion time variance (CTV), which is closely related to service stability. We focus on the unrestricted case such that an idle time is permitted to insert before the job processing. We prove that the mean completion time on each machine should be the same under an optimal schedule. We also prove a series of favorable properties, based on which we propose a heuristic algorithm that reduces CTV more efficiently than the existing scheduling algorithms do. [PUBLICATION ABSTRACT]