# Production Planning Problem of a Two-Level Supply Chain with Production-Time-Dependent Products
## 3 Heuristic Algorithm  
Since an uncapacitated facility location problem (UFLP) is known as NP-hard [51], our problem, FLPP-VC, is also NP-hard. Note that the UFLP is a special case of the FLPP-VC, that is, it is the case in which the capacities of the facilities are unlimited, demands of each product in all periods are the same, and suppliers produce a single product. Since it may take an excessive amount of time to obtain optimal solutions of the FLPP-VC using a commercial solver even for small-size instances, we present a two-step heuristic algorithm in this paper. First, to simplify the problem, we group the demands for semi-finished products (of the same type or different types) based on the start time to produce the semi-finished products for satisfying the demand. That is, a demand group for period \(t\) is the set of demands for all semi-finished product types that must be started at period \(t\) in order for the supplier's production to meet the demands on time. Before explaining the heuristic in detail, an additional notation is provided. \begin{tabular}{l l} \(i\) & for suppliers (\(i=1,\,\ldots,\,I\)) \\ \(l\) & index for semi-finished product \\ \(\widetilde{D}_{t}\) & total demand quantity of demand group \(t\), i.e., the sum of demand quantities of semi-finished products for which the production should be started in period \(t\) to meet their demand \\ \(\overline{C}_{i}^{p}\) & average of production costs of semi-finished product types produced at supplier \(i\), \\ \(\overline{C}_{i}^{t}\) & average of transportation costs of semi-finished product types produced at supplier \(i\), \\ \(\sum_{l=1}^{L}C_{il}^{t}/L\) \\ \(E_{t}^{\text{av}}\) & set of suppliers that are available (to start production) in period \(t\), those have been set up at the beginning of period \(t\) for production of semi-finished products \\ \(E_{t}^{st}\) & set of suppliers that are to start production in period \(t\) \\ \(Z_{jlt}\) & \(=1\) if \(i\in E_{t}^{st}\), i.e., if supplier \(i\) with production line \(j\) is selected to start production in period \(t\), and 0 otherwise \\ \end{tabular}   
To develop the two-step heuristic algorithm, we decompose the considered problem into two parts, and these are solved in each of the two steps, respectively. In the first step, we select suppliers that produce semi-finished products in each period and determine a production line of the selected suppliers. This decision made at the first step is related to the allocation of the suppliers to each period. Given the selected suppliers in each period, the second step is to determine the production quantity of each semi-finished product type at each of the selected suppliers. However, it may take an excessive amount of time if we consider demands for all semi-finished product types in all periods individually. Therefore, we use the concept of the demand group defined above. In the first step, the following integer program is used for the selection decisions for period \(t\) where \(t=1,\,2,\,\ldots,\,T\). Here, we use a new cost term, \(V_{ij}=S_{ij}^{lt}+\left(\overline{C}_{i}^{p}+\overline{C}_{i}^{t}\right)K_{ ij}\), which represents the setup, production, and transportation costs associated with supplier \(i\) of production line \(j\). \[[\text{IP}_{t}]\text{ Minimize}\quad\sum_{i\in E_{t}^{\text{av}}}\sum_{j}V_{ij} \cdot Z_{ij} \tag{10}\]  
\[\text{subject to}\quad\sum_{i\in E_{t}^{\text{av}}}K_{ij}\cdot Z_{ij}\geq \widetilde{D}_{t}\qquad\forall\,j \tag{11}\]  
\[\sum_{j}Z_{ijt}\leq 1\qquad\forall\,i \tag{12}\]  
\[Z_{ijt}\in\{0,1\}\qquad\forall\,i,\,j \tag{13}\]By the objective function, the sum of the operation costs at the suppliers in period \(t\) is minimized. Constraint (11) ensures that the sum of capacity of production lines of the selected suppliers in \(E_{t}^{av}\) can satisfy the demand quantity of the demand group of period \(t\). Therefore, by using [IP\({}_{t}\)], we can select suppliers to satisfy the demand in period \(t\) with the minimum cost.