Theoretical Analysis of Workload Imbalance Minimization Problem on Identical Parallel Machines

This paper considers the problem of assigning N non-preemptive jobs to M identical parallel machines or processors as equally as possible. This problem is known as workload imbalance minimization problem. First, we establish that this problem can be formulated as the difference between the maximum and minimum workloads. In other words, it is defined as the minimization of the difference between the workload of the bottleneck machine and the workload of the fastest machine. Then, we present comparative analysis between this criterion and other criteria proposed in the literature such as: The average absolute deviation from the mean value of the total workload and Normalized Sum of Square for Workload Deviations (NSSWD) criteria proposed in the literature.