A heuristic algorithm for minimizing mean flow time with unit setups

In this note we consider the problem of scheduling a set of jobs on, m iden tical parallel machines. For each job, a setup has to be done by a single s erver. 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 bound ed by the product of the number of short jobs (with processing times less t han m - 1) and m - 2. (C) 2001 Elsevier Science B.V. All rights reserved.