1 Introduction
2 Literature Review and Problem Definition
2.1 Literature Review
2.2 Flexible Job Shop Problem Definition
3 Modified Iterated Greedy
3.1 Classical Iterated Greedy
3.2 Presented Algorithm (MIG)
3.3 Destruct Phase
3.4 Reconstruct Phase
3.5 Dispatching Rules
3.5.1 Offline Dispatching Rules
3.5.2 Online Dispatching Rules
3.6 Techniques Used to Control the Algorithm
4 Experiments and Discussion
4.1 Experiment 1
n × m | HA | GATS | TABC | HHS | HDE-N2 | hGA | MIG |
---|---|---|---|---|---|---|---|
4 × 5 | ‒ | 11 | 11 | ‒ | 11 | ‒ | 11 |
10 × 7 | ‒ | 11 | 11 | ‒ | 11 | ‒ | 11 |
10 × 10 | 7 | 7 | 7 | 7 | 7 | 7 | 7 |
8 × 8 | 14 | 14 | 14 | 14 | 14 | 14 | 14 |
15 × 10 | 11 | 11 | 11 | 11 | 11 | 11 | 11 |
n × m | HA | GATS | TABC | HHS | HDE-N2 | hGA | MIG |
---|---|---|---|---|---|---|---|
4 × 5 | ‒ | 0.05 | 0.47 | ‒ | 0.09 | ‒ | 0.00 |
10 × 7 | ‒ | 0.72 | 1.2 | ‒ | 0.46 | ‒ | 0.00 |
10 × 10 | 0.01 | 1.51 | 1.4 | 0.01 | 0.37 | 43.1 | 0.00 |
8 × 8 | 0.00 | 0.36 | 1.19 | 0.00 | 0.31 | 22.4 | 0.00 |
15 × 10 | 0.33 | 29.71 | 2.97 | 0.42 | 2.19 | 112.2 | 0.07 |
4.2 Experiment 2
Ins. | HA | EPSO | EM2 | MILP | AIA | HHS | MIG |
---|---|---|---|---|---|---|---|
SFJS01 | 66 | 66 | 66 | 66 | 66 | 66 | 66 |
SFJS02 | 107 | 107 | 107 | 107 | 107 | 107 | 107 |
SFJS03 | 221 | 221 | 221 | 221 | 221 | 221 | 221 |
SFJS04 | 355 | 355 | 355 | 355 | 355 | 355 | 355 |
SFJS05 | 119 | 119 | 119 | 119 | 119 | 119 | 119 |
SFJS06 | 320 | 320 | 320 | 320 | 320 | 320 | 320 |
SFJS07 | 397 | 397 | 397 | 397 | 397 | 397 | 397 |
SFJS08 | 253 | 253 | 253 | 253 | 253 | 253 | 253 |
SFJS09 | 210 | 210 | 210 | 210 | 210 | 210 | 210 |
SFJS10 | 516 | 516 | 516 | 516 | 516 | 516 | 516 |
MFJS01 | 468 | 468 | 468 | 468 | 468 | 468 | 462 |
MFJS02 | 446 | 446 | 446 | 446 | 448 | 446 | 446 |
MFJS03 | 466 | 466 | 466 | 466 | 468 | 466 | 450 |
MFJS04 | 554 | 554 | 564 | 564 | 554 | 554 | 554 |
MFJS05 | 514 | 514 | 514 | 514 | 527 | 514 | 514 |
MFJS06 | 634 | 634 | 634 | 634 | 635 | 634 | 634 |
MFJS07 | 879 | 879 | 928 | 879 | 879 | 879 | 881 |
MFJS08 | 884 | 884 | – | – | 884 | 884 | 889 |
MFJS09 | 1055 | 1059 | – | – | 1088 | 1055 | 1059 |
MFJS10 | 1196 | 1205 | – | – | 1267 | 1196 | 1214 |
Ins. | n × m | HA | EM2 | MILP | AIA | HHS | MIG |
---|---|---|---|---|---|---|---|
SFJS01 | 2 × 2 | 0.00 | 0.03 | 0.00 | 0.03 | 0.00 | 0.00 |
SFJS02 | 2 × 2 | 0.00 | 0.10 | 0.01 | 0.03 | 0.00 | 0.00 |
SFJS03 | 2 × 2 | 0.00 | 0.05 | 0.05 | 0.04 | 0.00 | 0.00 |
SFJS04 | 3 × 2 | 0.00 | 0.04 | 0.02 | 0.04 | 0.00 | 0.00 |
SFJS05 | 3 × 2 | 0.00 | 0.06 | 0.04 | 0.04 | 0.00 | 0.00 |
SFJS06 | 3 × 3 | 0.00 | 0.28 | 0.01 | 0.04 | 0.00 | 0.00 |
SFJS07 | 3 × 5 | 0.00 | 0.03 | 0.00 | 0.04 | 0.00 | 0.00 |
SFJS08 | 3 × 4 | 0.00 | 0.16 | 0.04 | 0.05 | 0.00 | 0.00 |
SFJS09 | 3 × 3 | 0.00 | 1.26 | 0.01 | 0.05 | 0.00 | 0.00 |
SFJS10 | 4 × 5 | 0.00 | 0.06 | 0.02 | 0.05 | 0.00 | 0.00 |
MFJS01 | 5 × 6 | 0.00 | 0.78 | 0.26 | 9.23 | 0.01 | 0.00 |
MFJS02 | 5 × 7 | 0.00 | 49 | 0.87 | 9.35 | 0.01 | 0.00 |
MFJS03 | 6 × 7 | 0.02 | 191 | 1.66 | 10.06 | 0.12 | 0.002 |
MFJS04 | 7 × 7 | 0.02 | 1051 | 27.43 | 10.54 | 0.06 | 0.00 |
MFJS05 | 7 × 7 | 0.02 | 225 | 4.55 | 10.61 | 0.02 | 0.00 |
MFJS06 | 8 × 7 | 0.01 | 231 | 52.48 | 22.18 | 0.01 | 0.00 |
MFJS07 | 8 × 7 | 0.08 | 3600 | 1890 | 24.82 | 0.11 | 0.00 |
MFJS08 | 9 × 8 | 0.06 | ‒ | ‒ | 26.94 | 0.08 | 0.00 |
MFJS09 | 11 × 8 | 0.48 | ‒ | ‒ | 30.76 | 0.94 | 0.005 |
MFJS10 | 12 × 8 | 0.59 | ‒ | ‒ | 30.94 | 0.69 | 0.005 |
4.3 Experiment 3
Ins. | n × m | HA | HTGA | GATS | TABC | Heuristic | AMMA | AIA | HHS | TS | IACO | MIG |
---|---|---|---|---|---|---|---|---|---|---|---|---|
MK01 | 10 × 6 | 40 | 40 | 40 | 40 | 42 | 40 | 40 | 40 | 40 | 40 | 40 |
MK02 | 10 × 6 | 26 | 26 | 27 | 26 | 28 | 26 | 26 | 26 | 26 | 26 | 26 |
MK03 | 15 × 8 | 204 | 204 | 204 | 204 | 204 | 204 | 204 | 204 | 204 | 204 | 204 |
MK04 | 15 × 8 | 60 | 60 | 64 | 60 | 75 | 60 | 60 | 60 | 60 | 60 | 60 |
MK05 | 15 × 4 | 172 | 173 | 173 | 173 | 179 | 172 | 173 | 172 | 173 | 173 | 172 |
MK06 | 10 × 10 | 57 | 61 | 65 | 60 | 69 | 57 | 63 | 58 | 58 | 60 | 60 |
MK07 | 20 × 5 | 139 | 141 | 144 | 139 | 149 | 139 | 140 | 139 | 144 | 140 | 140 |
MK08 | 20 × 10 | 523 | 523 | 523 | 523 | 555 | 523 | 523 | 523 | 523 | 523 | 523 |
MK09 | 20 × 10 | 307 | 307 | 311 | 307 | 342 | 307 | 312 | 307 | 307 | 307 | 307 |
MK10 | 20 × 15 | 197 | 213 | 222 | 202 | 242 | 198 | 214 | 205 | 198 | 208 | 221 |
Ins. | n × m | HA | GATS | TABC | Heuristic | AIA | HHS | MIG |
---|---|---|---|---|---|---|---|---|
MK01 | 10 × 6 | 0.06 | 0.93 | 3.36 | 0.09 | 97.21 | 3.87 | 0.002 |
MK02 | 10 × 6 | 0.59 | 1.18 | 3.72 | 0.17 | 103.46 | 5.79 | 0.005 |
MK03 | 15 × 8 | 0.16 | 1.55 | 1.56 | 0.52 | 247.37 | 36.60 | 0.00 |
MK04 | 15 × 8 | 0.49 | 4.36 | 66.58 | 0.20 | 152.07 | 13.30 | 0.04 |
MK05 | 15 × 4 | 4.57 | 8.02 | 78.45 | 0.20 | 171.95 | 35.78 | 0.32 |
MK06 | 10 × 10 | 53.82 | 110.01 | 173.98 | 0.45 | 245.62 | 111.65 | 2.38 |
MK07 | 20 × 5 | 20.01 | 19.73 | 66.19 | 0.39 | 161.92 | 26.16 | 0.04 |
MK08 | 20 × 10 | 0.02 | 11.50 | 2.15 | 0.66 | 392.25 | 171.10 | 0.00 |
MK09 | 20 × 10 | 0.86 | 79.68 | 304.43 | 0.94 | 389.71 | 172.24 | 0.42 |
MK10 | 20 × 15 | 33.21 | 185.64 | 418.19 | 1.20 | 384.54 | 437.69 | 1.42 |