Application of Genetic Algorithm for Flow Shop Scheduling Problem

It's about application of Genetic Algorithms to Flow Shop Scheduling Problem.

1. Introduction to Introduction to
Genetic AlgorithmsGenetic Algorithms

2. The general structure of GAThe general structure of GA
Start
Encode
Genes
Generate
Population
Genetic Operation
Parent 1
Crossover operation
Parent 2
Offspring 1
Offspring 2
Parent 1 Offspring 1
Mutation operation
Evaluate Fitness of the offspring and place
it into population and discard a comparatively
weaker solution
Roulette
Wheel
Stop
Terminate?
Number of
generation
Yes
No
Chromosome
selection
Create population
for the next
generation
Randomly combine
genes with a repair
process
Integer representing
a sequence
Elitist
Strategy
Evaluate
Fitness

3. Step 1: Genetic representationStep 1: Genetic representation
What sort of chromosome
representation is supposed to be used
and what would be the length (number
of geans) of each chromosome
• Binary numbers based
representation
• Integer based representation
• Alphabets

4. Step 2: Generating the initial population randomlyStep 2: Generating the initial population randomly
Chrom Sequence
C1 5 4 3 2 1 6
C2 1 2 3 4 5 6
C3 6 5 3 4 2 1
C4 3 2 5 5 6 1
C5 2 3 6 4 5 1
C6 5 3 4 6 2 1
C7 6 3 4 5 1 2
C8 1 5 6 4 3 2
C9 6 2 4 5 1 3
C10 1 6 4 5 2 3

5. Step 3: Evaluation of the randomly generated solutionsStep 3: Evaluation of the randomly generated solutions
Chrom Sequence Makespan
Cmax
C1 5 4 3 2 1 6 60
C2 1 2 3 4 5 6 140
C3 6 5 3 4 2 1 55
C4 3 2 5 5 6 1 75
C5 2 3 6 4 5 1 95
C6 5 3 4 6 2 1 88
C7 6 3 4 5 1 2 130
C8 1 5 6 4 3 2 110
C9 6 2 4 5 1 3 89
C10 1 6 4 5 2 3 90

6. Step 4: CrossoverStep 4: Crossover
Chrom Sequence Makespan
Cmax
C1 5 4 3 2 1 6 60
C2 1 2 3 4 5 6 140
C3 6 5 3 4 2 1 55
C4 3 2 5 5 6 1 75
C5 2 3 6 4 5 1 95
C6 5 3 4 6 2 1 88
C7 6 3 4 5 1 2 130
C8 1 5 6 4 3 2 110
C9 6 2 4 5 1 3 89
C10 1 6 4 5 2 3 90
Chromosomes are selected on the basis of elitist
strategy
Selected
Chrom

7. 5 4 3 2 1 6
6 5 3 4 2 1
C1
C3
5 4 6 3 2 1
6 5 4 3 2 1
O1
O2
Step 4: Crossover (Contd.)Step 4: Crossover (Contd.)
Cmax = 120
Cmax = 110

8. Step 5: MutationStep 5: Mutation
A chromosome can be randomly selected for
mutation
Chrom Sequence Makespan
Cmax
C1 5 4 3 2 1 6 60
C2 1 2 3 4 5 6 140
C3 6 5 3 4 2 1 55
C4 3 2 5 5 6 1 75
C5 2 3 6 4 5 1 95
C6 5 3 4 6 2 1 88
C7 6 3 4 5 1 2 130
C8 1 5 6 4 3 2 110
C9 6 2 4 5 1 3 89
C10 1 6 4 5 2 3 90
Selected
Chrom
for mut

9. 5 3 4 6 2 1C6
Genes
selected for
mutation
Mutated
chromosome
5 2 4 6 3 1O3
Step 5: Mutation (Contd.)Step 5: Mutation (Contd.)
Cmax = 105

10. Chro
m
Sequence Makespan
Cmax
Previous
makespan
C1 54 3216 60
C2 54 6321 120 140
C3 65 3421 55
C4 32 5561 75
C5 23 6451 95
C6 53 4621 88
C7 65 4321 110 130
C8 52 4631 105 110
C9 62 4513 89
C10 16 4523 90
Step 6: Placing the crossed over and mutated Step 6: Placing the crossed over and mutated
chromosomes back into populationchromosomes back into population

