## 3 Approximation Solution Algorithm
### Solution Encoding and Modification  
GA relies on a population of individuals to explore a search space. Each individual is a set of chromosomes representing a candidate solution. In this work, a solution is denoted by \(\pi\). Thus, each individual (i.e., a candidate solution) in GA is encoded as a string of 1 (if the corresponding position is a virtual wafer) and 0 (if the corresponding position is a real wafer). For Step \(i\), \(i{\in}\)N\({}^{+}_{n}\), if \(d_{i}=1\) obtained by Equation (5), it means that at least one virtual wafer is required to be loaded into a PM at the step to ensure the chamber cleaning requirement after \(m_{i}\) real wafers are continuously processed in the PM, at most. In order to check if the chamber cleaning requirement at Step \(i\), \(i{\in}\)N\({}^{+}_{n}\), with \(d_{i}=1\) is met, it needs to know the type (i.e., virtual or real) of the \(j\)-th wafer processed in a PM at the step. Thus, Algorithm 1 is developed to update \(x_{j},j>0\), based on \(\pi=(x^{\prime}_{  
Notice that after \(n_{i}\times k_{i}\) wafers are processed at Step \(i\), \(k_{i}\) wafers are processed by each PM at the Step. Further, the next \(k_{i}\) wafers (including virtual and real ones) to be processed by a PM has the same wafer loading sequence as the processed \(k_{i}\) wafers. Thus, Statements (8)-(11) obtain the type of the \(j\)-th wafer, \(1+n_{i}\times k_{i}\leq j\leq(m_{i}+k_{i})\times n_{i}\), loaded into the step. For Step \(i\), \(i\)\(\in\)N\({}^{+}\)n, if \(d_{i}=2\) obtained by Equation (5), it means that at least two virtual wafers are required to be consecutively loaded into a PM at the step to ensure the chamber cleaning requirement after \(m_{i}\) real wafers are continuously processed in the PM, at most. Then, Algorithm 2 is developed to obtain the type of the \(j\)-th wafer processed at the step, i.e., update \(x_{j}\), \(j>0\), based on \(\pi\). ```
Input:\(\pi\); Output:\(x_{j}\), \(1\leq j\leq(2k_{i}+1)\times n_{i}\); (1)-(7) Same as the ones in Algorithm 1, respectively (8) For \(g=1\) to \(n_{i}\) (9) For \(h=0\) to \(k_{i}-1\) (10) \(x_{g+h\times n_{i}+k_{i}\times n_{i}}=x_{g+h\times n_{i}}\); (11) \(x_{g+2k_{i}\times n_{i}}=x_{g}\);
```
**Algorithm 2**Updating \(x_{j}\) based on \(\pi\) for the case with \(d_{i}=2\)  
In Algorithm 2, Statements (1)-(7) are same as those in Algorithm 1, and are used for setting \(x_{j}\), \(1\leq j\leq n_{i}\times k_{i}\). Notice that, under a PVS, the wafer type sequence to be processed by a PM at Step \(i\) is periodically repeated, and the number of wafers in such a sequence is \(k_{i}\) obtained by Equation (6). Then, three consecutive wafer processing sequence are named as WPS-1, WPS-2, and WPS-3, respectively. Further, let \(x_{j}\), \(j=g+h\times n_{i}\), \(g\in\{1\), \(2\),..., \(n_{i}\}\), \(0\leq h\)\(\leq k_{i}-1\), denote a wafer in WPS-1; \(x_{j}\), \(j=g+h\times n_{i}\), \(g\in\{1\), \(2\),..., \(n_{i}\}\), \(k_{i}\leq h\leq 2k_{i}-1\), a wafer in WPS-2; and \(x_{j}\), \(j=g+h\times n_{i}\), \(g\in\{1\), \(2\),..., \(n_{i}\}\), \(2k_{i}\leq h\leq 3k_{i}-1\), and a wafer in WPS-3. There may exist a case when only two virtual wafers are consecutively processed by a PM in a processing sequence consisting of WPS-1 and WPS-2. In such a case, one virtual wafer is at the \(k_{i}\)-th position in WPS-1 (i.e., \(x_{j}\), \(j=g+h\times n_{i}\), \(h=k_{i}-1\)), while the other virtual wafer is at the first position in WPS-2 (i.e., \(x_{j}\), \(j=g+h\times n_{i}\), \(h=k_{i}\)). These two consecutive wafers represent a chamber cleaning operation. In order to check if the chamber cleaning requirement can be met, how many real wafers are processed between this chamber cleaning operation and the next one needs to be known. In this case, two consecutive virtual wafers at the \(k_{i}\)-th position in WPS-2 (i.e., \(x_{j}\), \(j=g+h\times n_{i}\), \(h=2k_{i}-1\)) and the first position in WPS-3 (i.e., \(x_{j}\), \(j=g+h\times n_{i}\), \(h=2k_{i}\)) represent the next one.