Capital flow constrained lot sizing problem with loss of goodwill and loan
Zhen Chen Ren-qian Zhang








zhangrenqian@buaa.edu.cn

[cor1]
Correspondence: Ren-qian Zhang, School of Economics and Management, Beihang University, Beijing 100191, China

School of Economics and Management, Beihang University, Beijing 100191, China



We introduce capital flow constraints, loss of good will and loan to the lot sizing problem. Capital flow constraint is different from traditional capacity constraints: when a manufacturer launches production, its present capital should not be less than its present total production cost; otherwise, it must decrease production quantity or suspend production. Unsatisfied demand in one period may cause customer's demand to shrink in the next period considering loss of goodwill. Fixed loan can be adopted in the starting period for production. A mixed integer model for a deterministic single-item problem is constructed. Based on the analysis about the structure of optimal solutions, we approximate it to a traveling salesman problem, and divide it into sub-linear programming problems without integer variables. A forward recursive algorithm with heuristic adjustments is proposed to solve it. When unit variable production costs are equal and goodwill loss rate is zero, the algorithm can obtain optimal solutions. Under other situations, numerical comparisons with CPLEX 12.6.2 show our algorithm can reach optimal in most cases and has computation time advantage for large-size problems. Numerical tests also demonstrate that initial capital availability as well as loan interest rate can substantially affect the manufacturer's optimal lot sizing decisions.






lot sizing; customer good will; capital flow; profit maximization; loan









§ INTRODUCTION


The lot sizing problem was first introduced and solved by <cit.>. They proposed a polynomial algorithm to solve the single-item uncapacitated deterministic lot sizing problem, which has a computational complexity of O(T^2) and T is the length of planning horizon. <cit.> developed an O(T T) algorithm for the Wagner-Whitin cases. There is now abundant literature in this area that extends the basic model, such as the capacitated lot sizing problem, multi-item lot sizing problem, multi-level lot sizing problem, stochastic lot sizing problem, etc. This has also resulted in the inflation of the problems complexity. Mathematical programming heuristics, Lagrangian relaxation heuristics, decomposition and aggregation heuristics, meta heuristics, problem-specific greedy heuristics, piecewise linear approximation methods are used to solve different lot sizing problems. Some works adopting those methods can be found in <cit.>, <cit.>, <cit.>, <cit.>, <cit.>. Comprehensive reviews on lot sizing problem could be addressed in <cit.>, <cit.>, <cit.>, <cit.>, <cit.>, <cit.>. 

In addition to large amount of papers setting the objective to minimize total cost in the lot sizing problems, there are also some works that formulate profit maximization models. <cit.> developed a forward recursive dynamic programming algorithm to solve a single-item lot sizing problem with immediate lost sales for a profit maximization model. <cit.> investigated the single-item lot sizing problem for a warm/cold process with immediate lost sales and established theoretical results on the structure of optimal solutions.  <cit.> built a multi-product capacitated lot sizing profit maximization model in which there is a negative relation between product price and customer demands. <cit.> also addressed a multi-product capacitated lot sizing problem with pricing, setup time, and more general holding costs. <cit.> studied the scheduling problem with demand choice flexibility and evaluated the efficiency of two mathematical models. However, those works didn't take capital flow constraints in their profit maximization models.

Loss of goodwill has been taken into consideration by some researchers in many inventory models. <cit.> employed goodwill loss in a news vendor model. <cit.> considered loss of goodwill in a deterministic EOQ model and EPQ model respectively. <cit.> assumed supply shortage and time window violation will cause goodwill loss in a production scheduling and vehicle routing problem. In the lot sizing model, the concept of goodwill loss was first introduced by  <cit.>. In the above papers, customer goodwill loss was assumed to result in a penalty cost. Some researchers began to consider that the loss of customer goodwill would manifest itself in terms of reduced future sales. This was first observed by <cit.>. Empirical evidence presented by <cit.> showed that goodwill loss occurred when there were alternative sources of supply for customers, and if there were better alternative sources, the prospect of long-term revenue loss was greater.  <cit.> developed a single-item lot sizing model in which the unsatisfied demand in a given period caused the demand in the next period to shrink due to the loss of customer goodwill. <cit.> addressed the multi-item capacitated lot sizing problem with setup times and lost sales, and they used a Lagrangian relaxation of the capacity constraints to decompose it into single-item uncapacitated sub-problems.

In business transactions, once a manufacturer encounters capital shortage, it needs to borrow money to maintain production; otherwise, it has to reduce or even cancel the production and could not provide sufficient products for their clients. A survey of 531 businesses that went bankrupt during the calendar year 1998 in <cit.> pointed out that inadequate financial planning was one of main reasons for their business failing. A report by <cit.> showed shortage of capital accounted for 17% of company bankruptcies in Australia in 2008. <cit.> found that 84% of high-tech entrepreneurs in the US had experienced a shortage of capital at some time. To deal with capital shortage problem, loan is a widespread and effective option for many companies. After an agreement between a borrower and a lender is made, the borrower receives money from the lender, and is obligated to pay back an equal amount of money with the addition of some interests to the lender at a later time. A survey in <cit.> about Small and medium enterprises (SMEs) in the 28 countries of the European Union showed that SMEs preferred to use bank loan, bank overdraft and trade credit. A report by <cit.> based on the surveys of over 1000 SMEs from 2014 to 2016 in UK revealed that bank loan, friend loan and third party loan together accounted for about 40% — and ranked first — of all external finances in the three years.



