Minimizing makespan in re-entrant permutation flow-shops

An re-entrant flow-shop (RFS) describes situations in which every job must be processed on machines in the order of M1,M2, …,Mm, M1, M2, …,Mm, …, and M1, M2, …,Mm. In this case, every job can be decomposed into L levels and each level starts on M1, and finishes on Mm. In a RFS case, if the job ordering is the same on any machine at each level, then it is said that no passing is allowed since any job is not allowed to pass any previous job. The RFS scheduling problem where no passing is allowed is called the re-entrant permutation flow-shop (RPFS) problem. This paper proposes three extended mixed BIP formulations and six extended effective heuristics for solving RPFS scheduling problems to minimize makespan.