Constrained multi-item inventory systems with quantity discounts via evolutionary algorithm.

Jucan, Daniela ; Tudose, Lucian ; Bojan, Ioan 等

1. INTRODUCTION

Many models for a single product under a variety of conditions and assumptions have been developed to help managers in charge of inventory to make the decisions about the quantity and the timing of orders. There are many circumstances in which stock items cannot be treated in isolation, including constraints on stock level or investments. Management of a single warehouse inventory system involves coordinating inventory orders in order to minimize costs without exceeding the warehouse capacity and the maximum average inventory investment.

The existent literature tries to solve the problem in two separate cases: all-units discount and incremental discount.

The non stationary ordering policies for multi-item inventory problem with a single resource constraint and all-units quantity discounts is studied in (Guder & Zydiak, 1997). A heuristic method for determining order quantities in an all-unit discount environment with budget constraint is presented in (Madan et al., 1993). (Rubin & Benton, 1993) presented a set of algorithms that collectively find the optimal order quantities for the situations where a buyer considers all-units discounts from multiple suppliers under a variety of constraints, such as limited storage space and restricted inventory budgets. A practical model for ordering in multi-item multi-constraint inventory systems with all-units quantity discount is presented in (Moussourakis & Haksever, 2008).

For the incremental discounts case few articles have been published. (Guder et al., 1994) considered the incremental discounts problem with a single constraint and independent order cycles. (Rubin & Benton, 2003) considered the same problem with multiple constraints such as budgets and space limitation.

2. OPTIMIZATION PROBLEM

Our model refers to a multi-item inventory problem, with limited capacity of warehouse and constraints on investment in inventories. Demand for each item is known and constant and it must be met over an infinite horizon without shortages or backlogging. Replenishments are instantaneous and we assume a zero lead time. The model allows two types of discount schedules: all unit discount schedule and incremental schedule. We assumed that a single supplier exists for each product, some of the suppliers offer all unit discount and the others offer the incremental discount. In an all-units discount schedule the lower unit cost is applied to all of the units in the order, in an incremental discount schedule the discount is applied only to the additional units beyond some breakpoint (Lee & Nahmias, 1993). The objective is to determine the optimal order size ([Q.sub.i.sup.*]) that minimize the total annual cost, which consists of three components: annual purchase cost, annual inventory holding cost and the annual ordering cost. The total cost can be expressed as:

MIN CT = [n.summation over (i=1)][[a.sub.i] x [D.sub.i]/[Q.sub.i] + [W.sub.i] x [D.sub.i]/[Q.sub.i] + 1/2 x [W.sub.i] x [epsilon]] (1)

subject to

[n.summation over (i=1)][d.sub.i] x [Q.sub.i] - D [less than or equal to] 0 (2)

1/2 x [n.summation over (i=1)][W.sub.i] [less than or equal to] C (3)

[Q.sub.i] [greater than or equal to] 0, i = l, ..., n (4)

where:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

[D.sub.i]--annual demand for item i [units/year];

[a.sub.i]--ordering cost for item i [euro/order];

[c.sub.ij]--unit cost for item i within discount interval j [euro/unit];

[d.sub.i]--unit space for item i [[m.sup.2]/unit];

[epsilon]--annual holding rate [euros/(euro x year)]

D--warehouse capacity [[m.sup.2]];

C--maximum of average investment in inventories [euro];

[Q.sub.ij]--quantity of product i within the interval j [units];

[N.sub.ti]--number of discount interval;

n--number of items.

Obviously, the following relationship is valid:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

The first term of the objective function represents the ordering cost, the second term represents the purchasing cost, and the third term is the holding cost. Equation (2) represents the space constraint; equation (3) requires that the average investment in inventories does not exceed a certain amount.

The input data for the optimization problem are presented in table 1 and 2.

Since our model has two types of quantity discounts and we considered constraints on both space and investment we think our model is more difficult to solve. We think that our model presents a more realistic assumption.

3. TWO-PHASE ENHANCED EVOLUTIONARY

ALGORITHM

In solving the optimization problem we used an original two-phase evolutionary algorithm (2PhEA) inspired from the evolutionary concept of "punctuated equilibrium". We think that the high level of stress in the population (which determines sudden and massive changes of the species) is comparable to the effect of constrains of an optimization problem. Therefore, the main idea behind our 2PhEA algorithm is its operation in two phases. In each phase, the individual's fitness is determined by another factor. In Phase 1, the individual's fitness depends only on the way in which an individual is more suitable (or not) in terms of constraints. In this phase, the population "fight for survival" and there is no interest for the best individual. For this reason, the number and level of mutations is high, respectively very high. We thought this phase as some kind of "feasible individual generator". The algorithm moves into the second phase when the number of feasible individuals of the population exceeds a preset threshold. Phase 2 is a common evolutionary algorithm (sometimes a simple genetic algorithm). 2PhEA is implemented in Cambrian v.3 which is in operation at the Optimal Design Centre of the Technical University of Cluj-Napoca, Romania.

