Production optimization by using genetic algorithms and simulation model of production system.

Schreiber, Peter ; Vazan, Pavel ; Tanuska, Pavol 等

1. INTRODUCTION

The lot size is one of the directions of production which markedly influences production costs. The lot size influences production flexibility, amount of parts in process, flow time, capacity utilization etc. The goal is to determine the lot size so that production costs will be minimal.

There are several known methods for determination of lot size in the world. One of them is called economically optimal lot size. This method defines the mathematical formula which minimizes the set-up costs and storage costs. This lot size is expressed by mathematical model that solves the compromise between the reduction of fixed costs per piece and increasing of lot size, and on the other side increasing of the storage costs.

The optimal lot size is determined as follows:

[D.sub.o] = [square root of 2*[Q.sub.p]*[N.sub.pz]/[N.sub.j]*[n.sub.s]*t]] (1)

[D.sub.o]--optimal lot size in pieces, [Q.sub.p]--planned number of parts in pieces, [N.sub.pz]--batch set-up costs, [N.sub.j]--costs per one piece, [n.sub.s]--annual storage costs, including credit interest, t--fraction--period of the year.

Another approach is based on search of minimal lot size which is needed for effective utilization, usually as bottleneck or capital-intensive capacity unit. The lot size, defined in this way, provides economical utilization of chosen capacity units (bottlenecks).

The minimal lot size is determined as:

a = [t.sub.pz]/[t.sub.k]*D [??] D = [t.sub.pz]/[t.sub.k]*a (2) tK * D tK * a

[t.sub.pz]--time for set-up in min., [t.sub.k]--part time in min., D--lot size in pieces, a--coefficient. a = 0,04 for complicated parts and a = 0,1 for production with automatic machines.

The other methods are based on empirically found variables with many defects. There are used different approaches, e.g. optimal lot size is defined at many possibilities and chosen is that one with its own minimal costs. This includes e.g. optimal lot size according to Teplov or Bankovsky (Gregor, 2000).

These classic calculation methods require accurate input values (set-up costs, storage costs, etc.). In fact these values are qualified approximations but not exact values. The analytical solution is more complicated when the model concerns constrains (Ramaswamy, 2006).

2. SIMULATION

Simulation of real production system behaviour by software tools is one of the possible approaches to determination of optimal lot size. It is possible to optimize the system through evaluation of system behaviour with different input parameters. The most appropriate simulation method is the discrete-event simulation for manufacturing model building. Rapid expansion of simulation tools for manufacturing allowed the usage of this procedure very effectively. The model building takes a short time and the model is very detailed. The authors used the simulation package Witness of the company Lanner group Ltd.

The objective function had to be defined for optimising of production cost. The production cost is computed according to following function in the realised model.

SumCosts = [p.summation over (i=1)] In_part_[costs.sub.t] + [p.summation over (i=1)] Added_[value.sub.t] (3)

where In_part_costs are initial costs for each entered parts, Added_value is gained amount in production system, P is number of entered parts. Total added value is calculated:

Sum_Added_value = [p.summation over (i=1)] [OC.sub.t] + [SC.sub.t] + [LC.sub.t] + [TC.sub.t] + [STC.sub.t] (4)

where OC--operation costs, SC--setup costs, LC--labour costs, TC--transport costs and STC--storage costs.

operation_costs = [m.summation over (x=1]) [t.sub.Aj] * unit_[costs.sub.j] (5)

setup_costs = [s.summation over (x=1)][t.sub.Bx] * unit_[costs.sub.x] (6)

where m is number of machines, [t.sub.Aj] is processing time, unit_costs is rate per unit of time, s--number of set up operations, [t.sub.Bx]--set up time, unit_costs is rate per unit of time.

labour_costs = [op.summation over (k=1)][t.sub.LBk] * unit_L_[costs2.sub.k] (7)

where op is number of operations with labour, [t.sub.LBk] is operation time with specific labour, unit_costs2 are rates per unit of time.

transport_costs = [top.summation over (i=1)]transport_operation_[costs.sub.l] (8)

storage_costs = [NS.summation over (n=1)][t.sub.Sn] * unit_[costs.sub.n] (9)

where top is number of transport operations and NS is number of storages.

All functions are calculated in elements of simulation model of production system. Partial values of objective function are always calculated when specific element of production system finishes its activity. SumCosts is calculated at the same time. Discrete-event simulation allows this process.

The function SumCost is growing up with rising of number of finished parts. Therefore it is not proper to use it as objective function. The function Unit_Cost is designed by the authors as objective function. This function calculates the production cost per finished part.

Subsequently the objective function is revised so that the production costs are optimized, but other production goals have to reach defined values (Vazan & Tanuska, 2003).

3. PRODUCTION SYSTEM OPTIMIZATION BY GENETIC ALGORITHM

Let suppose that production costs depend on the lot sizes and their input intervals will be minimized. The constraints are flow time, capacity utilization and the number of finished parts. Then :

N([d.sub.1], [t.sub.1], [d.sub.2], [t.sub.2], ..., [d.sub.n], [t.sub.n]) [right arrow] min (11)

[T.sub.i]([d.sub.i], [t.sub.1], [d.sub.2], [t.sub.2], ..., [d.sub.n], [t.sub.n]) [less than or equal to] [T.sub.imax,] i = 1..n (12)

