Sequencing and Tabu Search Heuristics for Hybrid Flow Shops with Unrelated Parallel Machines and Setup Times

Abstract. The goal of this paper is to investigate scheduling heuristics to seek the minimum of a positively weighted convex sum of makespan and the number of tardy jobs in a static hybrid flow shop environment where at least one production stage is made up of unrelated parallel machines. In addition, sequence- and machine- dependent setup times are considered. The problem is a combinatorial optimization problem which is too difficult to be solved optimally for large problem sizes, and hence heuristics are used to obtain good solutions in a reasonable time. Some dispatching rules and flow shop makespan heuristics are developed. Then this solution may be improved by fast polynomial heuristic improvement algorithms based on shift moves and pairwise interchanges. In addition, metaheuristic proposed is a tabu search algorithm. Three basic parameters (i.e., number of neighbors, neighborhood structure, and size of tabu list in each iteration) of a tabu search algorithm are briefly discussed in this paper. The performance of the heuristics is compared relative to each other on a set of test problems with up to 50 jobs and 20 stages