## 1. Introduction

Dynamic lot sizing (DLS) is the problem of determining the quantity and timing of ordering items in order to satisfy customer demands over a finite planning horizon. The problem has received a lot of popularity from researchers and practitioners over the last few decades since the first model by Wagner and Whitin (1958) due to its importance as a production and inventory management tool. Therefore, the problem has been extended by considering various practical considerations such as production capacity, inventory capacity, multiple items, remanufacturing, minimum order size, backorder, lost sales , and so on. See Karimi et al. (2003), Brahimi et al. (2006) and Jans and Degraeve (2008) for a review of DLS.

Among the various cases, this paper focuses on DLS with two important practical considerations: minimum order size and lost sales. The minimum order size is the minimum amount of items that should be purchased. In many companies, the minimum size is a common practice, i.e., suppliers may accept any order from customers only if the order size is not less than the minimum order size since it may not be profitable to accept the order if the order size is less than the minimum size. On the other hand, the lost sale is the sales amount lost if enough inventories are not on hand or losing the sales is more economical than selling the items, which can be also commonly found in real practices.

Since comprehensive reviews of DLS are provided in Karimi et al. (2003), Brahimi et al. (2006) and Jans and Degraeve (2008), the literature review in this paper focuses on previous research on the problems with minimum order size or lost sales. To the best of our knowledge, the restriction of minimum order size was first considered by Anderson and Cheah (1993) who consider capacitated multi-item DLS. To solve the problem, they propose a Lagrangian heuristic algorithm in which decomposed problems are DLSs with minimum order size. Merce and Fontan (2003) extended the model of Anderson and Cheah (1993) by considering backorder which is another consequence of running out of stock, i.e., items are back ordered for the customer and the customer waits until the item arrives. To solve the problem, they suggest two heuristic algorithms since their problem belongs to NP-hard. Recently, Okhrin and Richter (2008) consider the problem with the objective of minimizing the number of inventories and suggest a polynomial algorithm. On the other hand, there are several studies considering the problem of lost sales. The problem with lost sales was first considered by Sanbothe and Thompson (1990). They proved that once inventory is zero in a given period, either a part of or the entire of demand for that period must be lost. Based on the property, they suggested a polynomial algorithm and a pseudo polynomial algorithm for the problems with constant and time-variant production capacities, respectively. Later, the same authors extended their previous research by considering inventory capacity and proposing another pseudo polynomial algorithm in Sandbothe and Thompson (1993). However, all cost factors were assumed to be time-invariant in Sandbothe and Thompson (1990, 1993). Therefore, Aksen et al. (2003) considered an uncapacitated problem with time-variant costs and restrictions that the lost sales in a period must not exceed the demand in the period. They showed that losing the demand in a period may incur less cost in spite of non-zero inventory than satisfying the demand, but in that case, the entire demand in the period must be lost. They suggested a polynomial algorithm based on their property similar to the dynamic programming algorithm of Wagner and Whitin (1958). Later, Liu et al. (2007) extended the algorithm of Aksen et al. (2003) by considering the maximum inventory restriction and suggest a polynomial algorithm. Also, Chu and Chu (2007, 2008) considered the model with maximum inventory restrictions but without the restrictions considered in Aksen et al. (2003) and Liu et al. (2007) which stated that the lost sales in a period must not exceed the demand for that period. They showed that the problem can be solvable in polynomial time if inventory holding and lost sales cost functions are linear.

According to the above literature review, there is clearly no previous research considering both the minimum order size and lost sales in DLS, yet these are important real-life considerations. In fact, this paper extends the research result of Aksen et al. (2003) by considering the minimum order size. Note that as in Aksen et al. (2003) and Chu and Chu (2007, 2008), we assume that the lost sale in a period must not exceed the demand in the period. The objective is to minimize the sum of ordering, item, inventory holding, and lost sale costs . To solve the problem, we formulate the problem as an integer programming model and propose a heuristic algorithm by extending the dynamic programming algorithm of Aksen et al. (2003). The performance of the heuristic algorithm is evaluated by randomly generated test instances in this paper.

This paper is organized as follows. The next section provides an integer programming model. Section 3 presents the heuristic algorithm and Section 4 presents the results of computational experiments. Finally, Section 5 concludes this paper by summarizing the research results and providing future research directions.

## 2. Integer Programming Model

