# Fix-and-Optimize and Variable Neighborhood Search Approaches for Stochastic Multi-Item Capacitated Lot-Sizing Problems

Authors: Liuxi Li; Shiji Song; Cheng Wu; Rui Wang
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

We discuss stochastic multi-item capacitated lot-sizing problems with and without setup carryovers (also known as link lot size), S-MICLSP and S-MICLSP-L. The two models are motivated from a real-world steel enterprise. To overcome the nonlinearity of the models, a piecewise linear approximation method is proposed. We develop a new fix-and-optimize (FO) approach to solve the approximated models. Compared with the existing FO approach(es), our FO is based on the concept of “k-degree-connection” for decomposing the problems. Furthermore, we also propose an integrative approach combining our FO and variable neighborhood search (FO-VNS), which can improve the solution quality of our FO approach by diversifying the search space. Numerical experiments are performed on the instances following the nature of realistic steel products. Our approximation method is shown to be efficient. The results also show that the proposed FO and FO-VNS approaches significantly outperform the recent FO approaches, and the FO-VNS approaches can be more outstanding on the solution quality with moderate computational effort.


---

## Body

## 1. Introduction

The stochastic multi-item capacitated lot-sizing problem (S-MICLSP) and its setup carryover extension (also known as linked lot size extension, in [1], abbreviated to “-L” ), S-MICLSP-L, are designed to map an industrial optimization problem in a realistic steel enterprise. The problem setting is as follows: there are several types of steel products. These products differ in various attributes: chemical composition (mixture), width, thickness, shape (bar, rod, tube, pipe, plate, sheet, etc.), microstructure (ferritic, pearlitic, martensitic, etc.), physical strength, and other attributes. Usually, each type of steel products should be used for only one particular purpose, and each purpose can be satisfied by one or several steel products. Hence, in this steel enterprise, a typical production schedule is made based on the need of one particular purpose, rather than the need of one particular customer. There are two categories of production scheduling, solid scheduling and flexible scheduling, applied in different factories in this steel enterprise. The solid one schedules all types of products simultaneously with a high frequency of restarting production states, while the flexible one schedules parts of the types simultaneously with a low frequency of restarting production states. All of the production schedules are made before the whole planning horizon. The problems with these settings can be suitably mapped to S-MICLSP and S-MICLSP-L.Both S-MICLSP and S-MICLSP-L are stochastic generalizations of the capacitated lot-sizing problems (CLSP, see [2]) and they consider backlogging and setup carryovers jointly. The deterministic CLSPs with backlogging or setup carryovers individually have been tackled by various models in the literature. We refer the interested readers to [3, 4] for the most recent review on CLSPs. For the lot-sizing problems considering backlogging and setup carryovers jointly, models were treated in [5–7]. Their problem formulations were similar to [8], who first solved problems with setup carryovers. All of the above studies focused on how to solve the lot-sizing problems by designing heuristics. As the authors highlighted, although there is a significant amount of research literature on CLSPs, the literature on problems that consider backlogging and setup carryover jointly is rather scarce.In this paper, we assume that demand is continuously stochastic which can cover majority of demand environment. Due to the model uncertainty, approximation methods are applied to reformulate the lot-sizing models for performing deterministic mixed integer programming (MIP) in the literature. Haugen et al. [9] generated subproblems for each scenario solved heuristically to capture the nature of demand uncertainty and specify a reasonable number of representative scenarios. Brandimarte [10] modeled the demand uncertainty through generating scenario trees. They made the generated scenario trees match the first, second, third, and fourth moments of the given distribution. The scenario method or scenario-generated method can also be found in [11–14]. Almost all approximation methods for lot-sizing problems are scenario methods. Nevertheless, Mietzner and Reger [15] stated the advantages and disadvantages of scenario methods. One of the crucial disadvantages is as follows: to capture more properties of the uncertainty, the approximated models should ensure an adequate number of scenarios, but the practice of scenario methods can be very time-consuming. This leads to the contradiction between computational time and approximation accuracy. In the following part, we will propose our approximation method to overcome this drawback.Since the approximated models can perform deterministic MIP, the methods used for deterministic CLSP and its extensions can be also applied to the approximated models. Historically, exact methods (branch & bound technique, Lagrangian relaxation, cut-generation technique, etc.) and metaheuristics (genetic algorithm, particle swarm optimization, tabu search, etc.) are adopted in the deterministic lot-sizing models. We refer interested readers to [16] for further review. Recently, MIP-based heuristics are developed to solve lot-sizing models since they combine the advantages of exact methods and (meta-)heuristics. An MIP-based heuristic shown to be outstanding is called fix-and-optimize (FO) approach, which is proposed by Sahling et al. [17]. The authors presented three types of decomposition method: product decomposition, resource decomposition, and time periods decomposition. Based on the work of [17], variants of FO are developed by [18–20]. However, all of the variants follow the decomposition framework of [17].Although FO exhibits its efficiency and effectiveness in the literature, it follows a prespecified trajectory and hence it is a local search method. This may result in low solution quality. To enhance the search space of FO approach, one can apply variable neighborhood search (VNS) proposed by [21]. VNS is a metaheuristic which involves two key steps. The first key step is using a local search method to obtain local optimum and the second is systematically changing the neighborhood structure of each local search. Unlike other metaheuristics, VNS does not follow a prespecified trajectory but explores increasingly distant neighborhoods of the current incumbent solution. Since VNS can enhance the search space, many integrative frameworks with VNS are proposed to solve lot-sizing problems. Hindi et al. [22] proposed an integrative Lagrangian relaxation- (LR-) VNS framework for the CLSP with setup times and got good feasible solutions. Zhao et al. [23] and Seeanner et al. [24] developed another type of VNS, the so-called variable neighborhood decomposition search (VNDS) to solve multilevel lot-sizing problems, and provided promising computational results. All of the above studies throw light upon solving lot-sizing problems by combining VNS.Newly, Chen [25] proposed an excellent integrative framework combining FO and VNS for deterministic lot-sizing problems. Since our models have“many-to-one” demand structure, his framework cannot be applied to our models. However, motivated from his work, we propose our FO and integrative FO-VNS for our stochastic lot-sizing problems. Compared with the work of [25], our proposed FO allows capacity-infeasible (overtime cost is not zero) solutions and can be applied to“many-to-one” demand structure, while he prohibited capacity-infeasible solutions and his framework was only valid for one-to-one demand structure. Thus, we apply the integrative framework to models without setup carryovers, S-MICLSP, and successfully extend it to our setup carryovers version, S-MICLSP-L, while Chen [25] only applied his framework to models without setup carryovers.In this paper, we follow a similar analytical procedure of solving stochastic lot-sizing problems to the reviewed literature. However, despite the above, our paper demonstrates other unique characteristics which distinguish from the existing related literature as follows:(1)
Derived from realistic industrial problems, we formulate S-MICLSP and S-MICLSP-L models considering backlogging, production overtime, and initial inventory at the same time, which is much more complicated than the existing models in the literature.(2)
We propose a piecewise linear method to approximate S-MICLSP and S-MICLSP-L models. This method is simple and easy-to-implement, providing a good trade-off between computational time and approximation accuracy. This method overcomes the drawback of scenarios generating on the computational end.(3)
A new FO approach is proposed for our approximated models. Differing from the decomposition framework of [17], this approach decomposes the main problem based on the combined information of products, resources, demands, and time periods.(4)
An integrative VNS heuristic which uses FO as the local search engine is proposed to solve our approximated models. This combined approach is running on a specially designed neighborhood structure.The outline of this paper is structured as follows: we formulate our S-MICLSP and S-MICLSP-L models and propose our piecewise linear approximation method in Section2. Our proposed FO approach and combined method (FO-VNS) are described in Sections 3 and 4. Numerical experiments of the two approaches on instances generated from a realistic case are presented in Section 5. In Section 6, the concluding remarks as well as discussions on future research are provided. The generating method is lengthy and is relegated to Appendix.


## 2. Models Formulation and Approximation

In this section, we first formulate S-MICLSP and S-MICLSP-L models. To overcome the nonlinearity and intractability of the models, we then propose a piecewise linear approximation method to reformulate the models. These approximated models are deterministic and hence can be tractably solved by our following proposed algorithms.


### 2.1. Model Description

In our models, demands have noone-to-one correspondence to products. Demands can be satisfied by multiple products and categorized into different classes by the purposes. We can use the term “demand class” to describe one demand for purpose. The term “demand class” can help readers recognize the unique structure of demands in our models. But to avoid ambiguity, we equate the term “demand” to the term “demand class” and use “demand” mostly in the context. For detailed description, we make additional assumptions as follows:(i)
General capacitated lot-sizing problems assumptions:
(a)
lot-sizing for multiple products(b)
finite time of planning horizon(c)
initial inventories(d)
capacitated production resource(e)
decision before planning horizon(ii)
Demands assumptions:
(a)
continuously randomized on a known distribution with a finite support, independent, and identically distributed from period to period for each demand (class)(b)
many-to-one structure: each product can only satisfy one demand (class), while each demand (class) can be satisfied by multiple products(iii)
Big-bucket assumption (see [26]):
(a)
permit the production of multiple products during a single period(iv)
Linked lot sizes assumption (see [1]):
(a)
the setup state of a resource to be carried over from the current period to the next period(v)
Other assumptions:
(a)
overtime production and backlogging setting are allowed, with high penalty costs.(b)
no lead times(c)
expected cost minimization objective(d)
continuous variables for lot sizesNote that the overtime production is allowed since the requirement of flexibility. This assumption is often used in practice if no feasible production plan could be found otherwise the following two facts: one is the production capacity limits are frequently “soft” as machines could run longer than the planned daily operating time, the other one is the total volume of production could be increased slightly if machines could run below their technical limits by default.Using the symbols given in Notations, the S-MICLSP can be formulated as given below.(1)min∑t∈T∑i∈PfiXit+piQit+hiEIit+∑j∈DbjEBjt+∑r∈RocrOrtsubject to constraints(2)Iit=Ii,t-1+Qit-∑j∈DiSijt,i∈P,t=1,…,T,(3)Bjt=∑i∈PjSijteij-Djt-Bj,t-1-,Bj0=0,j∈D,t=1,…,T,(4)∑j∈DiSijt⩽Qit+Ii,t-1,i∈P,t=1,…,T,(5)∑i∈PrciQit+stiXit⩽kr+Ort,r∈R,t=1,…,T,(6)ciQit⩽miXit,i∈P,t=1,…,T,(7)Sijt,Qit,Ort⩾0,i∈P,j∈Di,r∈R,t=1,…,T,(8)Xit∈0,1,i∈P,t=1,…,T.The objective function (1) to be minimized is the sum of setup costs, production costs, inventory holding costs, backlogging penalty costs, and overtime costs. Constraints (2) and (3) are the inventory-balanced equations that each demand (class) can be satisfied by multiple products. Additionally, constraints (4) imply that the quantity of one product used to fulfill one demand (class) should not exceed the sum of inventory and production quantity. Constraints (5) give the capacity constraint of each resource in each period with overtime. Constraints (6) are the coupling constraints linking each production variable Qit with its corresponding setup variables Xit, where the choice of each large positive number mi must not limit any feasible production quantity of product i in period t. The coupling constraints imply that Qit=0 if Xit=0 for all i and t. The nonnegative real or binary nature of each variable in the model is indicated by constraints (7) and (8).The S-MICLSP-L allows the setup state of each resource to be carried over from the current period to the next period. To formulate the S-MICLSP-L, additional binary variables indicating setup carryovers and additional constraints linking the setup state variables with the setup carryover variables are required. We adopt the formulation of [27] with overtime. Additional variables can also be found in Notations. The S-MICLSP-L can be formulated as given below.(9)min∑t∈T∑i∈PfiXit-Zit+piQit+hiEIit+∑j∈DbjEBjt+∑r∈RocrOrtsubject to constraints (2)~(4), (6)~(8), and constraints(10)∑i∈PrciQit+stiXit-Zit⩽kr+Ort,r∈R,t=1,…,T,(11)∑i∈PrZit⩽1,r∈R,t=1,…,T,(12)Zit⩽Xit,Zit⩽Xi,t-1,i∈P,t=1,…,T,(13)Pr2-Zit-Zi,t+1+1⩾∑i′∈PrXi′t,i∈Pr,t=1,…,T,(14)Zit∈0,1,Zi1=0,i∈P,t=1,…,T.Constraints (10) are similar to constraints (5). Constraints (11) imply that, in each period, the setup carryover of a resource is possible only for at most one product. Constraints (12) indicate that the setup carryover of a resource for product i occurs in period t only if the resource is set up for the item in both periods t-1 and t. Constraints (13) indicate multiperiod setup carryovers. Constraints (14) specify the binary nature of setup carryover variables.


### 2.2. Piecewise Linear Approximation

