# Metaheuristics for a Flow Shop Scheduling Problem with Urgent Jobs and Limited Waiting Times
## 3 Problem Description and an MIP Model  
This section describes the considered problem in more detail with assumptions made in this study and provides a mixed-integer programming (MIP) formulation. There are \(n\) independent jobs (\(i=1,\,\ldots,\,n\)) to be scheduled in a two-stage flow shop with limited waiting times between the stages. The \(n\) jobs belong to one of two classes, \(A\) or \(B\), according to their urgencies. Two classes \(A\) and \(B\) represent each class of urgent jobs and normal jobs, respectively. Accordingly, let \(J_{A}\) and \(J_{B}\) be the sets of jobs in classes \(A\) and \(B\), respectively. The objective function of this scheduling problem is the weighted sum of makespan for normal jobs and total tardiness for urgent jobs, which is to be minimized. For this problem, only permutation schedules are considered. In other words, jobs are processed on the two machines in the same order. Note that, although the permutation schedule does not guarantee optimality for the scheduling measures, semiconductor manufacturing systems process wafer lots in permutation schedules for ease of lot management and flexibility in material handling, and because of limited buffer spaces [3]. The following assumptions are also made this study:  
1. no job can be preempted;
2. machines do not fail (no breakdown);
3. all normal jobs are available to be processed at time zero (beginning of the scheduling horizon);
4. release times and arriving times of urgent jobs are positive and given in advance;
5. the due date of an urgent job \(i\) is set to the earliest possible completion time assuming that the urgent job \(i\) is started immediately as arrived at the flow shop and processed without waiting, i.e., \(d_{i}=r_{i}+p_{i1}+p_{i2}\). Table 1 represents the notation for parameters and decision variables used to describe the MIP and proposed heuristic algorithms throughout this paper. The following is the MIP for the scheduling problem considered in this study. \[[\mathrm{P}]\quad\mathrm{minimize}\quad\alpha\sum_{i}\tau_{i}+(1- \alpha)Z\] (1) subject to \[\sum_{t}x_{it}=1,\forall i \tag{2}\] \[\sum_{i}x_{it}=1,\forall t\] (3) \[c_{t1}\geq\sum_{i}(r_{i}+p_{i1})x_{it},\forall t\] (4) \[c_{t1}\geq c_{(t-1)1}+\sum_{i}p_{i1}\cdot x_{it},\quad t\geq 2\] (5) \[c_{t2}\geq c_{(t-1)2}+\sum_{i}p_{t2}\cdot x_{it},\quad t\geq 2\] (6) \[c_{t2}\geq c_{t1}+\sum_{i}p_{t2}\cdot x_{it},\ \forall t\] (7) \[c_{t2}\leq c_{t1}+\sum_{i}(w_{i}+p_{t2})x_{it},\quad\forall t\] (8) \[c_{t2}\leq c_{i}+(1-x_{it})M,\quad\forall i,t\] (9) \[c_{t2}\geq c_{i}+(1-x_{it})M,\quad\forall i,t\] (10) \[\sum_{t}x_{it}=1,\forall i \tag{2}\]0 (11) \[\sum_{t}x_{it}=1,\forall i \tag{2}\]1 (12) \[\sum_{t}x_{it}=1,\forall i \tag{2}\]2 (13) \[\sum_{t}x_{it}=1,\forall i \tag{2}\]3  
The objective function (1) is to minimize the weighted sum of total tardiness for urgent jobs and the makespan for normal jobs. Constraints (2) and (3) ensure that each job can be and should be assigned to only one position, and each position requires only one job. Constraint (4) ensures that jobs can be started after their release times. Constraints (5) amd (6) define the completion times of jobs assigned to \(t\)th position on machines 1 and 2, respectively. Constraints (7) and (8) ensure that jobs should keep their limited waiting times between machines 1 and 2. Constraints (9) and (10) define the com