Relevant works taking capital flow or financing into account in inventory management problems are the following. <cit.> adopted a news vendor model to analyze the importance of joint consideration of production and financial decisions.  <cit.> investigated a multi period news vendor problem constrained by cash flow and proved the optimality of a base stock policy.  <cit.> extended the model by considering short term financing.  <cit.> built a periodic review inventory problem with working capital constraints, payment delay and multiple sources of financing. The above mentioned works are not for lot sizing problem and there are no fixed ordering costs in their models. Considering capital flow constraints, <cit.> built a single-item lot sizing model with trade credit and apply a dynamic programming algorithm to solve it.

From the literature review above we can find that, most previous works on lot sizing problems seldom consider the influence of capital flow constraints and external financing to production planning. This, together with our discussion on the importance of capital management and widespread use of loan by manufacturers, motivate our study. The main contributions of this paper are the following. 


  * We introduce capital flow constraints to the traditional lot sizing problems and formulate a profit maximization model.

  * Optimality structures of the solution to the problem is discussed, and we develop a polynomial forward recursive algorithm with some heuristic adjustments to solve the problem. 

  * A common supply chain financing behavior, loan, is also introduced and discussed in the lot sizing problem.


The rest of this paper is organized as follows. Section 2 formulates the mathematical model and discusses its NP-hardness. Section 3 gives some mathematical properties and approximates this model to a traveling salesman problem. Section 4 divides the problem into sub-linear problems and proposes an algorithm with some heuristic adjustment techniques. Section 5 implements the numerical analysis: use some numerical cases to show the influence of capital flow constraints; compare the performance of our algorithm on large random generated test cases with CPLEX; analyze the main factors affecting the performance of our algorithm. Finally, section 6 concludes the paper and outlines future research directions.



§ PROBLEM DESCRIPTION




 §.§ Notations and assumptions

We adopt the following notations for our model. Some relevant notations will be introduced when needed. 


t        index of a period, t=1,2,…,T.0 pt5 mm

d_t    demand in period t.

p_t    unit selling price in period t.

c_t    unit production cost (variable cost) in period t.

h_t    unit inventory holding cost in period t.

s_t    production launching cost (fixed cost) in period t.


B_c    quantity of self-owned capital at the beginning of period 1.

B_L    quantity of loan at the beginning of period 1.

B_0    total initial capital at the beginning of period 1 and B_0=B_c+B_L.

I_0    initial inventory level at the beginning of period 1.

T_L    length of loan, T_L≤ T.

r        interest rate of loan.

β    customer goodwill loss rate.

M        a large number.




The decision variables used in the models include the following:


B_t    end-of-period capital for period t.0 pt5 mm

I_t    end-of-period inventory level for period t.

x_t    a binary variable signaling whether the production occurs in period t.

y_t    production quantity in period t.

w_t     demand shortage (lost sales) in period t, and we define w_0=0.

Ed_t    effective demand in period t when considering customer goodwill loss.

v_t     realized demand in period t and v_t= Ed_t-w_t.

δ_t     a binary variable signaling whether Ed_t is positive.




In our problem, we make the following assumptions:

  
  * Initial  capital of period t should not be less than the total production cost in period t, namely, B_t-1≥ s_tx_t+c_ty_t, in which initial capital of period t is B_t-1, and the total production cost in period t is production launching cost s_tx_t plus variable production cost c_ty_t.
  
  * End-of-period capital for each period should be not less than 0, namely, B_t≥ 0.
  
  * Initial inventory of the planning horizon is 0, namely, I_0=0.
  
  * No backorder is allowed.
  
  * The manufacturer could decide the realized quantity for customer's demand without paying penalty cost, but lost sales can cause the shrinking of demand in the next period.
  
  * The manufacturer uses loan in the first period and pays back the principal and interest after a certain length of periods; length of loan is shorter than the length of total planning horizon; mortgages are not required for loan. 


The biggest difference between our problem and traditional lot sizing problem is Assumption <ref> and <ref>: how much to produce is constrained by present capital, and end-of-period capital for each period should be above zero to avoid bankruptcy. Assumption <ref> and <ref> are also the standard assumptions of the Wagner-Whitin model. 
Assumption <ref> means the manufacturer can decide how much products they want to provide for customers. Assumption <ref> defines the loan type in our paper. Loan length is smaller than the total planning horizon because lenders tend to have higher risks for longer loan length and they generally don't provide loan out of the planning horizon in order to reduce risks.   







































 §.§ Mathematical models for our problem


Considering loss of customer goodwill, effective demand is the remnant demand after the goodwill loss from the original demand. As in <cit.>, the effective demand in period t can be represented as:

    Ed_t=max{0,d_t-β w_t-1},  ∀ t.


Eq. (<ref>) is a nonlinear equation. For convenience of computation, we bring several linear constraints to replace this nonlinear equation and construct the mixed integer programming model below.



Model P

    max         B_T-B_c-B_L=∑_t=1^T[p_t(Ed_t-w_t)-(h_tI_t+s_tx_t+c_ty_t)]-B_L (1+r)^T_L

   s.t.                   for t=1,2,…,T 

                                  y_t≤Mx_t,
 
                                 s_tx_t+c_ty_t≤B_t-1,

                                 w_t≤Ed_t,
  
                                 I_t=I_t-1+y_t-Ed_t+w_t,  

                                  B_0=B_c+B_L,

                                 B_t=
 
 B_t-1+p_t(Ed_t-w_t)-h_tI_t-s_tx_t-c_ty_t,     t≠T_L,

 B_t-1+p_t(Ed_t-w_t)-h_tI_t-s_tx_t-c_ty_t-B_L(1+r)^T_L,     t=T_L,

 

                                 d_t≤βw_t-1+Mδ_t, 

                                 d_t≥βw_t-1-M(1-δ_t), 

                                 Ed_t≤d_t-βw_t-1+M(1-δ_t), 

                                Ed_t≥d_t-βw_t-1-M(1-δ_t), 

                                Ed_t≤d_tδ_t, 

                               I_0=0,I_t≥0,
  
                               Ed_t≥0, w_t≥0,y_t≥0,
  
                               x_t∈{0,1}, δ_t∈{0,1}.  


