Analysis of Heuristics of 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 interruption on the first machine and then on the second machine. The maximum completion time is minimized. 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.