Production Planning Problem of a Two-Level Supply Chain with Production-Time-Dependent Products

Featured Application

Production planning problems with supply chains such as livestock, steel and chemical industries.

Abstract

This study considers a production planning problem with a two-level supply chain consisting of multiple suppliers and a manufacturing plant. Each supplier that consists of multiple production lines can produce several types of semi-finished products, and the manufacturing plant produces the finished products using the semi-finished products from the suppliers to meet dynamic demands. In the suppliers, different types of semi-finished products can be produced in the same batch, and products in the same batch can only be started simultaneously (at the same time) even if they complete at different times. The purpose of this study is to determine the selection of suppliers and their production lines for the production of semi-finished products for each period of a given planning horizon, and the objective is to minimize total costs associated with the supply chain during the whole planning horizon. To solve this problem, we suggest a mixed integer programming model and a heuristic algorithm. To verify performance of the algorithm, a series of tests are conducted on a number of instances, and the results are presented.

1. Introduction

This study considers a problem of production planning in a two-level supply chain consisting of multiple suppliers and a manufacturing plant. Each supplier that consists of multiple production lines can produce several types of semi-finished products and the manufacturing plant produces the finished products using the semi-finished products from the suppliers to meet dynamic demands. The planning manager of this supply chain selects suppliers to produce semi-finished products and determines the quantity of semi-finished products to be produced for each period to minimize total costs associated with the supply chain (the information of demand in each period is known in advance).

We focus on a case in which semi-finished products are produced by almost the same general process, but those products are sorted according to their production times. That is, the type of semi-finished product depends on the production time. In this paper, we assume that different types of semi-finished products can be produced in the same batch, and products in the same batch can only be started simultaneously (at the same time) even if they complete at different times. Such production characteristics (called production time-dependent products) can be easily found in food industries such as fermented foods, wines, and poultry. In the case of poultry farming industry, it has only been studied to analyze diseases and environmental issues [1,2], or to determine the location and size of livestock [3]. However, production management of the poultry industry is also one of the most important issues, but there is little research on this issue. Therefore, we focus on the production planning with consideration of characteristics of poultry farming.

In this industry, sizes (or weights) of the products are one of major attributes that distinguish the types of final products. In the suppliers, the size (weight) of the poultry may be the only distinguishing attribute if we do not consider exceptional cases like infection of diseases. In general, the size of poultry depends on the breeding time, and hence production plans for the semi-finished products at the suppliers are established considering the breeding time (or production time) of the semi-finished products. The production time-dependent products can also be found in other industries such as steel industry and chemical industry.

In the poultry industry, many companies own and operate manufacturing plants and many poultry farms together. In the concept of supply chains, the farms occupy the role of suppliers. However, the farms are not independent but are subordinate to headquarters. Therefore, the production plan of such suppliers depends on the manufacturer’s plan. Based on this situation, we consider a system in which one management unit controls all suppliers and a manufacturing plant. The management determines:

• whether each supplier should be opened and operated in each period;
• the total production quantities of the semi-finished product among candidate levels;
• production quantities of each type of semi-finished product at the operated suppliers in each period.

When we determine suppliers to start production in each period, we also have to determine production quantity levels of the suppliers. For example, in real-world cases of poultry farms, there may be multiple numbers of production quantity levels depending on the number of production lines of a farm. That is, production quantity levels of farms are determined by the number of production lines to be operated to satisfy the quantity of products to be produced in each period. In other words, the farms may have to determine production quantity levels of semi-finished products in each period. We call this problem as the production planning problem with discrete production quantity levels for production-time-dependent products (FLPP-VC).

As mentioned above, the FLPP-VC determines production quantity levels in each period as a normal production planning problem. However, in each period, not every supplier starts its setup operation for processing a production batch. Therefore, we have to determine not only the production quantity, but also suppliers to be operated. Focusing on the determination in each period, the considered problem becomes the special case of a typical facility location problem (FLP). Both problems deal with selecting locations of the facilities to be operated among possible (candidate) facilities to satisfy the demand. Additionally, in general, these decisions are handled by the central manager of department, taking into account the entire systems. However, in a typical FLP, the locations of facilities are decided at the beginning of the planning horizon and the locations are fixed throughout the entire period, whereas the decisions on suppliers’ operations in the FLPP-VC can be changed during the planning horizon.

