An efficient heuristic for solving balancing problem in determinist case.

Coculescu, Cristina

1. INTRODUCTION

For solving different types of balancing problem, there have been used several kinds of approaching. Used methods can be divided in two classes: exact methods and heuristic ones. The first warrant the optimality of given solutions but demand very large computing time and/or memory space. The others demand reasonable time and space resources (limited to o polynomial of the length of problem instance) and generally give a solution of problem but without warrant its optimality.

Heuristic methods are richly represented in dedicated literature. However they give the inconvenient that they don't warrant the optimality of purposed solutions, heuristic methods give satisfactory solving for the problems put in industrial practice (Swamidass, 2002).

To justify using heuristic methods for technical line balancing, in the followings some feature which characterize existing methods will be pointed. Making a simple overview of purposed techniques for finding solution of the balancing problem for established times and unique model, solution wherefore the optimality is warranted, they can be put in evidence methods of enumeration of all solutions and choice of that with a minimum number of stations, approaches through dynamic programming, "branch and bound" methods, "backtracking" methods, optimization methods based on bivalent variables.

Because there are several exact methods, a classification of they is important. A criterion of classification is demanded time resources for finding an optimum solution. For all kinds of mentioned methods, aprioristic analysis of time complexity drives to resources which vary exponentially in rapport to the number of phases (Filip&Barbat, 1999).

On other side, all computing experiences certified that if for technical lines with a few tens of phases, an optimum solution is found in some tens of minutes, for lines having hundreds of phases, all exact methods become impracticable because of excessively big time.

Heuristic methods can be also projected to be interactive. Interactive working kind allows human factor to intercede directly with all the stages of making solutions, thus facilitating the application of subjective criteria hard to be mathematically modeled, or of heuristics that come from technologist's particular experience and which can be results of intuition.

However, it worth to be mentioned that when it wants finding solutions whose optimality to be warranted, above mentioned methods remain the only available, computing time appearing as a price of optimality. It isn't in a lack of interest that in the context of continuous computer improvement, especially relative to computing speed and adding facilities of parallel processing, this price becomes smaller and smaller.

2. BALANCING PROBLEM IN THE CASE OF AN ONLY MODEL WITH ESTABLISHED OPERATING TIMES AND FIXED RHYTHM

As follows, we'll show mathematical model of the problem of technical line balancing where on only a model of a product is assembled, operating times of phases are established and operating rhythm of the line is fixed (Vernadat, 1996).

Let be F = {1, 2, ..., n} the phase manifold of technical process and the t : F [right arrow] [R.sub.+] which associates to a phase i [member of] F, the number t(i) which represents operating time of the phase i for that model.

The running of process phases is subject to precedence restrictions whose there is associated the acyclic digraph G = (F, U), where if x, y [member of] F, then (x, y) [member of] U if and only if the beginning of the phase y need finishing of phase x. The condition to have the digraph acyclic technically returns to the demand of the beginning of every phase not to imply finishing of that phase.

Let be R [member of] [R.sub.+] the rhythm of technical line representing the time whereupon a new series of products quit technical line. Considering technical significance of the rhythm, it is necessary that R [greater than or equal to] t(i), i = 1, 2, ..., n.

Let be Q = {[Q.sub.1], [Q.sub.2], ..., [Q.sub.m]} with [Q.sub.i] [subset or equal to] F, 1 [less than or equal to] i [less than or equal to] m a grouping of the phases having the following conditions:

[Q.sub.1] [union] [Q.sub.2] [union] ... [union] [Q.sub.m] = F (1)

[Q.sub.i] [intersection] [Q.sub.j] = [empty set], 1 [less than or equal to] i < j [less than or equal to] (2)

T([Q.sub.j]) = [summation over (x[member of][Q.sub.j])] t(x) [less than or equal to] R, 1 [less than or equal to] j [less than or equal to] m (3)

(x,y) [member of] U, x [member of] [Q.sub.r] and y [member of] [Q.sub.s] implies r [less than or equal to] s, for every (x, y) [member of] U (4)

The manifolds [Q.sub.j], 1 [less than or equal to] j [less than or equal to] m are named workstations.

Because the movement of the lot from station [Q.sub.j] to station [Q.sub.j+1], 1 [less than or equal to] j [less than or equal to] m - 1, is made in time intervals equals to R, it results that after all the phases of [Q.sub.j] are run over the lot in time T([Q.sup.j]), it waits till the transfer to next station, a while equal to R - T([Q.sup.j]). This time is the non-operating time associated to the station .

