Heuristics for flexible flowshop scheduling problems

Abstract

A flexible flowshop consists of a number of work centers, each having one or more parallel machines. A set of immediately available jobs has to be processed through the ordered work centers. A job is processed on any and only one of the parallel machines at each of the work centers?) Structurally, a flexible flowshop represents a generalization of the simple flowshop and the identical parallel machine shop. For the case of having the same number of identical parallel machines at every work center, two approaches are developed: the para-flow approach and the flow-para approach. Two situations regarding the job route are examined. These are the partially flexible job route situation and the completely flexible job route situation. (The objective of this research is to find heuristics that minimize the makespan of the problem in reasonable computation time. A computer experiment verifies that the para-flow approach and the flow-para approach outperform published algorithms. Problem size includes three elements: the number of jobs, the number of work centers, and the number of parallel machines at each work center. By fixing any two of the three elements, the trend caused by the third element can be analyzed. A trend analysis of the proposed algorithms has been conducted.