Sequence-dependent group scheduling problems in flexible flow shops

Group scheduling within the context of sequence dependent setup times in flexible flow shops is considered in this paper. Flexible flow shops are becoming very popular in industry practice, primarily because of large workloads required by jobs within groups on some machine types. The objective is to minimize the makespan required to process jobs in all groups released on the shop floor. There is clearly a need for efficiently solving large problems that have industrial merit. To address this need, three different algorithms based on tabu search are developed. Problem sizes ranging in size from small, medium to large are considered along with three levels of flexibility. The higher the number of stages and the number of parallel machines in each stage, the higher is the flexibility introduced into the problem. Three different initial solution (IS) finding mechanisms with varying levels of computational difficulty are proposed to aid the search algorithms in identifying an IS. Thus, problem size is regarded as the main factor, while flexibility, IS finding mechanism, and algorithms are considered subplot factors. The makespan which speaks for efficacy and computation time which speaks for efficiency of the algorithms are considered separately as response variables in the proposed 3(4) factorial split-plot design used in the detailed statistical experiment. Based on the results, the search algorithm that uses short term memory is recommended for problems of all sizes and levels of flexibility. Also, as IS finding mechanisms are found statistically insignificant with respect to both makespan and computation time, the mechanism which requires the least amount of computation time is recommended. (c) 2005 Elsevier B.V. All rights reserved.