Three-stage ordered flow shops with either synchronous flow, blocking or no-idle machines

摘要

We show by induction that the shortest processing time sequence is optimal for a number of three-stage ordered flow shops with either synchronous flow, blocking or no-idle machines, effectively proving the optimality of an index priority rule when the adjacent job pairwise interchange argument does not hold. We also show that when the middle machine is maximal, the synchronous flow, blocking and no-wait problems are equivalent, because they can be effectively decomposed into two equivalent two-stage problems. A similar equivalence is shown for the classical flow shop and the flow shop with no-idle machines. These equivalences facilitate the solution of one problem by using the optimal algorithm for the equivalent problem. Finally, we observe that when the middle machine is minimal, the optimal sequence is not a pyramid sequence for the synchronous flow and blocking flow shops. On the other hand, we show that the optimal sequence for the flow shop with no-idle machines is a pyramid sequence obtainable by dynamic programming in pseudo-polynomial time.