The objective defined by Eq. (<ref>) is to maximize the capital increment from the beginning of the planning horizon to the final period, where the realized sales in period t are given by Ed_t-w_t, revenue in period t is p_t(Ed_t-w_t), total cost in period t is h_tI_t+s_tx_t+c_ty_t, or h_tI_t+s_tx_t+c_ty_t+B_L(1+r)^T_L if period t should pay back the loan.  

Constraint (<ref>) enforces setups with positive production in each period. Constraint (<ref>) represents Assumption <ref> and <ref>:  initial  capital in period t should be not less than the total production cost in period t. It also ensures the non-negativity of B_t-1, which avoids bankruptcy. Constraint (<ref>) ensures that any lost demand w_t in period t not exceed the effective demand of that period. Constraint (<ref>) provides the inventory flow balance equation, and Constraints (<ref>) and (<ref>) define the capital flow balance.

Constraints (<ref>)-(<ref>) are the linear descriptions of Eq. (<ref>). Among them, Constraints (<ref>) and (<ref>) ensure the binarity of δ_t: if d_t≤β w_t-1, δ_t=0 and effective demand Ed_t is also 0, else, δ_t=1 and effective demand Ed_t is positive;  Constraint (<ref>), (<ref>) and (<ref>) determine the value of effective demand Ed_t: if d_t≤β w_t-1, δ_t=0 and Ed_t=0; else, δ_t=1 and Ed_t=d_t-β w_t-1. Constraints (<ref>), (<ref>) and (<ref>) guarantee the non-negativity and binarity of variables. Constraint (<ref>) also represents Assumption <ref> and <ref> in our problem.

Note that if β=0, this model is transformed to a capital flow constrained problem without loss of goodwill.



 §.§ Computational complexity of Model P

The single-item capacitated lot sizing problem has been shown by <cit.> to be NP-hard. As for our problem, the capital flow constraint c_ty_t+s_tx_t≤ B_t-1 is a capacity constraint by removing s_tx_t and replacing B_t-1 with C_t, where C_t is the capacity in period t. Therefore, capital flow constraint is a special type of capacity constraints, and model P is also a NP-hard problem. 



§ MATHEMATICAL PROPERTIES


To describe the mathematical properties of our problem, we first define the concepts of production cycle and production round.



In a production plan, if the manufacturer launches production at the beginning  of period m, and it does not launch new production till the end of period t (m≤ t≤ T), we call period m to period t a production cycle. 



In a production plan, for one or more consecutive production cycles that last from the beginning of m to the end of period t, if initial inventory for period m and end-of-period inventory for period t are zeros, we call period m to period t a production round. 




 §.§ Properties about initial inventory and capital

 
If unit variable production costs are equal, namely, c_t=c, ∀ t, for any production cycle starting at period t+1 (t+1=1,…,T),  the optimal solution satisfies I_t y_t+1=0. 



Lemma 1 is apparently true when t+1=1 because I_0=0. For t+1>1, if there is a solution that does not satisfy Lemma 2, namely, I_t>0 and y_t+1>0, assume that period t+1's former production cycle begins at period m (1≤ m≤ t), and the production cycle beginning at period t+1 lasts till period n (n≤ T). The production plan is shown in Figure <ref>.



According to capital flow balance equation (<ref>), end-of-period capital for period t and period T are given by the following equations.

    B_t   =
    B_m-1+∑_i=m^tp_i(Ed_i-w_i)-s_m-c_my_m-∑_i=m^th_iI_i,     t≠ T_L,
    
    B_m-1+∑_i=m^tp_i(Ed_i-w_i)-s_m-c_my_m-∑_i=m^th_iI_i-B_L(1+r)^T_L,    t=T_L,
    
    
    B_T   =
    
    B_t+∑_i=t+1^T[p_i(Ed_i-w_i)-(h_iI_i+s_iy_i+c_iy_i)],     T≠ T_L,
    
    B_t+∑_i=t+1^T[p_i(Ed_i-w_i)-(h_iI_i+s_iy_i+c_iy_i)]-B_L(1+r)^T_L,    T=T_L.


If the production quantity in period m reduces I_t and the production quantity in period t+1 increases I_t, then the effective demands Ed_i (i=1,…,T) would not be influenced and the production plan is still feasible. B_t and B_T change to the following:

    B_t^'   =B_t+c_mI_t+∑_i=m^th_iI_t,
    
    B_T^'   =B_T+c_mI_t+∑_i=m^th_iI_t-c_t+1I_t.


If unit variable production costs are equal, B_T^'=B_T+∑_i=m^th_iI_t≥ B_T, The final  capital increases. Therefore, I_t>0 and y_t+1>0 is not the optimal solution; optimal solution always satisfies I_ty_t+1=0.


Lemma <ref> is also known as the zero-inventory-ordering policy, which means initial inventory of a production cycle is always zero. Define f_t(I_t-1,B_t-1,w_t-1) as the maximum capital increment during period t, t+1,…,T, given period t's initial inventory I_t-1, initial capital B_t-1, and previous period's demand shortage quantity w_t-1. 

 
For any period t (t=1,…,T), when initial inventory I_t-1 and last period's demand shortage w_t-1 are fixed, f_t(I_t-1,B_t-1,w_t-1) is nondecreasing with period t's initial capital B_t-1. 