BothE[Iit] and E[Bjt] in S-MICLSP and S-MICLSP-L models are nonlinear stochastic functions. We have specified the continuous nature of demand uncertainty. Thus it is intractable to solve these models. We could apply scenario method to approximate the models. However, we have discussed in Section 1 that the computational efforts can be unacceptable and the precision of approximation can be low. Fortunately, it is possible to replace the functions of E[Iit] and E[Bjt] by suitably chosen piecewise linear functions. The functions of E[Iit] and E[Bjt] can be approximated as follows. Let qjt denote the total amount available to fill the cumulated demand j from period 1 to period t (cumulated quantity produced up to period t plus initial inventory in period 1). Let yjt denote the cumulated demand from period 1 up to period t and let fyjt denote the associated density function. Denote E[Ijt](qjt) the expected physical inventory on hand at the end of period t for demand j corresponding to qjt. Then consequently E[Ijt](qjt) is equal to(15)EIjtqjt=∫0qjtqjt-yjt·fyjtyjtdyjt=qjt-Eyjt+∫qjt∞yjt-qjt·fyjtyjtdyjt=qjt-Eyjt+Pyjtqjt,where Pyjt(qjt) is the well-known expected loss function or the failure function of the random variable yjt with respect to the quantity qjt. Figure 1 illustrates the function Pyjt(qjt).Figure 1
Illustration of piecewise linear approximation forPyjt(qjt) with segments number L=3.A backlog of demandj occurs at the end of period t, if the cumulated demand up to period t, yjt, is greater than the cumulated production quantity up to period t, qjt. Hence the expected backlog of demand j at the end of period t, denoted by E[Ijtend](qjt), is(16)EIjtendqjt=∫qjt∞yjt-qjt·fyjtyjtdyjt=Pyjtqjt.Consider the backlog just after production but before demand occurrence in period t. This backlog cannot be affected by demand since demand does not occur. Hence the expected backlog just after production but before demand occurrence of demand j corresponding to qjt in period t, denoted by E[Ijtprod](qjt), is(17)EIjtprodqjt=∫qjt∞yj,t-1-qjt·fyj,t-1yj,t-1dyj,t-1=Pyj,t-1qjt.The expected backlog number of demand j in period t can be expressed as the difference between the backlog at the end of period t and the expected backlog just after production but before demand occurrence of period t.(18)EBjtqjt=EIjtend-EIjtprod=Pyjtqjt-Pyj,t-1qjt.Define L line segments with interval limits ujtl for demand j that mark the cumulated production up to period t. Let ujt0 be the lower limit of the relevant region for demand j. Accordingly, the slope of the inventory on hand function for the line segment l is(19)aIjtl=EIjtujtl-EIjtujtl-1ujtl-ujtl-1=ujtl-Eyjt+Pyjtujtl-ujtl-1-Eyjt+Pyjtujtl-1ujtl-ujtl-1=ujtl+Pyjtujtl-ujtl-1+Pyjtujtl-1ujtl-ujtl-1.Similar to the above calculation, the nonlinear function of backlogging in period t can be approximated, whereby the slope can be calculated as(20)aBjtl=Pyjtujtl-Pyj,t-1ujtl-Pyjtujtl-1-Pyj,t-1ujtl-1ujtl-ujtl-1.Both aIjtl and aBjtl are calculated from the function Pyjt(qjt) when L segments are defined (see Figure 1). Once slope values of expected inventories and backlogging can be found from the distribution of the random variable yjt,j∈D,t∈T, we can approximate the original model in the following. Let wijtl be the production quantity of product i for demand j in period t associated with interval l. As Pyjt(x) is convex, ∑i∈Pjwijtl/eij⩽ujtl-ujtl-1 should be satisfied. Also, q^ijt=∑l=1Lwijtl is the cumulated production quantity of product i for demand j up to period t and qijt=q^ijt-q^ij,t-1 (see Figure 1). Thus constraints (2)~(4) can be rewritten. We introduce the slope values into the model. Let aIjt0 be the expected inventory and aBjt0 be the expected backlogging at point ujt0. In that sense, the physical inventory of product i in period t can be approximated as E[Iit]≈∑j∈DiaIjt0+∑l=1LaIjtlwijtl, and the backlog number can be approximated as E[Bjt]≈∑i∈PjaBjt0+∑l=1LaBjtlwijtl/eij. All the additional symbols in this section are listed in Notations. The following linear approximated S-MICLSP is obtained:(21)min∑t∈T∑i∈PfiXit+pi∑j∈Diqijt+∑i∈Phi·∑j∈DiaIjt0+∑l=1LaIjtlwijtl+∑j∈Dbj·∑i∈PjaBjt0+∑l=1LaBjtlwijtleij+∑r∈RocrOrtsubject to constraints (8) and constraints(22)∑l=1Lwij,t-1l⩽∑l=1Lwijtl,j∈D,i∈Pj,t=2,…,T,(23)∑i∈Pjwijtleij⩽ujtl-ujtl-1,j∈D,l=1,…,L,t=1,…,T,(24)∑l=1Lwijtl-∑l=1Lwij,t-1l=qijt,j∈D,i∈Pj,t=1,…,T,(25)∑i∈Prci∑j∈Diqijt+stiXit⩽kr+Ort,r∈R,t=1,…,T,(26)ci∑j∈Diqijt⩽miXit,i∈P,t=1,…,T,(27)Ort,wijtl⩾0,j∈D,i∈Pj,l=1,…,L,r∈R,t=1,…,T.Constraints (22)~(24) are approximated constraints of (2)~(4) by piecewise linear approximation. Constraints (25)~(27) are similar to constraints (5)~(7).The linear approximated S-MICLSP-L is as follows:(28)min∑t∈T∑i∈PfiXit-Zit+pi∑j∈Diqijt+∑i∈Phi·∑j∈DiaIjt0+∑l=1LaIjtlwijtl+∑j∈Dbj·∑i∈PjaBjt0+∑l=1LaBjtlwijtleij+∑r∈RocrOrtsubject to constraints (22)~(24), (26)~(27), (8), and (11)~(14) and constraints(29)∑i∈Prci∑j∈Diqijt+stiXit-Zit⩽kr+Ort,r∈R,t=1,…,T.Constraints (29) are similar to constraints (25).Models (21) and (28) are both deterministic models; hence these models can be tractably solved by our next proposed algorithms.


## 2.1. Model Description

In our models, demands have noone-to-one correspondence to products. Demands can be satisfied by multiple products and categorized into different classes by the purposes. We can use the term “demand class” to describe one demand for purpose. The term “demand class” can help readers recognize the unique structure of demands in our models. But to avoid ambiguity, we equate the term “demand” to the term “demand class” and use “demand” mostly in the context. For detailed description, we make additional assumptions as follows:(i)
General capacitated lot-sizing problems assumptions:
(a)
lot-sizing for multiple products(b)
finite time of planning horizon(c)
initial inventories(d)
capacitated production resource(e)
decision before planning horizon(ii)
Demands assumptions:
(a)
continuously randomized on a known distribution with a finite support, independent, and identically distributed from period to period for each demand (class)(b)
many-to-one structure: each product can only satisfy one demand (class), while each demand (class) can be satisfied by multiple products(iii)
Big-bucket assumption (see [26]):
(a)
permit the production of multiple products during a single period(iv)
Linked lot sizes assumption (see [1]):
(a)
the setup state of a resource to be carried over from the current period to the next period(v)
Other assumptions:
(a)
overtime production and backlogging setting are allowed, with high penalty costs.(b)
no lead times(c)
expected cost minimization objective(d)
continuous variables for lot sizesNote that the overtime production is allowed since the requirement of flexibility. This assumption is often used in practice if no feasible production plan could be found otherwise the following two facts: one is the production capacity limits are frequently “soft” as machines could run longer than the planned daily operating time, the other one is the total volume of production could be increased slightly if machines could run below their technical limits by default.Using the symbols given in Notations, the S-MICLSP can be formulated as given below.(1)min∑t∈T∑i∈PfiXit+piQit+hiEIit+∑j∈DbjEBjt+∑r∈RocrOrtsubject to constraints(2)Iit=Ii,t-1+Qit-∑j∈DiSijt,i∈P,t=1,…,T,(3)Bjt=∑i∈PjSijteij-Djt-Bj,t-1-,Bj0=0,j∈D,t=1,…,T,(4)∑j∈DiSijt⩽Qit+Ii,t-1,i∈P,t=1,…,T,(5)∑i∈PrciQit+stiXit⩽kr+Ort,r∈R,t=1,…,T,(6)ciQit⩽miXit,i∈P,t=1,…,T,(7)Sijt,Qit,Ort⩾0,i∈P,j∈Di,r∈R,t=1,…,T,(8)Xit∈0,1,i∈P,t=1,…,T.The objective function (1) to be minimized is the sum of setup costs, production costs, inventory holding costs, backlogging penalty costs, and overtime costs. Constraints (2) and (3) are the inventory-balanced equations that each demand (class) can be satisfied by multiple products. Additionally, constraints (4) imply that the quantity of one product used to fulfill one demand (class) should not exceed the sum of inventory and production quantity. Constraints (5) give the capacity constraint of each resource in each period with overtime. Constraints (6) are the coupling constraints linking each production variable Qit with its corresponding setup variables Xit, where the choice of each large positive number mi must not limit any feasible production quantity of product i in period t. The coupling constraints imply that Qit=0 if Xit=0 for all i and t. The nonnegative real or binary nature of each variable in the model is indicated by constraints (7) and (8).The S-MICLSP-L allows the setup state of each resource to be carried over from the current period to the next period. To formulate the S-MICLSP-L, additional binary variables indicating setup carryovers and additional constraints linking the setup state variables with the setup carryover variables are required. We adopt the formulation of [27] with overtime. Additional variables can also be found in Notations. The S-MICLSP-L can be formulated as given below.(9)min∑t∈T∑i∈PfiXit-Zit+piQit+hiEIit+∑j∈DbjEBjt+∑r∈RocrOrtsubject to constraints (2)~(4), (6)~(8), and constraints(10)∑i∈PrciQit+stiXit-Zit⩽kr+Ort,r∈R,t=1,…,T,(11)∑i∈PrZit⩽1,r∈R,t=1,…,T,(12)Zit⩽Xit,Zit⩽Xi,t-1,i∈P,t=1,…,T,(13)Pr2-Zit-Zi,t+1+1⩾∑i′∈PrXi′t,i∈Pr,t=1,…,T,(14)Zit∈0,1,Zi1=0,i∈P,t=1,…,T.Constraints (10) are similar to constraints (5). Constraints (11) imply that, in each period, the setup carryover of a resource is possible only for at most one product. Constraints (12) indicate that the setup carryover of a resource for product i occurs in period t only if the resource is set up for the item in both periods t-1 and t. Constraints (13) indicate multiperiod setup carryovers. Constraints (14) specify the binary nature of setup carryover variables.


## 2.2. Piecewise Linear Approximation

BothE[Iit] and E[Bjt] in S-MICLSP and S-MICLSP-L models are nonlinear stochastic functions. We have specified the continuous nature of demand uncertainty. Thus it is intractable to solve these models. We could apply scenario method to approximate the models. However, we have discussed in Section 1 that the computational efforts can be unacceptable and the precision of approximation can be low. Fortunately, it is possible to replace the functions of E[Iit] and E[Bjt] by suitably chosen piecewise linear functions. The functions of E[Iit] and E[Bjt] can be approximated as follows. Let qjt denote the total amount available to fill the cumulated demand j from period 1 to period t (cumulated quantity produced up to period t plus initial inventory in period 1). Let yjt denote the cumulated demand from period 1 up to period t and let fyjt denote the associated density function. Denote E[Ijt](qjt) the expected physical inventory on hand at the end of period t for demand j corresponding to qjt. Then consequently E[Ijt](qjt) is equal to(15)EIjtqjt=∫0qjtqjt-yjt·fyjtyjtdyjt=qjt-Eyjt+∫qjt∞yjt-qjt·fyjtyjtdyjt=qjt-Eyjt+Pyjtqjt,where Pyjt(qjt) is the well-known expected loss function or the failure function of the random variable yjt with respect to the quantity qjt. Figure 1 illustrates the function Pyjt(qjt).Figure 1
Illustration of piecewise linear approximation forPyjt(qjt) with segments number L=3.A backlog of demandj occurs at the end of period t, if the cumulated demand up to period t, yjt, is greater than the cumulated production quantity up to period t, qjt. Hence the expected backlog of demand j at the end of period t, denoted by E[Ijtend](qjt), is(16)EIjtendqjt=∫qjt∞yjt-qjt·fyjtyjtdyjt=Pyjtqjt.Consider the backlog just after production but before demand occurrence in period t. This backlog cannot be affected by demand since demand does not occur. Hence the expected backlog just after production but before demand occurrence of demand j corresponding to qjt in period t, denoted by E[Ijtprod](qjt), is(17)EIjtprodqjt=∫qjt∞yj,t-1-qjt·fyj,t-1yj,t-1dyj,t-1=Pyj,t-1qjt.The expected backlog number of demand j in period t can be expressed as the difference between the backlog at the end of period t and the expected backlog just after production but before demand occurrence of period t.(18)EBjtqjt=EIjtend-EIjtprod=Pyjtqjt-Pyj,t-1qjt.Define L line segments with interval limits ujtl for demand j that mark the cumulated production up to period t. Let ujt0 be the lower limit of the relevant region for demand j. Accordingly, the slope of the inventory on hand function for the line segment l is(19)aIjtl=EIjtujtl-EIjtujtl-1ujtl-ujtl-1=ujtl-Eyjt+Pyjtujtl-ujtl-1-Eyjt+Pyjtujtl-1ujtl-ujtl-1=ujtl+Pyjtujtl-ujtl-1+Pyjtujtl-1ujtl-ujtl-1.Similar to the above calculation, the nonlinear function of backlogging in period t can be approximated, whereby the slope can be calculated as(20)aBjtl=Pyjtujtl-Pyj,t-1ujtl-Pyjtujtl-1-Pyj,t-1ujtl-1ujtl-ujtl-1.Both aIjtl and aBjtl are calculated from the function Pyjt(qjt) when L segments are defined (see Figure 1). Once slope values of expected inventories and backlogging can be found from the distribution of the random variable yjt,j∈D,t∈T, we can approximate the original model in the following. Let wijtl be the production quantity of product i for demand j in period t associated with interval l. As Pyjt(x) is convex, ∑i∈Pjwijtl/eij⩽ujtl-ujtl-1 should be satisfied. Also, q^ijt=∑l=1Lwijtl is the cumulated production quantity of product i for demand j up to period t and qijt=q^ijt-q^ij,t-1 (see Figure 1). Thus constraints (2)~(4) can be rewritten. We introduce the slope values into the model. Let aIjt0 be the expected inventory and aBjt0 be the expected backlogging at point ujt0. In that sense, the physical inventory of product i in period t can be approximated as E[Iit]≈∑j∈DiaIjt0+∑l=1LaIjtlwijtl, and the backlog number can be approximated as E[Bjt]≈∑i∈PjaBjt0+∑l=1LaBjtlwijtl/eij. All the additional symbols in this section are listed in Notations. The following linear approximated S-MICLSP is obtained:(21)min∑t∈T∑i∈PfiXit+pi∑j∈Diqijt+∑i∈Phi·∑j∈DiaIjt0+∑l=1LaIjtlwijtl+∑j∈Dbj·∑i∈PjaBjt0+∑l=1LaBjtlwijtleij+∑r∈RocrOrtsubject to constraints (8) and constraints(22)∑l=1Lwij,t-1l⩽∑l=1Lwijtl,j∈D,i∈Pj,t=2,…,T,(23)∑i∈Pjwijtleij⩽ujtl-ujtl-1,j∈D,l=1,…,L,t=1,…,T,(24)∑l=1Lwijtl-∑l=1Lwij,t-1l=qijt,j∈D,i∈Pj,t=1,…,T,(25)∑i∈Prci∑j∈Diqijt+stiXit⩽kr+Ort,r∈R,t=1,…,T,(26)ci∑j∈Diqijt⩽miXit,i∈P,t=1,…,T,(27)Ort,wijtl⩾0,j∈D,i∈Pj,l=1,…,L,r∈R,t=1,…,T.Constraints (22)~(24) are approximated constraints of (2)~(4) by piecewise linear approximation. Constraints (25)~(27) are similar to constraints (5)~(7).The linear approximated S-MICLSP-L is as follows:(28)min∑t∈T∑i∈PfiXit-Zit+pi∑j∈Diqijt+∑i∈Phi·∑j∈DiaIjt0+∑l=1LaIjtlwijtl+∑j∈Dbj·∑i∈PjaBjt0+∑l=1LaBjtlwijtleij+∑r∈RocrOrtsubject to constraints (22)~(24), (26)~(27), (8), and (11)~(14) and constraints(29)∑i∈Prci∑j∈Diqijt+stiXit-Zit⩽kr+Ort,r∈R,t=1,…,T.Constraints (29) are similar to constraints (25).Models (21) and (28) are both deterministic models; hence these models can be tractably solved by our next proposed algorithms.


