A heuristic algorithm for minimizing mean flow time with unit setups
Generate an AI Snapshot to get a quick, structured summary of this paper.
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A heuristic algorithm with an absolute error bounded by the product of the number of short jobs (with processing times less than m−1 ) and m−2 is given.
Abstract
In this note 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 processing times less than m−1) and m−2.