Approaching of balancing problem through simulation.

Coculescu, Cristina ; Coculescu, Cristian Catalin

1. INTRODUCTION

In many cases, experiences on real objects are difficult to make and need a big amount of funds and human resources for make then acceptably.

Nowadays, grace of computing facilities of electronic computers, that are big amount of memory and computing speed, it acts modeling methods improving, complex systems modeling with simulation techniques having a privileged place.

The problem of technical process balancing supposes the grouping of phases in workstations so the sum of operating times of the phases which are in a station to be less then or equal to a value R called rhythm. For approached model of balancing problem, R is fixed and is the same for all stations. The phases of technical process must be executed in a certain order in the meaning that certain phases can't have place before others. Order relations between phases reflect technologically, real development of the process and are called relation of precedence. Mathematically, they form an acyclic digraph (James, 2000). Balancing objective is the reaching of the smallest number of station having prior property.

Because in simulation programs, random number generation has a relatively big part of total computer operating time, it is necessary to find efficient ways to do this, to get random strings with big cyclicity.

Another important feature in technical line simulation is also the testing of acyclicity of the graph of precedence relations.

In this work we follow making an algorithm for simulate a technical process, relied on random generation of the main characteristics of working phases, which will be considered in solving balancing problem of a technical line whereon an only model of a product is assembled, operating times are established and line operating rhythm is fixed, relied also on solving the two essential features above mentioned.

2. SIMULATION OF A TECHNICAL LINE WHICH IS SUBJECT TO THE BALANCING PROCESS

2.1 Possibilities of random number generation

For realistic reproduce certain elements of simulated system, and also for solving some numeric problems, it appears the need of existence of some numbers "happily chosen".

In simulation programs, generation of random numbers has a relative big part of computer running time.

We'll mark F = {1,2, ..., n} the manifold of technical process' phases which follow to be simulated and t = {t(1),t(2), ..., t(n)}, the vector of operating times associated to the phases.

Within this context, we purpose to build a function having property that it has equal likelihoods to generate its values. So, we consider the function rnd defined like this: for a natural number n, rnd(n) is a natural number between 0 and n-1. If we want a real value, let's say a number between -2 and 3, having two exact digits, we use an expression like rnd (500)/100--2.

If maximum number of phases is marked maxphases the number of the phases from process will be rnd(maxphases)+1.

We consider operating time of each phase at most equal to maxtime time units, therefore for the phase i, t(i) = rnd(100 x maxtime)/100 + 0.01 (it is computed with at most two exact digits and cannot be zero).

As follows, we consider that arithmetic operations that will be used for generate such function (rnd), are with 32 bits that is, every result of an arithmetic operation is considered as the rest of the division of real result by 2 (32). This value has chosen because it is enough for usual needs and is easy to be used in programming.

There is considered the string [{x.sub.n}.sub.n[greater than or equal to]0] defined like:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

where a and b are odd numbers (a is a number of shape a = 4 x k +1).

Such string, especially a and b are prime numbers, has an extreme long cyclicity and is good enough for usual needs.

If to its value there is added also that of the standard function which generates random numbers, from the libraries of several programming languages, and it is set by the time counter and computer's internal clock, the result can be of a big variety.

There is also the possibility of combination of two or three strings of mentioned type, their sum being a string having a very long cyclicity and in this case the result being very easy to compute too.

2.2. Acyclicity test of the graph of precedence relations

Let be maxphases maximum number of process' phases and maxtime maximum operating time of a phase.

At the beginning we'll establish the number of phases (nrphases) and operating times of phases.

For i = 1 , nrphases t(i) = rnd(maxtime) + 0.01 .

The number of phases is randomly generated.

After this, phases' names are read. For each phase, we generate then the operating time. Making a precedence relation follows.

A precedence relation (shortly, a precedence) can be considered as a couple ([f.sub.1], [f.sub.2]) where [f.sub.1] = rnd(nrphases) [f.sub.2] = rnd (nrphases) and [f.sub.1] [not equal to] [f.sub.2] .

That means that [f.sub.2] operates before [f.sub.1]. Clearly, the first care we have is not to have the relation already generated and [f.sub.1] [not equal to] [f.sub.2] . After that, total operating time and maximum operating time for a phase (the biggest operating time of generated phases) are computed. This computing is very important because if in balancing problem, a rhythm is smaller than maximum working time for a phase, the problem is wrong (Vernadat, 1996).

After that, we must decide whether precedence relation we put in is correct. It not, it will be cancelled in the sense of cancellation of its value in precedence matrix.

There are two ways to do the test. First, it is necessary to clarify what means that precedence ([f.sub.1], [f.sub.2]) is correct, that is, if [f.sub.2] can precede [f.sub.1] . The relation is correct if and only if no phase precede itself. If we have precedence of type ([f.sub.1] , [f.sub.2]) and ([f.sub.2], [f.sub.1]), between indirect predecessors of [f.sub.1] is also [f.sub.1] as predecessor of [f.sub.2] and we reach up-mentioned contradiction.

