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

The paper on hand addresses the workload balancing problem that asks for an assignment of n independent jobs to in 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 >= 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]. (C) 2016 Elsevier Ltd. All rights reserved.