job-shop.dvi
|
|
|
- かつかげ かんけ
- 9 years ago
- Views:
Transcription
1 21 GA GA for job-shop scheduling problem by plural chromosome expression
2 GA 1,,,,,,,, 4, 4,, i
3 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
4 JSP iii
5 511 (PMX) (CX) iv
6 GA J J J J J J J J J v
7 PMX PMX PMX PMX CX CX , , , , vi
8 21 JSP makespan %, 10% %, 50% 26 vii
9 1,,,,,,,, NP, 1,,,,,
10 ,, 5 6 2
11 2 21 (job-shop scheduling problem: JSP),, ( ) (makespan),, (makespan) 1 ( ) JSP, 21 4, 3 4 J 1,J 2,J 3,J 4, 3 M 1,M 2,M 3 3
12 22 21 JSP 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
13 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 J 1 21, M 2 J 2, M 2 J 1 22 makespan 10,
14 3 31 (Genetic Algorithm: GA),,, [1] ( ) ( ) ( ) GA 31 GA 6
15 , , 2, ( ), 2 [1],,, ( ), 0, 1, 2,, [2] 7
16 ( ), 324 GA, 8
17 4 JSP JSP, [3] 1,, makespan 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
18 , 2 J 4 2 3, J 2 2, 3 43 makespan , J 4 10
19 42 1 J J 1 1, M 2 J 2 1 M 2, J 1 1 1, 1 makespan J 1 1 J 2 2 makespan 46, J 2 47 J 2 11
20 42 1 makespan J 1 J makespan J J 4 1, makespan 10 12
21 J , 1 1, , f 1, o 1, f
22 43 o 1 J 1 2, 3, J 4,J 2 J makespan , 1 makespan 43 42, 1 15, , , , , 14
23 44 44, 1, , 1 15, , , , makespan upper bound, lower bound [4][5] upper bound 1, (= * ), ( ) 4, ,
24 45, 2 J J J , J J J 3 3 J makespan J
25 , 420 M 1 J 4 J 3 1 1, makespan, 1 15, , , , , 15, JSP, 17
26 5 51, 1 *, 4, , (PMX) (partial mapped crossover: PMX), 2 ( ) 1 2, 53 2 P 1, P 2 18
27 51 53 PMX P 1 P 2, P 2 P 1 P 1 P 2 P 1 4 7, PMX 1 55 PMX 2 P P 2 P 2 P 1, 56 C 1, C 2 C 1 P 2, C 2 P 1 56 PMX,,, 19
28 (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 , P 1 P 2 59, P 1, P 2 C 1, C 2 20
29 52 59 CX , %
30 %, 50% 50%, 50% 54 makespan, makespan, 1, 1,, , 2, 22
31 55 51 PMX( ) PMX( ) PMX( ) PMX( ) CX , , PMX, makespan 51 PMX, PMX 55, , makespan makespan 23
32 , , , , , 1500, ,
33 %, 10% 61, 55%, 50% 62, 61, ( 511 ), 75% 4 1, 10% 3 75%, 10% 55%, 50%, 2, 55% , 2 makespan 61 25
34 %, 10%, PMX( ) PMX( ) 10, , , , , , , %, 50%, PMX( ) PMX( ) 10, , , , , , , , 5 makespan 62 10, 10 PMX( ) makespan 10, 10, makespan, 61, 62 upper bound 1 26
35 62 62, 4, 10, 5 15, 15 makespan,, upper bound upper bound upper bound 15, 5 20, 5 30, 10, 30, 20 50, , 20 PMX( ), 62, M 2 1, ( J 1 ), J 1 2 M (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
36 62 62,, J 1 3,, 62 = (1, 1, 2, ), 1,
37 ,,,,,,, 29
38 [1],, 1998 [2] L Dabis, Handbook of Genetic Algorithms (,,, 1944) [3], NEH, No [4] OR-Library, /12/18 [5] CP2SAT:JSS benchmark redults, /1/27 [6], /12/18 30
2
1 2 3 4 5 6 7 8 9 10 I II III 11 IV 12 V 13 VI VII 14 VIII. 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 _ 33 _ 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 VII 51 52 53 54 55 56 57 58 59
untitled
i ii iii iv v 43 43 vi 43 vii T+1 T+2 1 viii 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 a) ( ) b) ( ) 51
i
14 i ii iii iv v vi 14 13 86 13 12 28 14 16 14 15 31 (1) 13 12 28 20 (2) (3) 2 (4) (5) 14 14 50 48 3 11 11 22 14 15 10 14 20 21 20 (1) 14 (2) 14 4 (3) (4) (5) 12 12 (6) 14 15 5 6 7 8 9 10 7
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 () - 1 - - 2 - - 3 - - 4 - - 5 - 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
soturon.dvi
12 Exploration Method of Various Routes with Genetic Algorithm 1010369 2001 2 5 ( Genetic Algorithm: GA ) GA 2 3 Dijkstra Dijkstra i Abstract Exploration Method of Various Routes with Genetic Algorithm
入門ガイド
ii iii iv NEC Corporation 1998 v P A R 1 P A R 2 P A R 3 T T T vi P A R T 4 P A R T 5 P A R T 6 P A R T 7 vii 1P A R T 1 2 2 1 3 1 4 1 1 5 2 3 6 4 1 7 1 2 3 8 1 1 2 3 9 1 2 10 1 1 2 11 3 12 1 2 1 3 4 13
<4D6963726F736F667420506F776572506F696E74202D208376838C835B83938365815B835683878393312E707074205B8CDD8AB78382815B83685D>
i i vi ii iii iv v vi vii viii ix 2 3 4 5 6 7 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
SC-85X2取説
I II III IV V VI .................. VII VIII IX X 1-1 1-2 1-3 1-4 ( ) 1-5 1-6 2-1 2-2 3-1 3-2 3-3 8 3-4 3-5 3-6 3-7 ) ) - - 3-8 3-9 4-1 4-2 4-3 4-4 4-5 4-6 5-1 5-2 5-3 5-4 5-5 5-6 5-7 5-8 5-9 5-10 5-11
262014 3 1 1 6 3 2 198810 2/ 198810 2 1 3 4 http://www.pref.hiroshima.lg.jp/site/monjokan/ 1... 1... 1... 2... 2... 4... 5... 9... 9... 10... 10... 10... 10... 13 2... 13 3... 15... 15... 15... 16 4...
これわかWord2010_第1部_100710.indd
i 1 1 2 3 6 6 7 8 10 10 11 12 12 12 13 2 15 15 16 17 17 18 19 20 20 21 ii CONTENTS 25 26 26 28 28 29 30 30 31 32 35 35 35 36 37 40 42 44 44 45 46 49 50 50 51 iii 52 52 52 53 55 56 56 57 58 58 60 60 iv
パワポカバー入稿用.indd
i 1 1 2 2 3 3 4 4 4 5 7 8 8 9 9 10 11 13 14 15 16 17 19 ii CONTENTS 2 21 21 22 25 26 32 37 38 39 39 41 41 43 43 43 44 45 46 47 47 49 52 54 56 56 iii 57 59 62 64 64 66 67 68 71 72 72 73 74 74 77 79 81 84
これでわかるAccess2010
i 1 1 1 2 2 2 3 4 4 5 6 7 7 9 10 11 12 13 14 15 17 ii CONTENTS 2 19 19 20 23 24 25 25 26 29 29 31 31 33 35 36 36 39 39 41 44 45 46 48 iii 50 50 52 54 55 57 57 59 61 63 64 66 66 67 70 70 73 74 74 77 77
1... 1... 1... 3 2... 4... 4... 4... 4... 4... 6... 10... 11... 15... 30
1 2420128 1 6 3 2 199103 189/1 1991031891 3 4 5 JISJIS X 0208, 1997 1 http://www.pref.hiroshima.lg.jp/site/monjokan/ 1... 1... 1... 3 2... 4... 4... 4... 4... 4... 6... 10... 11... 15... 30 1 3 5 7 6 7
平成18年版 男女共同参画白書
i ii iii iv v vi vii viii ix 3 4 5 6 7 8 9 Column 10 11 12 13 14 15 Column 16 17 18 19 20 21 22 23 24 25 26 Column 27 28 29 30 Column 31 32 33 34 35 36 Column 37 Column 38 39 40 Column 41 42 43 44 45
178 5 I 1 ( ) ( ) 10 3 13 3 1 8891 8 3023 6317 ( 10 1914 7152 ) 16 5 1 ( ) 6 13 3 13 3 8575 3896 8 1715 779 6 (1) 2 7 4 ( 2 ) 13 11 26 12 21 14 11 21
I 178 II 180 III ( ) 181 IV 183 V 185 VI 186 178 5 I 1 ( ) ( ) 10 3 13 3 1 8891 8 3023 6317 ( 10 1914 7152 ) 16 5 1 ( ) 6 13 3 13 3 8575 3896 8 1715 779 6 (1) 2 7 4 ( 2 ) 13 11 26 12 21 14 11 21 4 10 (
44 4 I (1) ( ) (10 15 ) ( 17 ) ( 3 1 ) (2)
(1) I 44 II 45 III 47 IV 52 44 4 I (1) ( ) 1945 8 9 (10 15 ) ( 17 ) ( 3 1 ) (2) 45 II 1 (3) 511 ( 451 1 ) ( ) 365 1 2 512 1 2 365 1 2 363 2 ( ) 3 ( ) ( 451 2 ( 314 1 ) ( 339 1 4 ) 337 2 3 ) 363 (4) 46
i ii i iii iv 1 3 3 10 14 17 17 18 22 23 28 29 31 36 37 39 40 43 48 59 70 75 75 77 90 95 102 107 109 110 118 125 128 130 132 134 48 43 43 51 52 61 61 64 62 124 70 58 3 10 17 29 78 82 85 102 95 109 iii
四校＿目次～巻頭言.indd
107 25 1 2016 3 Key Words : A 114 67 58.84 Mann-Whitney 6 1. 2. 3. 4. 5. 6. I. 21 4 B 23 11 1 9 8 7 23456 108 25 1 2016 3 78 9 II. III. IV. 1. 24 4 A 114 2. 24 5 6 3. 4. 5. 3 42 5 16 6 22 5 4 4 4 3 6.
エクセルカバー入稿用.indd
i 1 1 2 3 5 5 6 7 7 8 9 9 10 11 11 11 12 2 13 13 14 15 15 16 17 17 ii CONTENTS 18 18 21 22 22 24 25 26 27 27 28 29 30 31 32 36 37 40 40 42 43 44 44 46 47 48 iii 48 50 51 52 54 55 59 61 62 64 65 66 67 68
01_.g.r..
I II III IV V VI VII VIII IX X XI I II III IV V I I I II II II I I YS-1 I YS-2 I YS-3 I YS-4 I YS-5 I YS-6 I YS-7 II II YS-1 II YS-2 II YS-3 II YS-4 II YS-5 II YS-6 II YS-7 III III YS-1 III YS-2
ii iii iv CON T E N T S iii iv v Chapter1 Chapter2 Chapter 1 002 1.1 004 1.2 004 1.2.1 007 1.2.2 009 1.3 009 1.3.1 010 1.3.2 012 1.4 012 1.4.1 014 1.4.2 015 1.5 Chapter3 Chapter4 Chapter5 Chapter6 Chapter7
AccessflÌfl—−ÇŠš1
ACCESS ACCESS i ii ACCESS iii iv ACCESS v vi ACCESS CONTENTS ACCESS CONTENTS ACCESS 1 ACCESS 1 2 ACCESS 3 1 4 ACCESS 5 1 6 ACCESS 7 1 8 9 ACCESS 10 1 ACCESS 11 1 12 ACCESS 13 1 14 ACCESS 15 1 v 16 ACCESS
活用ガイド （ソフトウェア編）
(Windows 95 ) ii iii iv NEC Corporation 1999 v P A R T 1 vi P A R T 2 vii P A R T 3 P A R T 4 viii P A R T 5 ix x P A R T 1 2 3 1 1 2 4 1 2 3 4 5 1 1 2 3 4 6 5 6 7 7 1 1 2 8 1 9 1 1 2 3 4 5 6 1 2 3 4
困ったときのQ&A
ii iii iv NEC Corporation 1997 v P A R T 1 vi vii P A R T 2 viii P A R T 3 ix x xi 1P A R T 2 1 3 4 1 5 6 1 7 8 1 9 1 2 3 4 10 1 11 12 1 13 14 1 1 2 15 16 1 2 1 1 2 3 4 5 17 18 1 2 3 1 19 20 1 21 22 1
活用ガイド （ソフトウェア編）
(Windows 98 ) ii iii iv v NEC Corporation 1999 vi P A R T 1 P A R T 2 vii P A R T 3 viii P A R T 4 ix P A R T 5 x P A R T 1 2 3 1 1 2 4 1 2 3 4 5 1 1 2 3 4 5 6 6 7 7 1 1 2 8 1 9 1 1 2 3 4 5 6 1 2 3 10
CRS4
I... 1 II... 1 A... 1 B... 1 C... 1 D... 2 E... 3 III... 3 A... 3 B... 4 C... 5 IV... 8 A... 8 B... 8 C... 9 D... 10 V... 11 A... 11 B... 11 C... 12 VI... 12 A... 12 B... 12 C... 12 VII... 13 ii I II A
25 Removal of the fricative sounds that occur in the electronic stethoscope
25 Removal of the fricative sounds that occur in the electronic stethoscope 1140311 2014 3 7 ,.,.,.,.,.,.,.,,.,.,.,.,,. i Abstract Removal of the fricative sounds that occur in the electronic stethoscope
パソコン機能ガイド
PART12 ii iii iv v 1 2 3 4 5 vi vii viii ix P A R T 1 x P A R T 2 xi P A R T 3 xii xiii P A R T 1 2 3 1 4 5 1 6 1 1 2 7 1 2 8 1 9 10 1 11 12 1 13 1 2 3 4 14 1 15 1 2 3 16 4 1 1 2 3 17 18 1 19 20 1 1
パソコン機能ガイド
PART2 iii ii iv v 1 2 3 4 5 vi vii viii ix P A R T 1 x P A R T 2 xi P A R T 3 xii xiii P A R T 1 2 1 3 4 1 5 6 1 2 1 1 2 7 8 9 1 10 1 11 12 1 13 1 2 3 14 4 1 1 2 3 15 16 1 17 1 18 1 1 2 19 20 1 21 1 22
1... 1 2... 1 1... 1 2... 2 3... 2 4... 4 5... 4 6... 4 7... 22 8... 22 3... 22 1... 22 2... 23 3... 23 4... 24 5... 24 6... 25 7... 31 8... 32 9... 3
3 2620149 3 6 3 2 198812 21/ 198812 21 1 3 4 5 JISJIS X 0208 : 1997 JIS 4 JIS X 0213:2004 http://www.pref.hiroshima.lg.jp/site/monjokan/ 1... 1 2... 1 1... 1 2... 2 3... 2 4... 4 5... 4 6... 4 7... 22
1996 2000 2004 1984 2005 7150 000 9 500 9 4 13 10 95 11 11 12 20002004 9 70
14 2006 1 Key Words 2002 3 1 2 3 3 1 2 3 1969 1987 69 1996 2000 2004 1984 2005 7150 000 9 500 9 4 13 10 95 11 11 12 20002004 9 70 14 2006 1 15 71 72 1 22 6 32 9 200 6 3 1 2 2000 10 1 2003 10 2005 6 5 4
立命館21_川端先生.indd
21 119-132 2010 ( ) ' Key Words 119 21 2010 7 1962 2001 2001 2007 1982 1988 1997 2007 1997 1998 1863 1880 1 1998 1998 2001 1599 120 121 1599 1695 8 1695 1714 4 1714 1715 5 1715 100 1812 9 1812 1864 2001
..,,,, , ( ) 3.,., 3.,., 500, 233.,, 3,,.,, i
25 Feature Selection for Prediction of Stock Price Time Series 1140357 2014 2 28 ..,,,,. 2013 1 1 12 31, ( ) 3.,., 3.,., 500, 233.,, 3,,.,, i Abstract Feature Selection for Prediction of Stock Price Time
06’ÓŠ¹/ŒØŒì
FD. FD FD FD FD FD FD / Plan-Do-See FD FD FD FD FD FD FD FD FD FD FD FD FD FD JABEE FD A. C. A B .. AV .. B Communication Space A FD FD ES FD FD The approach of the lesson improvement in Osaka City University
長崎県地域防災計画
i ii iii iv v vi vii viii ix - 1 - - 2 - - 3 - - 4 - - 5 - - 6 - - 7 - - 8 - - 9 - 玢 - 10 - - 11 - - 12 - - 13 - - 14 - - 15 - - 16 - - 17 - - 18 - - 19 - - 20 - - 21 - - 22 - - 23 - - 24 - - 25 - -
ONLINE_MANUAL
JPN ii iii iv v 6 vi vii viii 1 CHAPTER 1-1 1 2 1-2 1 2 3 4 5 1-3 6 7 1-4 2 CHAPTER 2-1 2-2 2-3 1 2 3 4 5 2-4 6 7 8 2-5 9 10 2-6 11 2-7 1 2 2-8 3 (A) 4 5 6 2-9 1 2-10 2 3 2-11 4 5 2-12 1 2 2-13 3 4 5
ONLINE_MANUAL
JPN ii iii iv v vi 6 vii viii 1 CHAPTER 1-1 1 2 1-2 1 2 3 1-3 4 5 6 7 1-4 2 CHAPTER 2-1 2-2 2-3 1 2 3 4 5 2-4 6 7 8 2-5 9 10 2-6 11 2-7 1 2 2-8 3 (A) 4 5 6 2-9 1 2-10 2 3 2-11 4 5 2-12 1 2 2-13 3 4 5