The problem considered in this paper can be defined as the problem of determining the quantity and timing of ordering items taking into account both the minimum order size and the lost sales over the finite planning horizon. The objective is to minimize the sum of ordering, item, inventory holding and lost sale costs. The ordering cost is associated with ordering a batch or lot of items and includes typing the purchase order, expediting the order, transportation costs, receiving costs, and so on. As in the other DLSs, it is assumed that the cost does not depend on the number of items purchased, i.e. a fixed cost is charged on any order. The item cost is the cost of buying the individual item proportional to the number of items procured. The inventory holding cost is associated with keeping items in inventory for a specific period of time, which commonly consists of three cost components: capital cost (forgone opportunity cost), storage cost, and costs of obsolescence, deterioration, and loss. The lost sales cost is associated with the revenue lost from not selling the items. All cost factors are assumed to be variable over the planning periods. The other assumptions are summarized as follows: (a) Inventory procurements are assumed instantaneous, and can be available in unlimited amounts in any period since we work on the uncapacitated version of the problem; (b) costs, demand, and minimum order size are given and deterministic; (c) the lost sales cost is higher than the item cost since lost sales correspond to the lost revenue which is not less than cost in common situations. (d) the lost sales in a given period are not more than the demand in that period.

Now, the problem is formulated as an integer programming model as follows and the notations used in the model are summarized below.

*Parameters*

*s _{t}* ordering cost in period t

*c _{t}* item cost in period t

*h _{t}* inventory holding cost in period t

*p _{t}* lost sales cost in period t

*d _{t}* demand in period t

*I*_{0} initial inventory level

*C*_{min} minimum order size

*M* arbitrary large number

*Decision variables*

*I _{t}* inventory level at the end of period t

*L _{t}* lost sale quantity in period t

*X _{t}* purchase quantity in period t

*Y _{t}* 1 if any item is purchased in period t and 0 otherwise

*Integer programming model*

[P] Minimize $\sum _{t=1}^{T}\left({s}_{t}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\cdot \text{\hspace{0.17em}}{Y}_{t}\text{}\text{\hspace{0.17em}}\text{\hspace{0.17em}}+\text{\hspace{0.17em}}\text{\hspace{0.17em}}{c}_{t}\text{\hspace{0.17em}}\cdot \text{\hspace{0.17em}}{X}_{t}\text{\hspace{0.17em}}+\text{\hspace{0.17em}}\text{\hspace{0.17em}}{h}_{t}\text{\hspace{0.17em}}\cdot \text{\hspace{0.17em}}{I}_{t}\text{\hspace{0.17em}}+\text{\hspace{0.17em}}{p}_{t}\text{\hspace{0.17em}}\cdot \text{\hspace{0.17em}}{L}_{t}\right)$

subject to

In the model, the objective function denotes the sum of ordering, item, inventory holding, and lost sales costs. Constraint (1) is the inventory flow conservation in each period. That is, the inventory level at the end of a period is the remaining quantity after satisfying the quantity of demand minus lost sales with the inventories stored in the immediately preceding period and the purchase quantity in that period. Constraint (2) guarantees that the lost sales in a period cannot exceed the demand of the period. Constraint (3) is associated with the minimum order size, i.e., the purchased quantity must be more than or equal to the minimum order size. Constraint (4) represents that the fixed ordering cost is charged if purchasing any item in a period. Finally, constraints (5) and (6) represent the restrictions on decision variables.

## 3. Heuristic Algorithm

This section describes the heuristic algorithm suggested in this paper. The basic idea of the algorithm is similar to that of the well-known Wagner and Whitin (1958) algorithm in that the original problem [P] is decomposed into *T* sub-problems, i.e., *t*-period sub-problems for *t* = 1,2, …, *T* where the *t*-period sub-problem is the problem from periods 1 to *t*. In each sub-problem, we determine the purchase quantity in the last order period and the lost sales quantity and inventory for each period by considering the total costs. Here, the last order period is the period when items are purchased and no items are purchased from the period immediately following to period *t*, i.e., if the last order period is *l*, *Xk* = *0* for *k* = *l*+*1*, *l*+*2*, *…, t*. The idea can be represented by the following dynamic programming model. In the model, *F(t)* denotes the minimum cost of the *t*-period sub-problem, *Fj(t)* denotes the total cost when the last order occurs in period *j*, and the case *j* = 0 implies that all demands from period 1 to *t* are lost.

where *F(-1)* = *F(0)* = *0*. Based on the model, a solution can be obtained by solving sub-problems from periods 1 to *T*. In other words, the model is a forward dynamic programming model.

The method to calculate *Fj(t)* is described below. I(*t, t*) denotes the inventory level in period *t* in the *t*-period sub-problem. *Xj(t, k)* denotes the purchase quantity in period *k, Ij(t, k)* the inventory in period *k,* and *Lj(t, k)* the lost sales quantity in period *k* when the last order occurs in period *j* in the *t*-period sub-problem. In the *t*-period sub-problem, two cases should be considered overall: The entire demand from period 1 to *t* is lost; and some of the demands are satisfied by ordering in a period and the unfulfilled demands are lost. The best is selected among the two cases by comparing their required costs.

