A look-ahead heuristic for scheduling jobs with release dates on a single machine

The paper explores how limited look-ahead improves the performance of on-line heuristics. In particular, the authors consider the NP-complete single machine scheduling of independent jobs with release dates to minimize the total completion time. They present an on-line with look-ahead algorithm which foresees the next in-coming job. The authors study its worst-case behavior and prove that it outperforms most on-line and off-line heuristics.