# 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. scheduling; two-stage assembly-type flow shop; limited waiting times; makespan; heuristic 40/1.11.11240.11.11.11240. the second stage can start after all necessary components have completed in the first stage. The completion time of each product is defined as the time when the assembly operation completes in the second stage. To enhance the flow shop productivity, this study aims to minimize the makespan, which is equal to the completion time of the last scheduled job. This study constrains the waiting times between stages 1 and 2. This implies that components completed in the first stage must be entered into the second stage for the assembly operation within the limited waiting times. Therefore, it is necessary to complete the operations of the first stage considering the time when the assembly operation can start in the second stage. Figure 1a,b illustrates example schedules with two jobs in the assembly flow shop with and without limited waiting times, respectively. The starts in the first stage in Figure 1a are delayed observing the limited waiting times \(w_{21}\) and \(w_{22}\), whereas the second job in Figure 1b can start without any delay. In general, waiting times are limited to prevent quality deterioration owing to increased waiting times. There are various cases considering the waiting time constraints in manufacturing industries, such as semiconductors, batteries, food, steelmaking, and biotechnology [12; 13; 14]. Since [PERSON] et al. [3] introduced a two-stage assembly-type flow shop problem, there have been many studies on the scheduling problems, and two review papers ([PERSON] et al. [2] and [PERSON] et al. [15]) were recently published. Many studies have sought to minimize the makespan. The makespan minimization problem was demonstrated to be strongly NP-hard in [3], even though only two machines existed in the first stage. [PERSON] et al. [3] also developed three heuristics based on [PERSON]'s algorithm [16] and suggested a branch-and-bound (B&B) algorithm. [PERSON] et al. [4] showed that an optimal solution for the problem with more than two machines in the first stage is always in permutation schedules where the sequences on all machines in the flow shop are the same. Additionally, [PERSON] and [PERSON] [17] and [PERSON] and [PERSON] [18] provided B&B algorithms, while [PERSON] et al. [19] proposed heuristic algorithms. On the other hand, [PERSON] and [PERSON] [20] considered the extended problem in which there are three stages and they developed heuristic algorithms. Additionally, [PERSON] and [PERSON] [21] proposed a B&B algorithm for the problem of outsourcing one type of component subject to the job-dependent lead time in the first stage. [PERSON] et al.