Heuristics for a Two-Stage Assembly-Type Flow Shop with Limited Waiting Time Constraints

Abstract

This study investigates a two-stage assembly-type flow shop with limited waiting time constraints for minimizing the makespan. The first stage consists of m machines fabricating m types of components, whereas the second stage has a single machine to assemble the components into the final product. In the flow shop, the assembly operations in the second stage should start within the limited waiting times after those components complete in the first stage. For this problem, a mixed-integer programming formulation is provided, and this formulation is used to find an optimal solution using a commercial optimization solver CPLEX. As this problem is proved to be NP-hard, various heuristic algorithms (priority rule-based list scheduling, constructive heuristic, and metaheuristic) are proposed to solve a large-scale problem within a short computation time. To evaluate the proposed algorithms, a series of computational experiments, including the calibration of the metaheuristics, were performed on randomly generated problem instances, and the results showed outperformance of the proposed iterated greedy algorithm and simulated annealing algorithm in small- and large-sized problems, respectively.

Keywords

• scheduling
• two-stage assembly-type flow shop
• limited waiting times
• makespan
• heuristic