A note on makespan minimization in two-stage flexible flow shops with uniform machines

We consider the two-stage flexible flow shop makespan minimization problem with uniform parallel machines. Soewandi and Elmaghraby developed a heuristic (S–E) and derived a machine speed-dependent worst-case ratio bound for it. We point out that this bound works well when the uniform machines have approximately equal speeds but is not indicative of the performance of the S–E heuristic when the machine speeds are in a wide range. Motivated by this observation, we propose an alternative tight machine-speed dependent worst-case bound for the S–E heuristic that works well when the machine speeds vary significantly. We then combine the two speed-dependent ratio bounds into a speed-independent bound. Our findings facilitate the narrowing of the gap between experimental performance and worst-case bound for the S–E heuristic.