21 GA GA for job-shop scheduling problem by plural chromosome expression 1100303 2010 3 1
GA 1,,,,,,,, 4, 4,, i
Abstract GA for job-shop scheduling problem by plural chromosome expression Tatsuki Shinohara Genetic algorithm imitates evolution of life a kind of approximate solution of optimization problem Express practicable answer of problem as chromosome, select, cross over and mutation genetic operation repeat generation find approximate solution Each chromosome corresponds to solution possible, therefore ability is understood, ability is called fitness value Selection of chromosome left in next generation is chosen by fitness value Cross over and mutation are operation to cause the variety of the solution In this paper, four kind of chromosome expression to job-shop scheduling problem was considered In the experiment a result, best solution among four kinds chromosome expression is Operation Permutation Adjust parameters such as cross over probability, mutation probability, approximate solution of Operation Permutation key words genetic algorithm, job-shop scheduling problem, chromosome expression ii
1 1 2 3 21 3 22 3 3 6 31 6 32 6 321 7 322 7 7 7 323 8 324 8 4 JSP 9 41 9 42 1 10 43 13 44 15 45 15 5 18 51 18 iii
511 (PMX) 18 512 (CX) 20 52 21 53 21 54 22 55 23 6 25 61 25 62 27 29 30 iv
21 4 22 5 31 GA 6 41 10 42 1 10 43 1 10 44 1 10 45 1 11 46 J 2 11 47 J 2 11 48 J 1 12 49 J 4 12 410 J 4 12 411 J 3 13 412 1 13 413 13 414 1 14 415 1 14 416 15 417 J 2 1 16 418 J 2 2 16 419 J 3 1 16 v
420 16 51 18 52 18 53 PMX 19 54 PMX 1 19 55 PMX 2 19 56 PMX 19 57 CX 20 58 20 59 CX 21 510 21 511 22 512 15, 15 24 513 20, 15 24 514 30, 15 24 515 50, 15 24 61 25 62 28 vi
21 JSP 4 41 9 42 14 43 15 44 makespan 17 51 23 61 75%, 10% 26 62 55%, 50% 26 vii
1,,,,,,,, NP, 1,,,,, 2 3 4 1
,, 5 6 2
2 21 (job-shop scheduling problem: JSP),, ( ) (makespan),, (makespan) 1 ( ) 2 3 22 JSP, 21 4, 3 4 J 1,J 2,J 3,J 4, 3 M 1,M 2,M 3 3
22 21 JSP 1 2 3 J 1 (M 2,4) (M 3,3) (M 1,2) J 2 (M 2,2) (M 1,1) (M 3,1) J 3 (M 1,4) (M 3,1) (M 2,1) J 4 (M 1,2) (M 3,1) (M 2,3) J 1 1 (M 2,4), J 1 M 2 4 1, J 1 M 2, M 3, M 1 J 2 J 4 makespan, M 2 10, makespan 10 JSP 21 21 4
22,, makespan 11 M 1 J 4,J 2,J 3,J 1 21 M 2 J 1 J 2 2, 2, M 2 J 1 J 2, 21 M 2 J 2 J 1 3, 21 M 2 2 J 1 4 2 J 1 21, M 2 J 2, M 2 J 1 22 makespan 10, 10 22 5
3 31 (Genetic Algorithm: GA),,, [1] ( ) ( ) ( ) 32 31 GA 31 GA 6
32 321 0, 1 2 1 322, 2, ( ), 2 [1],,, ( ), 0, 1, 2,, [2] 7
32 323 ( ), 324 GA, 8
4 JSP JSP, [3] 1,, makespan 41 2 21 41 1 2 3 J 1 (M 2,4) (M 3,3) (M 1,2) J 2 (M 2,2) (M 1,1) (M 3,1) J 3 (M 1,4) (M 3,1) (M 2,1) J 4 (M 1,2) (M 3,1) (M 2,3) 41 41, ( 1 ) 41 J 4,J 2,J 1,J 3 1 9
42 1 41 42, 2 J 4 2 3, J 2 2, 3 43 makespan 13 42 1 43 1 42 1 2 44, 44 1 1 J 4 10
42 1 J 2 45 45 1 J 1 1, M 2 J 2 1 M 2, J 1 1 1, 1 makespan J 1 1 J 2 2 makespan 46, 47 46 J 2 47 J 2 11
42 1 makespan 9 11 1 48 48 J 1 J 3 1 49 410 makespan 10 411 49 J 4 410 J 4 1, 1 412 makespan 10 12
43 411 J 3 412 1 1, 1 1, 43 1 1 413 413 2, f 1, o 1, f 1 414 13
43 o 1 J 1 2, 3, J 4,J 2 J 3 415 makespan 12 414 1 415 1 1, 1 makespan 43 42, 1 15, 15 20 2 20 20, 20 40 5 60 30, 20 60 20 1 30 50, 20 2 30 2 3, 14
44 44, 1, 3 43 43, 1 15, 15 1231 1005 1497 1524 1514 20, 20 1626 1314 2049 2049 2100 30, 20 1983 1761 2673 2673 2623 50, 20 2868 4018 3911 3955 makespan upper bound, lower bound [4][5] upper bound 1, 45 416 (= * ), ( ) 4, 3 1 4 4, 3 416 15
45, 2 J 2 1 417 2 J 2 2 2 J 2 2 418, 1 2 2 417 J 2 1 418 J 2 2 3 J 3 3 J 3 1 419 420 makespan 11 419 J 3 1 420 16
45 1 2 1 1 2, 420 M 1 J 4 J 3 1 1, 44 44 makespan, 1 15, 15 1231 1005 1497 1524 1514 1372 20, 20 1626 1314 2049 2049 2100 1879 30, 20 1983 1761 2673 2673 2623 2348 50, 20 2868 4018 3911 3955 3328 15, 15, JSP, 17
5 51, 1 *, 4, 3 51 4 1 52, 416 52 51 52 511 (PMX) (partial mapped crossover: PMX), 2 ( ) 1 2, 53 2 P 1, P 2 18
51 53 PMX P 1 P 2, P 2 P 1 P 1 P 2 P 1 4 7, 54 54 PMX 1 55 PMX 2 P 1 8 3 55 P 2 P 2 P 1, 56 C 1, C 2 C 1 P 2, C 2 P 1 56 PMX,,, 19
51 4 512 (CX) (cycle crossover: CX), 2 1, 1 57 P 1, P 2 57 CX, P 1 8 P 2 3 P 1 3 P 1 3 P 2 8 58 58, P 1 P 2 59, P 1, P 2 C 1, C 2 20
52 59 CX 52 1 2 510, 6 11 510 53 5% 1 3 511 21
54 511 50%, 50% 50%, 50% 54 makespan, makespan, 1, 1,, 1 1 51, 2, 22
55 51 PMX( ) PMX( ) PMX( ) PMX( ) CX 15 1354 1339 1334 1357 1318 15 1275 1329 1273 1304 1305 30 2444 2357 2392 2410 2360 20 2214 2299 2246 2265 2294 15, 15 1231 1005 30, 20 2064 1850 PMX, makespan 51 PMX, PMX 55, 512 515 5000, makespan makespan 23
55 512 15, 15 513 20, 15 514 30, 15 515 50, 15 4500, 1500, 1 1500, 2 4500 2 24
6 61 75%, 10% 61, 55%, 50% 62, 61, ( 511 ), 75% 4 1, 10% 3 75%, 10% 55%, 50%, 2, 55% 3 2 1 2 2, 2 makespan 61 25
61 61 75%, 10%, PMX( ) PMX( ) 10, 5 666 732 666 666 10, 10 943 1037 948 948 15, 15 1233 940 1356 1271 1269 20, 15 1345 1329 1479 1427 1411 30, 20 2057 1949 2262 2288 2282 50, 20 3071 3378 3309 3250 100, 20 5464 6010 5610 5583 62 55%, 50%, PMX( ) PMX( ) 10, 5 666 732 666 666 10, 10 943 1037 948 943 15, 15 1233 940 1356 1271 1242 20, 15 1345 1329 1479 1426 1365 30, 20 2057 1949 2262 2242 2188 50, 20 3071 3378 3281 3225 100, 20 5464 6010 5631 5501 10, 5 makespan 62 10, 10 PMX( ) makespan 10, 10, makespan, 61, 62 upper bound 1 26
62 62, 4, 10, 5 15, 15 makespan,, upper bound upper bound upper bound 15, 5 20, 5 30, 10, 30, 20 50, 20 62 100, 20 PMX( ), 62, M 2 1, ( J 1 ), J 1 2 M 2 62 2 (M 1 ) 1 (J 2 ), J 1 2 J 1 1, J 2 M 1 J 1 2 J 2 1, 62 M 1 27
62 62,, J 1 3,, 62 = (1, 1, 2, ), 1, 1 2 1 1 28
,,,,,,, 29
[1],, 1998 [2] L Dabis, Handbook of Genetic Algorithms (,,, 1944) [3], NEH, No36 2008 [4] OR-Library, http://peoplebrunelacuk/~mastjjb/jeb/infohtml, 2009/12/18 [5] CP2SAT:JSS benchmark redults, http://bachistckobe-uacjp/csp2sat/jss/, 2010/1/27 [6], http://mikilabdoshishaacjp/dia/research/report/2002/0504/018/report20020504018html, 2009/12/18 30