11. Step 7: Fitness function valuesStep 7: Fitness function values
Chro
m
Sequence Makespan
Cmax
Fitness values
Fk
C1 54 3216 60 0.166
C2 54 6321 120 0.083
C3 65 3421 55 0.182
C4 32 5561 75 0.133
C5 53 4621 95 0.105
C6 53 4621 88 0.113
C7 65 4321 110 0.091
C8 53 4621 105 0.095
C9 62 4513 89 0.112
C10 16 4523 90 0.111
Fitness Function = Fk = (1/ Cmax) * 10

12. Step 8: Total Fitness Value of the entire PopulationStep 8: Total Fitness Value of the entire Population
Chro
m
Sequence Makespan
Cmax
Fitness values
Fk
C1 54 3216 60 0.166
C2 54 6321 120 0.083
C3 65 3421 55 0.182
C4 32 5561 75 0.133
C5 53 4621 95 0.105
C6 53 4621 88 0.113
C7 65 4321 110 0.091
C8 53 4621 105 0.095
C9 62 4513 89 0.112
C10 16 4523 90 0.111
Total Fitness of the population = Ft = 1.191
Total Fitness = Ft = Σ Ck
K =1
Pop size

13. Step 9: Selection probability of each chromosomeStep 9: Selection probability of each chromosome
Chr
om
Sequence Makespa
n Cmax
Fitness values
Fk
Sel Prob
Pk
C1543216 60 0.166 0.1393
C2546321 120 0.083 0.0697
C3653421 55 0.182 0.1528
C4325561 75 0.133 0.1117
C5534621 95 0.105 0.0882
C6534621 88 0.113 0.0949
C7654321 110 0.091 0.0764
C8534621 105 0.095 0.0798
C9624513 89 0.112 0.0940
C10164523 90 0.111 0.0931
Total Fitness of the population = Ft = 1.191
Selection Probaility of a chromosome = Pk = Fk / Ft

14. Step 10: Cumulative ProbabilityStep 10: Cumulative Probability
Chro
m
Entries used in calculating Cumulative Probability of a
solution
Cum
Prob
CPk
C1
0.139
3
0.1393
C2
0.139
3
0.069
7
0.2090
C3
0.139
3
0.069
7
0.152
8
0.3618
C4
0.139
3
0.069
7
0.152
8
0.111
7
0.4735
C5
0.139
3
0.069
7
0.152
8
0.111
7
0.088
2
0.5617
C6
0.139
3
0.069
7
0.152
8
0.111
7
0.088
2
0.094
9
0.6566
C7
0.139
3
0.069
7
0.152
8
0.111
7
0.088
2
0.094
9
0.076
4
0.7330
C8
0.139
3
0.069
7
0.152
8
0.111
7
0.088
2
0.094
9
0.076
4
0.079
8
0.8128
C9
0.139
3
0.069
7
0.152
8
0.111
7
0.088
2
0.094
9
0.076
4
0.079
8
0.094
0
0.9068
C10
0.139
3
0.069
7
0.152
8
0.111
7
0.088
2
0.094
9
0.076
4
0.079
8
0.094
0
0.093
1
0.9999

15. Step 11:Step 11: Roulette Wheel Selection Roulette Wheel Selection
• Now generate a random number between 0 and 1.
e.g. the number generated is 0.15.
• Now compare this value with the cumulative
probability values calculated in step 4.
• It is between C1 and C2 (i.e. 0.1393 < 0.15 <0.2090)
• Since the generated number is greater than CP1 and
less
than CP2 so C2 is selected in the next generation
• Repeat the same procedure population times
• This would give us a new population in which some
chromosomes may have multiple entries

16. Chrom Sequence Makespan
Cmax
Fitness values
Fk
C3 6 53421 55 0.182
C4 3 25561 75 0.133
C9 6 24513 89 0.112
C3 6 53421 55 0.182
C1 5 43216 60 0.166
C10 1 64523 90 0.111
C6 5 34621 88 0.113
C1 5 43216 60 0.166
C5 5 34621 95 0.105
C8 5 34621 105 0.095
Chromosomes selected for the Chromosomes selected for the
next generationnext generation

17. 
The procedure is kept continuedThe procedure is kept continued

Until a stopping criteria is reachedUntil a stopping criteria is reached

That may be the maximum number of That may be the maximum number of
generationsgenerations

Or the time when no improvement can Or the time when no improvement can
be recorded furtherbe recorded further

Or the algorithm has converged to an Or the algorithm has converged to an
already known optimum valuealready known optimum value
Further ProcessingFurther Processing