We present an O(mn) two-group (TG) heuristic for the m-machine, n-job permutation flow-shop scheduling problem. We show that heuristic TG has a worst-case performance ratio of (m + 1)/2. We also establish worst-case bounds for several heursitcs proposed in the past.
