A Multilocation Inventory Model and its Parallel Heuristic Optimization

Yuefan Deng and Yuan Wang
Center for Scientific Computing, SUNY at Stony Brook
Yuefan.Deng@sunysb.edu
YWang@ams.sunysb.edu

Abstract

A stochastical inventory model with networked multilocation and its optimization on distributed-memory MIMD parallel computers are developed. The parallel heuristic algorithm, based on a Markovian decision approach and genetic algorithm in this study, can solve for our model with 2000 locations at nearly perfect speedup. Parallel computer makes it feasible to solve such a problem of application values.

The model concerns the determination of the initial order quantity, re-order level and redistribution of the product so as to maximize the total profit. Initially, the product is delivered to all N locations which can then redistribute among themselves by paying the setup and shipment expenses. In the redistribution, the product arrives in a batch from other locations. The ordered product which arrives after the end of the pre-determined waiting period will be treated as leftovers and sold at a lower price.

At the i location, let , and be the selling, buying, and salvage prices of unit product; , and be the expected demand, unit holding cost, and shortage penalty cost per unit time; and be the initial order quantity and re-order level, respectively. From i location to j location, let , and be the redistribution, setup cost, and unit product shipment cost, respectively. Let T be the interval of a period for inventory checking. , the demand, is a random variable with a distribution function , which is the probability that the demand is m units during the interval of time x. , the delivery lag, is a random variable with a probability density function .

In our model, the total profit, C(Q, L, q), consists of six components: the expected cost or revenue in buying , in holding , in shortage , in salvage , in selling , and in redistribution . We define:

;

, where the expected holding is

and

, where the expected shortage is

, where the expected number of the product which cannot arrive before the end of a period is

;

.

The service rate is defined as

The problem is concluded into a nonlinear programming model, Maximize C(Q, L, q) subject to and nonnegative variables, where S(x) is a prescribed service rate constraint.

There are variables in our model. The computation is reduced greatly as a result of solving a multivariant problem by the multistage method. A parallel global optimization method is implemented in two steps. Step one employes a Markovian decision approach to adjust the redistributions. Step two is a parallel heuristic optimization algorithm based on the genetic algorithm shown below:

1. Restart: Choose a population of M points, , at random and evenly distribute them onto P processors to be evaluated, that is, each processor has [M/P] function evaluations. And then, a master processor computes the average value of M functions, Set , and .
2. Crossover: Pick up V pairs of parents from the set X at random to produce V offsprings. The V couples are assigned onto the P processors. Every processor averagely has [V/P] parents. Each pair of points are always indexed in this way, . Create a new point as follows: , where . Evaluate . Keep the offspring if .
3. Reproduce: Pick a point from set X. Replace by in the population if .
4. Recircle: Set . Compute . Go to step 2 if .
5. Termination test : set . Go to step 1 if . Otherwise, stop.

 

=0.58em

Processors 1 10 20 30 40 N 1000 2000

Time(Hours) 314 32 16.6 10.7 8.2 4583969 9110136

Speedup 10 19 29 38 .18 .16