The studies of FLPP-VC are very rare, while FLPs have been studied by many researchers. Thus, we categorized and reviewed the variants of FLPs into four parts: uncapacitated FLP, capacitated FLP, dynamic FLP, and FLP determining capacities. For an uncapacitated facility location problem (UFLP), a branch-and-bound algorithm (B&B) was proposed in [4]. Additionally, for capacitated facility location problems (CFLPs), various algorithms were devised, including B&B [5,6], genetic algorithms [7,8,9,10], and Lagrangian relaxation based heuristic algorithms [11,12,13,14].

The dynamic facility location problem (DFLP), which is an FLP with multi-period dynamic demands, is very similar to our problem (FLPP-VC). However, like a typical FLP, the locations of the facilities in the DFLP are determined once at the beginning and not changed, even if it can worsen the overall efficiency of the supply chain for the entire planning period. Additionally, the semi-finished products inventory is not allowed in FLPP-VC, while DFLP can have positive inventory. For the DFLP, dynamic programming algorithms were developed in [15,16,17], while a simulated annealing was developed in [18] and an MIP based heuristic algorithm in [19]. In addition, an optimal solution algorithm was suggested in [20], considering a dual problem of the original DFLP. Additionally, ref. [21] studied an extended version of the problem considering setup, transportation, production costs and taxes (between two countries), and proposed a branch-and-bound algorithm, while [22] studied the problem considering relocation of facilities for the planning horizon and propose heuristics based on Bender’s decomposition and Lagrangian relaxation method. In their model, the opening and closing of the facilities are determined in each period but opening decisions for each facility can be done only once in the planning horizon. Ref. [23] considered a multi-period facility location problem with two different classes of customers, depending on the tolerance of delayed delivery. Ref. [24] proposed heuristic algorithms for dynamic facility location problems consisting of determining locations and sizes of facilities. Several extensions of the DFLP are also found, such as considering multi-commodities [25,26] and time restrictions for deliveries [27]. Furthermore, many heuristics and exact methods have been studied to solve the discrete multi-period facilities location problem, for example in [28,29,30,31,32].

In the considered problem, capacities of facilities can be changed. There have been very few previous studies, if any, in which changeable capacity levels were considered. However, the FLPs with determining capacities of suppliers have been considered in several studies. Among them, refs. [33,34,35,36,37] consider models in which at most one capacity level can be selected among a set of possibilities. Additionally, there are some studies on FLPs in which expansion of capacities is considered [38,39,40,41,42]. On the other hand, the production-time-dependent products dealt with in this paper have just been introduced in [43], and [44] studied a production planning problem of a two-level supply chain with production-time-dependent products considering outsourcing. These two studies consider that each supplier has only one production line, whereas this study considers multiple production lines in each supplier. Note that, in practice, a facility with multiple production lines opens the appropriate number of lines, not all lines.

Finally, we reviewed several papers related to centralized supply chains that are controlled by a central managerial department (or manager): ref. [45] developed a model to design a centralized supply chain network in markets under deterministic price-depended demands and with a rival chain present; ref. [46] analyzed and compared centralized and decentralized model predictive control strategies to control inventory positions and to reduce the bullwhip effect in a benchmark four-echelon supply chain; ref. [47] investigated the supply chain scenarios for their relevant performance at the conceptual design stage and showed that the centralized supply chain scenario demonstrates superiority in cost performance; ref. [48] presented a mathematical model to plan logistics activities in a forest products supply chain; ref. [49] analyzed control policies for a centralized two-stage supply chain with subcontractors at each stage a number of numerical results show the impact of variations in certain system parameters on file optimal control parameters and the corresponding profit; and ref. [50] explored the impact of misplaced inventory on a centralized two-level supply chain, which consists of a risk-neutral supplier and a risk-averse retailer.

The main contributions of this paper are as follows. To the best of our knowledge, this study is the first attempt to solve a production planning problem that needs to determine the location of facilities (suppliers) with multiple production lines in each period and the quantities of production-time-dependent products to be produced in each supplier. For the problem, we propose a mixed-integer linear programming (MILP) and a heuristic algorithm, considering variable capacity levels for production-time-dependent products with dynamic demands in a two-level supply chain. The heuristic algorithm consists of two steps: determining locations of facilities and then determining capacities of the facilities, i.e., determining which suppliers should be operated in each period, and the quantity produced for each type of semi-finished product from the supplier (selected for operating in each period).

