# Optimization on Production-Inventory Problem with Multistage and Varying Demand

Authors: Duan Gang; Chen Li; Li Yin-Zhen; Song Jie-Yan; Akhtar Tanweer
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

This paper addresses production-inventory problem for the manufacturer by explicitly taking into account multistage and varying demand. A nonlinear hybrid integer constrained optimization is modeled to minimize the total cost including setup cost and holding cost in the planning horizon. A genetic algorithm is developed for the problem. A series of computational experiments with different sizes is used to demonstrate the efficiency and universality of the genetic algorithm in terms of the running time and solution quality. At last the combination of crossover probability and mutation probability is tested for all problems and a law is found for large size.


---

## Body

## 1. Introduction

Production-inventory control plays a vital role in the management of manufacturing enterprises. During production process we often hope that the volume of a given product is just enough to satisfy customers’ demand without overextending the production line and manufacturing too many. The redundant inventory will cut down our net profit. On the other hand, lacking supply will also make a heavy loss when a big order is placed. So there must be an optimal production quantity.Many researchers are interested in this problem and it has been investigated from various perspectives. Goyal and Giri [1] develop two different models for the production-inventory problem, in which the demand, production, and deterioration rates of a product are assumed to vary with time over an infinite planning horizon. Shortages of a cycle are allowed to be backlogged partially. Huang [2] proposes an optimal integrated vendor-buyer inventory policy for flawed items in a just-in-time manufacturing environment. The production process is assumed to deteriorate during processing and produces a certain number of defective items. The objective is to minimize the total joint annual costs incurred by the vendor and the buyer. Hill [3] considers the problem of a vendor supplying a product to a buyer with the product manufactured in batches at a finite rate. And the structure of the globally-optimal solution is derived. Gayon et al. [4] formulate the joint production-control and inventory-allocation problem as a Markov decision process and characterize the structure of the optimal policy.  They draw a conclusion that the optimal inventory-allocation policy is a state-dependent multilevel rationing policy, with the rationing level for each class nondecreasing in the number of announced orders. An adaptive control approach with a feedback is applied to track the inventory levels toward their goal levels by Alshamrani [5, 6].Considering uncertainty, Doğru et al. [7] develop a stochastic program to allow preferential component allocation for minimizing total inventory cost in assemble-to-order inventory systems with identical component lead times.  Zijm and Houtum [8] compare the optimal base stock policy under stochasticcircumstance with an MRP systemin terms of cost effectiveness given a predefined target customer service level. And they also take stochasticlead times into consideration in amultistage production-to-ordersystem. According to setting safety lead times, it leads to similar decomposition structures as those derived formultistage inventory systems. Kleywegt et al. [9] formulate the inventory routing problem as a Markov decision process. Gupta and Wang [10] investigate credit terms in inventory problem with random demand. They prove that the structure of the optimal inventory policy is not affected by credit terms under a discrete time of the retailer’s operations, although the value of the optimal policy parameter is.Ouyang et al. [11] address the same problem based on a deterministic model by fuzzifying the rate of interest charges, the rate of interest earned, and the deterioration rate into the triangular fuzzy number. Hsieh [12] proposes two fuzzy inventory models with fuzzy parameters for crisp order quantity, or for fuzzy order quantity under decision maker’s preference. He demonstrates that the optimal order quantity or the optimal fuzzy order quantity of the two models are the real numbers. The optimal solutions can be specified to meet classical production inventory models under a given condition. References [13–16] also focus on the fuzzy optimal inventory problem.Chao et al. [17] research operational decisions in dynamic inventory management are correlated with and constrained by financial flows of the firm. A general framework for incorporating financial states of an organization in multiperiod inventory models with lost sales is proposed. Hopp and Xu [18] propose a static approximation of dynamic demand substitution behavior based on a fluid network model and a service-inventory mapping. The interdependent inventory/service, price, and product assortment decisions in noncompetitive and competitive scenarios with demand substitution are analyzed. Olsen and Parker [19] investigate consumer behavior of potentially leaving the firm’s market when he encounters an inventory stockout at a retailer under the stochastic demand distribution in a time-dynamic context. A single firm and a duopoly case are modeled, respectively.Many researches of perishable inventory problem are investigated. Broekmeulen and Donselaar [20] take into account of the age of the inventory for perishable products at retailers. The new policy they conclude leads to substantial cost reductions compared with a base policy that does not take into account the age of inventories. Duan et al. [21] propose two kinds of inventory models, with and without backlogging, respectively, for perishable items. At last they draw a conclusion that the proposed model is generalization of present ones. Gumasta et al. [22] consider the transportation of perishable goods from distributer to retailer. They simultaneously maximize the revenue and minimize transportation and inventory cost so as to maximize the net profit. Other related researches under stochasticcircumstance can be referenced in [23, 24]. And Markov model for an inventory system with perishable items can be referenced in [25–27] and so on.Some researchers are interested indiscussing backorder problem in inventory.  Yao and Chiang [28] take the storing cost a, backorder cost b, cost of placing an order c, total demand r, order quantity q, and shortage quantity as the triangular fuzzy numbers and use the signed distance method to defuzzify. Gürler et al. [29] consider bayesian updating of demand and backorder distributions in a partial backorder newsvendor model. In order to model the relationship between risks and risk propagation in supply chain, Shin et al. [30] apply bayesian belief network to develop alternative backorder replenishment plan to minimize the total replenishment cost and expected risk cost. Hu et al. [31] and Shahand Soni [32] assume production elapsed time and demand to be a fuzzy random variable with backorder, respectively. We can also refer to [33–38] about backorder aspect.The method for assembly line balancing problem is very similar to the inventory problem. Sotskov et al. [39, 40] minimize the number of stations m for processing n partially ordered operations within the given cycle time. They derive necessary and sufficient conditions when optimality of the line balance b  is stable with respect to sufficiently small variations of the operationtimes. Özcan and Toklu [41–43] and Purnomo et al. [44] research two-sided assembly lines balancing problem. Kellegöz and Toklu [45] address a branch and bound algorithm to solve the problem. Compared with the existing algorithm, the proposed algorithm outperforms it in terms of both CPU times and quality of feasible solutions found.The traditional deterministic inventory models are based on the assumption that the demand rate is constant and order cycle is inflexible. As we all know the total cost is the integral of the production-inventory function because the production time is the same and the maximum inventory in every stage is also equal. But actually there is more than one customer. Demand cycles of these customers are different and the demand rate of every customer is also varying. This is multistage and varying demand production-inventory problem without stockout. In the planning horizon, which is the sum of all stages, what we face to decide is also when and how many quantity to produce in order to minimize the total cost subject to meeting every stage demand. Under the circumstance the traditional unconstrained optimization method is not suitable for the issue although it is still linear. Because according to every demand and its cycle there are different maximum inventory in every stage under different production  schedules which means production frequency and production time. We have to define the maximum inventory in every stage for the sake of obtaining the objective function. And this definition relation is only determined by the constraint. So constrained optimization method will be applied to solve the problem. Motivated by the above case we model a hybrid integer programming to characterize the problem and solve it by using genetic algorithm.The remainder of the paper is organized as follows. Section2 is dedicated to the description of the modeling approach. Section 3 presents a genetic algorithm to solve the problem. Section 4 reports our computational results on test instance. Finally, conclusions are drawn in Section 5.


