不雨錄

PowerPoint in here.

The program you can download in here.

In this program, I was tried to write a genetic algorithm to solve flow-shop problem.

Flow-shop problem is try to sequencing the job sequence with more than two machines.

Because only have two machines we can use Johnson’s rule to solve it, so there are m machine(m should > 2) and j jobs(j should > 1) with several conditions need to be in place:

1. The time for each job must be constant.
2. The job times must be mutually exclusive of the job’s sequence.
3. All jobs must go through first work center before going through the second work center.
4. There must be no job priorities.

So in this program, I would tried to find out the best sequencing of jobs.

Here has a example with gantt chart:

In this picture, the table on the left hand side has shown the time each job need in every machine. And right hand side is a gantt chart for showing the total time of sequence job A-B-C.

Because we are sequence the job’s sequence, so there are j!(e.g. j=4, 4!=24) combination.

In this program, I have set the population sizes for 500, 10 jobs, 10 machines and run 10 generations. The probability of mutation and crossover are 0.1 and 0.8. All of these you can change in the top of Chromosome.java.

The program will output the work table first, and print out best sequence in each generation and finally will output over all the best.

The program still not find out the best one, only find a better one, so I think I still need to take notice of evaluate fitness.

This idea came from jijng’s Blog, but some pictures were missing, so many concepts were difficult to get, especially 3.3 how to calculate the fitness, this may the main problem of why my program didn’t as efficient as jijng’s work.

output:

| 0 1 2 3 4 5 6 7 8 9
|0 7 8 3 8 2 2 1 2 3 1
|1 2 8 9 5 6 7 8 5 1 7
|2 2 2 5 4 8 9 8 2 9 3
|3 7 1 9 5 7 4 7 5 4 2
|4 9 1 6 6 1 4 8 1 4 9
|5 5 8 9 7 4 2 4 1 3 9
|6 6 3 8 1 4 3 3 7 3 8
|7 2 4 9 7 4 8 2 5 3 2
|8 2 7 4 1 2 3 6 1 5 9
|9 2 6 9 9 6 6 3 9 1 7

Generation:1
The best one is 183
4 2 7 5 0 6 1 3 9 8

Generation:2
The best one is 182
0 6 2 9 1 4 7 3 5 8

Generation:3
The best one is 185
4 2 9 1 7 5 0 6 3 8

Generation:4
The best one is 188
4 2 9 1 7 8 6 3 5 0

Generation:5
The best one is 184
8 3 5 6 2 9 4 7 1 0

Generation:6
The best one is 184
4 7 6 2 9 3 1 5 0 8

Generation:7
The best one is 182
0 6 2 9 1 4 7 3 5 8

Generation:8
The best one is 188
4 6 8 2 9 7 5 3 1 0

Generation:9
The best one is 186
0 6 2 9 1 7 3 5 4 8

Generation:10
The best one is 182
0 6 2 9 1 4 7 5 3 8

Over all the best one is 182
0 6 2 9 1 4 7 3 5 8