First, consider the case in which all demands from period 1 to t are lost. Since all demands are lost, the total cost in this case is the sum of lost sales costs defined as:

To explain the case in which some demands are satisfied from ordering in a period and unfulfilled demands are lost, suppose that the last order occurs in period *j*. Since we need to use the remaining inventory in the *j*-1-period sub-problem, we need to consider the following three cases: 1) when the remaining inventory is enough to satisfy all demands from period *j* to *t*; 2) when the remaining inventory is not enough to satisfy all demands from period *j* to *t* and used to satisfy some of the demands from period *j* to *t* but the unfulfilled demands are not more than the minimum order size; and 3) when the remaining inventory is used to satisfy some of the demands from period *j* to *t* but the unfulfilled demands are more than the minimum order size.

Case 1:

This case implies that the inventory in period *j*-1 in the *j*-1-period sub-problem is sufficient to satisfy all demands from period *j* to *t*. In this case, the total cost *Cj(t)* consists of the minimum cost of the *j*-1-period sub-problem and inventory holding costs due to no need of purchase . The total cost can be represented by

where *Ij(t, j)* = *I(j – 1, j – 1) – dj* and *Ij(t, k)* = *Ij(t, k – 1) – dk* for *k* = *j*+*1*, *j*+*2*,*…,**t*. *Then*, *X0(t, k)* = *L0(t, k)* = *0* for *k* = *j*, *j*+*1*,*…,**t*.

Case 2:

This case implies that the inventory in period *j*-1 in the *j*-1-period sub-problem is not sufficient to satisfy all demands from period *j* to *t*. That is, the unfulfilled demands (after some demands are fulfilled with the inventory in period *j*-1 in the *j*-1-period sub-problem) are not more than all the demands from period *j* to *t*. Therefore, we need to order by the minimum order size in period *j* or lose all the unfulfilled demands. Then, the best is selected among two alternatives. When ordering the minimum order size in period *j*, the corresponding total cost is calculated by:

where *I _{j}*(

*t,j*) =

*I*(

*j*− 1,

*j*− 1) +

*C*

_{min}−

*d*and

_{j}*I*(

_{j}*t,k*) =

*I*(

_{j}*t,k*−1) −

*d*for

_{k}*k*=

*j*+1,

*j*+2,…,

*t*. Then,

*X*(

_{j}*t,j*) =

*C*

_{min},

*X*(

_{j}*t,k*) = 0 for

*k*=

*j*+ 1,

*j*+ 2, …,

*t*, and

*L*(

_{j}*t,k*) = 0 for

*k*=

*j*= 1 …,

*t*. On the other hand, when losing all the unfulfilled demands requires the following total cost,

where index *r* denotes the last period with non-negative inventory remaining after satisfying the demands from period *j* to *r* by the inventory in period *j*-1 of the *j*-1-period sub-problem. That is,

Here,

Finally, the total cost of Case 2 is calculated by *Fj(t)* = *min{A1t(t), A2t(t)}* and the corresponding solution is updated by the solution of the selected alternative.

Case 3:

This case implies that the unfulfilled demands (after some demands are fulfilled with the inventory in period *j*-1 of the *j*-1-period sub-problem) are more than the minimum order size. In this case, we satisfy first some demands with the inventory in period *j*-1 of the *j*-1-period sub-problem. Then, for the unfulfilled demands in some periods, we need to check whether we satisfy or lose the demand in a period by comparing the lost sales cost in the period with the sum of item cost in period *j* and the inventory holding costs from period *j* to the period. That is, if the following cost for period *k* is not positive, we purchase the demand in the period and otherwise, we lose the demand since the negative value of the cost implies that procuring and holding the items is more economical and vice versa.

After checking all periods from *j* to *t* using the just above term, if the demands selected to be ordered are not less than the minimum order size, we lose all of the demands in periods with a positive value of ${c}_{j}+{\displaystyle \sum _{l=j}^{k-1}{h}_{l}}-{p}_{k\cdot}\text{\hspace{0.17em}}$ Then, the total cost is

