A note on minimizing the sum of squares of machine completion times on two identical parallel machines
Abstract
In this short note, we address the coherence between minimizing the sum of squares of machine completion times and minimizing makespan on two identical parallel machines. We show equivalence of the two objectives and identify interesting and useful relations which allow us to transfer worst-case ratios of approximation algorithms from one problem to the other.
