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