Here, ${X}_{j}\left(t,j\right)={\displaystyle {\sum}_{k\in \Omega \left(j\right)}{d}_{k}}$ where *Ω*(*j*) implies the set of periods with a non-positive value of ${c}_{j}+{\displaystyle {\sum}_{l=j}^{k-1}{h}_{j}-{p}_{k\cdot}}$ Also, the inventory and lost sales quantity are obtained by the following equations.: In the equations, *Φ*(*j*) implies the set of periods with positive value of ${c}_{j}+{\displaystyle {\sum}_{l=j}^{k-1}{h}_{j}-{p}_{k\cdot}}$

For *k*∈*Φ*(*j*),

where *Rj (t, r* + *1*) = *dr*+*1**–Ij (t, r)*. Unfulfilled demands in period *r*+1 after demands from period *j* to r are fulfilled with the inventory in period *j*-1 in the *j*-1-period sub-problem and period *r* is the period when *Ij(t, r) ≥0* and *Ij(t, r* + *1*) = *Ij(t, r) –dr*+*1 < 0*.

For *k*∈*j,j*+1,…,*t*\*Φ*(*j*),

On the contrary, if the demands selected to be purchased are less than the minimum order size, we need to consider purchasing the demand in periods in set *Φ(j)*. Then, we select the demands with lower cost defined below until the minimum order size is selected, *i.e.,Xj(t,j)* = *Cmin*.

Then, the total cost is

Here, solutions in *Fj(t)* are obtained by following equations. First, the ordering quantity is simply obtained by

On the other hand, the inventory level and lost sales are calculated by considering three subcases for the demand in a period: S1) only ordering; S2) ordering and lost sale occurs at the same time; and S3) only lost sales. Note that there may be a period when ordering and lost sale are incurred at the same time. For simplicity of explanation, let the period be *m* and purchase quantity be *qm*. The inventory and lost sales quantity are obtained by the following equations

Subcase S1: Demand in period *k* is selected to be ordered.

Subcase S2: *k* = *m*, i.e., ordering and lost sales occur at the same time in period *k*.

Subcase S3: Demand in period k is selected to be lost.

Finally, the following procedure summarizes the earlier method. The procedure starts from period *r*+1 when *Ij(t, r) ≥ 0* and *Ij(t, r* + 1) = *Ij(t, r)* –d* _{r+1}* < 0 and unfulfilled demands in period

*r*+1 after demands from period

*j*to r are fulfilled with the inventory in period

*j*-1 in the

*j*-1-period sub-problem is defined as

*Rj (t, r + 1)*=

*dr*+1

*–Ij (t, r)*.

*Step* 1. Set *t* = 1

*Step* 2. Obtain the minimum cost *F(t)* and the last setup period *ls(t)* of the *t*-period sub-problem by

Set the solution as

Here, *Fj(t), Cj(t), Xj(t, k), Ij(t, k),* and *Lj(t, k)* are obtained by the methods described earlier

*Step* 3. Set *t* = *t* + 1. If *t* > *T*, go to Step 4 and go to Step 2, otherwise

*Step* 4. Set *t* = *T*

*Step* 5. Set the solution as

*Step* 6. Set *t* = *ls(t)* – 1. If *t* < 1, stop and go to Step 5, otherwise

## 4. Computational Experiments

To show the performance of the heuristic algorithm suggested in this paper, computational experiments were done on randomly generated test instances. First, the heuristic algorithm was tested on the test instances with various problem sizes, i.e., instances with different numbers of planning periods. Second, the sensitivities of parameter values were analyzed by solving the test instances with different amounts of minimum order sizes, ordering costs, and lost sales costs. Also, a comparative analysis between the heuristic algorithm and the direct implementation of the integer programming model [P] with CPLEX 11.2, a type of commercial integer programming software, was performed for all the test instances with different number of periods and different amounts of parameter values. Also, the heuristic algorithm and program to generate integer programming model were coded in C and the test was done on a personal computer with a Pentium processor operating at 3.0 GHz clock speed.

For the test on the different numbers of periods, 50 test instances were generated randomly, that is, 10 instances for each combination of five levels of the number of planning periods (10, 20, 30, 40, 50). Demands were generated from *DU*(50, 150), where *DU*(a, b) denotes a discrete uniform distribution with range [a, b]. Ordering, item, inventory holding and lost sale costs were generated from *DU*(500, 600), *DU*(10, 12), *DU*(1, 2), and *DU*(15, 17), respectively, and the initial inventory level was set to zero without loss of generality. Also, the minimum order size was set to the average value of demands in all periods according to Merce and Fontan (2003). In the CPLEX tests, to prevent excessive computation, we set a time limit of 3600s (1 hr) and hence the non-optimal solutions (obtained by CPLEX) were compared if no optimal solutions could be obtained within the time limit. The test results are summarized in Table 1 which shows percentage deviations from the CPLEX solutions (optimal or non-optimal solutions) and average computation times. As can be seen in the table, the heuristic algorithm suggested in this paper gave optimal or near-optimal solutions for all test instances within 0.0005 seconds, and 49 test instances were solved optimally by our heuristic algorithm. Also, the number of periods did not affect the computation time of the heuristic algorithm but highly affected that of CPLEX, which indicates that the heuristic algorithm may be a viable tool for practical situations with long planning horizons.

