Improved algorithms to minimize workload balancing criteria on identical parallel machines

Building upon our prior work, in this follow-up paper we suggest an enhanced version of WB3 that leads to a significant speed-up of several orders of magnitude and we considerably improve on the performance of LS on difficult instances where the ratio of the number of jobs to the number of machines is small. Moreover, we investigate a simple surrogate balancing measure that can also be optimized by our algorithms with only a slight modification. Results of a comprehensive computational study on a large set of benchmark as well as random test instances demonstrate the effectiveness of the improved algorithms.