# Heuristics for a Two-Stage Assembly-Type Flow Shop with Limited Waiting Time Constraints
###### Abstract
[22] addressed two scenario-dependent jobs processing times and proposed a B&B algorithm and metaheuristics to minimize the robust makespan, and [PERSON] et al. [23] considered a processing time-based learning effect and proposed a B&B algorithm and several metaheuristics. On the contrary, for other objectives, [PERSON] and [PERSON] [24] proposed a B&B algorithm to minimize total tadariness, whereas [PERSON] [25; 26] developed B&B algorithms to minimize total completion times and total weighted tadiness, respectively. Additionally, there have been various studies on the assembly-type flow shop problems [27; 28; 29; 30; 31; 32]. Although typical assembly-type flow shop scheduling problems have been studied by many researchers, only a few studies have considered waiting time constraints or time lags. According to recent review papers, it is necessary to study scheduling problems with waiting time constraints, but there are only a few studies that considered no-wait constraints. [PERSON] et al. [33] introduced a no-wait two-stage assembly flow shop and proposed three metaheuristic algorithms: a genetic algorithm, differential evolution algorithm, and population-based variable neighborhood algorithm. In addition, [PERSON] et al. [34] proposed a two-stage assembly-type flow shop problem, where the two-stage assembly-type flow shop problem is solved by a genetic algorithm, and the two-stage assembly-type flow shop problem is solved by a genetic algorithm. Figure 1: Example schedules with two jobs: (**a**) with waiting time constraints; (**b**) without waiting time constraints. provided a hybrid particle swarm optimization algorithm, and [PERSON] et al. [35] proposed an iterated local search method. [PERSON] et al. [36] suggested an iterated local search method and a variable neighborhood search. Most of the studies related to the no-wait assembly flow shop considered metaheuristic algorithms [37; 38; 39; 40] as solution methodologies because these problems are NP-hard. The considered scheduling problem is defined as \(AF(m,1)\mid max\text{-}wait\mid C_{max}\) in three-field notation suggested by [PERSON] et al. [41]. \(AF(m,1)\) represents an assembly-type flow shop where there are \(m\) machines to fabricate components in stage 1 and a single assembly machine in stage 2. _Max-wait_ denotes the limited waiting constraints between the two stages. \(C_{max}\) represents the makespan, which is the objective function of the scheduling problem. Assuming that there is only one machine in the first stage, this scheduling problem becomes a two-machine flow shop problem with limited waiting time constraints (\(F2\mid max\text{-}wait\mid C_{max}\)), which has been proven to be NP-hard in [42]. Therefore, this problem is also NP-hard. To the best of the authors' knowledge, no assembly flow shop study has considered the limited waiting time constraints that are generalized from no-wait. Thus, as its main contribution, this study is the first attempt to consider the assembly flow shop with limited waiting times to fill part of the existing research gap. Additionally, this paper proposes various solution methodologies, including the mathematical formulation, priority rule-based list scheduling, constructive heuristic, and three metaheuristic algorithms. Furthermore, we suggest a method that converts a sequence obtained by the heuristics into a complete schedule with waiting time constraints. This study aims to minimize the makespan in a two-stage assembly flow shop with limited waiting time constraints. We provide a mixed-integer programming (MIP) to define the considered problem clearly and use a commercial optimization solver, CPLEX 12.10, to solve the MIP. However, because this problem is NP-hard, there is a limitation in obtaining an optimal solution despite using the solver. Thus, we propose various heuristic algorithms, such as priority rule-based list scheduling, constructive heuristic, and metaheuristic to solve the large-sized problem within a short computation time.