# Workload Balancing on Identical Parallel Machines: Theoretical and Computational Analysis
## 1 Introduction
However, [13] provided a counter-example for the case with more than two machines to prove that this result was wrong. They also carried out a computational study to give an overview on \(C_{max}\) as well as \(NSSWD\) optimal schedules and empirically analyzed the correlation between both criteria. The numerical results revealed that the \(C_{max}\) criterion may be a good approximation for \(NSSWD\) when the ratio \(\frac{n}{m}\) is rather small. However, for some other instances, especially the largest ones, the \(C_{max}\) -optimal solution is not a good candidate solution for workload balancing. [PERSON] et al. [15] also recommended the minimization of the difference between the most and least loaded machine (\(C_{\Delta}=C_{max}-C_{min}\)) as a measure for workload balancing on identical parallel machines. They performed a computational study to show that, in general, a makespan optimal schedule is not optimal for \(C_{\Delta}\) criterion. One of the recent works dealing with this problem is that of [PERSON] and [PERSON] [17]. The authors investigated the workload balancing problem on a parallel machines environment where the objective was to minimize the normalized sum of square for workload deviations. They proposed an exact subset sum-based algorithm to solve a three-machine case. In a follow-up paper, [PERSON] and [PERSON] [18] provided a dynamic programming approach to solve the same problem. They also suggested two local search procedures to solve large instances and provided a complete and dedicated benchmark to the workload balancing problem. This paper consists of a theoretical and computational analysis of the different criteria addressed in the literature to deal the workload balancing problem. More specifically, it aims to investigate the theoretical relationships between \(P||C_{max}\), \(P||NSSWD\) and \(P||C_{\Delta}\) problems. As mentioned by [PERSON] et al. [10], 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. Different criteria have been addressed in the literature and some of them are trivial. That is why we present in this work a rigorous theoretical analysis of the most important criteria that have been considered for this problem. The main theoretical contribution of this paper is to establish the exact mathematical relationship between NSSWD and (\(C_{\Delta}\)) as a measure for the workload balancing on identical parallel machines. Then, based on this theoretical analysis, new mathematical bounds are developed and incorporated into mathematical programming models to provide a number of optimal solutions to some unsolved instances in the benchmark proposed by [PERSON] and [PERSON] [18]. The remainder of this paper is organized as follows. The next section introduces the problem considered in this study with the different notations. Section 3 presents the workload balancing problem using two cases: the case of identical jobs and the general case with jobs having different processing times. Section 4 introduces three mathematical formulations to the problem. Numerical tests are presented in Section 5. Finally, Section 6 summarizes the contribution of this paper.