# Workload Balancing on Identical Parallel Machines: Theoretical and Computational Analysis
## 1 Introduction  
Balancing workload among a set of resources or operators is an important issue in many services and production environments. For instance, in the manufacturing industry, balancing the workload among machines can reduce idle time. It also helps to manage bottlenecks in many production systems. This problem can be formally defined as the assignment of a set of jobs to identical parallel machines (or other types of resources) with the objective of balancing the total workload among those machines as equally as possible. Recently, this scheduling problem has found application in the Fog Computing empowered Internet of Things (IoT) [1]. This study proposes that a workload balancing scheme may reduce the latency of data flow, which is a key performance metric for IoT applications. In addition, workload balancing criteria have gained a lot of attention in key concepts of scheduling in Industry 4.0, such as of Flexible Manufacturing System [2] and Smart Manufacturing System [3]. Balancing the workload among a set of machines or human workers is also an important issue in many practical cases. For instance, assigning human resources is an important concern for many industries and organizations like hospitals, manufacturing firms, transportation companies, etc. [PERSON] et al. [4] addressed a human resources assignment problem with the objectives of maximizing employee satisfaction and production rate on a real world case of a large production firm. [PERSON] et al. [5] presented different MIP models to solve workforce scheduling problems for a single-shift, taking into consideration constraints relative to labor regulations. [PERSON] and [PERSON] [6] addressed on a balancing problem encountered by a mail order firm. To handle order taking and billing, and to ease order tracking, customer groups should be assigned almost equally to the employees. Many researchers, especially in the scheduling community, are interested in the workload balancing problem. They have addressed this problem in different ways: as a series of constraints or as an objective function. For example, [PERSON] and [PERSON] [7] proposed an approached optimization method based on heuristics and a genetic algorithm in order to deal with semirelated parallel machines under sequence-dependent setups and load balancing constraints. [PERSON] et al. [8] introduced a mixed integer-programming model and a genetic algorithm to minimize total tardiness and workload imbalance in a parallel machine-scheduling environment. In 2012, [PERSON] et al. [9] attempted to minimize the relative workload imbalance on parallel machines via two metaheuristic methods. [PERSON] et al. [10] noted that there is no established performance measure in the literature to characterize the workload balancing problem. However, different criteria have been proposed in the literature. The first is the relative percentage of imbalances (RPI) introduced by [PERSON] et al. [11; 12]. However, [PERSON] and [PERSON] [13] showed that this criterion is equivalent to maximum completion time minimization and does not provide perfectly balanced schedule. [PERSON] et al. [14] introduced a new workload balancing criterion, the so-called Normalized Sum of Squared Workload Deviations (NSSWD). They also analyzed some properties of the problem and introduced a heuristic algorithm to solve it. Later, [PERSON] et al. [15] showed that the \(NSSWD\) criterion is equivalent to \(\sum_{m=1}^{M}C_{m}^{2}\). In other words, \(NSSWD\) represents a normalized variant of the problem of minimizing \(\sum_{m=1}^{M}C_{m}^{2}\). This problem was first treated by [PERSON] and [PERSON] [16] in 1975, who analyzed the worst-case performance of Longest Processing Times rule, and derived its worst-case performance ratio, i.e., \(\frac{25}{24}\). [PERSON] et al. [14] also stated that, in the case of identical parallel machines, a \(NSSWD\)-optimal schedule is necessarily a \(C_{max}\)-optimal schedule as well.