[C.sub.j]([d.sub.1], [t.sub.1], [d.sub.2], [t.sub.2], ..., [d.sub.n], [t.sub.n]) [greater than or equal to] [C.sub.jmn], j = 1..m (13)

[P.sub.i]([d.sub.1], [t.sub.1], [d.sub.2], [t.sub.2], ..., [d.sub.n], [t.sub.n]) [greater than or equal to] [P.sub.imin], i = 1..n (14)

[d.sub.imin] [less than or equal to] [d.sub.i] [less than or equal to] [d.sub.imax,] i = 1 .. n (15)

[t.sub.imin] [less than or equal to] [t.sub.i] [less than or equal to] [t.sub.imax,] i = 1 .. n (16)

N--production costs, n--number of parts, [d.sub.i]--lot size of the ith part, [t.sub.i]--input interval of batch of the ith part, [T.sub.i]--flow time of ith part, [C.sub.j]--capacity utilization of jth part, M--number of equipment, [P.sub.i]--number of finished ith part, [T.sub.imax]--maximally acceptable flow time of ith part, [C.sub.jmin]--minimally acceptable capacity utilization of jth equipment, [P.sub.imin]--minimally acceptable number of finished ith parts, [d.sub.imin], [d.sub.imax], [t.sub.imin], [t.sub.imax],--limits of scanned space.

The objective function (1) and constraints (2)-(4) cannot be expressed analytically but the simulation model determines values N, Ti, Cj, Pi (Duzinkiewicz & Kwiesielewicz, 1998)

It is necessary to associate production system and its parts together with terms used in genetic algorithms for production system optimization by means of genetic algorithm (Sekaj, 2001).

Chromosome (the solution of optimising problem) will be a vector of numbers which represents input parameters of the system (d1, t1, d2, t2, ..., dn, tn). Its elements are genes.

Population: Let there are 40 individuals (solutions) in one generation.

Objective function is given by relation (1) and evaluates each solution. The value N is determined by simulation.

Selection: Genetic algorithm requires surviving "good solutions. They are those with small value N. The fitness of individual solutions is inversely related to their costs. If we use roulette selection, the probability of survival is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (17)

where [p.sub.k] is selection probability of kth solution, [F.sub.k] is fitness of kth solution, [N.sub.k] are costs of kth solution obtained by simulation, g is the number of solutions in population (40).

Elitisms: The best 4 solutions turn to the next generation unchanged to keep the best solutions. The other 36 solutions are crossovered and mutated.

Crossover operation: one-point crossover of two individuals in randomly chosen position. Let [p.sub.c] = 1.

Mutation: Mutation is realized with probability [p.sub.m] = 0.05.

Solution ending: Number of generations or calculation time is an ending condition.

The form of genetic algorithm is following:

1. Random solutions--vectors ([d.sub.1], [t.sub.1], [d.sub.2], [t.sub.2], ..., [d.sub.n], [t.sub.n]) are generated, the generated values should fulfil conditions (12)-(16).

2. The solutions are evaluated according to relation (11).

3. If the ending condition is fulfilled, the best individual is the desired solution.

4. The best 4 solutions are chosen into new generation. The serial numbers 1-4 will be assigned.

5. Remaining 36 individuals in new generation will be obtained in the following way:

a. Roulette selection (according to relation (17)). 36 individuals are given to the positions 5-40.

b. Neighbouring pairs crossover. Conditions (12)-(14) are checked by simulation. If the solution is inadmissible, another random crossover point is used.

c. Some genes are chosen for mutation in solutions 5-40. New genes have to fulfil conditions (15)-(16) and also new solutions have to fulfil conditions (12)-(14).

6. New generation is formed by solutions gained in steps 4 and 5. Algorithm continues by the step 2.

The results of this optimization are comparable or better than the values obtained by embedded optimizers of Witness.

4 CONCLUSION

The simulation optimization is a proper method for the lot size determination. It is able to respect more factors, which determine the lot size, than classic optimizing methods. It requires the existence of simulation model. On the other side classic methods are faster and simpler.

The authors want to verify this method by various types of production systems, especially by flexible manufacturing systems. The next goal is to compare systematically the results obtained by various optimising methods.

This paper has been supported as a part of solution of projects VEGA 1/0368/08 and VEGA 1/0170/08.

5. REFERENCES

Duzinkiewicz, K. & Kwiesielewicz, M. (1998). Multicriteria approach to production tasks planning in systems with continuous switchable production processes. In: Proceedings of 13th International Conference on Systems Science, pp.25-31, Wroclaw, Poland, II

Gregor, M., Kosturiak, J., Micieta, B., Bubenik, P., Ruzicka, J. (2000) Dynamicke pldnovanie a riadenie vyroby (Dynamic planning and control of production), KPI-ZU EDIS, ISBN 80-7100-607-6, Zilina, Slovakia

Ramaswamy K.V.(2006) Optimal lot sizing in manufacturing revisited. Journal of Information and Optimization Sciences. Vol. 27 no.1, (2006) pp 97-105, ISSN: 0252-2667

Sekaj, I. (2001) Genetic algorithms. AT&T Journal, vol.8 (11, 2001) pp.46-48, ISSN 1335-2237

Vazan, P. & Tanuska, P. (2003) Optimization of control goals of flexible manufacturing system, In: CIM: Computer Integrated Manufacturing : Advanced Design and Management, Wydawnictwa Naukowo-Techniczne, pp. (586-591), ISBN 83-204-2830-5, Warszawa