To prove this property, we build a dynamic programming model for our problem. For any at period t (t=1,…,T), its states are: initial inventory I_t-1, initial  capital is B_t-1, and demand shortage quantity of previous period w_t-1. Its actions are production quantity y_t and demand realized quantity v_t. Lower bounds for y_t and v_t are both 0; Upper bound for y_t is the maximum production quantity under present capital and upper bound for  v_t is the quantity of effective demand in this period, which are shown by Eq. (<ref>) and Eq. (<ref>), respectively.

    y_t=   max{0,(B_t-1-s_t)/c_t},
    v_t=   max{0,β(d_t-w_t-1)}.


Define a unit step function K(z): K(z)=1 if z>0;  K(z)=0 if z≤ 0. The state transition equations are:

    I_t=   I_t-1+y_t-v_t,
    
    B_t=    
     B_t-1+p_tv_t-h_tI_t-s_tK(y_t>0)-c_ty_t,     t≠ T_L,
    
     B_t-1+p_tv_t-h_tI_t-s_tK(y_t>0)-c_ty_t-B_L(1+r)^T_L,     t=T_L,
     
    
     w_t=   max{0,β(d_t-w_t-1)}-v_t.


The functional equation for dynamic programming is:

    f_t(I_t-1,B_t-1,w_t-1)=max_0≤ y_t≤y_t, 0≤ v_t≤v_t{B_t-B_t-1+f_t+1(I_t,B_t,w_t)},
    
    f_T+1(I_t,B_t,w_t)=0.


when I_t-1 and w_t-1 are fixed, if increasing B_t-1, from Eq. (<ref>) and Eq. (<ref>), the feasible domain for v_t does not change, but the feasible domain for y_t stays constant or expands. There always exists actions y'_t and v'_t that make f'_t(I_t-1,B'_t-1,w_t-1) not lower than f_t(I_t-1,B_t-1,w_t-1). Therefore, f_t(I_t-1,B_t-1,w_t-1) is nondecreasing with B_t-1 with fixed I_t-1 and w_t-1.


 
For any period t (t=1,…,T), if goodwill lost rate is 0, when I_t-1 are fixed, f_t(I_t-1,B_t-1) is nondecreasing with B_t-1. 


The proof is similar to Lemma <ref>. If goodwill shortage rate is 0, demand shortage is not the states of the dynamic programming problem. The actions are still y_t and v_t and state transition equations are Eq.  (<ref>) and Eq. (<ref>). The functional equation changes to be:

    f_t(I_t-1,B_t-1)=max_0≤ y_t≤y_t, 0≤ v_t≤v_t{B_t-B_t-1+f_t+1(I_t,B_t)},
    
    f_T+1(I_t,B_t)=0.


When I_t-1 are fixed and increasing B_t-1, feasible domain for v_t keeps unchanged while feasible domain for y_t stays constant or expands. Therefore, f_t(I_t-1,B_t-1) is nondecreasing with B_t-1.




 §.§ Approximated traveling salesman problem













Define BB_m,n^B_m-1 as the maximum capital increment in a production round from period m to period n with initial capital B_m-1. Based on Lemma <ref>, Lemma <ref> and Lemma <ref>, our problem is approximately transformed to a traveling salesman problem finding the longest route as shown in Figure <ref> (in this case, T=4). Main ideas behind this approximation are that we apply the zero-inventory-ordering policy to divide production plan into several production rounds, and apply Lemma <ref> and Lemma <ref> to always select maximum initial capital for computation of the length of arcs in the traveling salesman problem.



A functional equation is constructed for computation of the problem, and we set B_0^∗=B_0.

    B_n^∗=max_1≤ m< n[B_m-1^∗+BB_m,n^B_m-1^∗],   n=1,2,… T.


Apparently, B_T^∗=max_1≤ m≤ T[B_m-1^∗+BB_m,T^B_m-1^∗]. On this functional equation, we have the following properties.



















If unit variable production costs are equal and goodwill loss rate is 0, for any period t, given end-of-period inventory of period t is 0, the optimal production plan from period 1 to t is part of the optimal production plan from period 1 to T.


If goodwill loss rate and end inventory level for period t are both 0, based on Eq. (<ref>), given initial capital and initial inventory, maximum capital increment during period t to period T is:

    f_t(I_t-1,B_t-1)=B_T-B_t-1=max_0≤ y_t≤y_t, 0≤ v_t≤v_t{B_t-B_t-1+f_t+1(0,B_t)}.


From Lemma <ref>, f_t+1(0,B_t) is a non-decreasing function of B_t, and gets the maximum value when B_t is the maximum end-of-period capital for period t. Given zero end-of-period inventory in period t, this happens when the production plan from period 1 to t is optimal because optimal production plan satisfies zero-inventory-ordering policy when the variable production costs are equal. So, what is optimal for period 1 to period t is also optimal for f_t+1(0,B_t), which is the maximum capital increment during period t+1 to period T.  Therefore, the optimal production plan from period 1 to t is part of the optimal production plan from period 1 to T.



If unit variable production costs are equal and goodwill loss rate is 0, for any two period t_1, t_2 (t_1<t_2), given initial inventory of period t_1 is 0, end-of-period inventory of period t_2 is 0, the optimal production plan from period t_1 to t_2 is part of the optimal production plan from period 1 to T.


By lemma <ref>, the optimal production plan from period 1 to t_1-1 is part of the whole production plan,  and the optimal production plan from period 1 to t_1-1 is also part of the optimal production plan from period 1 to t_2. If the production plan from period t_1 to t_2 is optimal, together with the optimal plan form period 1 to t_1-1, it will result in an optimal production plan from period 1 to t_2 under the zero-inventory-ordering policy. Since the optimal production plan from period 1 to t_2 is part of the whole production plan, the optimal production plan from period t_1 to t_2 is part of the optimal production plan from period 1 to T.




If unit variable production costs are equal and goodwill lost rate is 0, namely, c_t=c, ∀ t, and β=0, B_T^∗=max_1≤ m≤ T[B_m-1^∗+BB_m,T] provides an optimal solution.