This paper is organized as follows. In Section 2, we present the MILP and explain the problem in detail, and then we introduce a heuristic algorithm in Section 3. In Section 4, to evaluate the performance of our proposed algorithm, computational experiments are performed, and the results are reported. Finally, we conclude this paper with a short summary and discuss possible extensions of our study in Section 5.

2. Problem Description

This study considers a problem of production planning for the production-time-dependent products in a two-level supply chain consisting of multiple suppliers and a manufacturing plant. Each supplier has an upper limited capacity for production quantity which can be produced simultaneously at the same batch. However, it is assumed that the manufacturing plant is uncapacitated, that is, the plant can satisfy all demands of external customers. In a poultry industry, the production process of a manufacturer is simple and automated, such as packaging or cutting. Additionally, in general, the capacity of manufacturer is relatively larger than those of the suppliers. Thus, it is sufficient to consider only the capacities of suppliers for solving the real problem. To establish a production plan for the considered supply chain, a planning manager determines which suppliers start to produce semi-finished products in each period, capacities of the selected suppliers, and production quantities of each semi-finished product type at each supplier. The results of the planning are quantities of raw materials to be input into the suppliers for production of the semi-finished products.

As mentioned in the previous section, the considered problem is motivated from a poultry farming industry in Korea. Thus, this study makes the following assumptions based on the situation of the poultry farming industry.

• The supply chain consists of multiple suppliers and a manufacturing plant;
• Locations of the manufacturing plant and the (candidate) suppliers are pre-determined and given;
• The suppliers produce several types of semi-finished products, and different semi-finished products may be produced at the same production line of a supplier. Note that we need to decide suppliers, product lines, and product types to produce, respectively;
• If two or more types of semi-finished products are to be produced at the same supplier, they should be started simultaneously;
• In a supplier, a new batch cannot be started while a batch is being produced;
• A setup operation is needed (for cleaning and maintenance of a production line) at each supplier before each production run of a batch;
• The capacity levels of production lines of each supplier and setup cost for each level are known and fixed;
• Capacity of each supplier is equal to the sum of capacity levels of production lines in the supplier;
• The demand for each product type in each period may vary by period and is known in advance;
• There is no shortage of raw material for the semi-finished products;
• There is no defective in the production process at the suppliers. Hence, the input and the output quantities at a supplier are the same;
• All suppliers are ready to start production at the beginning (starting) of the planning horizon. In addition, there is no need for a setup operation for the first batch of the planning horizon;
• The transportation time is negligibly short (compared to a period);
• Only one production line can be selected and operated for a supplier at each operating period;
• Production quantity of operated production line in a supplier to be operated in each period is equal to the capacity of the operated production line.

For a clearer description of the problem, we develop a mixed integer programming formulation. We use this formulation to find an optimal solution for this problem using a commercial integer programming solver in the computational experiments.

The following notation is used throughout the paper.

2.1. Indices and Parameters

i 

index for suppliers (i = 1,…, I)

l 

index for semi-finished product types (l = 1,…, L)

t 

index for time periods (t = 1,…,T)

j 

index for production lines (j = 1,…,J)

$p_l$

production time (in the number of time periods) of semi-finished product type l at the suppliers

$S_{ij}^U$

setup cost for each batch at supplier i with production line j

$K_{ij}$

capacity of production line j at supplier i

$D_{lt}$

demand quantity (at the manufacturing plant) of semi-finished product type l in period t

$C_{il}^P$

production cost per one unit of semi-finished product type l at supplier i

$C_{il}^T$

transportation cost per one unit of semi-finished product type l from supplier i to the manufacturing plant

M 

a very large (positive) number

2.2. Decision Variables

$Q_{ijlt}$

production quantity of semi-finished product type l, the quantity that is being processed, at production line j in supplier i on period t

$Y_{ijlt}$

= 1 if production line j of supplier i starts processing semi-finished product l in period t, and 0 otherwise

$Z_{ijt}$

= 1 if production line j of supplier i starts producing semi-finished products in period t, and 0 otherwise

Now, we give a mixed integer programming formulation for our problem below.

