International Journal of Economics, Finance and Management Sciences
Volume 3, Issue 5, October 2015, Pages: 460-464

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

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

Contents

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.

Figure 1. A Network Representation.

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

1. Jong Hyup Lee, Jung Man Hong,"Two product, two region production, inventory, and transportation",International Journal of Economics, Finance and Management Sciences, 2014; 2(6), pp.313-318, 2014.
2. H. M. Wagnerand T. M. Whitin, "Dynamic Version of the Economic Lot Size Model", Management Science,vol. 14, pp.429-450, 1968.
3. W. I.Zangwill, "Minimum Concave Cost Flows in Certain Network", Management Science,vol. 14, pp.429-450, 1968.
4. M. Florian and M. Klein, "Deterministic Production Planning with Concave Costs and Capacity Constraints", Management Science,vol. 18, pp.12-20, 1971.
5. C. S.Sung, "A Production Planning Model for Multi-Product Facilities" Journal of the Operations Research Society of Japan,vol. 28,no. 4, pp.345-358, 1985.
6. H.Luss, "A Capacity-Expansion Model for Two Facility Types", Naval Research Logistics Quarterly,vol. 26, pp.291-303, 1979.
7. Nafee Rizk and Alain Martel,"Supply Chain Flow Planning Methods: A Review of the Lot-Sizing Literature", Working Paper DT-2001-AM-1, Centre de recherche sur les technologies de l’organisation réseau (CENTOR), Université Laval, QC, Canada, January 2001.
8. B. Karimi, S.M.T. Fatemi Ghomi,andJ.M. Wilson,"The capacitated lot sizing problem: a review of models and algorithms", The International Journal of Management Science, Omega 31,pp.365-378, 2003.
9. Lisbeth Buschkuhl, Florian Sahling, Stefan Helber, and Horst Tempelmeier,"Dynamic capacitated lot-sizing problems: a classification and review of solution approaches", OR Spectrum, vol. 32, pp.231-261, 2010.
10. A.Clark, B.Almada-Lobo,andC.Almeder,"Lot sizing and scheduling: industrial extensions and research opportunities", International Journal of Production Research, vol.49,pp.2457 2461,2011.
11. Endy Suwondo and Henry Yuliando,"Dynamic Lot-Sizing Problems: A Review on Model and Efficient Algorithm", Agroindustrial Journal,vol. 1,issue 1, pp.36-49,2012.
12. Adulyasak, Yossiri, Jean-Francois Cordeau, and Raf Jans, "The Production Routing Problem: A Review of Formulations and Solution Algorithms", Computers & Operations Research, available online 7 February 2014.
13. L.C.Coelho, J.-F.Cordeau, G.Laporte,"The inventory-routing problem with transshipment", Computers and Operations Research,vol. 39, pp. 2537-2548,2012.
14. D.Ozdemir, E.Yucesan, Y.T.Herer,"Multi-location transshipment problem with capacitated production", European Journal of Operational Research,vol. 226, pp. 425-435,2013.
15. A. J. Hoffman and J. B. Kruskal, "Integral Boundary Points of Convex Polyhedra", in H. W. Tucker (eds.) Linear Inequalities and Related Systems, Annals of Mathematics Study,no. 38, Princeton Univ. Press, Princeton, New Jersey, pp.233-246, 1956.
16. G. B. Danzig, "Linear Programming and Extensions", Princeton Univ. Press, Princeton, N. J., 1963.

 Contents 1. 2. 3. 3.1. 3.2. 4.
Article Tools