When the variable production costs are equal, Lemma <ref> shows the problem satisfies the zero-inventory ordering policy. Hence, the optimal production plan can be a combination of several production rounds. The functional equation (<ref>) in fact enumerates all the possible production rounds.  Lemma <ref> and Lemma <ref> indicate that the optimal production plan in a given production round is part of total optimal production plan. These are the same properties as the Wagner-Whitin case <cit.>. Therefore, for all the combinations of production rounds in the computation of B_T^∗=max_1≤ m≤ T[B_m-1^∗+BB_m,T], the one that gives maximum final capital is the optimal solution. 


When the variable production costs are not all equal, or goodwill loss rate is not 0, the functional equation in Theorem <ref> only gets an approximate solution. However, based on some properties below, we devise some heuristic adjustments to make it close to the optimal solution.



 §.§ Properties for production plan adjustment



In a feasible solution, assume the solution is x_t, y_t, w_t (t=1,2,… ,T). For any two consecutive production cycles, assume the former production cycle begins at period t_1, ends at t_2-1; the latter production cycle begins at period t_2, ends at period t_3, with end-of-period inventory at period t_3 is 0, end-of-period capital at period t_3 is B_t_3 and demand shortage at period t_3 is w_t_3. We can make a production plan adjustment from t^' (t_1+1≤ t^'≤ t_2-1) to t_2-1 if the  capital B_t_3^'≥ B_t_3, shortage quantity w_t_3^'≤ w_t_3 and still with 0 end-of-period inventory in t_3 after this adjustment.



The feasible solution is presented by Figure <ref>. For period t_3+1, its functional equation is

    f_t_3+1(I_t_3,B_t_3,w_t_3)=max_0≤ y_t_3+1≤y_t_3+1, 0≤ v_t_3+1≤v_t_3+1{B_t_3+1-B_t_3+f_t_3+2(I_t_3+1,B_t_3+1,w_t_3+1)}.


From Lemma <ref>, f_t_3+1(I_t_3,B_t_3,w_t_3) is non decreasing with B_t_3 when I_t_3 and w_t_3 are fixed. In the adjustment, I_t_3 are fixed to be 0, after increasing B_t_3 and decreasing w_t_3, the domains for y_t_3+1 and v_t_3+1 both expand from Eq. (<ref>) and Eq. (<ref>). Therefore, the final capital increment is non decreasing with this adjustment. 


The adjustment in Corollary <ref> is shown by Figure <ref>.




In a feasible solution, assume that the solution is x_t, y_t, w_t (t=1,2,… ,T). For any two consecutive production cycles, assume that the former production cycle begins at period t_1, ends at period t_2-1, and the latter production cycle begins at period t_2. If B_t_1-1-s_t_1-c_t_1y_t_1>0, c_t_1+∑_i=t_1^t_2-1h_i<c_t_2, then it is better to move some production amount Δ y_t_2 from y_t_2 to y_t_1 to obtain more final capital.



This heuristic step is shown in Figure <ref>. If B_t_1-1-s_t_1-c_t_1y_t_1>0, production cycle t_1 has residual production capacity, which could produce more. After the moving adjustment, the final  capital changes to the following:

    B_T^'=B_T+(c_t_2-c_t_1-∑_i=t_1^t_2-1h_i)Δ y_t_2.


If c_t_1+∑_i=t_1^t_2-1h_i<c_t_2, this adjustment does not affect the feasibility of the solution and B_T^'>B_T. Therefore, final capital increases.


The moving production amount Δ y_t_2 can be obtained by Eq. (<ref>).


    Δ y_t_2=B_t_1-1-s_t_1/c_t_1-y_t_1.



Eq. (<ref>) is the maximum production quantity increment that cycle t_1 can provide. 





§ SUB-PROBLEMS AND ALGORITHM FOR OUR PROBLEM


For the computation of BB_m,n in the recursive equation (<ref>), we remove the integers of Model P and divide it into sub-linear problems. In the sub-linear variables, only realized demand v_t, ∀ t, are decision variables. We also devise some heuristic techniques to adjust the production plan.



 §.§ sub-linear problems



By definition, BB_m,n is the maximum  capital increment in a production round. Therefore, it may include several production cycles. For a production round with fixed k production cycles, assume the production launching periods are t_1, t_2, …, t_k (for convenience of expression, we set m=t_1, n=t_k+1-1), the production plan is shown in Figure <ref>.



To compute BB_m,n, there are still integer variables δ_t, which is a 0-1 variable indicating whether previous goodwill loss is below effective demand. In Model P-sub1 below, we use a heuristic step by assuming δ_t=1, m≤ t≤ n, namely, all demand from period m to period n are above previous goodwill loss. With known w_t_1-1, we convert Model P to a sub linear problems P-sub1.



Model P-sub1

    max         BB_m,n =max{B_n-B_m-1} 

   s.t.             for t=m,m+1,…,n  

                           c_t_i∑_j=t_i^t_j+1-1v_j+s_t_i≤B_t_i-1,  i=1,2,…,k,

                          B_t≥0,

                          I_t=∑_j=t+1^t_i+1-1v_j,  t_i<t<t_i+1,i=1,2,…,k,

                          B_t=

B_t-1+p_tv_t-(h_tI_t+s_t+c_t∑_j=t_i^t_i+1-1v_j),      t≠T_L,t=t_i,i=1,2,…,k,

B_t-1+p_tv_t-h_tI_t,      t≠T_L,t≠t_i,i=1,2,…,k,



                          B_t=

B_t-1+p_tv_t-(h_tI_t+s_t+c_t∑_j=t_i^t_i+1-1v_j)-T_L(1+L)^L,      t=T_L,t=t_i,i=1,2,…,k,