$$\begin{array}{ll}[\mathrm{P}]\mathrm{Minimize}& {\sum }_i{\sum }_j{\sum }_t{S}_{ij}^U{Z}_{ijt}+{\sum }_i{\sum }_j{\sum }_l{\sum }_t\left(C_{il}^P+C_{il}^T\right)Q_{ijlt}\end{array}$$

(1)

$$\begin{array}{ll}\mathrm{subject}\mathrm{to}& {\sum }_i{\sum }_j{Q}_{ijlt}\ge D_{l,t+p_l}\forall l,t\end{array}$$

(2)

$${\sum }_l{Q}_{ijlt}=K_{ij}·Z_{ijt}\forall i,j,t$$

(3)

$${\sum }_j{Z}_{ijt}\le 1\forall i,t$$

(4)

$${\sum }_l{Y}_{ijlt}\le L·Z_{ijt}t=1,\text{…},T-p_l,\forall i,j,l$$

(5)

$${\sum }_{t^{\prime }=t+1}^{t+p_l}{Z}_{ij{t}^{\prime }}\le M·\left(1-Y_{ijlt}\right)t=1,\text{…},T-p_l,\forall i,j,l$$

(6)

$$Q_{ijlt}\le M·Y_{ijlt}\forall i,j,l,t$$

(7)

$$Q_{ijlt}\ge 0\forall i,j,l,t$$

(8)

$$Y_{ijlt},Z_{ijt}\in \left\{0,1\right\}\forall i,j,l,t$$

(9)

The objective function (1) is to minimize the total costs incurred in the supply chain, including setup costs of suppliers to start production, production costs at the suppliers, and transportation costs from suppliers to the manufacturing plant. Constraint (2) ensures demand is satisfied, i.e., the sum of production quantities of suppliers for each semi-finished product type is larger than demand. Constraint (3) ensures that the total production quantity is equal to the capacity of the operated production line of the supplier operated in each period. Constraint (4) ensures that only one production line can be selected and operated for a supplier at each operating period. Additionally, constraint (5) ensures that the selected production line can produce up to L types of products. This constraint defines relationship between $Y_{ijlt}$ and $Z_{ijt}$. In addition, constraint (6) prevents a supplier from starting a new batch in the middle of processing a batch. Constraint (7) defines the relationships between $Q_{ijlt}$ and $Y_{ijlt}$. Constraints (8) and (9) define the domain of decision variables.

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.

i 

for suppliers (i = 1,…, I)

l 

index for semi-finished product

