A new heuristic for workload balancing on identical parallel machines and a statistical perspective on the workload balancing criteria

We consider the multiprocessor scheduling problem in which independent jobs are scheduled on identical parallel machines, with the objective of minimizing the normalized sum of square for workload deviations (NSSWD) criterion in order to obtain workload balancing. NSSWD and other criteria for the related problem of number partitioning are presented from a statistical viewpoint, which allows to derive some insightful connections with statistical measures of dispersion. A new local search algorithm is also developed. The algorithm at first generates and merges a set of partial solutions in order to obtain a feasible solution for the multiprocessor scheduling problem. Then a set of interchange procedures are utilized in order to improve the solution. The effectiveness of this approach is evaluated by solving a large number of benchmark instances.