## DIMACS TR: 2001-49

## Approximation algorithms for Offline scheduling with set-ups

### Authors: Srikrishnan Divakaran and Michael Saks

**
ABSTRACT
**

In this paper, we present new approximation results for the offline
problem of scheduling $n$ independent jobs with sequence independent
set-ups and common release times on a single machine system for the
following optimality criteria :
- total weighted completion time

- maximum lateness

For the total weighted completion time criterion, we present a
$2$-approximation algorithm, the first known polynomial time constant
approximation algorithm for this problem. For this criterion, when the
number of job types is arbitrary, the computational complexity is open and
prior to our results there were no known polynomial time constant
approximation algorithms even when all jobs have unit weight and all job
types have unit set-up times.

For the maximum lateness criterion, we present an algorithm that obtains
an optimal solution in a relaxed framework where our algorithm is given
strictly more resources (i.e. a machine with higher processing speed) than
the optimal offline algorithm to which it is compared. For this criterion,
when the number of job types is arbitrary, this problem is known to be
$NP$-hard even when there are two jobs in each type or when all job types
have unit set-up times, there are at most three jobs in each type and
there are at most three distinct due dates. Also, for this criterion, when
the number of job types and the due dates are arbitrary, there are no
constant approximation algorithms unless $P=NP$.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-49.ps.gz

DIMACS Home Page