## 3. New Fix-and-Optimize (FO) Approach

In the FO approach of [17], a series of MIP subproblems is solved in each of which most of the binary setup variables are tentatively fixed to 0 or 1. Only a subset of binary variables of the original model is treated as decision variables and “optimized” by a run of an MIP solver. MIP subproblems are generated using three types of basic decompositions, product decomposition, resource decomposition, and time periods decomposition. The authors also proposed three more combined decomposition methods: (1) product decomposition first and then resource decomposition, (2) product decomposition first and then time periods decomposition, and (3) product decomposition first, then resource decomposition, and finally time periods decomposition. Figure 2 exemplifies the FO approach of product decomposition with 4 products. In this section, we will propose our FO approach, which differs from [17]. In the following, we first define the so-called “k-degree-connection” to combine the decision of resources, products, demands, and time periods. Then the subproblems of the fix-and-optimize approach can be redefined based on the concept “k-degree-connection” (as we have discussed before, our models have “many-to-one” demand structure; we need to state that, in the work of [25], a similar concept “Interrelatedness” is defined; however, his concept is for one-to-one demand structure and cannot be applied to our models). Finally, we present our FO approach for both the S-MICLSP and S-MICLSP-L models.Figure 2
Example of fix-and-optimize with product decomposition.


### 3.1. Definition of “k-Degree-Connection”

In S-MICLSP, the binary setup variables are closely connected to other decision variables. We can infer from constraints (26) that if the setup variable Xit is set to be zero, no production can be planned in this period. If the setup variable Xit is set to be one, the corresponding production qijt can be made. If the value of qijt changes, the value of qi,j,t-1 and qi,j,t+1 may also change due to constraints (24). The change of Xit may also cause the change of qi′,j,t, whereby Di′=Di=j, due to constraints (23). Similarly, the change of Xit may also cause the change of qi′′,j,t, whereby i,i′′∈Pr,r∈R, due to constraints (25).First we define “1-degree-connection.” Let Ω~={Xit∣i∈P,t∈T} denote the set of all binary setup variables. We say two setup variables Xit∈Ω~ and Xi′t′∈Ω~ have “1-degree-connection” or Xit is “1-degree-connected” to Xi′t′ if one of the following conditions holds:(1)
Period timet and period time t′ are consecutive; that is, i′=i and t′∈{t-1,t+1};(2)
Producti and i′ both satisfy demand j; that is, Di′=Di=j and t′=t;(3)
Producti and i′ are produced by the same resource r; that is, i,i′∈Pr and t′=t;then we can define the set of binary setup variables that are “1-degree-connected” to Xit, denoted by DC(Xit), as follows: (30)DCXit=Xi,t-1,Xit,Xi,t+1∪Xi′t∣Di′=Di=j∪Xi′t∣i,i′∈Pr.For any Xit∈S⊆Ω~, whereby S is a subset of all binary setup variables Ω~, the set of binary setup variables that are “1-degree-connected” to S, denoted by DC(S), is given by(31)DCS=Xi,t-1,Xit,Xi,t+1∪Xi′t∣Di′=Di=j∪Xi′t∣i,i′∈Pr∣Xit∈S.Now we can continue to define “2-degree-connection” based on “1-degree-connection.” We say two binary setup variables Xit and Xi′t′ have “2-degree-connection” or Xit is “2-degree-connected” to Xi′t′ if there exists a setup variable Xi1,t1∈Ω~ such that both Xit and Xi′t′ are “1-degree-connected” to Xi1,t1. Based on the previous definitions, “3-degree-connection,” “4-degree-connection”,…, “k-degree-connection” can be defined by induction. Then the sets DC2(Xit), DC3Xit,…,DCk(Xit) can be defined.Similar to “1-degree-connection”, we can define the set of binary setup variables that are “k-degree-connected” to S, denoted by DC(S), as follows: (32)DCkS=DCDCk-1S,k⩾1.Without ambiguity, we define “0-degree-connection” for completeness as follows, if two binary setup variables Xit and Xi′t′ are “0-degree-connected” or have “0-degree-connection” if and only if i′=i and t′=t. Hence, the definition of “k-degree-connection” is reflexive, transitive, and symmetric.


### 3.2. New FO Approach for S-MICLSP

Note that our FO approach solves a series of subproblems iteratively. The key to defining subproblems of our FO approach is to clarify whichXit should be reoptimized and which Xit should be fixed in each iteration. In the following, we apply the concept of “k-degree-connection” to decompose S-MICLSP and define subproblems of our FO approach. However, we also need some complementary definitions of “k-degree-connection.” Recall the set of all binary setup variables, Ω~={Xit∣i∈P,t∈T}. For any binary setup variable, Xit∈Ω~, we define the complement set of DCk(Xit) denoted by DC¯k(Xit)=Ω~∖DCk(Xit), which is the set of binary setup variables that are not “k-degree-connected” to Xit.The subproblems of levelk associated with Xit, denoted by SPitk, are simple and are defined in the following: DC¯k(Xit) is fixed and DCk(Xit) is reoptimized. In this definition, we need to point out k is a control parameter and the bigger the level k is, the more binary setup variables are reoptimized in the corresponding subproblem SPitk. Due to this reason, we limit the maximum number of k to 3 for each subproblem SPitk in the following numerical experiments of Section 5.To describe our FO approach, we denoteX¯={Xit,i∈P,t∈T} a setup plan or a setup solution of the model. Also, X¯ is called the values of all setup variables at a solution of the model. Note that our FO approach allows the capacity-infeasible solutions in each loop of solving subproblems, while Chen [25] only selected capacity-feasible solutions. We present the pseudocode of our FO approach in Algorithm 1.Algorithm 1:Fix-and-Optimize algorithm with parameters (k,n).
(1) Set an initial feasible solution of the model, Xit=1 for all i and t
(2) iter=0
(3) repeat
(4)  iter=iter+1
(5)  Choose a pair (i,t) from (N×T) randomly with the same probability for each element in N×T
(6)  Solve the subproblem SPitk: Fix DC¯k(X¯) and re-optimized DCk(X¯).
(7)  if the solution of SPitk, X¯SPitk has lower costs than the current solution X¯then
(8)   X¯=X¯SPitk
(9)   iter=0
(10)  end if
(11) untiliter⩾nNote that, from the pseudocode of Algorithm1, we only choose a pair (i,t) from N×T in each iteration. Hence, the number of possible subproblems is N×T, where N is the number of the items and T is the number of periods. The number of iterations, n, is another control parameter of the approach. Since N×T may be very big and it may be too time-consuming for the approach to terminate after N×T iterations, we need to take an appropriate n that is equal to or smaller than N×T in the numerical simulation.


### 3.3. New FO Approach for S-MICLSP-L

Before we propose the new FO approach for S-MICLSP-L, we need to define the “k-degree-connection” of the setup carryover variables Zit in a similar way and extend the scope of “k-degree-connection” of Xit. If Zit changes, it may cause the change of the setup carryover variable Zi′t, whereby Di′=Di=j. The change of Zit can also cause the change of the consecutive setup carryover variables Zi-1,t and Zi+1,t by the consecutive setup carryover constraints. From the resource constraints, we can infer that if Zit changes, Zi′t may change, whereby i,i′∈Pr.An observation shows thatZit is restricted by Xit. Conversely, if Zit changes, Xit may change according to the constraints of the model. The change of Zit can also influence Xi′,t and Xi′,t-1 whereby Di′=Di=j or i,i′∈Pr. Now we can define DCZ(Zit) (the subscript Z indicates the approach for S-MICLSP-L), the set of binary variables that are “1-degree-connected” to Zit, or the set of binary variables that have “1-degree-connection” with Zit as follows: (33)DCZZit=Zi,t-1,Zit,Zi,t+1∪Zi′t∣Di′=Di=j∪Zi′t∣i,i′∈Pr∪Xi,t-1,Xit∪Xi′,t-1,Xi′t∣Di′=Di=j∪Xi′,t-1,Xi′t∣i,i′∈Pr.The definition of “k-degree-connection” for Zit, DCZk(Zit) is similar. We say that Zit and Zi′t′ have “connection” or Zit is “connected” to Zi′t′ if there is a finite integer k⩾1 such that they are “k-degree-connected.”Respectively, we need to redefineDC(Xit) (we use another denotation DCZ(Xit) for S-MICLSP-L), the set of binary variables that is “1-degree-connected” to Xit, or the set of binary variables that have “1-degree-connection” with Xit as follows: (34)DCZXit=Xi,t-1,Xit,Xi,t+1∪Xi′t∣Di′=Di=j∪Xi′t∣i,i′∈Pr∪Zit,Zi,t+1∪Zi′t,Zi′,t+1∣Di′=Di=j∪Zi′t,Zi′,t+1∣i,i′∈Pr.With the “1-degree-connection” of Xit defined above, we can similarly derive the new definition of “k-degree-connection” for Xit as previously described. Based on the new definition of “k-degree-connection” for Xit, we can define the subproblems for S-MICLSP-L, with defining the fix binary variables set DC¯Z(Xit) and the reoptimized binary variables set DCZ(Xit), for any binary setup variable Xit or pair (i,t)∈N×T. The fix-and-optimize approach for S-MICLSP-L is the same as S-MICLSP, except that their definitions of DCZ(Xit) and DCZ(Zit) are different.


## 3.1. Definition of “k-Degree-Connection”

In S-MICLSP, the binary setup variables are closely connected to other decision variables. We can infer from constraints (26) that if the setup variable Xit is set to be zero, no production can be planned in this period. If the setup variable Xit is set to be one, the corresponding production qijt can be made. If the value of qijt changes, the value of qi,j,t-1 and qi,j,t+1 may also change due to constraints (24). The change of Xit may also cause the change of qi′,j,t, whereby Di′=Di=j, due to constraints (23). Similarly, the change of Xit may also cause the change of qi′′,j,t, whereby i,i′′∈Pr,r∈R, due to constraints (25).First we define “1-degree-connection.” Let Ω~={Xit∣i∈P,t∈T} denote the set of all binary setup variables. We say two setup variables Xit∈Ω~ and Xi′t′∈Ω~ have “1-degree-connection” or Xit is “1-degree-connected” to Xi′t′ if one of the following conditions holds:(1)
Period timet and period time t′ are consecutive; that is, i′=i and t′∈{t-1,t+1};(2)
Producti and i′ both satisfy demand j; that is, Di′=Di=j and t′=t;(3)
Producti and i′ are produced by the same resource r; that is, i,i′∈Pr and t′=t;then we can define the set of binary setup variables that are “1-degree-connected” to Xit, denoted by DC(Xit), as follows: (30)DCXit=Xi,t-1,Xit,Xi,t+1∪Xi′t∣Di′=Di=j∪Xi′t∣i,i′∈Pr.For any Xit∈S⊆Ω~, whereby S is a subset of all binary setup variables Ω~, the set of binary setup variables that are “1-degree-connected” to S, denoted by DC(S), is given by(31)DCS=Xi,t-1,Xit,Xi,t+1∪Xi′t∣Di′=Di=j∪Xi′t∣i,i′∈Pr∣Xit∈S.Now we can continue to define “2-degree-connection” based on “1-degree-connection.” We say two binary setup variables Xit and Xi′t′ have “2-degree-connection” or Xit is “2-degree-connected” to Xi′t′ if there exists a setup variable Xi1,t1∈Ω~ such that both Xit and Xi′t′ are “1-degree-connected” to Xi1,t1. Based on the previous definitions, “3-degree-connection,” “4-degree-connection”,…, “k-degree-connection” can be defined by induction. Then the sets DC2(Xit), DC3Xit,…,DCk(Xit) can be defined.Similar to “1-degree-connection”, we can define the set of binary setup variables that are “k-degree-connected” to S, denoted by DC(S), as follows: (32)DCkS=DCDCk-1S,k⩾1.Without ambiguity, we define “0-degree-connection” for completeness as follows, if two binary setup variables Xit and Xi′t′ are “0-degree-connected” or have “0-degree-connection” if and only if i′=i and t′=t. Hence, the definition of “k-degree-connection” is reflexive, transitive, and symmetric.


