# Production Planning Problem of a Two-Level Supply Chain with Production-Time-Dependent Products
## 3 Heuristic Algorithm
Even though [IP\({}_{t}\)] is based on the simplified demand groups, it is not easy to find the optimal solution of [IP\({}_{t}\)]. As an alternative, we suggest a heuristic algorithm to select suppliers and determine their production line to produce semi-finished products. In each period, we first select a supplier with the minimum operating cost (\(V_{it}\)) among those in \(E_{t}^{av}\) and add the selected supplier into \(E_{t}^{st}\). If the demand quantity of the demand group is not satisfied by the selected supplier, other suppliers are selected one by one with the same method until the demand is satisfied by the capacity levels of the selected suppliers. When suppliers are selected for demand group of period 1, all suppliers with all (candidate) production lines are available, that is, all suppliers are in \(E_{1}^{av}\). If supplier \(i\) with production line \(j\) is selected in period 1, it is included in the set of selected suppliers (\(E_{1}^{st}\)) and is not considered for being selected until the production of a batch is completed. By updating \(E_{t}^{av}\) for the subsequent periods, we can solve [IP\({}_{t}\)] and obtain \(E_{t}^{st}\) for \(\forall t=1,\,2,\,\ldots,\,T\). Once suppliers are allocated to each period, that is, suppliers to be opened (or operated) in each period and their production line for producing are determined, the subproblem of determining production quantities of each supplier can be defined, and it is formulated as the following linear program. \[\text{[LP] Minimize}\qquad\sum_{i\in E_{t}^{st}}\sum_{j}\sum_{l}\Big{(}C_{il}^ {p}+C_{il}^{t}\Big{)}Q_{ijlt}+\sum_{i\in E_{t}^{st}}\sum_{j}S_{ij}^{l}\cdot Z _{ijt} \tag{14}\]  
subject to \[\qquad\sum_{i\in E_{t}^{st}}\sum_{j}Q_{ijlt}\geq D_{l,t+p_{l}}\qquad\quad \forall\,l\] (15)  
\[\sum_{l}Q_{ijlt}=K_{ij}\cdot Z_{ijt}\qquad\quad\forall\,i\in E_{t}^{st},\,j \tag{16}\]  
\[Q_{ijlt}\geq 0\qquad\forall\,i\in E_{t}^{st}\,,\,j,\,l \tag{17}\]  
Solution values of the second term of the objective function (14) are given from the solutions of (IP\({}_{t}\)). Constraints (15), (16), and (17) correspond to (2), (3), and (8), respectively. Constraint (15) ensures that the sum of production quantities of suppliers for each semi-finished product type in period \(t\) have to satisfy the demand in period \(t\). Constraints (16) ensures that the capacity of the operated production line of the supplier operated in period \(t\) is equal to the total production quantity in period \(t\). Note that only the suppliers selected to produce semi-finished products, i.e., suppliers \(i\) such that \(i\in E_{t}^{st}\), are considered in [LP], and hence there are much fewer constraints to be considered. In our solution procedure, [LP] is solved with a commercial programming solver for linear programming. By applying the above two steps sequentially, we can obtain a feasible, and possibly a good solution of FLPP-VC. The overall procedure of the heuristic can be summarized as follows. **Procedure 1. ** (Two-step heuristic for FLPP-VC) \begin{tabular}{l l} _Step 0_ & \(\text{Set }E_{0}^{av}=\{1,\,2,\,\ldots,\,I\}\), \(E_{1}^{st}=\emptyset\), \(t\)=1, and \(TC^{*}=\infty\). Compute \(\widetilde{D}_{t}\) for \(t=1,\,\ldots,\,T\), and \(V_{ij}\) for \(i=1,\,\ldots,\,I\) and \(j=1,\,\ldots,\,J\). Let \(t=1\). \\ _Step 1_ & \(\text{If there are suppliers with }\widetilde{D}_{t}<K_{ij}\), select a supplier with the smallest value of \(V_{ij}\) among them; otherwise, select a supplier and its production line with the smallest \(V_{ij}\) among suppliers in \(E_{t}^{av}\). Update \(E_{t}^{st}\) and \(E_{t}^{av}\), and let \(\widetilde{D}_{t}\leftarrow\widetilde{D}_{t}-K_{ij}\). \\ _Step 2_ & \(\text{If }\widetilde{D}_{t}>0\), go to Step 1. Otherwise (\(\widetilde{D}_{t}\leq 0\)), if \(t=T\), go to Step 3; otherwise, let \(t\)\(\leftarrow\)\(t+1\) and go to Step 1. \\ _Step 3_ & \(\text{Solve the linear program, [LP], defined by the solution of _Step_ 1 (with a commercial LP solver), and stop. \\ \end{tabular}