B_t-1+p_tv_t-h_tI_t-T_L(1+L)^L,      t= T_L,t≠t_i,i=1,2,…,k,




                          I_t_1-1=0, I_t_2-1=0, …, I_t_k-1=0, I_n=0,

                           Ed_t=
max{0,d_t-βw_t-1},  t=t_1,

          
 Ed_t=d_t-β(Ed_t-1-v_t-1),  t≠t_1,

                          0≤v_t≤Ed_t.


The objective function (<ref>) is to maximize capital increment from a production round starting at period m and ending at period n. Constraints (<ref>) and (<ref>) represents our paper's assumptions 1 and 2 about capital flow constraints. Constraint (<ref>) shows the relationship between I_t and v_t. Constraint (<ref>) and Constraint (<ref>) are the capital flow balance. Constraint (<ref>) means that initial inventory and end-of-period inventory of each production cycle are both zeros, which is a heuristic step if unit variable production costs are not equal. Constraints (<ref>) and (<ref>) are expressions of effective demands. Constraint (<ref>) also reflects the heuristic assumption:  δ_t=1, m≤ t≤ n.
Constraint (<ref>) provides the lower and upper bounds of variables v_t, which is realized demand in period t.

If Model P-sub1 does not obtain a feasible solution, this may be related with the heuristic assumption of δ_t. So next step we relax this assumption without loss of goodwill: removing Constraint (<ref>) in Model P-sub1, amending  Constraint (<ref>) to get another sub linear problem P-sub2 below.



Model P-sub2

    max         BB_m,n =max{B_n-B_m-1}<ref>

   s.t.             for t=m,m+1,…,n  

                          (<ref>)–(<ref>)
 
                          0≤v_t≤d_t.

 
Based on the solution of Model P-sub2, compute δ_t according to equations (<ref>) and (<ref>) below.

    w_t   =Ed_t-v_t,   t=m,m+1…,n,
    δ_t   =
    
    0,     if  d_t-β w_t-1<0,t=m,m+1…,n, 
    
    1,     if  d_t-β w_t-1≥ 0, t=m,m+1…,n.


Based on the values of δ_t, another sub linear problem is formulated.



Model P-sub3

    max         BB_m,n =max{B_n-B_m-1}<ref>

   s.t.         for t=m,m+1,…,n  

                          (<ref>)–(<ref>)
 
                        Ed_t=
d_t-β(Ed_t-1-v_t-1),       if δ_t=1,

0,       if δ_t=0,


                        d_t-β(Ed_t-1-v_t-1)<0,    if δ_t=0.


























If Model P-sub1, Model P-sub2 and Model P-sub3 all do not have a feasible solution, we deem BB_m,n does not have a feasible solution and set v_t=0 (t=m,m+1,…,n). The relation of v_t with w_t is provided by Eq. (<ref>). The relation of v_t with y_t is given by Eq. (<ref>).

    y_t=∑_j=t_i^t_i+1-1v_j,     t=t_i, i=1,2,…,k,
    
    0,    t≠ t_i, i=1,2,…,k.




 §.§ Heuristic techniques in recursion and adjustments

It is time consuming and complex to enumerate all the possible production cycles in a production round. Therefore, when customer goodwill loss rate is zero, we use one production cycle in a production round; when goodwill loss rate is not zero, we use at most two production cycles in a production round for computation.  For a certain period t+1 and given production plan from period 1 to period t, two situations are considered in computation of capital increment during a production round when goodwill loss rate is not zero: if there exists no production cycle before t+1, we compute only one production cycle beginning with period t+1 as a production round; if there exists production cycles before t+1, we view the nearest previous production cycle and the production cycle beginning with t+1 together as a production round, and make computations.

After computation of capital increments during production rounds, we can get an approximated production plan from period 1 to any period n (1≤ n≤ T). Based on Corollary <ref>, we make heuristic adjustments to this production plan. Three situations are considered for this adjustment, which are shown by Figure <ref>. In Figure <ref>, period  n's production cycle beginning at period t+1.




  * Figure <ref> means we make adjustments to the first production cycle in the production round m to n: dividing the first production cycle into two cycles by enumerating all new production launching periods between period m to period t; recomputing BB_m,n, and selecting the one which gives maximum capital increment.


  * Figure <ref> means sometimes it's better to launch a new production cycle before period t+1 when there exists no production cycles before it: enumerating all new production launching period between period 1 to period t as m; recomputing BB_m,n and selecting the optimal one.


  * Figure <ref> means sometimes it's better to launch production later if the first production cycle include period 1: enumerating all new production launching period between period 1 to period t as m;  recomputing BB_m,n, and selecting the optimal one that can give maximum capital increment.


In computing BB_m,n for the three heuristic adjustments, a new linear constraint is added to the sub-linear problems: w_n'≤ w_n, which means demand shortage at period n after the adjustment should be not higher than its original value before the adjustment.

If goodwill loss rate is zero, Corollary <ref> is not necessary and there is no need for the adjustments above. After the recursion of BB_m,n till the final period T, a production plan for the the whole planning horizon is obtained. Backward from period T to period 1, check if it satisfies the criteria of Corollary <ref> and make production adjustments. 



 §.§ Computation Algorithm


Based on functional equation (<ref>), sub-linear problems and heuristic techniques, we propose a forward recursive algorithm with heuristic adjustment algorithm (FRH) to solve Model P.



Algorithm FRH for Model P



initialization:  t=1, m=1, 1× T zero matrices x, y, B^∗, T× T zero matrices BB.


Step 1:  For n=t, t+1, …, T, select the production round beginning at m and end at n, compute BB_m,n and record its value in BB(t,n).  

