DIMACS TR: 2001-50
Online scheduling with release times and set-ups
Authors: Srikrishnan Divakaran and Michael Saks
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:
DIMACS Home Page