2001-50: Online scheduling with release times and set-ups

DIMACS TR: 2001-50

Online scheduling with release times and set-ups

Authors: Srikrishnan Divakaran and Michael Saks

ABSTRACT
In this paper, we address the problem of online scheduling of $n$ independent jobs with release times and sequence independent set-ups on a single machine system with the objective of minimizing the maximum flow time. For this problem, we present an $O(1)$-competitive online algorithm. We also present the proof of $NP$-completeness of the offline problem.

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

DIMACS Home Page