4. OPTIMIZATION RESULTS

The results of the optimization are presented in table 3 and table 4. The optimal value of the objective function is CT = 389,607.14 euro.

One can find in the literature (Lee & Nahmias, 1993) that for all-unit discount the optimal [Q.sup.*] must be either the EOQ for some discount level, or one of the breakpoints of some discount interval. This rule stands on only for product 3 even we have all-unit discount for product 1 also. This may be due to the presence of the incremental discount schedule. From the obtained results one can see that the optimum order for product 5 is very low. The two possible reasons are that its unit cost is high and its necessary space for storage is high respectively. It can be seen that the storage capacity is not reached since the investment constraint is more restrictive.

As future research one can think to take into account supplier selection if there are multiple suppliers for each product suppliers with different discount schedules.

Other directions for the future research may be the staggering problem and the JRP with constraints.

5. CONCLUSION

In this paper we presented an application of a two-phase enhanced evolutionary algorithm to an inventory system with two resource constraints and with two types of quantity discounts: all-unit discount and incremental discount.

The obtained results show that the presence of the incremental discount may influence the rule that says that the optimal orders must be either the EOQ for some discount interval, or one of the breakpoints of some discount interval for the all-unit discount schedule.

As future research one can take into account the supplier selection, complete the problem with the staggering aspect and solving Joint Replenishment Problem with constraints.

This work has been supported by the Grant of the Romanian Government PN II CNCSIS ID_593/2009.

6. REFERENCES

Guder, F. & Zydiak, J. L. (1997). Non-stationary ordering policies for multi-item inventory systems subject to a single resource constraint and quantity discounts. Computers & Operations Research, Vol. 24, Issue 1, (January 1997), pp 61-71, ISSN 0305-0548

Guder, F.; Zydiak, J. & Chaudry, S. (1994). Capacitated Multiple Item Ordering with Incremental Quantity Discounts. Journal of the Operational Research Society, Vol. 45, No. 10, pp 1197-1205, ISSN 0160-5682

Lee, H. L. & Nahmias, S. (1993). Single-Product, Single-Location Models, In: Handbooks in OR & MS Vol.2, S.C. Graves et al., (Ed.), pp 11-12, North Holland, ISBN: 0-44487472-0, Amsterdam

Madan, M.; Bramorski, T. & Gnanendran, K. (1993). A heuristic methodology to evaluate price discount structures from the buyer's perspective. International Journal of Production Economics, Vol. 29, Issue 2, (March 1993), pp 223-231, ISSN 0925-273

Moussourakis, J. & Haksever, C. (2008). A Practical Model for Ordering in Multi-Product Multi-Constraint Inventory Systems with All-Units Quantity Discounts. Information and Management Science, Vol. 19, No. 2, pp 263-283, ISSN 1017-1819

Rubin, P. A. & Benton, W. C. (1993). Jointly constrained order quantities with all-units discounts. Naval Research Logistics, Vol. 40, Issue 2, pp 255-278, ISSN 0894-0469X

Rubin, P. A. & Benton, W. C. (2003). Evaluating jointly constrained order quantity complexities for incremental discounts. European Journal of Operation Research, Vol. 149, Issue 3, (September 2003), pp 557-570, ISSN 0377-2217

Tab. 1. Input data for the optimization problem

 i D [a.sub.i] [d.sub.i] [epsilon] D

1 200 500 1 0.2 500
2 300 1,000 2
3 500 1,050 2
4 400 1,200 3
5 100 575 5

Tab. 2. Data for the discount schedules

Item i Discount type Discount interval

1 All unit discount Q < 20
 20 [less than or equal to] Q < 40
 Q [greater than or equal to] 40

2 Incremental discount Q < 40
 40 [less than or equal to] Q < 60
 Q [greater than or equal to] 60

3 All unit discount Q < 30
 30 [less than or equal to] Q < 60
 Q [greater than or equal to] 60

4 Incremental discount Q < 50
 50 [less than or equal to] Q < 75
 Q [greater than or equal to] 75

5 Incremental discount Q < 10
 10 [less than or equal to] Q < 30
 Q [greater than or equal to] 30

Tab. 3. Optimization results

 i Discount interval

 1 2

 [Q.sup.ij] [c.sub.ij] [Q.sup.ij] [c.sub.ij]

1 -- 100 26 98
2 31 200 -- 180
3 -- 300 -- 290
4 39 200 -- 175
5 9 500 5 425

 i Discount interval

 3

 [Q.sup.ij] [c.sub.ij]

1 -- 95
2 -- 150
3 60 280
4 -- 150
5 -- 400

Tab. 4. Optimization results

 i [d.sub.i] [Q.sub.i.sup.*] 0,5 x [summation]
 [summation] [Q.sub.i]
 [W.sub.i] [d.sub.i]

1 1 26 1,274 26
2 2 31 3,100 62
3 2 60 8,400 120
4 3 39 3,900 117
5 5 14 3,312.5 70
Total 19,986.5 395
Constraint 20,000 500