Step 2:  Compute B_t^∗ according to Eq. (<ref>), and obtain the production plan from period 1 to period t: x (1:t), y (1:t), w (1:t).  

Step 3:  Check if the present production plan from period 1 to t meets the three adjustment situations shown by Figure <ref>. If meeting the adjustment criteria, make adjustments and update x (1:t), y (1:t), w (1:t), BB(t,n:T).
 
Step 4:  t=t+1, update m and repeat Step 1 ∼ Step 3 until t=T.

Step 5:  Check if production plan meets Corollary <ref>, if meeting the criteria, make plan adjustments. Obtain final production plan: x (1:T), y (1:T), w (1:T) and final capital B^∗_T.


Flow char of our algorithm is shown by Figure <ref>.





 §.§ Computation complexity of our algorithm

During recursion and heuristic adjustments, when customer goodwill loss rate is zero, there are T(T+1)/2 computations of BB_m,n and BB_m,n includes one sub-linear problem; when customer goodwill loss rate is not zero, in the best case, it is same as the situation when goodwill loss rate is zero: there are no heuristic adjustments meeting Corollary <ref>, and computation of BB_m,n requires only one sub-linear problem. In the worst case, there are 3T(T+1)/2 computation of BB_m,n in total: T(T+1)/2 computations of BB_m,n at first, at most T(T+1)/2 computations of BB_m,n for the heuristic adjustments, and T(T+1)/2 computations of BB_m,n to update BB(t,n:T); each computation of BB_m,n includes 3 sub-linear problems.

Therefore, there are T(T+1)/2 computations of sub-linear problems in the best case and at most 9T(T+1)/2 computations of sub-linear problems in the worst case. The computational complexity of our algorithm is O(T^2ψ), where ψ is the computational complexity of the algorithm for the sub-linear problems. 

Without integer variables, the sub-linear problems can be solved by polynomial interior point algorithm. For the common used polynomial interior point algorithm by <cit.>, ψ is O(T^3.5ℒ), where ℒ denotes the
total length of the binary coding of the input data. This is the reason why we remove integer variables from original mixed integer model and divide it into sub-linear problems. Therefore, total computational complexity of our algorithm is O(T^5.5ℒ), which is a polynomial algorithm.






§ NUMERICAL ANALYSIS

In this section, we first employ some numerical examples to show the influence of initial capital and loan, to the optimal production plan and final capital increment of a manufacturer, and then compare our algorithm with the business software CPLEX. In our numerical experiments, the linear programming algorithm for sub-linear problems is a function in MATLAB based on the paper of <cit.>, which is an interior point algorithm. The solution accuracy of the interior algorithm in MATLAB is controlled by the termination tolerance on the function, which we set as 0.0001%. The number of maximum iterations for interior point algorithm is set to be 50. 

Our algorithm is coded in MATLAB 2016a, and run on a desktop computer with an Intel (R) Core (TM) i5-6500 CPU, at 3.20 GHz, 16GB of RAM, and 64-bit Windows 7 operating system. 



 §.§ Numerical examples about influence of capital flow to production plan


Assume T=12, and goodwill loss rate β=0.5. The values of some other parameters are listed in Table <ref>. 




We solve the problem via our algorithm FRH. The solutions are optimal verified by CPLEX. When initial capital is 150 without loan, the optimal production plan is shown by Figure <ref>, in which the manufacturer could only launch two productions because of capital shortage. When initial capital is 200 without loan, the optimal production plan is shown by Figure <ref>. When initial capital is 200 with  loan quantity 300, loan length 3 periods and loan interest rate 10%, a different optimal production plan is shown by Figure <ref>. Figures in Figure <ref> illustrate that quantity of initial capital and whether or not loan, does influence the optimal production plan of a manufacturer.




Without loan, for different initial capital, maximum final capital increments are displayed by Figure <ref>. With fixed quantity of initial capital 200, fixed quantity of loan 300, loan length 3 periods, for different loan interest rates, maximum final capital increments is displayed by Figure <ref>.

mydata.csv
Initial capital,  Interest rate, Capital increment1, Capital increment2
50, 0.01, 0,2060
150, 0.05, 70,2023
200, 0.1, 1891,1971
250,0.15, 2300,1913
300, 0.2, 2360,1851
350, 0.25, 2360,1784
400,0.3, 2360,1710













In Figure <ref>, the dashed line represents the maximum capital increment without loan. Figure <ref> shows if capital is not sufficient, more initial capital will bring more final capital increment; if capital is sufficient, maximum final capital increment for a manufacturer is stable. Figure <ref> shows loan is helpful for a manufacturer if interest is low; but if interest rate is too high, final capital increment decreases and it is better for the manufacture not to loan. Therefore, the numerical examples above demonstrate initial capital availability as well as loan interest rate can substantially influence the operational decisions for a manufacturer. 



 §.§ Comparison of our algorithm with some other heuristics

To the best of our knowledge, although there are many heuristic algorithms in the literature dealing with capacity constrained lot sizing problems, those algorithms are not suitable for solving capital flow constrained lot sizing problem like ours. Solutions obtained by those algorithms are not feasible by the definition of capital flow constrains in this paper. Compared with traditional capacity constraints, capital flow constraints are stronger constraints which require initial capital of each period is above this period's total production cost, end-of-period capital of each period is above zero, and capital flow is related with many parameters like selling price, interest rate, etc. 

In terms of the comparison of our algorithm with meta heuristics, we attempt to solve our capital flow constrained lot sizing problem with some meta heuristics: genetic algorithm and simulated annealing algorithm. However, because of the capital flow constraints and other constraints, it is difficult for both genetic algorithm and simulated annealing algorithm to obtain a feasible solution even for a small numerical case. Therefore, we omit the comparison of our algorithm with other heuristic algorithms.



 §.§ Comparison of our algorithm with CPLEX on randomly generated problems


