A fast and effective subset sum based improvement procedure for workload balancing on identical parallel machines

•We minimize the normalized sum of squared workload deviations to balance workload.•We develop an exact algorithm for the case of three machines.•We propose an effective subset sum based local search procedure for multiple machines.•The innovation is to use triples of machines as a neighborhood instead of pairs.•We optimally solve 98% of the benchmark instances within very short computation time.

The paper on hand addresses the workload balancing problem that asks for an assignment of n independent jobs to m identical parallel machines so that the normalized sum of squared workload deviations (NSSWD-criterion) is minimized. For the special case of m  =3 machines we propose an exact algorithm that requires solving a sequence of subset sum problems. This algorithm also builds the core of our local search procedure for solving the general case of m≥3m≥3 machines. The main innovation of our approach compared to existing methods, therefore, consists in using triples of machines as a neighborhood instead of pairs of machines. Results of a comprehensive computational study on the benchmark library established by Ho et al. [10] and Cossari et al. [5] attest to the effectiveness of our approach. In addition, we demonstrate its capability to determine high-quality solutions for further balancing criteria as discussed in Cossari et al. [6].