A heuristic algorithm for minimizing mean flow time with unit setups

What is it about?

We consider the problem of scheduling a set of jobs on m identical parallel machines. For each job, a setup has to be done by a single server. The objective is to minimize the sum of the completion times in the case of unit setup times and arbitrary processing times. For this strongly NP-hard problem, we give a heuristic algorithm with an absolute error bounded by the product of the number of short jobs (with a processing times less than m−1) and m−2.

Featured Image