Modeling the Two-Region, Two-Product Capacitated Production and Transportation Problem
Jong Hyup Lee
Dept.of Information and Communications Engineering, Inje University, Gimhae, Republic of Korea
Email address:
To cite this article:
Jong Hyup Lee. Modeling the Two-Region, Two-Product Capacitated Production and Transportation Problem.International Journal of Economics, Finance and Management Sciences.Vol.3, No. 5, 2015, pp. 460-464. doi: 10.11648/j.ijefm.20150305.17
Abstract: In this paper, we examine the problem of establishing minimum cost production and transportation plans that satisfy known demands over a finite planning horizon. Two products, product 1 and 2, can be produced in each of two regions. Each region uses its own facility to supply the demands for two products. Demands for product 2 in one region can be satisfied either by its own production or by transportation from other region, while no transportation between two regions is allowed for product 1. Moreover, the transportation in each period is constrained by a time-dependent capacity bound. Production and transportation costs are assumed to be non-decreasing and concave. Using a network flow approach, properties of extreme points are identified. Then, a dynamic programming algorithm is developed to find an optimal plan.
Keywords: Production Planning, Dynamic Programming, Capacitated Transportation
1. Introduction
In this paper, we consider a production and transportation planning problem for which two production regions are involved with capacity bounds on transportation between them. In each region, a single facility manufactures two items, product 1 and 2, each taking a fixed part of the whole production amount to satisfy its own demands over the discrete periods, . In the problem, we assume that the transportation is allowed only for product 2 from one region to another.
A deterministic production and transportation planning problem for two products that can be produced in each of two regions and transported between two regions was examined in [1]. We extend the approach developed in the previous paper [1] to time-dependent capacity bounds on transportation.
Such a model that multi-products are produced by a facility in each region and some of them can be transported from the other region to meet the demand occurs frequently in manufacturing industries such as chemical industry and machinery (or food) industry. [1]
The problem addressed in this paper is meaningful in that the transportation capacity is additionally considered to impart a sense of reality as an extension of the previous model.
Traditional dynamic lot-sizing models have been considered for solving the production and inventory problems for a long time. Various models have been developed for single and multi-facility problem with a finite planning horizon of T periods. [2-6] Moreover, a lot of papers have been published handling the problems for many different types of production environment. [7-11]
In 1990s, there have been many efforts to resolve the integrated problems considering key business processes of production, storage and distribution, from original suppliers through end users. [12-14] However, they have assumed the cost functions to be linear due to the intrinsic complexity of the concave function. But it is more realistic that the cost functions are assumed to be non-decreasing and concave reflecting the economies of scale. In this paper, based on the traditional dynamic lot-sizing problem, we consider integrated production, inventory and transportation problem. We assume that the cost functions are to be non-decreasing and concave in order to represent the realistic cost functions. Though the problem suggested in this paper does not resolve the general integrated supply chain problem, it is meaningful in respect of applying more realistic cost functions to somewhat simplified supply chain problem. We consider a capacitated production, inventory and transportation planning problem for which two production regions are involved and time-dependent capacity bounds on transportation are imposed. In each region, a single facility manufactures two items (or products) each taking a fixed part of the whole production amount to satisfy its own demands over the discrete periods. In the problem, we assume that the transportation is allowed only for product 2 from one region to another.
2. Model Formulation
The proposed model is formulated using the following parameters, decision variables, and cost functions.
: Demand for product in region at period , where s are positive integers
: Amount of production for product in region at the beginning of period
: Amount of inventory for product in region at the end of period
: Transportation amount of product 2 from region to region at the beginning of period , where = 1, 2 and
: Transportation capacity of product 2 from region to region at the beginning of period , where = 1, 2 and
: Cost of producing at the beginning of period
: Cost of transporting from region to region at the beginning of period
: Inventory holding cost of from period to period
Production, transportation, and inventory holding costs are assumed to be non-decreasing and concave. We can let , for all under the assumption of .
Using the parameters, decision variables, and cost functions, the complete model is presented below.
(PB)
minimize F(z) = +
subject to
(1)
,
(2)
(3)
(4)
(5)
The objective is to minimize the total costs incurred, specifically the production, transportation, and inventory holding costs over all periods.
The equations (1) express that the amount of inventory of product 1 at the end of the period is the remaining one after deleting the demand in a region from the sum of the inventory at the previous period -1 and the production at the period . Similarly, the equations (2) represent the amount of inventory of product 2 at the end of the period . For product 2, we have to reflect the difference between the transportation amount from its own region to another region and the amount transported to the other direction. The constraints (3) imply that the inventories are not allowed both at the initial period and after period T. The constraints (4) specify the bounds on transportation capacities for product 2. The constraints (5) enforce non-negativity restriction for all decision variables. Since the objective function is non-decreasing concave and the constraints (1)-(5) define a closed bounded convex set, there exists an extreme point optimal solution.
3. Solution Approach
3.1. Characterization of an Optimal Solution
To derive the extreme flow properties it is convenient to view the problem (PB) as a network flow problem, as shown in Figure 1.
It can be shown easily that a feasible flow in the network of Figure 1 corresponds to an extreme flow if and only if it does not contain any cycle with positive flows. [16] Furthermore, an extreme flow is composed of some nodes and arcs, where each of the nodes has at most one positive input. [3] These extreme flow properties lead to the following sufficient conditions for an extreme point solution of the given problem:
i.
ii.
iii.
However, the extreme flow property clarified in [3] is for single source networks, so that it is not always satisfied in our model. Therefore, we shall find some additional properties that are useful for our algorithm development.
Let period be called an inventory point if for at least one of both and , that is, . And a production (transportation) point of a schedule in region is defined as a period in which .
And also we can see that a feasible solution and consequently optimal solution will exist if and only if
, for ,
(6)
Henceforth, we shall assume in the remaining part of this paper that the equation (6) is satisfied.
Since the constraints of the problem (PB) define a compact convex set and is concave, the problem then attains its minimum at an extreme point of the set. The constraints can also be shown to be totally unimodular. Thus, a solution search will be processed for extreme point solutions with integer inventories. It will first be discussed about the optimal solution properties, which will be used later for an algorithm development.
Theorem 1 Let and (be the consecutive inventory points. If is an extreme point, then the following properties are satisfied:
i. There exists at most one production point between and (including ) in each region.
ii. There exists at most one partial (positive but less than its capacity) transportation period between and (including ).
Proof of (i). It is identical to (i) in Theorem 1 in [1].
Proof of (ii). Suppose that (ii) does not be satisfied. That is, there exists two periods and () such that , and , (. Therefore, there exists such that
Hence, the following two solutions also satisfy (i) and are feasible:
i. , , and all other variables are identical to those of the original solution.
ii. , , and all other variables are identical to those of the original solution.
Since the original solution is represented in a linear combination of the latter two, each having partial transportations at and , cannot then be an extreme point solution.
The case of which and can also be proved similarly. Thus, the proof is completed.
The results of Theorem 1 lead to Corollary 1, which indicates that any optimal solution does not allow mutual transportation in a period.
Corollary 1 If is an optimal solution, then
Proof. Its proof will be done by contradiction. Assume that . That is, one of the following cases is satisfied:
i. , , for
ii. , , for
iii. , , for
From the proof steps of Theorem 1, we see that any feasible solution including case (i) cannot be an extreme point solution and consequently not be an optimal solution.
In case (ii) and (iii), the following two adjustments are possible for an alternative transportation policy:
a) If , then adjust it as, .
b) If , then adjust it as , .
These adjustments show that and so that the alternative is feasible. By the way, the alternative policy incurs less cost than the original one. This contradicts the hypothesis, so that the proof is completed.
3.2. A Dynamic Programming Approach
We reformulate the problem (PB) as a dynamic programming problem. The approach uses the vector to represent the state space, but at the period , for at least one of both and .
From the totally unimodular property, it follows that an extreme point consists of integer values. Hence, a search for an optimal solution is limited to integer values of that satisfy the conditions, and . Therefore, our goal is to find an optimal sequence of successive inventory points and the associated solutions of the sequence. The minimum cost incurred between any two consecutive inventory points can be computed using the aforementioned properties for extreme points.
Let be the minimal cost between two successive inventory points and . Then, we can define the subproblem value as follows:
(7)
so that
i. Constraints (1)-(5) are satisfied for,
ii. , ,
iii. and are inventory point values, and
iv. and satisfy the properties described in Theorem 1, for all and , .
Constraints (i) require a feasible solution over periods . Constraints (ii) and (iii) state that periods and are two successive inventory points with specified values.
Since all the possible sequence of those subproblems include all the extreme points of the constraints (1)-(5), there exists an optimal solution of (PB) that consists of a sequence of subproblems with values as defined above. The step-by-step procedure to compute each value will be described in detail later in this section.
Let be the cost of optimal policy over periods , given that period is an inventory point with a value . If all values are known, the problem (PB) can be reformulated as a dynamic programming problem:
, ,
(8)
, and , (9)
where is the set of all possible inventory point values at period . The equations (8) and (9) indicate a backward dynamic procedure starting and ending . represents the cost of an optimal solution.
Most of the computational efforts involved in solving the problem (PB) are spent on computing values for each (u-v) subproblem solution. Thus we will concentrate our efforts on solving more efficiently such subproblems.
Let be the production amount of product at facility (i.e., region ), during periods , given and as successive inventory points. Then,
(10)
,
(11)
From the assumption that , for all , we see that , =1, 2. And let be the transportation amount from region to region ( = 1, 2, ) over periods ; that is, . Then equation (11) can be expressed as follows:
(11’)
Since , =1, 2, we can see from (11’) that
(12)
(13)
Subsequently, if the right hand sides of the equation (12) and (13) are not equal, then the subproblem is infeasible. Otherwise the subproblem is feasible. Letting and denote the absolute value of , we can see from Theorem 1 that either or . In other words, if , but , . Further, if any one of and is negative, then the subproblem is also infeasible.
Moreover, suppose that but and 1, 2). Then, or is required to satisfy the demand . However, since , it is required that . This implies that in this case, the production point in region is fixed at period .
These properties lead to the following propositions, which describe the feasible location of a transportation point for a (u-v) subproblem.
Now, consider the additional conditions such that
, for all and (14)
These conditions can make the solution search rather easy. This will be verified in Proposition 1.
Proposition 1 Consider a subproblem satisfying the conditions (14). If any feasible solution satisfies the conditions that and , , , , then it cannot be an optimal solution.
Proof. For the case of in which and , we see from Theorem 1 that is not an extreme point solution.
Consider the other case that and . If , we also see from Corollary 1 that is not an optimal solution. Otherwise, there exists such that , so that a new plan, say , including and is also feasible; , , and all other variables are identical to those of the original solution.
From the new feasible solution , we observe that the inventory holding cost doesn’t change in view of (14) but the transportation cost decreases because of . Therefore, cannot be an optimal solution.
In the case that and (or and ), we can similarly prove that is not an optimal solution. This completes the proof.
The following proposition can be easily showed from Proposition 1.
Proposition 2 If in a (u-v) subproblem, , then for an optimal solution for , , .
Under the assumptions that for all () and the equation (14) holds, the results of Theorem 1, Corollary 1 and Proposition 1 can be applied to solve such subproblems and give the associated values discussed earlier.
The step-by-step procedure to compute each value is presented as follows:
(Step 1) Compute , and decide , . Go to (Step 2).
(Step 2) If in each region only period () can be a candidate for production point, then let () and go to (Step 3). If in region such a period is not specified, fix some period () initially, i.e., . Go to (Step 3). Period will then be moved in turn from to .
(Step 3) Once the production point is fixed at period in region , it follows from Theorem 1 that . For the sake of convenience, we can let . If (> 0), then we need adjust the demands for product 2 in region , where (. There is no loss of generality in assuming (> 0). That is, determine first the periods that can be covered by or and then adjust the demands ’s to give the new demands, , for product 2 in region as follows:
(a)
i. Let and decide such that (). Then, , , where .
ii. Let
If , then , , and .
Otherwise, decide such that , .
Then, , .
iii. The other demands do not be adjusted; that is, , for .
(b)
In this case, we can let and then accomplish the above (Step 3)-ii. It follows that for .
(Step 4) As a matter of fact, the inventory at the end of period can be regarded as the additional demand at period . So, the adjusted demand at period , , must be adjusted once more by adding the inventory . That is, update .
(Step 5) With the adjusted demands for product 2 in region , we can decide the possible transportation amount in each period using Theorem 1, Corollary 1 and Proposition 2. For this step, we can use the shortest route algorithm proposed by Florian and Klien [4], additionally, eliminating vertices having inventory levels indicating infeasibility, i.e., those unsatisfying , . Then, if , for all (), go to (Step 6), otherwise, , that is, is replaced by , and go to (Step 3).
(Step 6) Determine the optimal production and transportation periods and find the associated solution having value represented by the equation (7) among the alternatives obtained by (Step 1)-(Step 4).
4. Concluding Remarks
In this paper, we extended the approach developed in the previous paper [1] to time-dependent capacity bounds on transportation. Using a network flow approach, properties of extreme points were identified. We showed that a production and transportation planning problem for which two production regions are involved with capacity bounds on transportation can be solved optimally using a dynamic programming algorithm. It would be interesting to study the added value of a more general multi-region, multi-product constraints with capacity bounds and more efficient algorithms to find an optimal or near-optimal schedule.
References