## 3.2. New FO Approach for S-MICLSP

Note that our FO approach solves a series of subproblems iteratively. The key to defining subproblems of our FO approach is to clarify whichXit should be reoptimized and which Xit should be fixed in each iteration. In the following, we apply the concept of “k-degree-connection” to decompose S-MICLSP and define subproblems of our FO approach. However, we also need some complementary definitions of “k-degree-connection.” Recall the set of all binary setup variables, Ω~={Xit∣i∈P,t∈T}. For any binary setup variable, Xit∈Ω~, we define the complement set of DCk(Xit) denoted by DC¯k(Xit)=Ω~∖DCk(Xit), which is the set of binary setup variables that are not “k-degree-connected” to Xit.The subproblems of levelk associated with Xit, denoted by SPitk, are simple and are defined in the following: DC¯k(Xit) is fixed and DCk(Xit) is reoptimized. In this definition, we need to point out k is a control parameter and the bigger the level k is, the more binary setup variables are reoptimized in the corresponding subproblem SPitk. Due to this reason, we limit the maximum number of k to 3 for each subproblem SPitk in the following numerical experiments of Section 5.To describe our FO approach, we denoteX¯={Xit,i∈P,t∈T} a setup plan or a setup solution of the model. Also, X¯ is called the values of all setup variables at a solution of the model. Note that our FO approach allows the capacity-infeasible solutions in each loop of solving subproblems, while Chen [25] only selected capacity-feasible solutions. We present the pseudocode of our FO approach in Algorithm 1.Algorithm 1:Fix-and-Optimize algorithm with parameters (k,n).
(1) Set an initial feasible solution of the model, Xit=1 for all i and t
(2) iter=0
(3) repeat
(4)  iter=iter+1
(5)  Choose a pair (i,t) from (N×T) randomly with the same probability for each element in N×T
(6)  Solve the subproblem SPitk: Fix DC¯k(X¯) and re-optimized DCk(X¯).
(7)  if the solution of SPitk, X¯SPitk has lower costs than the current solution X¯then
(8)   X¯=X¯SPitk
(9)   iter=0
(10)  end if
(11) untiliter⩾nNote that, from the pseudocode of Algorithm1, we only choose a pair (i,t) from N×T in each iteration. Hence, the number of possible subproblems is N×T, where N is the number of the items and T is the number of periods. The number of iterations, n, is another control parameter of the approach. Since N×T may be very big and it may be too time-consuming for the approach to terminate after N×T iterations, we need to take an appropriate n that is equal to or smaller than N×T in the numerical simulation.


## 3.3. New FO Approach for S-MICLSP-L

Before we propose the new FO approach for S-MICLSP-L, we need to define the “k-degree-connection” of the setup carryover variables Zit in a similar way and extend the scope of “k-degree-connection” of Xit. If Zit changes, it may cause the change of the setup carryover variable Zi′t, whereby Di′=Di=j. The change of Zit can also cause the change of the consecutive setup carryover variables Zi-1,t and Zi+1,t by the consecutive setup carryover constraints. From the resource constraints, we can infer that if Zit changes, Zi′t may change, whereby i,i′∈Pr.An observation shows thatZit is restricted by Xit. Conversely, if Zit changes, Xit may change according to the constraints of the model. The change of Zit can also influence Xi′,t and Xi′,t-1 whereby Di′=Di=j or i,i′∈Pr. Now we can define DCZ(Zit) (the subscript Z indicates the approach for S-MICLSP-L), the set of binary variables that are “1-degree-connected” to Zit, or the set of binary variables that have “1-degree-connection” with Zit as follows: (33)DCZZit=Zi,t-1,Zit,Zi,t+1∪Zi′t∣Di′=Di=j∪Zi′t∣i,i′∈Pr∪Xi,t-1,Xit∪Xi′,t-1,Xi′t∣Di′=Di=j∪Xi′,t-1,Xi′t∣i,i′∈Pr.The definition of “k-degree-connection” for Zit, DCZk(Zit) is similar. We say that Zit and Zi′t′ have “connection” or Zit is “connected” to Zi′t′ if there is a finite integer k⩾1 such that they are “k-degree-connected.”Respectively, we need to redefineDC(Xit) (we use another denotation DCZ(Xit) for S-MICLSP-L), the set of binary variables that is “1-degree-connected” to Xit, or the set of binary variables that have “1-degree-connection” with Xit as follows: (34)DCZXit=Xi,t-1,Xit,Xi,t+1∪Xi′t∣Di′=Di=j∪Xi′t∣i,i′∈Pr∪Zit,Zi,t+1∪Zi′t,Zi′,t+1∣Di′=Di=j∪Zi′t,Zi′,t+1∣i,i′∈Pr.With the “1-degree-connection” of Xit defined above, we can similarly derive the new definition of “k-degree-connection” for Xit as previously described. Based on the new definition of “k-degree-connection” for Xit, we can define the subproblems for S-MICLSP-L, with defining the fix binary variables set DC¯Z(Xit) and the reoptimized binary variables set DCZ(Xit), for any binary setup variable Xit or pair (i,t)∈N×T. The fix-and-optimize approach for S-MICLSP-L is the same as S-MICLSP, except that their definitions of DCZ(Xit) and DCZ(Zit) are different.


## 4. Integrative FO and Variable Neighborhood Search (VNS) Approach

We have stated that FO is a local method in Section1. Since the structure of the feasible-solution set defined by the concept “k-degree-connection” can be relatively large, the solution searched by the FO approach can only be a local optimum in most cases. In order to find a global optimum, or a solution close to the global optimum, Chen [25] proposed an excellent framework which integrates FO and VNS. In his paper, the integrative framework emphasized great performances comparing to his FO approach. In this section, we partly adopt the framework and propose our integrative FO-VNS approach for the S-MICLSP and S-MICLSP-L. The main novelty in contrast to [25] is that our FO-VNS can be extended to models with setup carryovers.


### 4.1. Integrative FO-VNS for S-MICLSP

To describe our FO-VNS approach, we will use symbols as shown in Notations. To integrate VNS with our FO approach, we need to predefine a finite set of neighborhood structuresGy(X¯), y=1,2,…,ymax, with G1(X¯)⊆G2(X¯)⊆⋯⊆Gymax(X¯), where y is the neighborhood index. Gy(X¯) can be defined as (35), where qy is an integer associated with neighborhood index y.(35)GyX¯=Xit,i∈P,t∈T∣∑i=1N∑t=1TXit1-X¯it+X¯it1-Xit⩽qy.We also define model S-MICLSP(X¯,qy,k), which is a linear relaxation model allowing 0⩽Xit⩽1 derived from the original model by adding constraint (35) to it, where k is the subproblem level described in Section 3. In the FO-VNS approach for S-MICLSP, we obtain the local optimum of S-MICLSP(X¯,qy,k) by applying our proposed FO approach in Section 3 aslocal search engine.To enhance the search space, we need to shake the starting solution generated by each local search loop. In theshaking procedure, we apply our proposed FO approach as the swapping generator. We define the swapping initial solution Xit, which can possibly change from Xit=X¯it to Xit=1-X¯it, and use Xit to define the subproblems of the FO generator. We also use a tabu list to keep the diversity realized by all previousshaking. Ourshaking procedure is similar to [25] except for the swapping generator. With the above descriptions and notations, our FO-VNS approach for the model can be presented in pseudocode (see Algorithm 2).Algorithm 2:FO-VNS for S-MICLSP.
(1) Set an initial feasible solution X¯0 of the model
(2) X¯ = X¯0, X¯∗ = X¯0, and y=1
(3) repeat
(4)  (local search) Apply the new FO approach as local search engine to solve S-MICLSP(X¯,qy), with the neighborhood
constraintGy(X¯). Then X¯′ is obtained.
(5)  ifX¯′isbetterthantheincumbentX¯∗then
(6)   X¯∗ = X¯′,X¯ = X¯′, and y=1
(7)  else
(8)   X¯ = X¯∗, and y=y+1
(9)   ify⩾ymaxthen
(10)    y=1
(11)   end if
(12)  end if
(13)  (shaking) Use the new FO approach and the tabu list to generate a new starting solution X¯′′ from the current solution
X¯. If the solution X¯′′ is better and does not exist in the tabu list, insert it into the list and let X¯=X¯′′.
(14)  Check the current computation time CT.
(15) untilCT⩾CTmax


### 4.2. Integrative FO-VNS for S-MICLSP-L

Due to the sophisticated multilevel structure, Chen [25] did not present the integrative framework for models with setup carryovers. However, in this paper, our model is single-level and hence we can extend our integrative FO-VNS to S-MICLSP-L. Similar to FO-VNS for S-MICLSP, the effective extension of FO-VNS for S-MICLSP-L also has two main parts,local search andshaking. Using symbols given in Notations, we now propose the FO-VNS for S-MICLSP-L.We denoteXZ={Xit,Zit} the setup and carryover plan. To construct a local searching engine for S-MICLSP-L, we first define the neighborhood structure of GyZ(X¯Z) as(36)GyZX¯Z=Xit,Zit∣∑i=1N∑t=1TXit1-X¯it+X¯it1-Xit+XitXi,t-1Zit1-X¯itX¯i,t-1Z¯it+X¯itX¯i,t-1Z¯it1-XitXi,t-1Zit⩽qyZ;then the linear relaxation S-MICLSP-L(X¯Z,qyZ,k) can be defined by adding the following constraint to the S-MICLSP-L model where 0⩽Xit⩽1, 0⩽Zit⩽Xit and 0⩽Zit⩽Xi,t-1. We predefine that Xi,0=X¯i,0=1 for all i∈P.The swapping of the current setup and carryover planX¯Z means that its value is possibly changed from Xit=X¯it and Zit=Z¯it to Xit=1-X¯it and Zit=XitXi,t-1(1-Z¯it). The tabu list contains the setup and carryover plans which will be prevented from being selected by any future swap.With the above statements, our FO-VNS approach for S-MICLSP-L is similar as Algorithm2 for S-MICLSP and we neglect the pseudocode.


## 4.1. Integrative FO-VNS for S-MICLSP

To describe our FO-VNS approach, we will use symbols as shown in Notations. To integrate VNS with our FO approach, we need to predefine a finite set of neighborhood structuresGy(X¯), y=1,2,…,ymax, with G1(X¯)⊆G2(X¯)⊆⋯⊆Gymax(X¯), where y is the neighborhood index. Gy(X¯) can be defined as (35), where qy is an integer associated with neighborhood index y.(35)GyX¯=Xit,i∈P,t∈T∣∑i=1N∑t=1TXit1-X¯it+X¯it1-Xit⩽qy.We also define model S-MICLSP(X¯,qy,k), which is a linear relaxation model allowing 0⩽Xit⩽1 derived from the original model by adding constraint (35) to it, where k is the subproblem level described in Section 3. In the FO-VNS approach for S-MICLSP, we obtain the local optimum of S-MICLSP(X¯,qy,k) by applying our proposed FO approach in Section 3 aslocal search engine.To enhance the search space, we need to shake the starting solution generated by each local search loop. In theshaking procedure, we apply our proposed FO approach as the swapping generator. We define the swapping initial solution Xit, which can possibly change from Xit=X¯it to Xit=1-X¯it, and use Xit to define the subproblems of the FO generator. We also use a tabu list to keep the diversity realized by all previousshaking. Ourshaking procedure is similar to [25] except for the swapping generator. With the above descriptions and notations, our FO-VNS approach for the model can be presented in pseudocode (see Algorithm 2).Algorithm 2:FO-VNS for S-MICLSP.
(1) Set an initial feasible solution X¯0 of the model
(2) X¯ = X¯0, X¯∗ = X¯0, and y=1
(3) repeat
(4)  (local search) Apply the new FO approach as local search engine to solve S-MICLSP(X¯,qy), with the neighborhood
constraintGy(X¯). Then X¯′ is obtained.
(5)  ifX¯′isbetterthantheincumbentX¯∗then
(6)   X¯∗ = X¯′,X¯ = X¯′, and y=1
(7)  else
(8)   X¯ = X¯∗, and y=y+1
(9)   ify⩾ymaxthen
(10)    y=1
(11)   end if
(12)  end if
(13)  (shaking) Use the new FO approach and the tabu list to generate a new starting solution X¯′′ from the current solution
X¯. If the solution X¯′′ is better and does not exist in the tabu list, insert it into the list and let X¯=X¯′′.
(14)  Check the current computation time CT.
(15) untilCT⩾CTmax


## 4.2. Integrative FO-VNS for S-MICLSP-L

