# Metaheuristics for a Flow Shop Scheduling Problem with Urgent Jobs and Limited Waiting Times
## 4 Heuristic Algorithms
### Iterated Greedy Algorithm  
The iterated greedy algorithm (IG) is a metaheuristic based on a stochastic local search strategy, developed in [43]. The original IG was specially devised for the permutation flow shop scheduling problem. Because of its simplicity of the structure and excellent performance, IGs have been popularly used in much flow shop research. The procedure of IG iterates four phases of destruction, construction, local search, and acceptance, to find better solutions. In the destruction phase, the predetermined number (\(d\)) of jobs are removed from a current schedule. Then, in the construction phase, a neighborhood schedule is generated by inserting the removed jobs in a constructive way such as that of NEH.  
1. In the proposed IG, \(d\) jobs are removed randomly from a current solution (\(S\)) in the destruction phase. Then, two partial schedules are generated. One (\(S_{\text{D}}\)) is a schedule consisting of \(d\) jobs removed from \(S\), the other is a partial schedule (\(S_{\text{R}}\)) with (\(n-d\)) jobs. After that, in the construction phase, a complete schedule is constructed by inserting the jobs of \(S_{D}\) into the best positions of \(S_{R}\), such as the _for-loop_ in Figure 1. After these two phases, the complete schedule is improved by a local search procedure. In this IG, the interchange method used in NEH is implemented for the improvement. Completing the local search, the new schedule (\(S^{\prime}\)) is compared to the current schedule (\(S\)). If \(S^{\prime}\) is better than \(S\), i.e., \(obj(S^{\prime})<obj(S)\), \(S^{\prime}\) replaces \(S\). Otherwise, borrowing the concept of an acceptance in a simulated annealing algorithm, the replacement is accepted with a probability \(exp(-\Delta/T)\), where \(\Delta=obj(S^{\prime})-obj(S)\), and \(T\) is an adjustable parameter (called _temperature_) in the IG. However, unlike SA, \(T\) is constant in IG. The temperature value \(T\) is calculated as  
\[T=\frac{\sum_{i=1}^{n}\sum_{k=1}^{m}p_{ik}}{10 nm} \tag{19}\]  
suggested in [44] for the permutation flow shop scheduling problem. In this study, \(m=2\). These four phases are repeated until a termination condition is satisfied. Herein, the maximum computation time is used for the termination condition. The whole procedure of IG is summarized in Figure 2. In the procedure, let _random_() denote a function to return a random number greater than or equal to zero and less than one.  
Figure 1: Procedure of the proposed NEH algorithm.  
procedure IG \(S^{*}\gets S\leftarrow\) NEH \(\textit{while}(\text{elapsed time < maximum CPU time})\) // destruction phase \(S_{D}\leftarrow\{d\}\) jobs randomly removed from \(S\)] \(S_{R}\gets S\setminus S_{D}\) //construction phase for(t=1; t <=d; t++) \(i\gets t\)-th job of \(S_{D}\) insert \(i\) into the best position of \(S_{R}\) \(\hat{S}\leftarrow\) a schedule resulting from the construction phase  
//local search phase \(t=1\) and \(t^{\prime}=t+1\) while(t <=n and t' <=n) \(S^{\prime}\leftarrow\) a new sequence by interchanging two jobs in \(t\)-th and \(t^{\prime}\)-th jobs of \(\hat{S}\) if(obj(\hat{S})<obj(\hat{S})\) \(\hat{S}\gets S^{\prime}\) if(t' <=t) \(t^{\prime}\gets t^{\prime}+1\) else \(t\gets t+1\) and \(t^{\prime}\gets t+1\) //acceptance phase ifobj(\hat{S})<obj(\hat{S}) then \(S\leftarrow\hat{S}\) else \(\Delta=obj(\hat{S})-obj(\hat{S})\) ifrandom(\(\hat{S}<\exp(-\Delta/T)\) then \(S\leftarrow\hat{S}\) ifobj(\hat{S})<obj(\hat{S}^{*})\) then \(S^{*}\gets S\) return \(S^{*}\) end procedure ```  
**Figure 2**. Procedure of the proposed IG algorithm.