# Heuristics for a Two-Stage Assembly-Type Flow Shop with Limited Waiting Time Constraints
## 2 Problem Description  
This section describes the scheduling problems considered in more detail with assumptions and mathematically defines the problem through an MIP formulation. In this study, there are \(n\) jobs to be scheduled, and it is assumed that information regarding the jobs is provided in advance. The first stage consists of \(m\) dedicated machines that fabricate \(m\) different components, whereas there is a single assembly machine to assemble the \(m\) components into a final product in the second stage. The assembly operations of all jobs must start within limited waiting times given to the jobs after completing the fabrication of their components. The objective function of the scheduling problem is to minimize the makespan, which is equal to the completion time of the last job. The other assumptions made in this study are as follows:  
* All jobs can be started at time zero;
* Preemption is not allowed;
* Not all machines can process multiple jobs simultaneously. In other words, machines can process only one job at a time;
* The distances and delivery times between the two stages are ignored.  
In this problem, there are \((n!)^{(m+1)}\) alternative sequences, because \(n!\) sequences are possible for each machine. However, there is an optimal solution among \(n!\) permutation schedules in which the operating sequences of the jobs are the same on the machines. This can be proven according to the proof by [PERSON] et al. [43] that permutation schedules are dominant for the two-stage assembly flow shop to minimize the total completion time, and this proof is sufficient to show that permutation schedules are also dominant for any regular performance measure, including makespan. Although this study considers the limited waiting time constraints, the left-shift schedules in which some operations begin earlier without delaying any other operations are dominant, because a delayed start increases the waiting time. Furthermore, in practical production lines, permutation schedules are commonly utilized to ensure simplicity of managing work, flexibility of material handling, and constrained buffer space. Therefore, this study only considers permutation schedules; that is, all sequences on the machines in the considered flow shop are the same. Table 1 provides the notation for a clear description of the algorithms proposed in this study.  
The following is the MIP formulation for the considered scheduling problem.  
\[\begin{array}{llll}\text{Minimize}&c_{[n](m+1)}&(1)\\ \text{subject to}&s_{[r]k}+\sum_{i=1}^{n}p_{ik}x_{ir}\leq s_{[r+1]k}&r\leq n-1 \text{ and }k\leq m&(2)\\ &s_{[r]k}+\sum_{i=1}^{n}p_{ik}x_{ir}\leq s_{[r](m+1)}&\forall r\text{ and }k\leq m&(3)\\ &s_{[r]k}+\sum_{i=1}^{n}(p_{ik}+w_{k})x_{ir}\geq s_{[r](m+1)}&\forall r\text{ and }k\leq m&(4)\\ &s_{[r](m+1)}+\sum_{i=1}^{n}p_{i(m+1)}x_{ir}=c_{[r](m+1)}&\forall r&(5)\\ &\sum_{r=1}^{n}x_{ir}=1&\forall i&(6)\\ &\sum_{i=1}^{n}x_{ir}=1&\forall r&(7)\\ &s_{[r]k},c_{[r](m+1)}\geq 0&\forall r,k&(8)\\ &x_{ir}\in\{0,1\}&\forall i,r&(9)\\ \end{array}\]  
The objective Function (1) is the minimization of the makespan, which is equal to \(c_{[n](m+1)}\), the completion time of the last scheduled job \([n]\) in the second-stage machine, that is, machine \((m+1)\). Constraints (2) and (3) define the starting times on the same machine and between the two stages, respectively. Constraint (4) ensures that jobs must maintain the limited waiting times between both stages. Constraint (5) computes the completion times of the jobs on the machine \((m+1)\). Constraints (6) and (7) consider only the permutation schedules. That is, each job can only be sequenced once, without being partitioned. Constraints (8) and (9) define the domain of the decision variables.