We test our algorithm on a large set of randomly generated problems with CPLEX 12.6.2. The solution accuracy of CPLEX is controlled by the number of iterations, CPU seconds and the termination tolerance, which are set as 750,000, 18,000, and 0.0001%, respectively. The randomized scheme of test problem generation is similar to Aksen's work <cit.>, and is presented in Table <ref>. 




Since capital and goodwill loss rate can influence optimal production plan, two initial capital, two initial loan and three goodwill loss rates are set for our experiments, while these three parameters in Aksen's 360 test cases <cit.> are fixed or not included. As for the initial capital, B_c=s_1+c_1(d_1+d_2) guarantees the manufacture has enough capital for the production of first two periods; and B_c=s_1+c_1(d_1+d_2+d_3) guarantees the production of first three periods. There are 864 numerical cases for testing in total. Experimental results for different periods are shown by Table <ref>.





As shown in Table <ref>, our algorithm performs well in the 844 test cases. There are only 57 cases that our algorithm doesn't get optimal solutions. Although there still exist some extreme cases with a maximum deviation 4.56% that our heuristic adjustment could not reach optimal, it could obtain optimal solutions in most cases and average deviation is 0.05%. Another finding of the experiment not shown by Table <ref> but also should be noted is that, when goodwill loss rate is zero and unit variable production costs are equal, our algorithm all obtain optimal solutions, which validates Theorem <ref>.  

In terms of computation time, CPLEX runs faster than our algorithm for small-size problems. However, when problem size grows large, average computation time for CPLEX increase rapidly and is much larger than our algorithm. This is because when T reaches 48, there are some cases that take maximum running time for CPLEX to stop iteration, which boost the average computation time. For the 864 numerical cases, average computation time of FRH algorithm is 19.95s while average computation time for CPLEX is 224.19s.  Therefore, our algorithm is suitable for solving large-size problems.



 §.§ Factors affecting the performance of our algorithm


In the next stage of experiment, we redesign the generation scheme of the test problems to investigate the influence of parameter values to the performance of our algorithm. In order to save computation time for comparison, we set production horizon length T fixed to be 12, initial loan B_L fixed to be 2000, and loaning length L fixed to be 6 in this stage of testing, setup cost s is also set fixed to be 1000. For other parameters, each has 2 generation modes: high fluctuations and low fluctuations with normal distribution, or high values and low values. Details of the generation scheme is displayed by Table <ref>.


lllll
Randomized generation scheme in the second stage of testing

   Low value (fluc.)     High value(fluc.)

Demand D   μ=150, δ=10    μ=150, δ=50

Unit production cost c    μ=13, δ=1    μ=13, δ=5

Unit holding cost h    μ=5, δ=0.5    μ=5, δ=2.5

Selling price p    μ=20, δ=1     μ=20, δ=5

Initial capital B_c    s_1+c_1(d_1+d_2)
   s_1+c_1∑_i=1^5d_i

Interest rate r    2%    5%

Goodwill loss rate β    10%    50%




For each combination of those parameters, we generate 10 numerical cases. Therefore, there are 2^7× 10=1280 cases for testing. Experimental results in this stage are presented by Table <ref>.




From table <ref>, of all the 1280 numerical cases, there are 96 numerical cases that our algorithm can't reach optimal with maximum deviation error 5.91% and average deviation 0.11%. we also find that for goodwill loss rate and initial capital, maximum deviation and average deviation between high and low values differ substantially. It seems goodwill loss rate and initial capital play a main role in affecting the performance of our algorithm. To consolidate this conclusion, we apply stepwise linear regression analysis by SPSS to all the 96 numerical cases that our algorithm has deviations. We set deviation as dependent variable, all the seven parameters as independent variables, confidence interval is 95%. Analysis of variance (anova) is presented by Figure <ref> and excluded variables by stepwise linear regression is given by Figure <ref>.





Figure <ref> shows goodwill loss rate affects deviation the most (significance value 0.001<0.05); initial capital and goodwill loss rate together have significant influence to the deviation error (significance value 0.000<0.05), while other parameters are excluded from regression as shown by Figure <ref>. This coincides with the finding in Table <ref>. The reason could be: if initial capital is low and goodwill loss rate is high, it is more difficult for the heuristic techniques to adjust original solution to optimal. However, experiments in the two stages demonstrate our algorithm can reach optimal in over 90% cases and average deviation of our algorithm is rather low; moreover, when goodwill loss rate is zero and unit variable production are equal, our algorithm can definitely obtain optimal solutions.



§ CONCLUSIONS


Capital shortage is a key factor affecting the growth of many small and medium enterprises. However, capital flow constraints have not been taken into consideration by many lot sizing works. Previous methods such as Wagner-Whitin algorithm <cit.> and Aksen algorithm <cit.> for lot sizing problems can not obtain feasible solutions when considering capital flow constraints under the assumptions in our paper. 

We formulate a mathematical model for the lot sizing problem with capital flow constraints. Loss of goodwill and loan are also introduced in our problem. Based on the mathematical properties of the problem, we develop a forward recursion algorithm with heuristic adjustments. When unit variable productions costs are equal and goodwill loss rate is zero, our algorithm can obtain optimal solutions. Under other situations, its average deviation error is rather low. It is suitable to solve large-size problems for its computational efficiency. We also find initial capital availability and loan interest rate can affect a manufacturer's optimal lot sizing decisions

Future research could extend in several directions: first is considering the multi-item model or the stochastic lot sizing problems with  capital flow constraints; second, other financial behaviors, such as trade credit, inventory financing and factoring business could also be taken into account in the lot sizing problem.











§ REFERENCE








jors
 