Due to the sophisticated multilevel structure, Chen [25] did not present the integrative framework for models with setup carryovers. However, in this paper, our model is single-level and hence we can extend our integrative FO-VNS to S-MICLSP-L. Similar to FO-VNS for S-MICLSP, the effective extension of FO-VNS for S-MICLSP-L also has two main parts,local search andshaking. Using symbols given in Notations, we now propose the FO-VNS for S-MICLSP-L.We denoteXZ={Xit,Zit} the setup and carryover plan. To construct a local searching engine for S-MICLSP-L, we first define the neighborhood structure of GyZ(X¯Z) as(36)GyZX¯Z=Xit,Zit∣∑i=1N∑t=1TXit1-X¯it+X¯it1-Xit+XitXi,t-1Zit1-X¯itX¯i,t-1Z¯it+X¯itX¯i,t-1Z¯it1-XitXi,t-1Zit⩽qyZ;then the linear relaxation S-MICLSP-L(X¯Z,qyZ,k) can be defined by adding the following constraint to the S-MICLSP-L model where 0⩽Xit⩽1, 0⩽Zit⩽Xit and 0⩽Zit⩽Xi,t-1. We predefine that Xi,0=X¯i,0=1 for all i∈P.The swapping of the current setup and carryover planX¯Z means that its value is possibly changed from Xit=X¯it and Zit=Z¯it to Xit=1-X¯it and Zit=XitXi,t-1(1-Z¯it). The tabu list contains the setup and carryover plans which will be prevented from being selected by any future swap.With the above statements, our FO-VNS approach for S-MICLSP-L is similar as Algorithm2 for S-MICLSP and we neglect the pseudocode.


## 5. Numerical Experiments

In this section, we evaluate the performances of our proposed FO and FO-VNS approaches.


### 5.1. Experimental Design

We generate problem instances based on the attributes of real-world steel products. The developed instance generator is documented in Appendix, as well as the instance settings. The experimental design structure is as follows: we generate100 instances with 10 products, 5 demands (or demand classes), 5 resources, and 50 periods. Both S-MICLSP and S-MICLSP-L are tested on the same instances.All algorithms are coded in C++ in the environment of Microsoft Visual Studio 2012, and all instances are tested on a PC with Intel Core-i53.20 GHz CPU, 4 GB RAM. We compare our approaches with the fix-and-optimize approach of [17]. All LP and MIP subproblems involved are solved by calling the MIP solver of ILOG CPLEX 12.7. All problems and subproblems use a relative MIP gap tolerance of 10-4; the time for ILOG CPLEX 12.7 to solve each subproblem is limited to 2 s for S-MICLSP and 4 s for S-MICLSP-L.As the results depend on the number of line segments used in the approximated models (see (21) and (28) in Section 2.2) as well as the computational times, we solved each of the 100 problem instances with 5, 10, and 15 line segments. The numerical experiment shows that 10 line segments provide a good compromise between accuracy and computational times. Hence we will choose 10 as the segments number in all other tests and comparisons.Table1 lists the algorithm variants compared in the computational experiments. We describe Table 1 in the following four aspects. (1) FO1 is referred to the fix-and-optimize approach proposed by [17], in which they presented three decomposition methods. They defined the subproblems, respectively, by product-, resource-, and time period-oriented decomposition (we refer to P-type, R-type, and T-type decomposition for short in the context). Further, they combined the three decomposition types and presented three more variants: P-type first and then R-type, P-type first and then T-type, and P-type first and then R-type ending with T-type. (2) FO2 is referred to our newly proposed FO approach, in which each variant is entitled with FO2-n-Lk. Recall that n is the control parameter of FO2 introduced in Section 3, and FO2 terminates if n subproblems are consecutively solved without improvement; that is, at most n subproblems are solved in each iteration. Otherwise, the solution of one subproblem is better than the current best solution of the main problem, and FO2 will proceed to a new iteration after the update of the best solution. The decomposition level k is another control parameter described in Section 3. Recall that a bigger k implies that more binary setup variables are reoptimized in one subproblem. Because considering subproblems of level larger than 3 is too time-consuming, we only test FO2 with subproblems of level k=1,2,3 (see Section 3.2). (3) FO-VNS is referred to our integrative FO and VNS method. We vary the decomposition level k and obtain three variants of FO-VNS. Overall, absolute time limit for the algorithms is set to 10 minutes for S-MICLSP and 20 minutes for S-MICLSP-L, which can be slightly exceeded by finalizing code. (4) CPXstd and CPX30std are referred to standard software (CPLEX, Branch & Cut) as comparisons. The absolute time limit for CPXstd is set to be same as FO-VNS, while the time limit of CPX30std is more than CPXstd by 30 times.Table 1
Algorithm variants.
Algorithm
Decomposition order
Maximum subproblemsn
Decomposition levelk
FO1-P
P
—
—
FO1-R
R
—
—
FO1-T
T
—
—
FO1-PR
P→ R
—
—
FO1-PT
P→ T
—
—
FO1-PRT
P→ R → T
—
—
FO2-n1-L1
—
N×T
1
FO2-n1-L2
—
N×T
2
FO2-n1-L3
—
N×T
3
FO2-n2-L1
—
0.5×N×T
1
FO2-n2-L2
—
0.5×N×T
2
FO2-n2-L3
—
0.5×N×T
3
FO2-n3-L1
—
0.25×N×T
1
FO2-n3-L2
—
0.25×N×T
2
FO2-n3-L3
—
0.25×N×T
3
FO-VNS-L1
—
—
1
FO-VNS-L2
—
—
2
FO-VNS-L3
—
—
3
CPXstd
—
—
—
CPX30std
—
—
—


### 5.2. Results and Interpretation

Table2 describes the notations used to measure the solution quality.Table 2
Notations for measuring solution quality.
Notation
Definition
Quality measure
Cost¯
Average total cost
Lower is better
Time¯
Average computational time
Lower is better
rate¯ot
Average proportion of periods with overtime (in %)
Lower is better
δ-SL¯
Averageδ-service level (in %) (see [29])
Higher is better
rateNOB
Proportion of instances for which a feasible solution with neither overtime nor backlogging has been found by the algorithm (in %)
Higher is better
devAverageCost¯
Deviation from the averageCost¯ of FO1 (in %)
Lower is better
devBestCost¯
Deviation from the bestCost¯ of FO1 (in %)
Lower is better
devAverageTime¯
Deviation from the averageTime¯ of FO1 (in %)
Lower is better
devBestTime¯
Deviation from theTime¯ of FO1 variants with best Cost¯ (in %)
Lower is better
devCost¯
Deviation from the comparedCost¯ (in %)
Lower is better
devTime¯
Deviation from the comparedTime¯ (in %)
Lower is better


#### 5.2.1. Computational Results on S-MICLSP

Table3 illustrates the computational results on S-MICLSP model. From this table, we can see that FO2 outperforms FO1 in terms of the solution quality. Among the six variants of FO1, FO1-PRT obtains the lowest Cost¯. It can be observed from Table 3 that the variants of FO2 with bigger n and bigger k consume more computational time than FO1. However, FO2 can reduce Cost¯ significantly compared with FO1 in general. 7 out of 9 FO2 variants perform a better Cost¯ with respect to FO1 on average, meanwhile 5 out of 9 FO2 variants are better with respect to FO1-PRT. Also, another observation from this table is that FO2 is more efficient than FO1 in general. Taking FO2-n2-L2 as an example, this FO2 variant can obtain both reduced Cost¯ and Time¯ compared either with FO1 on average or the best FO1 variant. Among all the variants of FO2, it seems that FO2-n2-L2 makes the best trade-off between Cost¯ and Time¯ since it can provide better solutions with lower computational time.Table 3
Computational results on S-MICLSP.
Algorithm
C
o
s
t
¯
T
i
m
e
¯
r
a
t
e
¯
o
t
δ
-
S
L
¯
r
a
t
e
N
O
B
FO1-P
705103.74
212.41
6.78
96.58
53.00
FO1-R
715294.16
205.67
6.92
95.71
54.00
FO1-T
696034.43
222.19
5.08
97.80
65.00
FO1-PR
700148.81
218.97
5.00
96.41
59.00
FO1-PT
690659.08
232.80
3.20
100.00
80.00
FO1-PRT
689240.75
234.44
3.56
100.00
79.00
devAverageCost¯
devBestCost¯
devAverageTime¯
devBestTime¯
FO2-n1-L1
−1.65
−0.20
2.13
−3.69
0.00
100.00
100.00
FO2-n1-L2
−2.27
−0.83
11.40
5.05
0.00
100.00
100.00
FO2-n1-L3
−3.20
−1.77
18.31
11.57
0.00
100.00
100.00
FO2-n2-L1
−0.77
0.70
−8.80
−14.00
4.00
97.75
84.00
FO2-n2-L2
−1.93
−0.48
−0.13
−5.82
3.86
100.00
86.00
FO2-n2-L3
−2.74
−1.30
10.99
4.67
3.92
100.00
86.00
FO2-n3-L1
2.38
3.90
−23.21
−27.58
5.00
95.24
51.00
FO2-n3-L2
0.69
2.18
−13.47
−18.40
5.00
95.15
55.00
FO2-n3-L3
−0.55
0.92
5.87
−0.16
5.22
97.90
52.00
FO-VNS-L1
−4.95
−3.55
172.32
156.81
0.00
100.00
100.00
FO-VNS-L2
−5.62
−4.23
173.06
157.50
0.00
100.00
100.00
FO-VNS-L3
−5.99
−4.60
172.84
157.29
0.00
100.00
100.00
CPXstd
4.08
5.62
171.50
156.03
4.62
95.59
81.00
CPX30std
−7.31
−5.95
8141.17
7671.53
0.00
100.00
100.00For other measurements of the solution quality, FO2 still performs better than FO1 under most circumstances. Consideringrate¯ot, which describes the proportion of periods with overtime, all of the FO1 variants are not able to provide solutions completely without overtime. However, when n=n1=N×T, FO2 can make rate¯ot at a zero level, which implies lower overtime cost than FO1. For other FO2 variants, they can also obtain competitive results against FO1. Considering δ-SL¯, only 2 out of 6 FO1 variants obtain 100 percent δ-service level while 5 out of 9 FO2 variants can achieve this goal. We find that, for bigger n and k, FO2 tends to achieve a high δ-service level from the column δ-SL¯ of Table 3. Consider rateNOB, which indicates the solution quality by combining rate¯ot and δ-SL¯ in a statistical sense. The results of FO2-n1-Lk (k=1,2,3) imply that there exist solutions without overtime and backlogging for all tested instances, while FO1 obtain solutions at a relative lower rateNOB proportion. We can also observe that for a lower n=n3, FO2-n3-L2 performs better than FO1-P and FO1-R, while other FO2-n3-Lk (k=1,3) perform worse than all the FO1 variants.The three rows entitled “FO-VNS-Lk” of Table 3 report the solution quality of FO-VNS variants with different k. From the results, the three variants of FO-VNS obtain around 4.95%~5.99% better solutions compared with FO1 on the average, and around 3.55%~4.60% compared with the best FO1 significantly, while the computational time can be considerably larger by 172.32%~173.06% and 156.81%~157.50% compared with the average FO1 and the best FO1. However, the S-MICLSP (also S-MICLSP-L) considered in this paper is usually solved weekly or monthly in a tactical decision for a factory of one steel enterprise. It is thus worth spending more but reasonable time to obtain a significantly better production plan by our FO-VNS.The last two rows of Table3 provide comparisons between CPLEX and our proposed algorithms. CPXstd runs the same time limit as FO-VNS but it performs worse than all other algorithms. Running a much longer time limit, CPX30std performs much better. However compared to FO-VNS, the solution quality of CPX30std is slightly improved with an extremely increased computational effort.


#### 5.2.2. Computational Results on S-MICLSP-L

The computational results on the S-MICLSP-L model are given in Table4. By the similar observations to Table 3, FO2 still outperforms FO1 in terms of the solution quality. Particularly, FO2-n1-L1 and FO2-n2-L2 outperform all the FO1 variants when considering Cost¯ and Time¯, which implies they make the best trade-off between Cost¯ and Time¯ in all FO2 variants. Similar to Table 3, FO-VNS gives quite outstanding results compared with FO1 and FO2. FO-VNS performs a better Cost¯ by reducing 5.17%~6.16% against FO1-PRT. All of the FO-VNS variants provide δ-SL¯ of 100%, yet FO1 and FO2 fail to do so. The results of the last two rows in Table 4 are similar to Table 3. CPXstd reports its drawbacks in terms of solution quality and computational effort, while CPX30std reports its better solution quality with much longer computational time.Table 4
Computational results on S-MICLSP-L.
Algorithm
C
o
s
t
¯
T
i
m
e
¯
r
a
t
e
¯
o
t
δ
-
S
L
¯
r
a
t
e
N
O
B
FO1-P
727790.95
436.31
15.36
82.41
37.00
FO1-R
741102.74
414.03
20.48
73.96
23.00
FO1-T
717907.32
429.78
14.52
83.69
33.00
FO1-PR
723629.97
442.17
13.00
80.94
45.00
FO1-PT
716389.74
452.53
13.32
87.00
42.00
FO1-PRT
712618.87
474.03
13.00
91.04
46.00
d
e
v
A
v
e
r
a
g
e
C
o
s
t
¯
d
e
v
B
e
s
t
C
o
s
t
¯
d
e
v
A
v
e
r
a
g
e
T
i
m
e
¯
d
e
v
B
e
s
t
T
i
m
e
¯
FO2-n1-L1
−2.40
−0.94
−5.27
−11.77
4.42
96.59
85.00
FO2-n1-L2
−3.17
−1.73
5.20
−2.02
4.20
96.31
87.00
FO2-n1-L3
−3.93
−2.50
13.38
5.59
3.94
95.80
88.00
FO2-n2-L1
−1.10
0.37
−8.28
−14.58
8.90
94.39
63.00
FO2-n2-L2
−2.36
−0.91
0.06
−6.81
8.38
96.03
62.00
FO2-n2-L3
−2.81
−1.36
9.21
1.71
8.00
98.80
68.00
FO2-n3-L1
1.95
3.47
−10.49
−16.63
10.64
85.49
53.00
FO2-n3-L2
0.71
2.22
−3.92
−10.52
9.68
89.13
50.00
FO2-n3-L3
−0.63
0.85
4.70
−2.49
9.00
92.03
56.00
FO-VNS-L1
−6.56
−5.17
172.67
153.95
4.94
100.00
83.00
FO-VNS-L2
−7.32
−5.94
172.74
154.01
4.54
100.00
84.00
FO-VNS-L3
−7.54
−6.16
173.38
154.61
4.02
100.00
84.00
CPXstd
4.14
5.69
172.56
153.84
7.84
93.76
71.00
CPX30std
−8.61
−7.25
8187.93
7618.80
0.00
100.00
90.00According to Tables3 and 4, it can be confirmed that the advantages of FO2 and FO-VNS against FO1 for S-MICLSP-L grow compared with S-MICLSP. For example, FO2-n1-L3 has −3.93% of devAverageCost¯ while it has −3.20% in the S-MICLSP case from Table 3. Also, this FO2 variant can obtain −2.50% of devBestCost¯ while it can obtain 1.77% in the S-MICLSP case from Table 3. This observation can also be found for all variants of FO-VNS.


