A two-stage hybrid flowshop scheduling problem with a function constraint and unrelated alternative machines

This article addresses a two-stage hybrid flowshop scheduling problem with unrelated alternative machines. The problem to be studied has m unrelated alternative machines at the first machine center followed by a second machine center with a common processing machine in the system. The objective is to minimize the makespan of the system. For the processing of any job, it is assumed that the operation can be partially substituted by other machines in the first center, depending on its machining constraints. Such scheduling problems occur in certain practical applications such as semiconductors, electronics manufacturing, airplane engine production, and petrochemical production. We demonstrate that the addressed problem is NP-hard and then provide some heuristic algorithms to solve the problem efficiently. The experimental results show that the combination of the modified Johnson's rule and the First-Fit rule provides the best solutions within all proposed heuristics. Scope and purpose A survey of the scheduling literature reveals that although a lot of research focusing on FSm1,(m2) has been done, no study has taken the functional constraint and unrelated alternative machines cases into account simultaneously. However, such scheduling problems occur in certain practical manufacturing environments such as semiconductors, electronics manufacturing, airplane engine production, and petrochemical production. Hence, the purpose of this report is to propose some efficient heuristics for solving the FSm1,(m2) problem. For the addressed problem, first, we demonstrate that the problem belongs to an NP case; then, 16 heuristics are provided for dealing with the problem. The computational results demonstrate the effectiveness of the heuristics. (c) 2006 Elsevier Ltd. All rights reserved.