${\tilde{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, ${\sum }_{l=1}^L{C}_{il}^p/L$

${\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^{\mathrm{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_ijt 

= 1 if i∈$E_t^{st}$, i.e., if supplier i with production line j is selected to start production in period t, and 0 otherwise

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, …, T. Here, we use a new cost term, $V_{ij}=S_{ij}^U+\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.

$$\begin{array}{ll}[{\mathrm{IP}}_t]\mathrm{Minimize}& {\sum }_{i\in E_t^{av}}{\sum }_j{V}_{ij}·Z_{ij}\end{array}$$

(10)

$$\begin{array}{ll}\mathrm{subject}\mathrm{to}& {\sum }_{i\in E_t^{av}}{K}_{ij}·Z_{ijt}\ge {\tilde{D}}_t\forall j\end{array}$$

(11)

$${\sum }_j{Z}_{ijt}\le 1\forall i$$

(12)

$$Z_{ijt}\in \left\{0,1\right\}\forall i,j$$

(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.

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 suppler 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 ∀t = 1, 2, …, 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.

$$[\mathrm{LP}]\mathrm{Minimize}{\sum }_{i\in E_t^{st}}{\sum }_j{\sum }_l\left(C_{il}^p+C_{il}^t\right)Q_{ijlt}+{\sum }_{i\in E_t^{st}}{\sum }_j{S}_{ij}^U·Z_{ijt}$$

(14)

$$\mathrm{subject}\mathrm{to}{\sum }_{i\in E_t^{st}}{\sum }_j{Q}_{ijlt}\ge D_{l,t+p_l}\forall l$$

(15)

$${\sum }_l{Q}_{ijlt}=K_{ij}·Z_{ijt}\forall i\in E_t^{st},j$$

(16)

$$Q_{ijlt}\ge 0\forall i\in E_t^{st},j,l$$

(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)

Step 0

Set $E_0^{av}$= {1, 2, …, I}, $E_1^{st}$ = ∅, t=1, and TC* = ∞. Compute ${\tilde{D}}_t$ for t = 1,…, T, and V_ij for i = 1,…, I and j = 1,…, J. Let t = 1.

Step 1

If there are suppliers with ${\tilde{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 ${\tilde{D}}_t\leftarrow {\tilde{D}}_t-K_{ij}$.

Step 2

If ${\tilde{D}}_t>0$, go to Step 1. Otherwise (${\tilde{D}}_t\le 0$), if t = T, go to Step 3; otherwise, let t←t + 1 and go to Step 1.

Step 3

Solve the linear program, [LP], defined by the solution of Step 1 (with a commercial LP solver), and stop.

4. Computational Experiments

In this paper, we evaluated the suggested algorithm through computational experiments on a number of problem instances. These problem instances were generated randomly based on real information from a poultry company in Korea. Three levels of the number of supplies (I = 10, 12, and 14) and three levels of the length of planning horizon (T = 6, 8, and 10) were considered. For the nine combinations of (I and T), 10 instances were generated (totally 90 instances). Based on the information from the poultry company, we considered three types of semi-finished products with different processing time (L = 3, 4, and 5), and the numbers of candidate production line are three for all suppliers (J = 3). Other data were generated as follows. Here, U(a, b) represents the discrete uniform distribution with range [a, b].

• Demand was generated from U(500, 800) for all types of product at each period;
• The capacities of the three production lines at a supplier were generated from U(100, 200), U(200, 300), and U(300, 400), and setup costs for these production lines were generated from U(500, 1000), U(1000, 1500), and U(1500, 2000), respectively;
• The production cost of each type of semi-finished products of a supplier were generated from U(10, 15), U(20, 25), and U(30, 35). The transportation costs between a supplier and the manufacturing plants were generated from U(5, 10), U(10, 15), and U(15, 20) for semi-finished product types 1, 2, and 3, respectively.

The heuristic algorithm was coded in Java programming language, and a commercial solver CPLEX was used for the linear and integer programs. We set the computation time limit to 15,000 s for an instance to prevent prolonged execution time. All tests were operated on a personal computer with AMD Phenom II (3.0-GHz) and 3 GB RAM.

Results of the test are given in

Table 1. Results of the test on 6-period instances.

I	Instances	Solutions			CPU Time (s)
		CPLEX	Heuristic	PE (%) †	CPLEX	Heuristic
10	1	61,241	64,138	4.52	8.72	0.01
	2	65,763	66,826	1.59	10.50	0.01
	3	63,785	65,348	2.39	9.88	0.01
	4	66,140	69,102	4.29	10.51	0.01
	5	67,249	67,336	0.13	10.15	0.01
	6	62,521	64,422	2.95	9.59	0.01
	7	67,159	68,917	2.55	10.20	0.01
	8	64,842	67,876	4.47	4.13	0.01
	9	64,898	67,874	4.38	9.54	0.01
	10	62,286	63,045	1.20	10.17	0.01
	average			2.86	9.34	0.01
12	11	66,482	69,100	3.79	10.33	0.01
	12	66,419	68,445	2.96	9.68	<0.01
	13	67,534	69,359	2.63	17.05	0.01
	14	69,480	70,481	1.42	11.13	<0.01
	15	66,838	69,198	3.41	18.30	<0.01
	16	63,811	66,202	3.61	10.19	<0.01
	17	68,788	71,314	3.54	10.58	<0.01
	18	66,745	67,238	0.73	20.91	<0.01
	19	69,016	70,455	2.04	36.71	<0.01
	20	66,568	68,379	2.65	5.08	0.01
	average			2.88	14.99	<0.01
14	21	67,916	70,694	3.93	8.09	0.01
	22	61,201	62,444	1.99	15.28	0.01
	23	60,641	63,014	3.77	16.34	0.02
	24	60,307	61,645	2.17	32.15	0.01
	25	64,082	66,033	2.95	16.37	0.02
	26	69,131	71,795	3.71	15.77	0.01
	27	66,336	67,238	1.34	16.75	0.01
	28	67,969	69,926	2.80	15.75	0.01
	29	68,762	70,799	2.88	64.61	0.01
	30	66,468	68,441	2.88	14.84	0.01
	average			2.86	21.60	0.01
overall				2.87	15.31	0.01

^† percentage error of the heuristic solution from the solution obtained with CPLEX.

,

Table 2. Results of the test on 8-period instances.

I	Instances	Solutions			CPU Time (s)
		CPLEX	Heuristic	PE (%) †	CPLEX	Heuristic
10	31	99,938	103,679	3.61	54.43	0.02
	32	100,048	103,625	3.45	83.15	0.02
	33	98,220	99,221	1.01	337.07	0.02
	34	96,713	97,831	1.14	65.65	0.02
	35	99,205	103,530	4.18	82.81	0.02
	36	97,558	100,409	2.84	5.59	0.02
	37	92,685	93,386	0.75	199.40	0.01
	38	97,727	98,997	1.28	17.76	0.01
	39	98,465	98,477	0.01	48.02	0.01
	40	95,509	99,563	4.07	51.15	0.01
	average			2.27	94.50	0.02
12	41	99,004	102,985	3.87	138.18	0.02
	42	95,393	99,588	4.21	94.93	0.02
	43	95,428	96,940	1.56	316.49	0.02
	44	100,728	102,010	1.26	4005.74	0.02
	45	92,420	93,997	1.68	394.93	0.02
	46	96,613	98,264	1.68	895.34	0.02
	47	96,676	101,203	4.47	167.93	0.02
	48	92,614	93,242	0.67	486.23	0.01
	49	91,582	92,525	1.02	575.96	0.01
	50	92,176	94,345	2.30	525.38	0.02
	average			2.30	760.11	0.02
14	51	115,364	119,444	3.42	8736.24	0.02
	52	111,140	113,723	2.27	>15,000 ‡	0.02
	53	117,477	118,300	0.70	>15,000 ‡	0.02
	54	110,723	113,863	2.76	12,163.61	0.01
	55	112,605	117,975	4.55	4699.99	0.02
	56	115,180	116,935	1.50	>15,000 ‡	0.01
	57	119,450	123,219	3.06	>15,000 ‡	0.02
	58	123,667	127,613	3.09	8910.81	0.02
	59	114,046	116,018	1.70	>15,000 ‡	0.01
	60	115,386	118,936	2.98	>15,000 ‡	0.02
	average			2.60	12,451.06 #	0.02
overall				2.39	4435.22 #	0.02

^† percentage error of the heuristic solution from the solution (or the best feasible solution in case where CPLEX could not solve the instance to optimality) obtained with CPLEX; ^‡ This shows that CPLEX could not solve the instance to optimality in 15,000 s. ^# This is a lower bound on the computation time.

and

Table 3. Results of the test on 10-period instances.

I	Instances	Solutions			CPU Time (s)
		CPLEX	Heuristic	PE (%) †	CPLEX	Heuristic
10	61	169,759	173,114	1.94	173.61	0.03
	62	155,805	158,119	1.46	9513.37	0.03
	63	167,030	169,765	1.61	12,856.51	0.02
	64	165,533	165,721	0.11	>15,000 ‡	0.02
	65	166,244	170,480	2.48	11,773.90	0.02
	66	165,533	167,651	1.26	>15,000 ‡	0.02
	67	160,947	167,575	3.96	3900.53	0.26
	68	152,001	153,545	1.01	433.19	0.03
	69	164,455	168,434	2.36	543.02	0.02
	70	164,631	168,660	2.39	4205.11	0.02
	average			1.49	10,719.57	0.03
12	71	167,634	169,971	1.37	10,465.67	0.02
	72	171,343	175,637	2.44	>15,000 ‡	0.02
	73	156,004	161,773	3.57	>15,000 ‡	0.02
	74	165,812	170,245	2.60	5367.22	0.02
	75	160,362	165,337	3.01	>15,000 ‡	0.02
	76	174,292	178,776	2.51	>15,000 ‡	0.02
	77	162,923	166,636	2.23	>15,000 ‡	0.02
	78	160,262	162,809	1.56	3284.66	0.02
	79	165,380	166,674	0.78	>15,000 ‡	0.12
	80	177,514	181,282	2.08	5342.69	0.02
	average			2.22	11786.71	0.03
14	81	143,200	146,261	2.09	2292.85	0.03
	82	148,173	150,786	1.73	>15,000 ‡	0.03
	83	140,813	144,716	2.70	>15,000 ‡	0.02
	84	144,862	149,986	3.42	>15,000 ‡	0.02
	85	143,006	145,343	1.61	2278.75	0.03
	86	136,539	140,606	2.89	>15,000 ‡	0.02
	87	144,260	149,363	3.42	>15,000 ‡	0.02
	88	140,587	144,633	2.80	>15,000 ‡	0.02
	89	138,474	142,013	2.49	14,701.13	0.02
	90	145,716	146,730	0.69	>15,000 ‡	0.03
	average			2.38	11,927.26 #	0.02
overall				2.03	11,477.85 #	0.03

^{†, ‡, #} See the footnotes of Table 2.

, which show solution values of the heuristic and CPLEX, CPU times, and percentage errors of the heuristic solutions from the solutions (or lower bounds) obtained by CPLEX. As can be seen from Table 1, for only 4 instances (with ten suppliers) out of 30 instances, the percentage errors were larger than 4%. Table 2 and Table 3 show similar results for larger instances. These results demonstrate the performance of the suggested heuristic algorithm that can give reasonably good solutions regardless of the length of the planning horizon. Additionally, the heuristic shows almost the same performance regardless of the number of the suppliers. The overall average percentage error (PE, %) of the 90 instances was 2.43%. Figure 1 shows the summary of the results of percentage errors according to different number of periods and suppliers. As shown in the figure, we could not find significant correlation between problem size and the percentage error.

For the 6-period instances, CPLEX required 15.31 s on average, while the suggested heuristic required only 0.01 s. In these instances, CPU time for both methods may look reasonable. However, as the length of the planning horizon increased, CPU times for CPLEX increased significantly, longer than one hour. On the other hand, the suggested heuristic found good solutions in a very short time. In the 10-period instances, which reflect practical situations, many instances failed to give an optimal solution by CPLEX within the time limit (15,000 s). In fact, we performed tests on instances of larger sizes (I > 14, T > 10), but none of these instances were solved by CPLEX within the time limit. In real situations, in which demand forecasts may be changed frequently, the problem may have to be solved accordingly, and even one hour for the solution of the planning problem may be considered too long.

In real situations in poultry farming companies, they have to establish a weekly production plan within one or two hours, but it may be required to modify or re-make due to changed forecast values. Therefore, the heuristic algorithm can be effectively used for such situations, because it gives reasonably good solutions within a very short computation time. Additionally, for longer-term planning with T > 10, which a company needs to prepare for demand fluctuations, the suggested heuristic may be more appropriate than CPLEX. Moreover, the results or solutions for the problem can be used for managerial decision by evaluating efficiency of the supply chain with selected production line. For example, if the production quantity is smaller than demand, they can change the production line of suppliers. On the other hands, if the production quantity is larger than demand, the company can reduce the number of suppliers to be operated. In other words, the proposed heuristic can also be used for design of the supply chain.

5. Discussion and Conclusions

This study investigated a planning problem for production in a two-level supply chain in which there are multiple suppliers with different capacity levels and a single manufacturing plant with dynamic demands for production-time-dependent products. This problem is to select suppliers to produce semi-finished products and to determine production quantities to be produced at the determined suppliers, in each period during the planning horizon. For the problem, a mixed integer programming model is provided, and a heuristic algorithm is also suggested to obtain good solutions quickly. In the heuristic, the problem is solved in two steps, selection of suppliers to be operated and their production line and then determination of production quantities at the suppliers. The two decisions are made sequentially with a heuristic method and a commercial LP solver.

This study can be the basis for research on production management of poultry and livestock industries. In addition, the study is highly expandable because the characteristics of production-time dependent can be found in various fields such as steel, fermented food, liquor, and chemical industries. This research can be extended in several ways. Since this study is the first attempt to consider a problem dealt with a design of supply chain and a production planning for the production-time-dependent products simultaneously, the considered model can be applied to a supply chain with similar characteristics. In addition, one may need to case involving determination of the locations of suppliers and manufacturing plants to design a supply chain. Also, research on the problem of limited capacity of the manufacturer can be studied and applied to various industries. Then, in the future, we can consider the problem in which the manufacturer and suppliers are not under the control of the one company unit.