A Genetic algorithm for facility layout problems of different manufacturing environments
by M. Adel El-Baz
Presented by Farooq Shah, Reg. no. 09PWIND0097;
Department of Industrial engineering, UET, Peshawar.
12/30/2013 1
A Genetic algorithm for facility layout problems of different manufacturing environments
Outline:
1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11)
12/30/2013
Introduction Mathematical model Approach String representation Selection operator Crossover operator Mutation operator Stopping Criterion Sample example Conclusion References
Department of IE, UET, Peshawar 2
Introduction
Effective facility layout design reduces manufacturing lead time, and increases throughput Major layouts in manufacturing systems are the process, the flow-line or single line, the multi-line, the semi-circular, and the loop layout
12/30/2013
Department of IE, UET, Peshawar
Contd.
12/30/2013
Department of IE, UET, Peshawar
Contd.
Each box represents a location The number in the top section indicates the location number The number in the lower section indicates the machine number The selection of a specific layout defines the way in which part moves from one machine to another machine Machine layout is affected by a number of factors Machine layout design seeks to assign machines to locations within a given layout arrangement such that a given performance measure is optimized
12/30/2013 Department of IE, UET, Peshawar 5
Mathematical model
The facility layout problem addressed here is the assignment of M machines to N locations The objective here is to minimize the total material handling cost of the system For the material handling cost for one of the possible layout plans, the production volumes, production routings, and the cost table should be known The total cost function is defined as:
12/30/2013
Department of IE, UET, Peshawar
Contd.
Where as: is the amount of flow among machines i and j (i,j = 1,2,.,M) is the unit material handling cost between locations of machine i and j (i,j = 1,2,,M) is the rectilinear distance between locations of machine i, and j is the total cost of material handling system
12/30/2013
Department of IE, UET, Peshawar
Approach
CONCEPTS: GA starts with an initial set of random solutions for the problem under consideration which is known as the Population The individuals of the population are called Chromosomes The chromosomes evolve through successive iterations called Generations Merging of chromosomes to create a new population is called Crossover, while modifying an existing one is known as Mutation In crossover, chromosomes are mixed and matched in a random fashion to produce an Offspring Mutation rearranges the structure of the chromosome to produce a new one The selection of chromosomes to crossover and mutate is based on their fitness function
12/30/2013 Department of IE, UET, Peshawar 8
Contd.
STEPS: Randomly generate an initial population of chromosomes with a population size P. Evaluate each chromosome in the population according to the material handling cost equation Determine the average fitness for the whole population Use the strategy to fix the potential best number of chromosomes by deleting the worst number of each generation, and copying the best numbers into the succeeding generation. The total no. of chromosomes is kept constant for computational economy and efficiency Apply the Monte Carlo selection technique to randomly select the parents for crossover and mutation from the current population Apply the crossover and mutation operators to generate a new population based on the values of crossover Pc and mutation Pm probabilities. The rest of population is brought from the previous population which has the best fitness value If the stopping criterion is reached, the search process stops. Otherwise, proceed to the next generation, and go to step 2.
12/30/2013 Department of IE, UET, Peshawar 9
12/30/2013
Department of IE, UET, Peshawar
10
String representation
12/30/2013
Department of IE, UET, Peshawar
11
Selection operator
A parent selection procedure operates as follows: 1. Calculate the fitness Fsum of all population members 2. Generate a random number(n) between 0 and Fsum 3. Return the first population member whose fitness, when added to the fitness of the preceding population members, is greater than or equal to n. 4. Repeat Step 3 for the second population member and check that the new selected member is not the same as the first member
12/30/2013 Department of IE, UET, Peshawar 12
Crossover operator
Steps involved are: 1.
2.
3.
12/30/2013
Department of IE, UET, Peshawar
13
Mutation operator
The mutation operator is used to rearrange the structure of a chromosome. Here, the Swap mutation is used, which is simply selecting two genes at random and swapping their contents. It is used where reproduction or crossover may not produce a good solution to a problem.
12/30/2013 Department of IE, UET, Peshawar 14
Stopping Criterion
The program is terminated when either the maximum number of generations is reached, or until the population converges.
12/30/2013
Department of IE, UET, Peshawar
15
Sample example
The proposed approach is evaluated with bench-mark numerical example taken from the work of Chan and Tansri (1994) and also with the work of Mak, Wong, and Chan (1998) who used the same example to evaluate their work. Their work conducted 19 sets of experiments to determine an appropriate combination of the population size P and the generation size G. Both the works used the genetic parameters of R = 5%, Pc 0.6, and Pm = 0.001. The approach proposed here uses a cut-off of 1.5 times the average fitness value of the whole population of each generation as a replication ratio, Pc = 0.9, and Pm = 0.1 per populations.
12/30/2013 Department of IE, UET, Peshawar 16
Contd.
12/30/2013
Department of IE, UET, Peshawar
17
Contd.
12/30/2013
Department of IE, UET, Peshawar
18
12/30/2013
Department of IE, UET, Peshawar
19
Contd.
12/30/2013
Department of IE, UET, Peshawar
20
Conclusion
The proposed approach considers different types of manufacturing layout environments The proposed GA approach produces the optimal machine layout which minimizes the total material handling cost The comparison with other works indicates that the proposed approach is more efficient and has higher chance of obtaining the best solution for the facility layout problem It has an advantage for tackling different manufacturing types of layout environments.
12/30/2013 Department of IE, UET, Peshawar 21
References
12/30/2013
Department of IE, UET, Peshawar
22
Any Questions?
12/30/2013
Department of IE, UET, Peshawar
23
