Minimizing workload balancing criteria on identical parallel machines

This paper considers the problem of scheduling nonpreemptive jobs on identical parallel processors to minimize workload balancing criteria. While workload balancing is an important practical criterion given the need of production systems to efficiently use all of their resources, there is no established measure of performance in the scheduling literature that characterizes total workload balance. In this paper, the normalized standard deviation, the normalized mean deviation, and the normalized mean difference are proposed as criteria that measure the balance of the workloads among the machines associated to a schedule. A local search algorithm, which performs multiple exchanges of jobs among machines, is presented. The results of a wide computational experimentation demonstrate that the proposed algorithm performs well for all the proposed measures.