#### 5.2.3. Comparison of Various Cases of Parameter Settings

To check the effectiveness and efficiency of our proposed approaches under various cases of parameter settings, we implement FO1-PRT, FO2-n1-L3, and FO-VNS-L3 (best variants of FO1, FO2, and FO-VNS tested ever) again using test cases of different TBO (time between orders) and ST (setup times). TBO can be computationally defined as the ratio between setup costs and inventory costs (see [28]). Varying different parameters, the results of Table 5 with measurements of Cost¯ and Time¯ are illustrated by groups of combinations of TBOs (low with TBO <2.0, medium with 2.0⩽ TBO <3.0, and high with 3.0< TBO) and STs (low with ST <25, and high with ST ⩾25).Table 5
Computational results with various parameters settings.
Algorithmmodel
TBO
ST
FO1-PRT
FO2-n1-L3
FO-VNS-L3
C
o
s
t
¯
T
i
m
e
¯
d
e
v
C
o
s
t
¯
d
e
v
T
i
m
e
¯
d
e
v
C
o
s
t
¯
d
e
v
T
i
m
e
¯
S-MICLSP
High
High
795664.08
245.51
−2.23
9.96
−4.94
145.95
Low
689240.75
234.44
−1.77
11.57
−4.60
157.29
Medium
High
575783.97
244.29
−1.71
8.03
−4.29
146.78
Low
489240.75
230.71
−1.07
9.63
−2.39
161.63
Low
High
336501.13
237.52
−0.38
2.35
−3.69
152.33
Low
230349.23
229.79
2.19
−4.34
−1.83
162.06
S-MICLSP-L
High
High
817073.11
490.18
−3.08
5.44
−6.39
145.87
Low
712618.87
474.03
−2.50
5.59
−6.16
154.60
Medium
High
576455.47
486.10
−2.00
3.71
−3.45
146.66
Low
502618.87
478.28
−1.16
4.26
−2.77
151.84
Low
High
337218.37
486.34
−0.13
−1.50
−2.50
147.05
Low
251979.47
466.17
0.18
0.57
−1.10
158.21We compare the results in terms of FO1-PRT for the benchmark. From Table5, we can see that for high TBO cases, FO2-n1-L3 and FO-VNS-L3 significantly outperform FO1-PRT in terms of solution quality. These outstanding performances of FO2-n1-L3 and FO-VNS-L3 can also be found in cases of high ST, compared to cases of low ST. Considering cases of high or medium TBO, FO2-n1-L3 and FO-VNS-L3 obtain lower devCost¯ in S-MICLSP-L than that in S-MICLSP. It implies that for high or medium TBO cases, the advantages of FO2 and FO-VNS in S-MICLSP-L grow compared to that in S-MICLSP, which is similar to the previous observations in Section 5.2.2. All of the above results imply that FO2 and FO-VNS are much more effective than FO1 in cases of high or medium TBO and high ST.


#### 5.2.4. Comparison with Scenario Methods

Typically, because of the continuous nature of demand uncertainty and the dynamic structure of the problems, multistage stochastic modeling methods can be applied and hence scenario methods are used to approximate the models. This methodology is distinguished from ours and here we numerically compare the difference between them. The methodology using scenario method is denoted by SCNm-BC, where Branch & Cut approach is used to solve the models approximated by scenario method. We generate m realizations of random demand for each period and hence the number of scenarios is mT, where T is the number of periods. We choose m=5,10 for small test cases. Our methodologies are denoted by PWL-FO2 and PWL-FO-VNS, whereby FO2-n1-L3 and FO-VNS-L3 are, respectively, applied.We compare the results in terms of the methodology of PWL-FO2 for the benchmark. From Table6, we can generally see that the methodology of PWL-FO-VNS is competitive with SCN5-BC and SCN10-BC in terms of Cost¯. The entry “∗∗∗∗” indicates that there are no computational results. Since the number of scenarios is growing in size exponentially, it is impossible to compute finalized results in reasonable time even when T is relatively small. Both PWL-FO2 and PWL-FO-VNS are more splendid than SCN5-BC in terms of solution quality. SCN10-BC can obtain better solutions when T=2,3; however the computational time is unacceptable when T=6,10. Our proposed PWL-FO-VNS obtains competitive solution quality against SCN10-BC while the computational efforts are much less. All of the results imply that our proposed approximation method and solving approaches are efficient.Table 6
Computational results compared with scenarios methods.
Methodologymodel
Periods
PWL-FO2
PWL-FO-VNS
SCN5-BC
SCN10-BC
C
o
s
t
¯
T
i
m
e
¯
d
e
v
C
o
s
t
¯
d
e
v
T
i
m
e
¯
d
e
v
C
o
s
t
¯
d
e
v
T
i
m
e
¯
d
e
v
C
o
s
t
¯
d
e
v
T
i
m
e
¯
S-MICLSP
T
=
2
31610.95
6.05
0.65
133.29
4.52
−19.82
−1.81
246.14
T
=
3
52896.83
9.84
−2.67
120.10
1.34
121.28
−2.44
1709.16
T
=
6
106087.66
16.48
−3.03
117.48
−4.13
15134.03
∗
∗
∗
∗
∗
∗
∗
∗
T
=
10
180137.95
27.52
−3.33
116.87
∗∗∗∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
S-MICLSP-L
T
=
2
35294.55
11.06
−2.15
161.47
3.20
−13.05
−1.61
236.42
T
=
3
55840.08
17.84
−2.86
144.40
3.73
207.43
−3.43
2439.68
T
=
6
113090.88
32.39
−3.54
137.08
−4.31
17906.94
∗
∗
∗
∗
∗
∗
∗
∗
T
=
10
195927.06
52.22
−4.02
135.99
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗


## 5.1. Experimental Design

We generate problem instances based on the attributes of real-world steel products. The developed instance generator is documented in Appendix, as well as the instance settings. The experimental design structure is as follows: we generate100 instances with 10 products, 5 demands (or demand classes), 5 resources, and 50 periods. Both S-MICLSP and S-MICLSP-L are tested on the same instances.All algorithms are coded in C++ in the environment of Microsoft Visual Studio 2012, and all instances are tested on a PC with Intel Core-i53.20 GHz CPU, 4 GB RAM. We compare our approaches with the fix-and-optimize approach of [17]. All LP and MIP subproblems involved are solved by calling the MIP solver of ILOG CPLEX 12.7. All problems and subproblems use a relative MIP gap tolerance of 10-4; the time for ILOG CPLEX 12.7 to solve each subproblem is limited to 2 s for S-MICLSP and 4 s for S-MICLSP-L.As the results depend on the number of line segments used in the approximated models (see (21) and (28) in Section 2.2) as well as the computational times, we solved each of the 100 problem instances with 5, 10, and 15 line segments. The numerical experiment shows that 10 line segments provide a good compromise between accuracy and computational times. Hence we will choose 10 as the segments number in all other tests and comparisons.Table1 lists the algorithm variants compared in the computational experiments. We describe Table 1 in the following four aspects. (1) FO1 is referred to the fix-and-optimize approach proposed by [17], in which they presented three decomposition methods. They defined the subproblems, respectively, by product-, resource-, and time period-oriented decomposition (we refer to P-type, R-type, and T-type decomposition for short in the context). Further, they combined the three decomposition types and presented three more variants: P-type first and then R-type, P-type first and then T-type, and P-type first and then R-type ending with T-type. (2) FO2 is referred to our newly proposed FO approach, in which each variant is entitled with FO2-n-Lk. Recall that n is the control parameter of FO2 introduced in Section 3, and FO2 terminates if n subproblems are consecutively solved without improvement; that is, at most n subproblems are solved in each iteration. Otherwise, the solution of one subproblem is better than the current best solution of the main problem, and FO2 will proceed to a new iteration after the update of the best solution. The decomposition level k is another control parameter described in Section 3. Recall that a bigger k implies that more binary setup variables are reoptimized in one subproblem. Because considering subproblems of level larger than 3 is too time-consuming, we only test FO2 with subproblems of level k=1,2,3 (see Section 3.2). (3) FO-VNS is referred to our integrative FO and VNS method. We vary the decomposition level k and obtain three variants of FO-VNS. Overall, absolute time limit for the algorithms is set to 10 minutes for S-MICLSP and 20 minutes for S-MICLSP-L, which can be slightly exceeded by finalizing code. (4) CPXstd and CPX30std are referred to standard software (CPLEX, Branch & Cut) as comparisons. The absolute time limit for CPXstd is set to be same as FO-VNS, while the time limit of CPX30std is more than CPXstd by 30 times.Table 1
Algorithm variants.
Algorithm
Decomposition order
Maximum subproblemsn
Decomposition levelk
FO1-P
P
—
—
FO1-R
R
—
—
FO1-T
T
—
—
FO1-PR
P→ R
—
—
FO1-PT
P→ T
—
—
FO1-PRT
P→ R → T
—
—
FO2-n1-L1
—
N×T
1
FO2-n1-L2
—
N×T
2
FO2-n1-L3
—
N×T
3
FO2-n2-L1
—
0.5×N×T
1
FO2-n2-L2
—
0.5×N×T
2
FO2-n2-L3
—
0.5×N×T
3
FO2-n3-L1
—
0.25×N×T
1
FO2-n3-L2
—
0.25×N×T
2
FO2-n3-L3
—
0.25×N×T
3
FO-VNS-L1
—
—
1
FO-VNS-L2
—
—
2
FO-VNS-L3
—
—
3
CPXstd
—
—
—
CPX30std
—
—
—


## 5.2. Results and Interpretation

Table2 describes the notations used to measure the solution quality.Table 2
Notations for measuring solution quality.
Notation
Definition
Quality measure
Cost¯
Average total cost
Lower is better
Time¯
Average computational time
Lower is better
rate¯ot
Average proportion of periods with overtime (in %)
Lower is better
δ-SL¯
Averageδ-service level (in %) (see [29])
Higher is better
rateNOB
Proportion of instances for which a feasible solution with neither overtime nor backlogging has been found by the algorithm (in %)
Higher is better
devAverageCost¯
Deviation from the averageCost¯ of FO1 (in %)
Lower is better
devBestCost¯
Deviation from the bestCost¯ of FO1 (in %)
Lower is better
devAverageTime¯
Deviation from the averageTime¯ of FO1 (in %)
Lower is better
devBestTime¯
Deviation from theTime¯ of FO1 variants with best Cost¯ (in %)
Lower is better
devCost¯
Deviation from the comparedCost¯ (in %)
Lower is better
devTime¯
Deviation from the comparedTime¯ (in %)
Lower is better


### 5.2.1. Computational Results on S-MICLSP

