1 Introduction
The objective function of model minimizes the total cost involved in material handling costs between the two facilities
For the above sample problem the prob when solved by the use of a C++ program developed on the basis of the above evolutionary algorithmic approach we get the following approach for an optimal solution as shown in figure 5
The Genetic Approach used in this study produces fine quality of the solution for Single/Multi – row and Equal size facility problem even though the approach is simple and basic. The best fitness value is used to compare to that of Simulated Annealing algorithm, which generates only one solution at a time. Genetic Algorithm generated solution as a bundle and it gives the user favorable alternatives. For exploring better quality of solution, the fine combination of parameters needs to be found out. Due to the time restrict, the experiment for finding the combination could not be done, but this is important for the procedure of searching for the better solution with the given problem set. For this reason, finding well-combined parameter set could be treated as a decision variable, and it could be a good subject for the future research
Material handling and layout related costs have been estimated to be about 20%-50% of the total operating expenses in manufacturing. To stay competitive in the market these high overhead costs have to be reduced considerably. One way of doing this is to develop an efficient facility layout. The secondary benefit of doing so is in reducing the large Work-In-Process inventory and justifying the costly long-term investment. Developing an efficient layout is primarily finding the most efficient arrangement of n facilities in m locations (m >= n).
Traditionally the layout problem has been presented as a Quadratic Assignment problem (QAP). The layout problem can also be termed as one-dimensional or two-dimensional problem corresponding to the single-row or multi-row patterns of layout. It is well known that QAP is NP-complete category due to the combinatorial function involved and cannot be solved for large layout problems. An alternative model for the QAP that consists of absolute values in the objective function and constraints that can be used for continuous formulations instead of discrete. The efficiency of these models however depends upon the efficient integer programming algorithms.
2 Problem Formulation
The facility layout problem has been termed as Quadratic Assignment Problem (QAP) because the objective function is a second-degree polynomial function of the variables, and the constraints are identical to the constraints of the assignment problem. The objective of the QAP is to find the optimal assignment of n facilities to n sites in order to minimize the material handling cost expressed as the product of workflow and the travel distance. The QAP can be formally stated as
where wij is the workflow between the facilities i and j, a(i) denotes the location to which i has been assigned. The distance function d is anyone of the lp distance between the facilities i and j and is defined as
where (xi, yj )and (xi, yj ) are the geometric centers for the locations a(i) and a(j) . If p = 1 the distances are the rectilinear distances whereas when p = 2 the distances are Euclidean. Each position can be occupied by only one facility and no facilities overlap each other. The Algorithms are based on those aforementioned statements and assumptions taking care of both the Rectilinear and the Euclidean distances while minimizing the objective.
2.1 Objective function Models adopted for the problem
Single/multi – row, Equal areas facilities model
wij is the workflow between the facilities i and j, a(i) denotes the location to which i has been assigned. The distance function d is anyone of the lp distance between the facilities i and j and, in this project, the rectilinear distances is used and set as p = 1. Hence the formulation is changed to
3 GENETIC ALGORITHMS APPROACH
3.1 Representation
The facilities are considered to be assigned to the possible sites, which are a rectangular lattice of locations in the plane, with the inter-site distance computed by rectilinear distance. The number of rows and columns were pre-specified and fixed, and unused sites were left for a possible candidate position for the new generation.
The sequence of the facility represents the position in the site, and this sequence, considered as a chromosome, are expressed using real number encoding for solution string. Each real number represents the site number and the size of these chromosomes is same as the number of facility to be assigned.
The facilities are assigned two-dimensional space as shown in the figure 2 and converted to the shape for using as a chromosome. In this case the number of candidate site (m*n) is bigger than that of facilities (k).
3.2 Initialization
The initial population of chromosome is generated randomly. Each chromosome is a real string containing k strings which ranges 1 to m*n. For not generating illegal chromosome, each process of generating random number checks the previous numbers which is once pick and choose a number which has not been chosen before in the chromosome. This procedure makes each real number shown just once in a chromosome. This initialization for chromosome keeps proceeding until the number of chromosome reaches the pre-set population size.
4 Genetic Operations
4.1 Crossover
The partial matched crossover is used here. Since the real number should not be duplicated in a chromosome after the process of crossover is finished, each procedure of crossover checks the each number.
The crossover procedure could generate infeasible chromosome in this problem if it is not checked that there is no two real numbers, which is same, in a new chromosome. The partial matched crossover method makes it avoid generating infeasible solution. Suppose two integers r and s are randomly selected. The GA then selects the first parent.
sets t = r, and swaps genes xt and yt in x only xnot equal to yt. This swapping is done for t = r through s, one by one, and then we have a feasible offspring. The same is done for
Because the partially matched crossover method swaps genes within a parent, feasible offspring are obtained. In this problem, the candidates swap position represent the facility (k) and the gene, which is expressed as a real string, represent the candidate site (m*n). Since the number of site (m*n) is greater than that of facilities (k), the partially matched crossover method for this problem allows swapping as x implies y. if there is not the same number in a one chromosome.
4.2 Mutation
The swap mutations, which simply select two positions at random and swap their contents, is used in this study. One different thing from the simple swap is that the procedure selects two real numbers not only in the chromosome but also in the site which has m*n candidates. If randomly selected two numbers are in the chromosome, then these are simply swapped and if one of these two numbers is not in the chromosome, then the number in the chromosome is replaced with the one not in the chromosome
There is no chance to select two real numbers not in the chromosome.
5 Evaluation and Selection
The evaluation procedure, in fact, is done just before the selecting procedure in this problem. Since I adopt the elitist approach for the selection, every individual in population should be evaluated and compared the fitness value. Basically, the objective function value is calculated based on the weighted distance between sites, which the facilities are assigned, and the each objective function value of the individual is compared for sorting. The problem that I’ve tried to solve is minimizing problem, so the individuals are sorted as the least value first.
The selection used here is roulette wheel and elitist approach. Roulette wheel selection was used for choosing parents for the crossover and mutation without any evaluation and arrangement of candidates. That means the fitness proportional method is not used and the parents selected for crossover and mutation are totally random. For new generation, the crossover and mutation procedure generates 25 and 10 percent of new population, and the rest of population is brought from the previous population, which has best fitness value. This method automatically keeps the ‘elitist’ chromosome from the current generation to the next generation.
The first step of the evaluation is calculating the objective function value of each individual in the population. For the sorting purpose, this calculated values are compared and listed least value first. Suppose f[i] indicate the chromosome, which has ith least objective function value, and xcount indicate the number of chromosome that is made from the crossover procedure. The ‘xcount + pop_size*0.1’ is the number of offspring made from crossover and mutation. It is assumed ‘xcount + pop_size*0.1’ of the new population are already made and need to be pick up the rest of the new population. Then this evaluation and selection procedure can be simply shown as:
The output of this particular problem generated by the example problem given data in the below table can be represented by:
The same problem can also be solved by another approach called the simulated annealing approach. This effectiveness and the efficiency by using simulated annealing approach in comparison with our genetic or evolutionary algorithmic approach can be shown on the particular graph given in figure below:
Figure shows the difference of solution visually. Genetic Approach produce slightly better solution than SA for most of problem. However, the SA algorithm has better quality of solution for 30- facility problem.
No comments:
Post a Comment