Acyclicity test of precedence relations reduces to establish if no phase precede itself. A checking method consists of the establishing of all predecessors of each phase. For this, we purpose the following algorithm:

Algorithm 1

Step 1. We consider [F.sub.1] the manifold of f predecessors. Let k = 1.

Step 2. k = k + 1. We consider [F.sub.k] the manifold of direct predecessors of the phases from [F.sub.k-1].

If [F.sub.k] [not equal to] [F.sub.k-1] we repeat step 2.

Step 3. If f [not member] [F.sub.k] , the precedence is not correct.

Otherwise it is correct.

Another method supposes weight computing of all technical process phases. The weight of a phase is the sum of its time with times of all its direct or indirect predecessors. Therefore, if a phase has no predecessor, its weight is equal to its working time. If the phase has predecessors, there is computed the sum of the times of precedent phases with computed weights. To have an acyclic graph of precedence relations, we must compute the weight of all phases and reciprocally, if there is a phase whose weight can't be computed, the graph is cyclic (Swamidass, 2002).

2.3 Simulation Algorithm

As follows, we'll describe an algorithm of simulation of a technical process, in the meaning of random generation of the main characteristics of working phases that will be considered for solving balancing problem of a technical line whereon an only model of a product is assembled, operating times are established and line operating rhythm is fixed.

The algorithm is the fruit of authors' research in the wide and very complex domain of the problematic of technical line balancing (Coculescu, 2005).

Algorithm 2

Step 1. There is randomly generated the number of phases and for each phase, working time is generated.

Step 2. Matrix PRED of precedence relations is initialized by zeros. This matrix has a number of lines equal to the number of phases and 20 columns.

Step 3. nrfail = 0;

Step 4. A triplet ([f.sub.1], [f.sub.2], p) is generated where [f.sub.1] = rnd(nrphases) , [f.sub.2] = rnd(nrphases) , p = rnd(20). If [f.sub.2] [not equal to] [f.sub.1] we make PRED([f.sub.1], p) = [f.sub.2] in the meaning that the phase [f.sub.2] precedes [f.sub.1]. If [f.sub.1] = [f.sub.2] or PRED( [f.sub.1], [f.sub.2]) [not equal to] 0 , we repeat step 4.

Step 5. There is checked with algorithm 1 if the matrix PRED corresponds to an acyclic graph of precedence relations,

Step 6. If the graph is cyclic, PRED([f.sub.1], p) = 0 and if nrfail < 10000 go to step 4. Else STOP.

Step 7. If the graph is acyclic, go to step 3.

3. CONCLUSIONS

Balancing using in industrial practice, can be facilitated by making a program which additional to a more efficient implementation of selected algorithms must offer the possibility of a comparative analysis of the methods used for solving balancing problem approached concerning the quality of given solutions.

Because this action demands the using of a relative big number of problem instance, we considered necessary the making of possibility of random generation of these models, being known that their gaining from real technical processes is difficult.

The idea we started from, was that to build a function which to have equal likelihoods of generation its values. For this, we combined standard random number generator of C programming language, with the values of random string (1) of natural parameters a, b, c.

By helping of gained function (rnd) there was realized a simulation model of real technical process in the meaning of random generation of the main characteristics of working phases that will be considered in solving balancing problem of a technical line whereon an only model of a product is assembled, operating times are established and line operating rhythm is fixed.

Simulation algorithm and its informatics implementation have been then integrated in a program, proving very useful within the process of testing performances of used methods for solving the approached balancing problem (Coculescu, 2005).

General rules from technical line simulation process shown in this work, can be applied for simulation other models, from other domain, especially of economic ones.

This paper was developed within the research Project "Development and the Implementation of the Integrated Management System (DI-IMS)", no. 2387/2007, PNCDI_II, developed on National Research Plan, it course being set it up to 2010. The institutional partners cover different activity fields, from various industries.

4. REFERENCES

Coculescu, C.; (2005). Modeling and Simulation of Economic Processes. Concepts, Models and Balancing Algorithms, Juristic Universe Editing Press, ISBN 973-8446-44-9, Bucharest

Filip, F.G.; Barbat, B. (1999). Industrial Informatics--New Paradigms and Applications, Technical Editing Press, ISBN 973-31-1324-7, Bucharest

James, A.J. (2000), Next Generation Manufacturing. Methods and Techniques, Wiley, ISBN 978-0471360063

Swamidass, P.M. (2002). Innovations in Competitive Manufacturing, AMACOM, ISBN 978-0814471401

Vernadat, F. (1996). Enterprise Modeling and Integration: Principles and Applications, Springer, ISBN 978-0412605505