Table3 illustrates the computational results on S-MICLSP model. From this table, we can see that FO2 outperforms FO1 in terms of the solution quality. Among the six variants of FO1, FO1-PRT obtains the lowest Cost¯. It can be observed from Table 3 that the variants of FO2 with bigger n and bigger k consume more computational time than FO1. However, FO2 can reduce Cost¯ significantly compared with FO1 in general. 7 out of 9 FO2 variants perform a better Cost¯ with respect to FO1 on average, meanwhile 5 out of 9 FO2 variants are better with respect to FO1-PRT. Also, another observation from this table is that FO2 is more efficient than FO1 in general. Taking FO2-n2-L2 as an example, this FO2 variant can obtain both reduced Cost¯ and Time¯ compared either with FO1 on average or the best FO1 variant. Among all the variants of FO2, it seems that FO2-n2-L2 makes the best trade-off between Cost¯ and Time¯ since it can provide better solutions with lower computational time.Table 3
Computational results on S-MICLSP.
Algorithm
C
o
s
t
¯
T
i
m
e
¯
r
a
t
e
¯
o
t
δ
-
S
L
¯
r
a
t
e
N
O
B
FO1-P
705103.74
212.41
6.78
96.58
53.00
FO1-R
715294.16
205.67
6.92
95.71
54.00
FO1-T
696034.43
222.19
5.08
97.80
65.00
FO1-PR
700148.81
218.97
5.00
96.41
59.00
FO1-PT
690659.08
232.80
3.20
100.00
80.00
FO1-PRT
689240.75
234.44
3.56
100.00
79.00
devAverageCost¯
devBestCost¯
devAverageTime¯
devBestTime¯
FO2-n1-L1
−1.65
−0.20
2.13
−3.69
0.00
100.00
100.00
FO2-n1-L2
−2.27
−0.83
11.40
5.05
0.00
100.00
100.00
FO2-n1-L3
−3.20
−1.77
18.31
11.57
0.00
100.00
100.00
FO2-n2-L1
−0.77
0.70
−8.80
−14.00
4.00
97.75
84.00
FO2-n2-L2
−1.93
−0.48
−0.13
−5.82
3.86
100.00
86.00
FO2-n2-L3
−2.74
−1.30
10.99
4.67
3.92
100.00
86.00
FO2-n3-L1
2.38
3.90
−23.21
−27.58
5.00
95.24
51.00
FO2-n3-L2
0.69
2.18
−13.47
−18.40
5.00
95.15
55.00
FO2-n3-L3
−0.55
0.92
5.87
−0.16
5.22
97.90
52.00
FO-VNS-L1
−4.95
−3.55
172.32
156.81
0.00
100.00
100.00
FO-VNS-L2
−5.62
−4.23
173.06
157.50
0.00
100.00
100.00
FO-VNS-L3
−5.99
−4.60
172.84
157.29
0.00
100.00
100.00
CPXstd
4.08
5.62
171.50
156.03
4.62
95.59
81.00
CPX30std
−7.31
−5.95
8141.17
7671.53
0.00
100.00
100.00For other measurements of the solution quality, FO2 still performs better than FO1 under most circumstances. Consideringrate¯ot, which describes the proportion of periods with overtime, all of the FO1 variants are not able to provide solutions completely without overtime. However, when n=n1=N×T, FO2 can make rate¯ot at a zero level, which implies lower overtime cost than FO1. For other FO2 variants, they can also obtain competitive results against FO1. Considering δ-SL¯, only 2 out of 6 FO1 variants obtain 100 percent δ-service level while 5 out of 9 FO2 variants can achieve this goal. We find that, for bigger n and k, FO2 tends to achieve a high δ-service level from the column δ-SL¯ of Table 3. Consider rateNOB, which indicates the solution quality by combining rate¯ot and δ-SL¯ in a statistical sense. The results of FO2-n1-Lk (k=1,2,3) imply that there exist solutions without overtime and backlogging for all tested instances, while FO1 obtain solutions at a relative lower rateNOB proportion. We can also observe that for a lower n=n3, FO2-n3-L2 performs better than FO1-P and FO1-R, while other FO2-n3-Lk (k=1,3) perform worse than all the FO1 variants.The three rows entitled “FO-VNS-Lk” of Table 3 report the solution quality of FO-VNS variants with different k. From the results, the three variants of FO-VNS obtain around 4.95%~5.99% better solutions compared with FO1 on the average, and around 3.55%~4.60% compared with the best FO1 significantly, while the computational time can be considerably larger by 172.32%~173.06% and 156.81%~157.50% compared with the average FO1 and the best FO1. However, the S-MICLSP (also S-MICLSP-L) considered in this paper is usually solved weekly or monthly in a tactical decision for a factory of one steel enterprise. It is thus worth spending more but reasonable time to obtain a significantly better production plan by our FO-VNS.The last two rows of Table3 provide comparisons between CPLEX and our proposed algorithms. CPXstd runs the same time limit as FO-VNS but it performs worse than all other algorithms. Running a much longer time limit, CPX30std performs much better. However compared to FO-VNS, the solution quality of CPX30std is slightly improved with an extremely increased computational effort.


### 5.2.2. Computational Results on S-MICLSP-L

The computational results on the S-MICLSP-L model are given in Table4. By the similar observations to Table 3, FO2 still outperforms FO1 in terms of the solution quality. Particularly, FO2-n1-L1 and FO2-n2-L2 outperform all the FO1 variants when considering Cost¯ and Time¯, which implies they make the best trade-off between Cost¯ and Time¯ in all FO2 variants. Similar to Table 3, FO-VNS gives quite outstanding results compared with FO1 and FO2. FO-VNS performs a better Cost¯ by reducing 5.17%~6.16% against FO1-PRT. All of the FO-VNS variants provide δ-SL¯ of 100%, yet FO1 and FO2 fail to do so. The results of the last two rows in Table 4 are similar to Table 3. CPXstd reports its drawbacks in terms of solution quality and computational effort, while CPX30std reports its better solution quality with much longer computational time.Table 4
Computational results on S-MICLSP-L.
Algorithm
C
o
s
t
¯
T
i
m
e
¯
r
a
t
e
¯
o
t
δ
-
S
L
¯
r
a
t
e
N
O
B
FO1-P
727790.95
436.31
15.36
82.41
37.00
FO1-R
741102.74
414.03
20.48
73.96
23.00
FO1-T
717907.32
429.78
14.52
83.69
33.00
FO1-PR
723629.97
442.17
13.00
80.94
45.00
FO1-PT
716389.74
452.53
13.32
87.00
42.00
FO1-PRT
712618.87
474.03
13.00
91.04
46.00
d
e
v
A
v
e
r
a
g
e
C
o
s
t
¯
d
e
v
B
e
s
t
C
o
s
t
¯
d
e
v
A
v
e
r
a
g
e
T
i
m
e
¯
d
e
v
B
e
s
t
T
i
m
e
¯
FO2-n1-L1
−2.40
−0.94
−5.27
−11.77
4.42
96.59
85.00
FO2-n1-L2
−3.17
−1.73
5.20
−2.02
4.20
96.31
87.00
FO2-n1-L3
−3.93
−2.50
13.38
5.59
3.94
95.80
88.00
FO2-n2-L1
−1.10
0.37
−8.28
−14.58
8.90
94.39
63.00
FO2-n2-L2
−2.36
−0.91
0.06
−6.81
8.38
96.03
62.00
FO2-n2-L3
−2.81
−1.36
9.21
1.71
8.00
98.80
68.00
FO2-n3-L1
1.95
3.47
−10.49
−16.63
10.64
85.49
53.00
FO2-n3-L2
0.71
2.22
−3.92
−10.52
9.68
89.13
50.00
FO2-n3-L3
−0.63
0.85
4.70
−2.49
9.00
92.03
56.00
FO-VNS-L1
−6.56
−5.17
172.67
153.95
4.94
100.00
83.00
FO-VNS-L2
−7.32
−5.94
172.74
154.01
4.54
100.00
84.00
FO-VNS-L3
−7.54
−6.16
173.38
154.61
4.02
100.00
84.00
CPXstd
4.14
5.69
172.56
153.84
7.84
93.76
71.00
CPX30std
−8.61
−7.25
8187.93
7618.80
0.00
100.00
90.00According to Tables3 and 4, it can be confirmed that the advantages of FO2 and FO-VNS against FO1 for S-MICLSP-L grow compared with S-MICLSP. For example, FO2-n1-L3 has −3.93% of devAverageCost¯ while it has −3.20% in the S-MICLSP case from Table 3. Also, this FO2 variant can obtain −2.50% of devBestCost¯ while it can obtain 1.77% in the S-MICLSP case from Table 3. This observation can also be found for all variants of FO-VNS.


### 5.2.3. Comparison of Various Cases of Parameter Settings

To check the effectiveness and efficiency of our proposed approaches under various cases of parameter settings, we implement FO1-PRT, FO2-n1-L3, and FO-VNS-L3 (best variants of FO1, FO2, and FO-VNS tested ever) again using test cases of different TBO (time between orders) and ST (setup times). TBO can be computationally defined as the ratio between setup costs and inventory costs (see [28]). Varying different parameters, the results of Table 5 with measurements of Cost¯ and Time¯ are illustrated by groups of combinations of TBOs (low with TBO <2.0, medium with 2.0⩽ TBO <3.0, and high with 3.0< TBO) and STs (low with ST <25, and high with ST ⩾25).Table 5
Computational results with various parameters settings.
Algorithmmodel
TBO
ST
FO1-PRT
FO2-n1-L3
FO-VNS-L3
C
o
s
t
¯
T
i
m
e
¯
d
e
v
C
o
s
t
¯
d
e
v
T
i
m
e
¯
d
e
v
C
o
s
t
¯
d
e
v
T
i
m
e
¯
S-MICLSP
High
High
795664.08
245.51
−2.23
9.96
−4.94
145.95
Low
689240.75
234.44
−1.77
11.57
−4.60
157.29
Medium
High
575783.97
244.29
−1.71
8.03
−4.29
146.78
Low
489240.75
230.71
−1.07
9.63
−2.39
161.63
Low
High
336501.13
237.52
−0.38
2.35
−3.69
152.33
Low
230349.23
229.79
2.19
−4.34
−1.83
162.06
S-MICLSP-L
High
High
817073.11
490.18
−3.08
5.44
−6.39
145.87
Low
712618.87
474.03
−2.50
5.59
−6.16
154.60
Medium
High
576455.47
486.10
−2.00
3.71
−3.45
146.66
Low
502618.87
478.28
−1.16
4.26
−2.77
151.84
Low
High
337218.37
486.34
−0.13
−1.50
−2.50
147.05
Low
251979.47
466.17
0.18
0.57
−1.10
158.21We compare the results in terms of FO1-PRT for the benchmark. From Table5, we can see that for high TBO cases, FO2-n1-L3 and FO-VNS-L3 significantly outperform FO1-PRT in terms of solution quality. These outstanding performances of FO2-n1-L3 and FO-VNS-L3 can also be found in cases of high ST, compared to cases of low ST. Considering cases of high or medium TBO, FO2-n1-L3 and FO-VNS-L3 obtain lower devCost¯ in S-MICLSP-L than that in S-MICLSP. It implies that for high or medium TBO cases, the advantages of FO2 and FO-VNS in S-MICLSP-L grow compared to that in S-MICLSP, which is similar to the previous observations in Section 5.2.2. All of the above results imply that FO2 and FO-VNS are much more effective than FO1 in cases of high or medium TBO and high ST.


### 5.2.4. Comparison with Scenario Methods

Typically, because of the continuous nature of demand uncertainty and the dynamic structure of the problems, multistage stochastic modeling methods can be applied and hence scenario methods are used to approximate the models. This methodology is distinguished from ours and here we numerically compare the difference between them. The methodology using scenario method is denoted by SCNm-BC, where Branch & Cut approach is used to solve the models approximated by scenario method. We generate m realizations of random demand for each period and hence the number of scenarios is mT, where T is the number of periods. We choose m=5,10 for small test cases. Our methodologies are denoted by PWL-FO2 and PWL-FO-VNS, whereby FO2-n1-L3 and FO-VNS-L3 are, respectively, applied.We compare the results in terms of the methodology of PWL-FO2 for the benchmark. From Table6, we can generally see that the methodology of PWL-FO-VNS is competitive with SCN5-BC and SCN10-BC in terms of Cost¯. The entry “∗∗∗∗” indicates that there are no computational results. Since the number of scenarios is growing in size exponentially, it is impossible to compute finalized results in reasonable time even when T is relatively small. Both PWL-FO2 and PWL-FO-VNS are more splendid than SCN5-BC in terms of solution quality. SCN10-BC can obtain better solutions when T=2,3; however the computational time is unacceptable when T=6,10. Our proposed PWL-FO-VNS obtains competitive solution quality against SCN10-BC while the computational efforts are much less. All of the results imply that our proposed approximation method and solving approaches are efficient.Table 6
Computational results compared with scenarios methods.
Methodologymodel
Periods
PWL-FO2
PWL-FO-VNS
SCN5-BC
SCN10-BC
C
o
s
t
¯
T
i
m
e
¯
d
e
v
C
o
s
t
¯
d
e
v
T
i
m
e
¯
d
e
v
C
o
s
t
¯
d
e
v
T
i
m
e
¯
d
e
v
C
o
s
t
¯
d
e
v
T
i
m
e
¯
S-MICLSP
T
=
2
31610.95
6.05
0.65
133.29
4.52
−19.82
−1.81
246.14
T
=
3
52896.83
9.84
−2.67
120.10
1.34
121.28
−2.44
1709.16
T
=
6
106087.66
16.48
−3.03
117.48
−4.13
15134.03
∗
∗
∗
∗
∗
∗
∗
∗
T
=
10
180137.95
27.52
−3.33
116.87
∗∗∗∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
S-MICLSP-L
T
=
2
35294.55
11.06
−2.15
161.47
3.20
−13.05
−1.61
236.42
T
=
3
55840.08
17.84
−2.86
144.40
3.73
207.43
−3.43
2439.68
T
=
6
113090.88
32.39
−3.54
137.08
−4.31
17906.94
∗
∗
∗
∗
∗
∗
∗
∗
T
=
10
195927.06
52.22
−4.02
135.99
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗


## 5.2.1. Computational Results on S-MICLSP

