Minimizing makespan in re-entrant permutation flow-shops

Abstract

A re-entrant flow-shop (RFS) describes situations in which every job must be processed on machines in the order of M₁, M₂, …, M_m, M₁, M₂, …,M_m, …, and M₁, M₂, …,M_m. In this case, every job can be decomposed into L levels and each level starts on M₁, and finishes on M_m. 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.

Keywords:

• scheduling
• re-entrant permutation flow-shops
• integer programming