- 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