Table3 illustrates the computational results on S-MICLSP model. From this table, we can see that FO2 outperforms FO1 in terms of the solution quality. Among the six variants of FO1, FO1-PRT obtains the lowest Cost¯. It can be observed from Table 3 that the variants of FO2 with bigger n and bigger k consume more computational time than FO1. However, FO2 can reduce Cost¯ significantly compared with FO1 in general. 7 out of 9 FO2 variants perform a better Cost¯ with respect to FO1 on average, meanwhile 5 out of 9 FO2 variants are better with respect to FO1-PRT. Also, another observation from this table is that FO2 is more efficient than FO1 in general. Taking FO2-n2-L2 as an example, this FO2 variant can obtain both reduced Cost¯ and Time¯ compared either with FO1 on average or the best FO1 variant. Among all the variants of FO2, it seems that FO2-n2-L2 makes the best trade-off between Cost¯ and Time¯ since it can provide better solutions with lower computational time.Table 3
Computational results on S-MICLSP.
Algorithm
C
o
s
t
¯
T
i
m
e
¯
r
a
t
e
¯
o
t
δ
-
S
L
¯
r
a
t
e
N
O
B
FO1-P
705103.74
212.41
6.78
96.58
53.00
FO1-R
715294.16
205.67
6.92
95.71
54.00
FO1-T
696034.43
222.19
5.08
97.80
65.00
FO1-PR
700148.81
218.97
5.00
96.41
59.00
FO1-PT
690659.08
232.80
3.20
100.00
80.00
FO1-PRT
689240.75
234.44
3.56
100.00
79.00
devAverageCost¯
devBestCost¯
devAverageTime¯
devBestTime¯
FO2-n1-L1
−1.65
−0.20
2.13
−3.69
0.00
100.00
100.00
FO2-n1-L2
−2.27
−0.83
11.40
5.05
0.00
100.00
100.00
FO2-n1-L3
−3.20
−1.77
18.31
11.57
0.00
100.00
100.00
FO2-n2-L1
−0.77
0.70
−8.80
−14.00
4.00
97.75
84.00
FO2-n2-L2
−1.93
−0.48
−0.13
−5.82
3.86
100.00
86.00
FO2-n2-L3
−2.74
−1.30
10.99
4.67
3.92
100.00
86.00
FO2-n3-L1
2.38
3.90
−23.21
−27.58
5.00
95.24
51.00
FO2-n3-L2
0.69
2.18
−13.47
−18.40
5.00
95.15
55.00
FO2-n3-L3
−0.55
0.92
5.87
−0.16
5.22
97.90
52.00
FO-VNS-L1
−4.95
−3.55
172.32
156.81
0.00
100.00
100.00
FO-VNS-L2
−5.62
−4.23
173.06
157.50
0.00
100.00
100.00
FO-VNS-L3
−5.99
−4.60
172.84
157.29
0.00
100.00
100.00
CPXstd
4.08
5.62
171.50
156.03
4.62
95.59
81.00
CPX30std
−7.31
−5.95
8141.17
7671.53
0.00
100.00
100.00For other measurements of the solution quality, FO2 still performs better than FO1 under most circumstances. Consideringrate¯ot, which describes the proportion of periods with overtime, all of the FO1 variants are not able to provide solutions completely without overtime. However, when n=n1=N×T, FO2 can make rate¯ot at a zero level, which implies lower overtime cost than FO1. For other FO2 variants, they can also obtain competitive results against FO1. Considering δ-SL¯, only 2 out of 6 FO1 variants obtain 100 percent δ-service level while 5 out of 9 FO2 variants can achieve this goal. We find that, for bigger n and k, FO2 tends to achieve a high δ-service level from the column δ-SL¯ of Table 3. Consider rateNOB, which indicates the solution quality by combining rate¯ot and δ-SL¯ in a statistical sense. The results of FO2-n1-Lk (k=1,2,3) imply that there exist solutions without overtime and backlogging for all tested instances, while FO1 obtain solutions at a relative lower rateNOB proportion. We can also observe that for a lower n=n3, FO2-n3-L2 performs better than FO1-P and FO1-R, while other FO2-n3-Lk (k=1,3) perform worse than all the FO1 variants.The three rows entitled “FO-VNS-Lk” of Table 3 report the solution quality of FO-VNS variants with different k. From the results, the three variants of FO-VNS obtain around 4.95%~5.99% better solutions compared with FO1 on the average, and around 3.55%~4.60% compared with the best FO1 significantly, while the computational time can be considerably larger by 172.32%~173.06% and 156.81%~157.50% compared with the average FO1 and the best FO1. However, the S-MICLSP (also S-MICLSP-L) considered in this paper is usually solved weekly or monthly in a tactical decision for a factory of one steel enterprise. It is thus worth spending more but reasonable time to obtain a significantly better production plan by our FO-VNS.The last two rows of Table3 provide comparisons between CPLEX and our proposed algorithms. CPXstd runs the same time limit as FO-VNS but it performs worse than all other algorithms. Running a much longer time limit, CPX30std performs much better. However compared to FO-VNS, the solution quality of CPX30std is slightly improved with an extremely increased computational effort.


## 5.2.2. Computational Results on S-MICLSP-L

The computational results on the S-MICLSP-L model are given in Table4. By the similar observations to Table 3, FO2 still outperforms FO1 in terms of the solution quality. Particularly, FO2-n1-L1 and FO2-n2-L2 outperform all the FO1 variants when considering Cost¯ and Time¯, which implies they make the best trade-off between Cost¯ and Time¯ in all FO2 variants. Similar to Table 3, FO-VNS gives quite outstanding results compared with FO1 and FO2. FO-VNS performs a better Cost¯ by reducing 5.17%~6.16% against FO1-PRT. All of the FO-VNS variants provide δ-SL¯ of 100%, yet FO1 and FO2 fail to do so. The results of the last two rows in Table 4 are similar to Table 3. CPXstd reports its drawbacks in terms of solution quality and computational effort, while CPX30std reports its better solution quality with much longer computational time.Table 4
Computational results on S-MICLSP-L.
Algorithm
C
o
s
t
¯
T
i
m
e
¯
r
a
t
e
¯
o
t
δ
-
S
L
¯
r
a
t
e
N
O
B
FO1-P
727790.95
436.31
15.36
82.41
37.00
FO1-R
741102.74
414.03
20.48
73.96
23.00
FO1-T
717907.32
429.78
14.52
83.69
33.00
FO1-PR
723629.97
442.17
13.00
80.94
45.00
FO1-PT
716389.74
452.53
13.32
87.00
42.00
FO1-PRT
712618.87
474.03
13.00
91.04
46.00
d
e
v
A
v
e
r
a
g
e
C
o
s
t
¯
d
e
v
B
e
s
t
C
o
s
t
¯
d
e
v
A
v
e
r
a
g
e
T
i
m
e
¯
d
e
v
B
e
s
t
T
i
m
e
¯
FO2-n1-L1
−2.40
−0.94
−5.27
−11.77
4.42
96.59
85.00
FO2-n1-L2
−3.17
−1.73
5.20
−2.02
4.20
96.31
87.00
FO2-n1-L3
−3.93
−2.50
13.38
5.59
3.94
95.80
88.00
FO2-n2-L1
−1.10
0.37
−8.28
−14.58
8.90
94.39
63.00
FO2-n2-L2
−2.36
−0.91
0.06
−6.81
8.38
96.03
62.00
FO2-n2-L3
−2.81
−1.36
9.21
1.71
8.00
98.80
68.00
FO2-n3-L1
1.95
3.47
−10.49
−16.63
10.64
85.49
53.00
FO2-n3-L2
0.71
2.22
−3.92
−10.52
9.68
89.13
50.00
FO2-n3-L3
−0.63
0.85
4.70
−2.49
9.00
92.03
56.00
FO-VNS-L1
−6.56
−5.17
172.67
153.95
4.94
100.00
83.00
FO-VNS-L2
−7.32
−5.94
172.74
154.01
4.54
100.00
84.00
FO-VNS-L3
−7.54
−6.16
173.38
154.61
4.02
100.00
84.00
CPXstd
4.14
5.69
172.56
153.84
7.84
93.76
71.00
CPX30std
−8.61
−7.25
8187.93
7618.80
0.00
100.00
90.00According to Tables3 and 4, it can be confirmed that the advantages of FO2 and FO-VNS against FO1 for S-MICLSP-L grow compared with S-MICLSP. For example, FO2-n1-L3 has −3.93% of devAverageCost¯ while it has −3.20% in the S-MICLSP case from Table 3. Also, this FO2 variant can obtain −2.50% of devBestCost¯ while it can obtain 1.77% in the S-MICLSP case from Table 3. This observation can also be found for all variants of FO-VNS.


## 5.2.3. Comparison of Various Cases of Parameter Settings

To check the effectiveness and efficiency of our proposed approaches under various cases of parameter settings, we implement FO1-PRT, FO2-n1-L3, and FO-VNS-L3 (best variants of FO1, FO2, and FO-VNS tested ever) again using test cases of different TBO (time between orders) and ST (setup times). TBO can be computationally defined as the ratio between setup costs and inventory costs (see [28]). Varying different parameters, the results of Table 5 with measurements of Cost¯ and Time¯ are illustrated by groups of combinations of TBOs (low with TBO <2.0, medium with 2.0⩽ TBO <3.0, and high with 3.0< TBO) and STs (low with ST <25, and high with ST ⩾25).Table 5
Computational results with various parameters settings.
Algorithmmodel
TBO
ST
FO1-PRT
FO2-n1-L3
FO-VNS-L3
C
o
s
t
¯
T
i
m
e
¯
d
e
v
C
o
s
t
¯
d
e
v
T
i
m
e
¯
d
e
v
C
o
s
t
¯
d
e
v
T
i
m
e
¯
S-MICLSP
High
High
795664.08
245.51
−2.23
9.96
−4.94
145.95
Low
689240.75
234.44
−1.77
11.57
−4.60
157.29
Medium
High
575783.97
244.29
−1.71
8.03
−4.29
146.78
Low
489240.75
230.71
−1.07
9.63
−2.39
161.63
Low
High
336501.13
237.52
−0.38
2.35
−3.69
152.33
Low
230349.23
229.79
2.19
−4.34
−1.83
162.06
S-MICLSP-L
High
High
817073.11
490.18
−3.08
5.44
−6.39
145.87
Low
712618.87
474.03
−2.50
5.59
−6.16
154.60
Medium
High
576455.47
486.10
−2.00
3.71
−3.45
146.66
Low
502618.87
478.28
−1.16
4.26
−2.77
151.84
Low
High
337218.37
486.34
−0.13
−1.50
−2.50
147.05
Low
251979.47
466.17
0.18
0.57
−1.10
158.21We compare the results in terms of FO1-PRT for the benchmark. From Table5, we can see that for high TBO cases, FO2-n1-L3 and FO-VNS-L3 significantly outperform FO1-PRT in terms of solution quality. These outstanding performances of FO2-n1-L3 and FO-VNS-L3 can also be found in cases of high ST, compared to cases of low ST. Considering cases of high or medium TBO, FO2-n1-L3 and FO-VNS-L3 obtain lower devCost¯ in S-MICLSP-L than that in S-MICLSP. It implies that for high or medium TBO cases, the advantages of FO2 and FO-VNS in S-MICLSP-L grow compared to that in S-MICLSP, which is similar to the previous observations in Section 5.2.2. All of the above results imply that FO2 and FO-VNS are much more effective than FO1 in cases of high or medium TBO and high ST.


## 5.2.4. Comparison with Scenario Methods

Typically, because of the continuous nature of demand uncertainty and the dynamic structure of the problems, multistage stochastic modeling methods can be applied and hence scenario methods are used to approximate the models. This methodology is distinguished from ours and here we numerically compare the difference between them. The methodology using scenario method is denoted by SCNm-BC, where Branch & Cut approach is used to solve the models approximated by scenario method. We generate m realizations of random demand for each period and hence the number of scenarios is mT, where T is the number of periods. We choose m=5,10 for small test cases. Our methodologies are denoted by PWL-FO2 and PWL-FO-VNS, whereby FO2-n1-L3 and FO-VNS-L3 are, respectively, applied.We compare the results in terms of the methodology of PWL-FO2 for the benchmark. From Table6, we can generally see that the methodology of PWL-FO-VNS is competitive with SCN5-BC and SCN10-BC in terms of Cost¯. The entry “∗∗∗∗” indicates that there are no computational results. Since the number of scenarios is growing in size exponentially, it is impossible to compute finalized results in reasonable time even when T is relatively small. Both PWL-FO2 and PWL-FO-VNS are more splendid than SCN5-BC in terms of solution quality. SCN10-BC can obtain better solutions when T=2,3; however the computational time is unacceptable when T=6,10. Our proposed PWL-FO-VNS obtains competitive solution quality against SCN10-BC while the computational efforts are much less. All of the results imply that our proposed approximation method and solving approaches are efficient.Table 6
Computational results compared with scenarios methods.
Methodologymodel
Periods
PWL-FO2
PWL-FO-VNS
SCN5-BC
SCN10-BC
C
o
s
t
¯
T
i
m
e
¯
d
e
v
C
o
s
t
¯
d
e
v
T
i
m
e
¯
d
e
v
C
o
s
t
¯
d
e
v
T
i
m
e
¯
d
e
v
C
o
s
t
¯
d
e
v
T
i
m
e
¯
S-MICLSP
T
=
2
31610.95
6.05
0.65
133.29
4.52
−19.82
−1.81
246.14
T
=
3
52896.83
9.84
−2.67
120.10
1.34
121.28
−2.44
1709.16
T
=
6
106087.66
16.48
−3.03
117.48
−4.13
15134.03
∗
∗
∗
∗
∗
∗
∗
∗
T
=
10
180137.95
27.52
−3.33
116.87
∗∗∗∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
S-MICLSP-L
T
=
2
35294.55
11.06
−2.15
161.47
3.20
−13.05
−1.61
236.42
T
=
3
55840.08
17.84
−2.86
144.40
3.73
207.43
−3.43
2439.68
T
=
6
113090.88
32.39
−3.54
137.08
−4.31
17906.94
∗
∗
∗
∗
∗
∗
∗
∗
T
=
10
195927.06
52.22
−4.02
135.99
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗


## 6. Conclusion

The key contributions and findings of this paper are as follows:(1)
We formulate dynamic S-MICLSP and S-MICLSP-L models mapped to a realistic problem in steel production. We also propose a piecewise linear approximation method to reformulate models that can be solved tractably. This method is novel and can balance the approximated accuracy and computational times. This method can also be extended to other cases such as the lot-sizing problems with substitutions (see [18]) and safety stocks (see [29]).(2)
We present a new fix-and-optimize (FO) approach for both S-MICLSP and S-MICLSP-L which possesses a novel way of decomposing. Our FO decomposes the problems based on the concept of “k-degree-connection” described in Section 3. This decomposition method combines all the information about products, resources, demands, and time periods. Hence, our presented approach is more effective in each iteration. The computational experiments show that our proposed approach outperforms the recent one.(3)
We develop an integrative FO-VNS approach, based on diversifying search space by VNS. The FO-VNS explores more promising regions in each iteration. This approach extends the scope of [25] and can be applied to models with setup carryovers. From numerical results, FO-VNS can obtain solutions with quite high quality by consuming reasonable time in a tactical planning decision, especially in the testing on S-MICLSP-L model.This paper can explore several avenues in future research; for example:(i)
Extend the S-MICLSP and S-MICLSP-L models to the multilevel versions.(ii)
Find a more effective way to construct decomposition frameworks in each iteration.(iii)
Develop a more efficient local search engine for the integrative metaheuristics.



---

*Source: 7209303-2017-04-12.xml*