## 2. Production-Inventory Model

### 2.1. Problem Description

In multistage production-inventory system, every stage extent is versatile, demand rate is also different and production rate is a constant and is more than demand rate in every stage. The production-inventory status is drawn in Figure1 according to the production rate and demand rate in every stage. The planning horizon is made up of five stages. Ti denotes the extent of stage i.  There are twice production in Figure 1. The production mode is as shown in Figure 1(a). The first production begins from Stage 1 and ends in Stage 2 lasting t1 time long. And at time t1 the inventory reaches maximum. The maximum inventory in the first production is consumed in the end of Stage 3. We call it a production cycle from Stage 1 to Stage 3. Stage 3 is called the end of one production cycle. The second production cycle includes Stage 4 and Stage 5 lasting t2 time long. Figure 1(b) depicts another case of twice production. The first production cycle is from Stage 1 to Stage 4 and the second production cycle is in Stage 5 alone.Production-inventory status.
(a)
Twice production
(b)
Another two times productionIn fact there are four production schemes under the circumstance of twice production. Except the above two schemes mentioned, one is that the first production is in Stage 1 alone and the second production starts from Stage 2 to Stage 5. The other is that the first production begins from Stage 1 to Stage 3 and the second production starts from Stage 4 to Stage 5.One extreme case is five times production in planning horizon, that is, production occurs in every stage and the quantity as inventory in every stage only  satisfies the current stage demand. The other extreme case is only once production in planning horizon. The best production times and quantity are specified by the total cost which bears setup cost of production and carrying cost held in inventory. And we will find the best production scheme under all production times.


### 2.2. Model

#### 2.2.1. Denotations Definition

