The basic parameter of this task is the finite set of operations . For each operation there is an assigned manufacturing time as well as a graph of sequence constraints showing the demand sequence of performance in relation to each other [2]. This graph can be presented in graphical form or can be coded as a file, a table or a dynamic structure. The solution of the task is the division of the operation set into subdivisions , preserving their minimal number and as the same time the following condition must be fulfilled:

(68)

In order to solve the optimization task by means of the genetic algorithm one has to start with the first step of coding the chromosome. In classic genetic algorithms the chromosome is the binary chain with the constant length I. Sometimes the evolutionary methods allow the application of the coding with other number series {eg. 1, 2, 3, 4, 5, ..., n} as well as the creation of chromosomes with varying length. The second step is to select the crossing method. Mutation is the third element of the genetic algorithm. The mutation determines the capacity of the searching space and at the same time determines the probabilistic character of this space. The fourth and the most important element of the genetic algorithm is the selection of parents that are assigned to create new individuals. There are many selection methods but selecting the one that is the most suitable is determined by the criterion which is treated as the adaptation function. The basic genetic algorithm makes the selection according to the so called roulette wheel. This is necessary to determine the probability of selecting the certain individual which is equal to the quotient of individual adaptive function and the sum value of this function for the whole population. Various methods, presented in the literature [1,3] are connected with natural selection in nature where the sum value of adaptation for the whole population is unknown. By means of these methods, populations with varying values are generated and many generations compete with each other at the same time. There are also created models connected with the niche theory where due to mutual mating the individuals with the certain features are obtained.

Balancing of the assembly line is the problem that is assigned to the theory of combination tasks and in such a case there is no direct representations in the chromosome of the genetic algorithm. It is caused by the two constraints: production pace and the graph of sequence constrains. It should be mentioned that for the task with n operations there are theoretically possible permutations and only small amount out of them fulfills the sequence constraints.

For the algorithm developed the binary chromosome with the length equal to the product of the coding number and the number of operations has been applied. Selection of operation is performed out of the operation list that are actually accessible. That means they do not have any predecessor. Such a list is dynamically created and operations are not sorted in growing sequence in relation to their realization time and the number. The algorithm has been tested on several tasks. The results of the task have already been known and this fact enabled authors to evaluate the proposed algorithm. The first tested task has been marked as "sawyer". The assembly process in this case has been composed of 30 operations and the sum of times was 324 units, the shortest time was 1 unit and the longest 25 units. The graph of the sequence constraints is composed of 32 edges. With the application of the algorithm presented it was very easy to find optimal solutions.

The main aim of the investigations performed by authors, concerned the effectiveness and usability of genetic algorithms for solving the tasks applied in assembly line balancing. Based on the results it is possible to state that the program, based on the classic genetic algorithm enabled optimal results to be obtained for many of the tasks.

1

D.E. Goldberg, "Algorytmy genetyczne i ich zastosowania", WNT, Warszawa 1998.

2

J. Zurek, O. Ciszak, "Modelowanie oraz symulacja kolejnosci montazu czesci i zespoów maszyn za pomoca teorii grafów", Wydawnictwo Politechniki Poznanskiej, Poznan, 1999.

3

Z. Michalewicz, "Algorytmy genetyczne + struktury danych = programy ewolucyjne", WNT, Warszawa 1999.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £105 +P&P)