Analysis of Heuristics for Two-Machine Flow-Shop Sequencing Subject to Release Dates

The two-machine flow-shop problem is considered in which each job becomes available for processing at its release date after which it must be processed without preemption on the first machine and then on the second machine. The objective is to minimize the maximum completion time. Three heuristics are presented which each have a worst-case performance ratio of 2. One of these is modified to give an improved worst-case performance ratio of 5/3.