First we define some denotations in our model to express the above conception.Parameters are defined as follows.P: Production rate.n: The extent of stages.m: Production times, m=1,2,…,n.Ti: Demand extent of stage i,i=1,2,…,n.Ri: Demand rate in stage i,i=1,2,…,n.K: Setup cost of production once.h: Holding cost per unit volume per unit time held in inventory.T: Planning horizon. Obviously T equals to the sum of Ti, that is, T=∑i=1nTi.Variables are defined as follows:(2.1)xi={1,if the production begins from stagei,0,otherwise,i=1,2,…,n.tik: The production time of one production cycle which begins from stage i and ends in stage k, 1≤i≤k≤n(2.2)vik={1,iftik>0,0,otherwise,1≤i≤k≤n.Qi: The inventory level at the beginning of stage i,i=1,2,…,nQijk: The maximum inventory level at time tik in stage j, 1≤i≤j≤k≤n. The variable maximum inventory Qijk is positive if and only if tik belongs to the interval (∑l=ij-1Tl,∑l=ijTl)(2.3)wijk={1,ifQijk>0,0,otherwise,1≤i≤j≤k≤n.


#### 2.2.2. Constraints

(1)
Because the stockout is not permitted, the total quantity should be equal to the sum of demands in the planning horizon. And the quantity in every production in a certain stage interval should satisfy the demand in the same stage interval:(2.4)P∑i=1n∑k≥intik=∑i=1nRiTi,(2.5)Ptik=vik∑l=ikRlTl,1≤i≤k≤n.
(2)
Production times in the planning horizon are calculated by the following formula:(2.6)∑i=1nxi=m
(3)
Production time should be less than demand time:(2.7)tik≤∑l=ikTl,1≤i≤k≤n.
(4)
The logic variables should satisfy the following:(2.8)vik=xi(1-Φ(∑l=i+1kxl))xk+1,1≤i≤k≤n.
The binary function Φ(a) is defined as
(2.9)Φ(a)={1,ifa>0,0,otherwise.
Formula (2.8) means vik=1 if and only if xi=1, xk+1=1 and every xl=0,l=i,…,k are met simultaneously.
(5)
The inventory levelQi at the beginning of stage i is derived by the following:
(2.10)Qi=maxl≤j≤k{wijk(Ψ(j-i)∑s=li-1(P-Rs)Ts+Ψ(i-(j+1))∑s=ikRsTs)},
where i≥2,1≤l≤i≤k≤n and
(2.11)Ψ(a)={1,ifa≥0,0,otherwise.
It is the fact that a new production begins in stage i when Qi becomes zero. In other case Qi is always more than zero. When the production time lasts tik time long in a production cycle, the first item Ψ(j-i)∑s=li-1(P-Rs)Ts in formula (2.10) indicates the inventory at the beginning of stage j which is before stage i. And the second item Ψ(i-(j+1))∑s=ikRsTs in formula (2.10) indicates the inventory at the beginning of stage j which is after stage i. For different j and k, the variable wijk may be zero. Only when wijk equals to one, Qi is the right inventory at the beginning of stage i. So we solve it by maximization.
(6)
The relationship between the logic variableswijk and vik and continuous variable tik is characterized as follows:
(2.12)wijk=vikΦ(tik-∑l=ij-1Tl)Ψ(∑l=ijTl-tik),1≤i≤j≤k≤n.
(7)
The maximum inventory levelQijk is deduced according to the following:
(2.13)Qijk=wijk(Qj+(tik-∑l=ij-1Tl)(P-Rj)),1≤i≤j≤k≤n,
(8)
whenwijk=1 and production time is tik, the item (tik-∑l=ij-1Tl)(P-Rj) in formula (2.13) means the new inventory level during stage j. So Qijk is the sum of the inventory Qj at the beginning of stage j and (tik-∑l=ij-1Tl)(P-Rj). At last the variables are defined as:
(2.14)xi,tik,Qi,Qijk≥0,vik,wijk∈{0,1},1≤i≤j≤k≤n.
The initial conditions are t1=0 and S1=Sn+1=0.


#### 2.2.3. Objective

The sum cost holds setup cost of production and carrying cost held in inventory. So the objective is to minimize the sum cost.When producingm times in the planning horizon the total setup cost is mK where K is setup cost producing once. In every production cycle we suppose that production time is tik and wijk=1,1≤i≤j≤k≤n. Then we employ formula (2.4) to formula (2.13) to get the values of Ql and Qijk,1≤i≤j≤k≤n.Q
l and Ql+1 are the inventory levels at the beginning of stage l and stage l+1, respectively. Because the inventory figures from stage i to stage j-1 are all trapezoids. The area of a trapezoid is calculated by (Ql+Ql+1)T/2. In fact the inventory figure of stage i is a triangle for the inventory level Qi is zero such as inventory figure of Stage 1 in Figure 1(b). We may take a triangle as a degenerate trapezoid in which one edge length is zero. So we use uniform area formula. From stage i to stage j-1 when j is more than i, the holding cost is
(2.15)h2∑l=ij-1(Ql+Ql+1)Tl,
where h is holding cost per unit volume per unit time held in inventory.In stagej where production stops the inventory figure is made up of two trapezoids such as the inventory figure of the Stage 3 in Figure 1(b). So the holding cost in stage j is
(2.16)h2((Qj+Qijk)(tik-∑l=ij-1Tl)+(Qijk+Qj+1)(∑l=ijTl-tik)).The case from stagej+1 to stage k is similar to stage i to stage j-1. Therefore, the holding cost from stage j+1 to stage k is
(2.17)h2∑l=j+1k(Ql+Ql+1)Tl.So given production timesm, we could solve the minimal average total cost under every possible production mode in the planning horizon T as
(2.18)min{1T(mK+h2∑i=1n∑j≥i∑k≥jwijk(∑l=ij-1(Ql+Ql+1)Tl+(Qj+Qijk)(tik-∑l=ij-1Tl)+(Qijk+Qj+1)(∑l=ijTl-tik)+∑l=j+1k(Ql+Ql+1)Tl))}.For every possible production timesm, we minimize the average total cost in the planning horizon. So the objective is
(2.19)min1≤m≤nF=min{1T(mK+h2∑i=1n∑j≥i∑k≥jwijk(∑l=ij-1(Ql+Ql+1)Tl+(Qj+Qijk)(tik-∑l=ij-1Tl)+(Qijk+Qj+1)(∑l=ijTl-tik)+∑l=j+1k(Ql+Ql+1)Tl))}.


## 2.1. Problem Description

In multistage production-inventory system, every stage extent is versatile, demand rate is also different and production rate is a constant and is more than demand rate in every stage. The production-inventory status is drawn in Figure1 according to the production rate and demand rate in every stage. The planning horizon is made up of five stages. Ti denotes the extent of stage i.  There are twice production in Figure 1. The production mode is as shown in Figure 1(a). The first production begins from Stage 1 and ends in Stage 2 lasting t1 time long. And at time t1 the inventory reaches maximum. The maximum inventory in the first production is consumed in the end of Stage 3. We call it a production cycle from Stage 1 to Stage 3. Stage 3 is called the end of one production cycle. The second production cycle includes Stage 4 and Stage 5 lasting t2 time long. Figure 1(b) depicts another case of twice production. The first production cycle is from Stage 1 to Stage 4 and the second production cycle is in Stage 5 alone.Production-inventory status.
(a)
Twice production
(b)
Another two times productionIn fact there are four production schemes under the circumstance of twice production. Except the above two schemes mentioned, one is that the first production is in Stage 1 alone and the second production starts from Stage 2 to Stage 5. The other is that the first production begins from Stage 1 to Stage 3 and the second production starts from Stage 4 to Stage 5.One extreme case is five times production in planning horizon, that is, production occurs in every stage and the quantity as inventory in every stage only  satisfies the current stage demand. The other extreme case is only once production in planning horizon. The best production times and quantity are specified by the total cost which bears setup cost of production and carrying cost held in inventory. And we will find the best production scheme under all production times.


## 2.2. Model

### 2.2.1. Denotations Definition

First we define some denotations in our model to express the above conception.Parameters are defined as follows.P: Production rate.n: The extent of stages.m: Production times, m=1,2,…,n.Ti: Demand extent of stage i,i=1,2,…,n.Ri: Demand rate in stage i,i=1,2,…,n.K: Setup cost of production once.h: Holding cost per unit volume per unit time held in inventory.T: Planning horizon. Obviously T equals to the sum of Ti, that is, T=∑i=1nTi.Variables are defined as follows:(2.1)xi={1,if the production begins from stagei,0,otherwise,i=1,2,…,n.tik: The production time of one production cycle which begins from stage i and ends in stage k, 1≤i≤k≤n(2.2)vik={1,iftik>0,0,otherwise,1≤i≤k≤n.Qi: The inventory level at the beginning of stage i,i=1,2,…,nQijk: The maximum inventory level at time tik in stage j, 1≤i≤j≤k≤n. The variable maximum inventory Qijk is positive if and only if tik belongs to the interval (∑l=ij-1Tl,∑l=ijTl)(2.3)wijk={1,ifQijk>0,0,otherwise,1≤i≤j≤k≤n.


### 2.2.2. Constraints

(1)
Because the stockout is not permitted, the total quantity should be equal to the sum of demands in the planning horizon. And the quantity in every production in a certain stage interval should satisfy the demand in the same stage interval:(2.4)P∑i=1n∑k≥intik=∑i=1nRiTi,(2.5)Ptik=vik∑l=ikRlTl,1≤i≤k≤n.
(2)
Production times in the planning horizon are calculated by the following formula:(2.6)∑i=1nxi=m
(3)
Production time should be less than demand time:(2.7)tik≤∑l=ikTl,1≤i≤k≤n.
(4)
The logic variables should satisfy the following:(2.8)vik=xi(1-Φ(∑l=i+1kxl))xk+1,1≤i≤k≤n.
The binary function Φ(a) is defined as
(2.9)Φ(a)={1,ifa>0,0,otherwise.
Formula (2.8) means vik=1 if and only if xi=1, xk+1=1 and every xl=0,l=i,…,k are met simultaneously.
(5)
The inventory levelQi at the beginning of stage i is derived by the following:
(2.10)Qi=maxl≤j≤k{wijk(Ψ(j-i)∑s=li-1(P-Rs)Ts+Ψ(i-(j+1))∑s=ikRsTs)},
where i≥2,1≤l≤i≤k≤n and
(2.11)Ψ(a)={1,ifa≥0,0,otherwise.
It is the fact that a new production begins in stage i when Qi becomes zero. In other case Qi is always more than zero. When the production time lasts tik time long in a production cycle, the first item Ψ(j-i)∑s=li-1(P-Rs)Ts in formula (2.10) indicates the inventory at the beginning of stage j which is before stage i. And the second item Ψ(i-(j+1))∑s=ikRsTs in formula (2.10) indicates the inventory at the beginning of stage j which is after stage i. For different j and k, the variable wijk may be zero. Only when wijk equals to one, Qi is the right inventory at the beginning of stage i. So we solve it by maximization.
(6)
The relationship between the logic variableswijk and vik and continuous variable tik is characterized as follows:
(2.12)wijk=vikΦ(tik-∑l=ij-1Tl)Ψ(∑l=ijTl-tik),1≤i≤j≤k≤n.
(7)
The maximum inventory levelQijk is deduced according to the following:
(2.13)Qijk=wijk(Qj+(tik-∑l=ij-1Tl)(P-Rj)),1≤i≤j≤k≤n,
(8)
whenwijk=1 and production time is tik, the item (tik-∑l=ij-1Tl)(P-Rj) in formula (2.13) means the new inventory level during stage j. So Qijk is the sum of the inventory Qj at the beginning of stage j and (tik-∑l=ij-1Tl)(P-Rj). At last the variables are defined as:
(2.14)xi,tik,Qi,Qijk≥0,vik,wijk∈{0,1},1≤i≤j≤k≤n.
The initial conditions are t1=0 and S1=Sn+1=0.


### 2.2.3. Objective

The sum cost holds setup cost of production and carrying cost held in inventory. So the objective is to minimize the sum cost.When producingm times in the planning horizon the total setup cost is mK where K is setup cost producing once. In every production cycle we suppose that production time is tik and wijk=1,1≤i≤j≤k≤n. Then we employ formula (2.4) to formula (2.13) to get the values of Ql and Qijk,1≤i≤j≤k≤n.Q
l and Ql+1 are the inventory levels at the beginning of stage l and stage l+1, respectively. Because the inventory figures from stage i to stage j-1 are all trapezoids. The area of a trapezoid is calculated by (Ql+Ql+1)T/2. In fact the inventory figure of stage i is a triangle for the inventory level Qi is zero such as inventory figure of Stage 1 in Figure 1(b). We may take a triangle as a degenerate trapezoid in which one edge length is zero. So we use uniform area formula. From stage i to stage j-1 when j is more than i, the holding cost is
(2.15)h2∑l=ij-1(Ql+Ql+1)Tl,
where h is holding cost per unit volume per unit time held in inventory.In stagej where production stops the inventory figure is made up of two trapezoids such as the inventory figure of the Stage 3 in Figure 1(b). So the holding cost in stage j is
(2.16)h2((Qj+Qijk)(tik-∑l=ij-1Tl)+(Qijk+Qj+1)(∑l=ijTl-tik)).The case from stagej+1 to stage k is similar to stage i to stage j-1. Therefore, the holding cost from stage j+1 to stage k is
(2.17)h2∑l=j+1k(Ql+Ql+1)Tl.So given production timesm, we could solve the minimal average total cost under every possible production mode in the planning horizon T as
(2.18)min{1T(mK+h2∑i=1n∑j≥i∑k≥jwijk(∑l=ij-1(Ql+Ql+1)Tl+(Qj+Qijk)(tik-∑l=ij-1Tl)+(Qijk+Qj+1)(∑l=ijTl-tik)+∑l=j+1k(Ql+Ql+1)Tl))}.For every possible production timesm, we minimize the average total cost in the planning horizon. So the objective is
(2.19)min1≤m≤nF=min{1T(mK+h2∑i=1n∑j≥i∑k≥jwijk(∑l=ij-1(Ql+Ql+1)Tl+(Qj+Qijk)(tik-∑l=ij-1Tl)+(Qijk+Qj+1)(∑l=ijTl-tik)+∑l=j+1k(Ql+Ql+1)Tl))}.


## 2.2.1. Denotations Definition

First we define some denotations in our model to express the above conception.Parameters are defined as follows.P: Production rate.n: The extent of stages.m: Production times, m=1,2,…,n.Ti: Demand extent of stage i,i=1,2,…,n.Ri: Demand rate in stage i,i=1,2,…,n.K: Setup cost of production once.h: Holding cost per unit volume per unit time held in inventory.T: Planning horizon. Obviously T equals to the sum of Ti, that is, T=∑i=1nTi.Variables are defined as follows:(2.1)xi={1,if the production begins from stagei,0,otherwise,i=1,2,…,n.tik: The production time of one production cycle which begins from stage i and ends in stage k, 1≤i≤k≤n(2.2)vik={1,iftik>0,0,otherwise,1≤i≤k≤n.Qi: The inventory level at the beginning of stage i,i=1,2,…,nQijk: The maximum inventory level at time tik in stage j, 1≤i≤j≤k≤n. The variable maximum inventory Qijk is positive if and only if tik belongs to the interval (∑l=ij-1Tl,∑l=ijTl)(2.3)wijk={1,ifQijk>0,0,otherwise,1≤i≤j≤k≤n.


## 2.2.2. Constraints

(1)
Because the stockout is not permitted, the total quantity should be equal to the sum of demands in the planning horizon. And the quantity in every production in a certain stage interval should satisfy the demand in the same stage interval:(2.4)P∑i=1n∑k≥intik=∑i=1nRiTi,(2.5)Ptik=vik∑l=ikRlTl,1≤i≤k≤n.
(2)
Production times in the planning horizon are calculated by the following formula:(2.6)∑i=1nxi=m
(3)
Production time should be less than demand time:(2.7)tik≤∑l=ikTl,1≤i≤k≤n.
(4)
The logic variables should satisfy the following:(2.8)vik=xi(1-Φ(∑l=i+1kxl))xk+1,1≤i≤k≤n.
The binary function Φ(a) is defined as
(2.9)Φ(a)={1,ifa>0,0,otherwise.
Formula (2.8) means vik=1 if and only if xi=1, xk+1=1 and every xl=0,l=i,…,k are met simultaneously.
(5)
The inventory levelQi at the beginning of stage i is derived by the following:
(2.10)Qi=maxl≤j≤k{wijk(Ψ(j-i)∑s=li-1(P-Rs)Ts+Ψ(i-(j+1))∑s=ikRsTs)},
where i≥2,1≤l≤i≤k≤n and
(2.11)Ψ(a)={1,ifa≥0,0,otherwise.
It is the fact that a new production begins in stage i when Qi becomes zero. In other case Qi is always more than zero. When the production time lasts tik time long in a production cycle, the first item Ψ(j-i)∑s=li-1(P-Rs)Ts in formula (2.10) indicates the inventory at the beginning of stage j which is before stage i. And the second item Ψ(i-(j+1))∑s=ikRsTs in formula (2.10) indicates the inventory at the beginning of stage j which is after stage i. For different j and k, the variable wijk may be zero. Only when wijk equals to one, Qi is the right inventory at the beginning of stage i. So we solve it by maximization.
(6)
The relationship between the logic variableswijk and vik and continuous variable tik is characterized as follows:
(2.12)wijk=vikΦ(tik-∑l=ij-1Tl)Ψ(∑l=ijTl-tik),1≤i≤j≤k≤n.
(7)
The maximum inventory levelQijk is deduced according to the following:
(2.13)Qijk=wijk(Qj+(tik-∑l=ij-1Tl)(P-Rj)),1≤i≤j≤k≤n,
(8)
whenwijk=1 and production time is tik, the item (tik-∑l=ij-1Tl)(P-Rj) in formula (2.13) means the new inventory level during stage j. So Qijk is the sum of the inventory Qj at the beginning of stage j and (tik-∑l=ij-1Tl)(P-Rj). At last the variables are defined as:
(2.14)xi,tik,Qi,Qijk≥0,vik,wijk∈{0,1},1≤i≤j≤k≤n.
The initial conditions are t1=0 and S1=Sn+1=0.


## 2.2.3. Objective

The sum cost holds setup cost of production and carrying cost held in inventory. So the objective is to minimize the sum cost.When producingm times in the planning horizon the total setup cost is mK where K is setup cost producing once. In every production cycle we suppose that production time is tik and wijk=1,1≤i≤j≤k≤n. Then we employ formula (2.4) to formula (2.13) to get the values of Ql and Qijk,1≤i≤j≤k≤n.Q
l and Ql+1 are the inventory levels at the beginning of stage l and stage l+1, respectively. Because the inventory figures from stage i to stage j-1 are all trapezoids. The area of a trapezoid is calculated by (Ql+Ql+1)T/2. In fact the inventory figure of stage i is a triangle for the inventory level Qi is zero such as inventory figure of Stage 1 in Figure 1(b). We may take a triangle as a degenerate trapezoid in which one edge length is zero. So we use uniform area formula. From stage i to stage j-1 when j is more than i, the holding cost is
(2.15)h2∑l=ij-1(Ql+Ql+1)Tl,
where h is holding cost per unit volume per unit time held in inventory.In stagej where production stops the inventory figure is made up of two trapezoids such as the inventory figure of the Stage 3 in Figure 1(b). So the holding cost in stage j is
(2.16)h2((Qj+Qijk)(tik-∑l=ij-1Tl)+(Qijk+Qj+1)(∑l=ijTl-tik)).The case from stagej+1 to stage k is similar to stage i to stage j-1. Therefore, the holding cost from stage j+1 to stage k is
(2.17)h2∑l=j+1k(Ql+Ql+1)Tl.So given production timesm, we could solve the minimal average total cost under every possible production mode in the planning horizon T as
(2.18)min{1T(mK+h2∑i=1n∑j≥i∑k≥jwijk(∑l=ij-1(Ql+Ql+1)Tl+(Qj+Qijk)(tik-∑l=ij-1Tl)+(Qijk+Qj+1)(∑l=ijTl-tik)+∑l=j+1k(Ql+Ql+1)Tl))}.For every possible production timesm, we minimize the average total cost in the planning horizon. So the objective is
(2.19)min1≤m≤nF=min{1T(mK+h2∑i=1n∑j≥i∑k≥jwijk(∑l=ij-1(Ql+Ql+1)Tl+(Qj+Qijk)(tik-∑l=ij-1Tl)+(Qijk+Qj+1)(∑l=ijTl-tik)+∑l=j+1k(Ql+Ql+1)Tl))}.


## 3. Solution Procedure

We solve the solution by employing Genetic Algorithm (GA). GA is a stochastic search method that works on a population of the solutions simultaneously and searches large and complicated fields based on the mechanics of natural genetics and evolutionary principles. In addition, it is particularly suitable for optimization problems with an objective function subject to numerous constraints. GA has demonstrated considerable success in these optimization problems and received more and more attentions during the past decades.


### 3.1. Chromosome Encoding and Decoding

We encode each chromosome as anm string of integers whose components are the production cycles. Suppose that there are n stages in the planning horizon. We generate m integers ai,i=1,2,…,m randomly to satisfy a1+a2+⋯+am=n. For example, let n=10 and m=4. A chromosome is may be (2 5 1 2). It means there is total 4 times production. The first production cycle is from Stage 1 to Stage 2. The second is from Stage 3 to Stage 7. The third is in Stage 8 alone. And the last production cycle is from Stage 9 to Stage 10.The decoding procedure is as follows. When a chromosome is determined, we could decode this chromosome to getvik first. Then according to formula (2.5) we could obtain tik. By formula (2.10) and formula (2.13) we would find wijk, Qi and Qijk finally.


### 3.2. Crossover

Crossover generates offspring by operating parent chromosomes. Let parameterPc be the crossover probability. A chromosome will be selected as a parent when r<Pc, where r is a random number generated from the interval [0,1]. We apply single parent crossover operator. For a selected parent chromosome with m integers, n1 and n2 are stochastically generated from the interval [1,m] and different. We exchange the value of location n1 and the value of location n2 in the parent chromosome. Figure 2 shows an example. The stochastically generated number is 2 and 3. An offspring (2 1 5 2) is obtained after exchanging 5 and 1. The crossover operator aims to change production scheme under a fixed production times.Figure 2
Example of single parent crossover operating.


### 3.3. Mutation

Mutation modifies a chromosome to form an offspring. Let parameterPm be the mutation probability. A chromosome will be selected as a parent when r<Pm, where r is a random number generated from the interval [0,1]. We randomly choose a location p in a selected chromosome. Then generate an integer stochastically, q, from the interval [1,n]. Then we compare the value of location p in the chromosome and q. For the offspring (2 1 5 2), p is 3 and q is 6. Obviously 5 is less than 6. So we sum the values of right position p and substitute the new sum, 7, for origin value, 5. The case of mutation is depicted in Figure 3(a). If q is less than 5, let the sum of two numbers which are both more than 0 equals to 5. For example, q=2, which is less than 5, we find two numbers a1 and a2 randomly satisfying a1+a2=5. Then a1 and a2 replace 5. The case of mutation is drawn in Figure 3(b) where a1=4 and a2=1. The mutation operator aims to change production times by increasing or decreasing it.Example of mutation operating.
(a)
Case 1:q is more than the value of position p
(b)
Case 2:q is less than the value of position p


### 3.4. Evaluation Function and Selection

Evaluation function is to evaluate the quality of a chromosome. We define evaluation value of a chromosome as the objective function of the corresponding solution.The selection strategy means how to choose the chromosomes in the current population will create offspring for the next generation. We take the roulette wheel as selection mechanism, in which each chromosome is assigned a slice of a circular roulette wheel and the size of the slice is proportional to the chromosome’s evaluation value.


## 3.1. Chromosome Encoding and Decoding

We encode each chromosome as anm string of integers whose components are the production cycles. Suppose that there are n stages in the planning horizon. We generate m integers ai,i=1,2,…,m randomly to satisfy a1+a2+⋯+am=n. For example, let n=10 and m=4. A chromosome is may be (2 5 1 2). It means there is total 4 times production. The first production cycle is from Stage 1 to Stage 2. The second is from Stage 3 to Stage 7. The third is in Stage 8 alone. And the last production cycle is from Stage 9 to Stage 10.The decoding procedure is as follows. When a chromosome is determined, we could decode this chromosome to getvik first. Then according to formula (2.5) we could obtain tik. By formula (2.10) and formula (2.13) we would find wijk, Qi and Qijk finally.


## 3.2. Crossover

Crossover generates offspring by operating parent chromosomes. Let parameterPc be the crossover probability. A chromosome will be selected as a parent when r<Pc, where r is a random number generated from the interval [0,1]. We apply single parent crossover operator. For a selected parent chromosome with m integers, n1 and n2 are stochastically generated from the interval [1,m] and different. We exchange the value of location n1 and the value of location n2 in the parent chromosome. Figure 2 shows an example. The stochastically generated number is 2 and 3. An offspring (2 1 5 2) is obtained after exchanging 5 and 1. The crossover operator aims to change production scheme under a fixed production times.Figure 2
Example of single parent crossover operating.


## 3.3. Mutation

Mutation modifies a chromosome to form an offspring. Let parameterPm be the mutation probability. A chromosome will be selected as a parent when r<Pm, where r is a random number generated from the interval [0,1]. We randomly choose a location p in a selected chromosome. Then generate an integer stochastically, q, from the interval [1,n]. Then we compare the value of location p in the chromosome and q. For the offspring (2 1 5 2), p is 3 and q is 6. Obviously 5 is less than 6. So we sum the values of right position p and substitute the new sum, 7, for origin value, 5. The case of mutation is depicted in Figure 3(a). If q is less than 5, let the sum of two numbers which are both more than 0 equals to 5. For example, q=2, which is less than 5, we find two numbers a1 and a2 randomly satisfying a1+a2=5. Then a1 and a2 replace 5. The case of mutation is drawn in Figure 3(b) where a1=4 and a2=1. The mutation operator aims to change production times by increasing or decreasing it.Example of mutation operating.
(a)
Case 1:q is more than the value of position p
(b)
Case 2:q is less than the value of position p


## 3.4. Evaluation Function and Selection

Evaluation function is to evaluate the quality of a chromosome. We define evaluation value of a chromosome as the objective function of the corresponding solution.The selection strategy means how to choose the chromosomes in the current population will create offspring for the next generation. We take the roulette wheel as selection mechanism, in which each chromosome is assigned a slice of a circular roulette wheel and the size of the slice is proportional to the chromosome’s evaluation value.


## 4. Computational Results

In this section we perform a series of computational experiments to evaluate the GA proposed in Section3 in different size problems. The experiments have been coded in C programming and implemented on an Athlon 3.10 GHz PC, with 3.12 GB of RAM, running on Windows XP.In order to test the efficiency and universality of the GA, we generate four groups of data randomly in which stages are 10, 20, 50, and 100, named problems 1, 2, 3, and 4, respectively. Tables1, 2, 3 and 4 show the exact values of demand extent and demand rate of every problem. The production rate is set as 320 in these problems. The setup cost of production once and holding cost per unit volume per unit time are $2 and $10000, respectively. The parameters in our GA are chosen as follows. The population size PS=30, crossover probability Pc=0.6, and mutation probability Pm=0.5.Table 1
Demand data in Problem 1.
Stage number
1
2
3
4
5
6
7
8
9
10
Demand extent
14
14
12
3
13
17
12
15
7
12
Demand rate
102
73
264
152
119
61
29
292
215
211Table 2
Demand data in Problem 2.
Stage number
1
2
3
4
5
6
7
8
9
10
Demand extent
14
3
11
17
6
15
9
13
16
13
Demand rate
169
60
54
240
246
68
202
18
123
107
Stage number
11
12
13
14
15
16
17
18
19
20
Demand extent
15
4
4
3
8
6
8
5
14
8
Demand rate
24
14
280
48
265
218
216
27
49
22Table 3
Demand data in Problem 3.
Stage number
1
2
3
4
5
6
7
8
9
10
Demand extent
4
14
4
5
4
12
10
7
7
9
Demand rate
229
230
84
263
121
167
254
70
121
188
Stage number
11
12
13
14
15
16
17
18
19
20
Demand extent
13
9
20
20
23
3
7
12
14
9
Demand rate
26
158
233
227
153
146
27
149
280
165
Stage number
21
22
23
24
25
26
27
28
29
30
Demand extent
4
3
6
7
12
9
9
4
6
10
Demand rate
267
194
295
12
224
290
274
77
246
281
Stage number
31
32
33
34
35
36
37
38
39
40
Demand extent
7
12
9
10
13
9
3
7
6
7
Demand rate
167
282
17
184
105
214
37
194
161
161
Stage number
41
42
43
44
45
46
47
48
49
50
Demand extent
6
14
11
3
6
3
6
14
8
13
Demand rate
244
145
144
160
117
173
18
236
268
246Table 4
Demand data in Problem 4.
Stage number
1
2
3
4
5
6
7
8
9
10
Demand extent
4
8
7
14
12
3
12
12
6
13
Demand rate
70
202
53
22
78
231
203
22
219
239
Stage number
11
12
13
14
15
16
17
18
19
20
Demand extent
11
10
10
9
9
6
14
10
7
11
Demand rate
149
23
239
72
231
168
111
234
79
87
Stage number
21
22
23
24
25
26
27
28
29
30
Demand extent
14
12
11
5
9
7
12
3
14
6
Demand rate
203
210
106
145
32
24
136
115
245
93
Stage number
31
32
33
34
35
36
37
38
39
40
Demand extent
11
12
6
4
4
4
13
9
7
10
Demand rate
97
209
289
238
174
114
174
194
124
94
Stage number
41
42
43
44
45
46
47
48
49
50
Demand extent
6
3
8
14
9
13
13
7
13
7
Demand rate
238
149
80
95
93
161
229
58
198
188
Stage number
51
52
53
54
55
56
57
58
59
60
Demand extent
4
8
6
10
6
4
7
4
9
8
Demand rate
242
250
293
159
180
198
185
83
285
262
Stage number
61
62
63
64
65
66
67
68
69
70
Demand extent
8
7
5
7
10
14
8
10
13
4
Demand rate
273
183
228
50
93
211
121
70
78
236
Stage number
71
72
73
74
75
76
77
78
79
80
Demand extent
6
7
9
10
3
4
12
5
5
13
Demand rate
133
218
167
30
127
48
195
222
213
238
Stage number
81
82
83
84
85
86
87
88
89
90
Demand extent
4
10
6
5
4
10
12
11
9
14
Demand rate
22
298
170
28
283
127
72
210
274
59
Stage No.
91
92
93
94
95
96
97
98
99
100
Demand extent
10
8
10
13
3
8
3
7
8
6
Demand rate
75
59
222
202
239
105
113
16
100
299We execute the GA in 30 independent runs on each problem. The evaluation value is recorded for every trial in every problem and shown in Figure4. Table 5 displays the computational results including number of generations, the best found evaluation value, average evaluation value, standard deviation, and average running time for the 30 trials in the four problems. Because the scale of every problem is different, the smaller the problem is the fewer the number of generations is. The results reveal that the proposed GA could effectively solve the problem in different sizes.Table 5
Computational results statistics.
Problem number
1
2
3
4
The number of generations
100
500
1000
2000
The best found evaluation value
1409.4977
1366.0474
1665.7842
1715.5158
The average evaluation value
1411.9887
1417.7661
1695.2008
1746.4505
Standard deviation
1.6308
32.4708
21.1338
13.45
The average running time (sec.)
0.45
1.8
4.22
8.48Figure 4
Computational results.Because the parameters in the proposed GA, crossover probability and mutation probability, play a crucial role of the result, we also test the best combination of the two parameters for all problems. Both crossover probability and mutation probability vary from 0.1 to 0.9 when the step is 0.1. So there are 81 combinations in every problem. The average evaluation value is obtained from 30 independent trials under all combinations. Figure5 displays the comparison results. The best combination is shown as Table 6. It is obvious that the average evaluation value in Table 6 is much better than that in Table 5 for the same problem.Table 6
The best combination of (Pc,Pm).
Problem number
1
2
3
4
The best combination
(0.4, 0.5), (0.9, 0.8)
(0.4, 0.2)
(0.6, 0.1)
(0.6, 0.1)
The average evaluation value
1410.8025
1398.782
1596.6894
1676.5948Comparison results with combination ofPc and Pm.
(a)
For Problem 1
(b)
For Problem 2
(c)
For Problem 3
(d)
For Problem 4For Problem 1 the best combination parameters are (0.4, 0.5) and (0.9, 0.8). This indicates that Problem 1 is not sensitive to the two parameters. Owing to the small size of Problem 1, if the number of generations increases we could find better solution than the former under any combination parameters. For example, when the number of generations reaches 1000, the average evaluation value is 1419.8273 from the 30 trials under the worst combination (0.1, 0.2) whose average evaluation value is 1482.9856 and number of generations is 100 in Figure5(a). At the same time the average running time is only one second.We find a law in Figures5(c) and 5(d) that when given a value of crossover probability, the average evaluation value almost increases with the increase of mutation probability. And we test other experiments generated randomly where stage is from 60 to 90 (in which step is 10) under all combination parameters. The results reflect the same law.  However, it is not the same case in Figures 5(a) and 5(b). This demonstrates that when the problem size is large the mutation probability should be small. So we could only find the best crossover probability. The best combination in Problems 3 and 4 is the same in Table 6. But it is just by chance because in the latter experiments we do not find the same best combination.Table7 reports the partial best solutions and evaluation values found during search under the best combination parameters for the four problems. The stages in a bracket in Table 7 indicate that they are in one continuous production cycle. And the stage which does not appear in Table 7 for every problem means a production cycle. For example, the first production cycle is from Stage 1 to Stage 2 in Problem 2. The second and the third production cycle are in Stage 3 and Stage 4, respectively. And the last production cycle starts from Stage 17 to Stage 20. So there are total twelve production cycles in Problem 2.Table 7
The partial best solutions and evaluation values.
Problem number
The stages in a continuous production cycle
Evaluation value
1
(3, 4), (6, 7), (8, 9)
1409.4977
2
(1, 2), (5, 6), (7, 8), (14, 15, 16), (17, 18, 19, 20)
1332.6984
3
(1, 2, 3), (4, 5), (7, 8), (16, 17), (19, 20), (21, 22, 23, 24), (26, 27, 28), (30, 31), (32, 33), (36, 37), (44, 45), (46, 47), (49, 50)
1487.9055
4
(2, 3), (6, 7, 8), (11, 12), (13, 14), (18, 19), (24, 25), (29, 30),(33, 34), (41, 42),(53, 54), (57, 58), (63, 64), (70, 71),(75, 76), (80, 81), (82, 83, 84), (95, 96, 97, 98)
1584.0483The most cases are that one production cycle includes two stages in Table7. When one production cycle includes two stages, the sum cost is obviously smaller if the demand rate in the first stage is more than that in the second stage. So we can conclude from Table 7 that all demands rate of two successional stages in one production cycle satisfy the above condition. There is similar regular pattern for demands rate of three and four successional stages in one production cycle except a case in Problem 2 from Stage 14 to Stage 16. For demand rate in Stage 1 is almost equivalent to that in Stage 2 in Problem 3, we consider that it does not violate the rule. The demand rate in Stage 14 in Problem 2 is much less than those in the next two stages, but the three stages are still included in one production cycle. The main reason is that the demand extent in Stage 14 is very short (only 3).  Among the four problems, the maximum number of stages included in a continuous cycle are four, whereas the last three problems it occurs only once. And demand rate in the first stage is greater than the sum of those in the latter three stages in Problem 2 and 4.By increasing the number of stages and demands rate, the total cost must increase. But the average cost may not always be so. Although the stage number in Problem 2 is twice of it in Problem 1 and the demand rate in Problem 2 is also more than that in Problem 1, the average cost of Problem 2 is less than that of Problem 1. This suggests that the best production mode (production times and volume of production) could reduce the average cost. So the total cost must  cut down.


## 5. Conclusion

In this paper it is found that the efficient and effective production-inventory strategy could reduce unnecessary funding, inventory cost, and production cycle. Furthermore, the production-inventory problem with multistage and varying demands, in which every stage extent is different, is investigated. Moreover, we generate a hybrid integer model to optimize the production-inventory process and a GA to find a better solution. Computational results illustrate that the proposed GA yields a high-quality solution relatively fast. According to the tests of combination parameters we find the law between the average evaluation value and mutation probability under the large size.



---

*Source: 648262-2012-11-13.xml*