JIT: Just In Time / Douki Seisan sequencing


  • A Bounded Dynamic Programming algorithm for the Blocking Flow Shop problem

(article)

Authors


Joaquin Bautista1, Alberto Cano1, Ramón Companys2 and Imma Ribas2

 

1 UPC - Nissan Chair

2 DOE - UPC


Abstract


We present some results attained with two variants of bounded dynamic programming algorithm to solve the Fm|block|Cmax problem using as experimental data the wellknown Taillard instances. We have improved the best known solutions for four of the Taillard’s instances.



Improved Sequences


Instance 68

Cmax=5882

56 53 21 12 32 13 10 88 49 81 61 89 64 18 83 93 31 27 46 79 84 39 58 78 34 1 52 80 48 8 45 90 29 86 74 2 85 55 99 72 73 22 70 69 43 75 65 54 23 92 4 63 5 11 57 3 24 67 41 14 62 51 7 33 100 47 44 60 38 28 50 97 30 35 36 87 42 91 76 77 71 20 94 19 25 9 59 17 82 40 68 96 26 37 16 66 15 6 98 95



Instance 70

Cmax=6154

24 63 21 5 13 60 51 87 57 49 69 40 34 16 38 7 46 27 92 29 31 95 82 33 93 53 61 68 72 22 11 48 17 71 52 78 89 99 36 25 43 67 76 4 79 50 35 37 15 55 88 80 1 75 18 42 83 84 14 44 56 77 39 91 97 23 10 90 32 64 6 30 19 8 81 98 58 100 26 62 74 70 20 94 41 96 3 59 86 85 54 28 66 9 45 73 47 12 65 2



Instance 92

Cmax=13287

31 27 170 104 158 155 182 174 96 133 1 197 140 156 146 28 121 13 131 195 78 173 128 16 108 191 58 51 38 132 198 129 192 141 17 37 18 175 190 32 152 11 112 61 186 122 42 69 29 166 119 143 88 157 9 48 25 134 5 52 193 59 151 60 6 41 124 71 111 113 179 118 102 185 3 53 123 82 97 200 14 50 187 33 150 8 94 63 188 181 98 55 65 161 70 115 62 163 160 164 74 7 125 103 144 54 81 83 184 165 24 4 72 43 12 147 180 120 49 153 106 39 44 91 66 172 178 30 34 57 148 95 149 99 142 90 159 85 162 76 194 68 89 171 116 36 189 137 45 168 110 138 135 105 23 40 21 107 87 2 20 109 75 56 126 47 80 26 92 130 19 73 64 15 145 86 114 22 167 93 154 84 46 176 35 169 67 199 79 136 183 177 117 139 100 77 127 101 196 10



Instance 95

Cmax=13319

198 74 154 108 98 73 100 44 70 48 118 113 65 42 91 196 117 17 66 121 156 152 83 75 176 62 116 82 38 71 109 22 93 168 63 132 172 67 14 54 106 163 190 36 10 12 57 139 160 26 155 2 60 180 189 150 127 95 135 114 130 8 137 119 53 129 19 13 1 56 27 170 47 23 6 16 169 35 195 110 46 175 164 120 136 58 128 92 144 79 157 111 21 3 178 76 9 88 104 197 167 81 97 123 30 126 52 84 89 131 55 4 51 192 29 80 191 166 94 149 103 40 188 96 72 147 184 194 68 7 138 187 20 43 115 162 49 142 87 77 145 41 173 179 101 181 125 186 105 193 185 25 33 153 161 102 37 171 143 5 99 133 69 159 31 141 107 11 61 18 151 112 28 199 165 148 122 140 182 34 45 85 39 59 134 177 32 50 15 158 78 24 146 200 64 183 124 90 86 174





Return to previous page