Total non-operating time for Q = {[Q.sup.1], [Q.sup.2], ..., [Q.sup.m]} satisfying (1)-(4) is

[T.sup.-]{Q)= [m.summation over (j=1)][R - T([Q.sup.j])] = mR - [n.summation over (i=1)]t{i) (5)

Let be [delta] the manifold of phase groups Q = {[Q.sub.1], [Q.sub.2], ..., [Q.sub.m]} satisfying (1)-(4) and Q* [member of] [delta] wherefore:

[T.sup.-]([Q.sup.*]) = min{[T.sup.-] (Q) | Q [member of] [delta]} (6)

There is clearly that Q* satisfies (6) if and only if it verifies:

[absolute value of [Q.sup.*]] = min{[absolute value of Q] / Q [member of] [delta]} (7)

that is, in above hypothesis, whole non-operating time is minimum for an assignation of phases to a minimum number of workstations (Vernadat, 1996).

Balancing problem in the case of an only model with established operating times and fixed rhythm, consists of finding a partition [Q.sup.*] [member of] [delta] of phase manifold that satisfies the relation (7).

A partition Q [member of] [delta] will be named solution of the problem and [Q.sup.*] [member of] [delta] defined by (7) will be an optimum solution.

3. AN EFFICIENT BALANCING HEURISTIC FOR ESTABLISHED TIMES AND UNIQUE MODEL

In the following we'll show a heuristic method for solving balancing problem for a model in determinist case. The method is author's searches fruit in the large and very complex domain of technical line balancing problematic and we entitled it "random seeking method".

Method originality consists of the mixing of phases from starting list. Then, the list is run according to other heuristic methods used for solving this problem, well-known methods in specific literature, through searching of phases which can be assigned in stations and whose operating time, added to operating time from that station, not to overrun the rhythm.

If such an attempt fails, other attempt is made till reaching theoretical optimum or mentioned number of attempts. The more the number of attempts is bigger, the better the chances to gain optimum solution increase (Coculescu, 2005).

The mixing algorithm is the following:

Step 1. A zero m-component vector is built.

Step 2. k = m;

Step 3. We choose a number between 0 and k - 1. Let suppose it is r.

Step 4. We run the vector till we reach r zero components. Zero component of r position takes the value 1 and its absolute position in vector represents chosen number that we mark in a vector.

Step 5. We put k = k - 1. For k = 0, STOP.

Otherwise, go to step 3.

Mixing algorithm makes a random permutation of the manifold of technical process phases. This permutation is not necessary admissible in the sense that we haven't warranted the conformation of precedence relations between phases.

Starting from the permutation generated by mixing algorithm, there is built not only an admissible permutation but also a grouping of phases in workstations so that operating time in every station not to overrun the rhythm and to be near it, as better as possible, that is a solution of the problem.

4. CONCLUSIONS

Heuristic methods are generally, practically, a realistic and satisfactory approaching of technical lime balancing. However heuristic methods give satisfactory solutions--these evaluations having a statistical character--it would be useful to know behavior kind of these methods in the most unfavorable case.

For testing efficiency of every heuristic method of the problem, it needs a generator of models and problems of given kind, so to be made tens of thousands of models in reasonable time for testing then the method on them. After solving this problem, it can make a conclusion about success likelihood of that method, and if it is small, another method or the same method with improved parameters (including random seeking method) can be tried. This method will be tested in turn, till the better heuristic is reached.

In what concerns technical line balancing problem in determinist case, a comparative study of efficiency of used solving methods brought the conclusion that random seeking method gives very good results, almost always offering optimum solution of balancing problem. Even in difficult cases, when balancing indices is almost 1, some hundreds of thousands of attempts prove to be enough.

Random seeking method is efficient even in the case of very small success likelihoods if a choice is made in small time. Generally, it can be applied if other methods fail and the rapport between total number of possible combinations (for studied model) and the number of combinations which give the solution is smaller then a billion. These choices can be directed in the sense of cancellation of domains with parameters which can't bring to problem solution or with chances to reach solution that can be considered as zero, so increasing success likelihood of the method (Coculescu, 2005).

This method can be applied on every problem hard to be solved by other ways or wherefore no efficient solving algorithm was found if the chances to give problem solution are good on this way, the case showed in this work being a particular one.

This paper was developed within the research Project "Development and the Implementation of the Integrated Management System (DI-IMS)", no. 2387/2007, PNCDI_II.

5. 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, Romania

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

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