Two-Machine Flow Shop Scheduling with Re-entrance

Re-entrant two machine flow shop scheduling problem with the objective of minimizing makespan is considered. There are n jobs to be processed on two machines and each job has the processing route (M₁, M₂, M₁, M₂, ..., M₁, M₂). In contrast to the classical scheduling assumption that each job visits each machine at most once, in this re-entrant shop, jobs can visit certain machines more than once. The re-entrant characteristic makes the problem much more complicated and intractable. In this paper, the re-entrant problem can be transformed into a two-machine flow shop scheduling problem subject to parallel chain precedence constraints, which is equivalent to the single machine scheduling subject to precedence delays under some conditions. Based on the relationships explored for the three scheduling problems, polynomial algorithms are developed for some special cases of the re-entrant problem.