Hybrid tabu search for re-entrant permutation flow-shop scheduling problem

A re-entrant flow-shop (RFS) refers to situations in which every job must be processed on machines in the order, M-1,M-2,...,M-m, M-1,M-2,...,M-m,..., and M-1,M-2,...,M-m. Every job can be decomposed into several layers each of which starts on M-1 and finishes on M-m. In the RFS case, if the job ordering is the same on any machine at each layer, then no passing is said to be allowed, since no job is allowed to pass any former job. The RFS scheduling problem in which no passing is allowed, is called a re-entrant permutation flow-shop (RPFS) problem. This study considers RPFS scheduling, and applies hybrid tabu search (HTS) to minimize the makespan of jobs. The hybridization method is used to improve pure tabu search (TS) performance. The HTS is compared to the optimal solutions generated using the integer programming technique, and to the near optimal solutions generated by pure TS and heuristic NEH. The experimental results show that HTS has better performance than the others tested. (c) 2007 Elsevier Ltd. All rights reserved.