The tests on the effects of minimum order size were performed on the test instances with 50 periods. The minimum order sizes were generated from ⌈ *f*_{1} • *d*̅ ⌉ where ⌈ • ⌉ denotes the smallest integer that is greater than or equal to •, *f1* is the factor used to examine the effects of the amount of minimum order size, and *d*̅ is an average demand. For the test, 50 instances were generated randomly, that is, 10 instances for each combination of five levels of minimum order sizes generated by setting *f1* to 0, 0.5, 1, 5, 10. The other data were generated using the methods described earlier. The test results are summarized in Table 2 above. As can be seen in the table, the heuristic algorithm suggested in this paper gave optimal or near-optimal solutions for all test instances within quite short computation time, while CPLEX requires a high amount of computation time to obtain optimal solutions or even non-optimal solutions. On the other hand, the amount of minimum order size only slightly affected the performance of the heuristic algorithm while it affected that of CPLEX highly. In particular, there may be a tendency for percentage deviation in the heuristic algorithm to increase before and decrease after the minimum order size factor is 5 where the performance of the heuristic algorithm is worst. This can be explained as follows. Since our heuristic algorithm basically extends the optimal algorithm of Aksen *et al.* (2003) who considers the DLS with only lost sales, our heuristic algorithm generates optimal solutions when the minimum order size is zero. Therefore, when the minimum order size is low, the optimal solutions tend to be similar to the optimal solutions for the DLS with only lost sales and hence the heuristic algorithm shows a good performance in this case. On the other hand, when the minimum order size is extremely big, the optimal solutions tend to be simple, infrequent purchase orders, so that optimal solutions can be found in short computation time. The second explanation may also explain the CPLEX results in which the computation time becomes shorter as the minimum order size factor increases.

See the footnotes in Table 1

The tests on the effects of ordering and lost sales costs were also performed on the test instances with 50 periods, respectively. The ordering costs and he lost sales costs were generated from *f2 ·DU* (500, 600) and *f3 ·DU* (16, 30), respectively, where *f2* and *f3* are the factors used to examine the effects of the amounts of ordering costs and the amounts of lost sales costs, respectively. Again, 50 test instances for each of ordering costs and lost sales costs were generated randomly, that is, 10 instances for each combination of five levels of ordering costs were generated by setting *f2* to 0.1, 0.5, 1, 5, 10 and for each combination of five levels of lost sales costs generated by setting *f3* to 0.1, 0.5, 1, 5, 10. The other data were generated using the methods used when testing test instances with different numbers of planning periods. Their test results are summarized in Tables 3 and 4. As can be seen in the tables, the heuristic algorithm suggested in this paper gave optimal or near-optimal solutions for all test instances within quite short computation times. Also, the performance of the heuristic algorithm is not sensitive to the amount of ordering and lost sales costs, which indicates that the heuristic algorithm is a robust tool in real practices regardless of the amount of ordering and lost sales costs. Finally, the heuristic algorithm showed a significantly better performance than CPLEX in terms of computation time.

See the footnotes in Table 1

See the footnotes in Table 1

## 5. Computational Remarks

This paper considered the dynamic lot sizing problem with minimum order sizes and lost sales, which are important considerations in practical situations. The objective is to minimize the sum of ordering, item, inventory holding and lost sale costs over the planning horizon. The problem was formulated as an integer programming model a dynamic program-based heuristic algorithm was created by extending an existing algorithm to consider minimum order size. Results of computational experiments on randomly generated test instances showed that the heuristic algorithm gave good solutions within quite a short computation time, compared to CPLEX, a commercial optimization solver for linear programming models, which took a long time to obtain optimal solutions. Various tests on different planning periods, minimum order sizes, ordering costs, and lost sales costs were performed and their results indicated that the heuristic algorithm is useful from a practical perspective since the performance of the heuristic algorithm was not sensitive to different values of the data.

This research can be extended in several ways. First, though this paper suggests a heuristic algorithm, a complexity analysis of the problem must be done in a future study. Second, it is worthwhile to consider problems with backorder, outsourcing, capacities of inventory and production. Third, uncertainties such as random demand, random capacities, and lead time are needed to be considered in a future study.