job | sequence | processing times |
5, 3, 8 | ||
8, 2, 7 |
The blocking job shop scheduling problem (BJSS) is a version of the classical job shop scheduling with no intermediate buffer between machines. The BJSS is known to be NP-hard in the strong sense. A known way to solve such a problem is to use the Tabu Search algorithm (TS) which is a higher level heuristic procedure for solving optimization problems, designed to guide other methods to escape the trap of local optimality. However, the use of the classical TS neighborhood on BJSS problem produces infeasible solutions in most cases (98% of cases). This leads to waste valuable time in exploring infeasible solutions. To overcome this drawback, we propose a new tabu search neighborhood based on reconstruction strategy. This neighborhood consists to remove arcs causing the infeasibility and rebuild the neighbor solutions by using heuristics. Experiments on the reference benchmark instances show that the TS algorithm using the proposed neighborhood improves most of the known results in the literature and gives new upper bounds for more than 52 benchmarks in both BJSS cases (BJSS with Swap and BJSS no-Swap). Moreover, the proposed approach reaches much faster the optimal solution for most of the optimally solved benchmarks.
Citation: |
Figure 3. Alternative graph for BJSS instance of table 1
Figure 4. Schedule for BJSS in Table 1 whit Cmax=26
Figure 5. Gantt chart of the schedule in figure 4
Table 1. BJSS instance with two jobs and three machines
job | sequence | processing times |
5, 3, 8 | ||
8, 2, 7 |
Table 2. The description of the symbols used in our TS
Symbol | Description |
s | a feasible schedule (solution) for the BJSS problem. |
The best solution found by TS. | |
The Cost (makespan) of the solution s. | |
Best solution in Cand(s). | |
Tabu List. | |
a set of unforbidden neighbor solutions of the schedule s. | |
a set of all neighbor solutions of schedule s. |
Table 3.
Comparison of the obtained Makespan results with the optimal solutions of the (10
Instance | BWS | BNS | |||||
Abz5 | 1468 | 1487 | 1468 | 1641 | 1641 | 1641 | |
Abz6 | 1145 | 1190 | 1160 | 1249 | 1254 | 1249 | |
Mt10 | 1068 | 1095 | 1071 | 1158 | 1168 | 1158 | |
Orb1 | 1175 | 1182 | 1175 | 1256 | 1265 | 1259 | |
Orb2 | 1041 | 1062 | 1041 | 1144 | 1154 | 1146 | |
Orb3 | 1160 | 1162 | 1160 | 1311 | 1311 | 1311 | |
Orb4 | 1146 | 1187 | 1146 | 1246 | 1246 | 1246 | |
Orb5 | 995 | 1008 | 995 | 1203 | 1203 | 1203 | |
Orb6 | 1199 | 1199 | 1199 | 1266 | 1266 | 1266 | |
Orb7 | 483 | 490 | 483 | 527 | 535 | 527 | |
Orb8 | 995 | 1003 | 995 | 1139 | 1139 | 1139 | |
Orb9 | 1039 | 1076 | 1045 | 1130 | 1131 | 1130 | |
Orb10 | 1146 | 1146 | 1146 | 1367 | 1367 | 1367 | |
La16 | 1060 | 1090 | 1060 | 1148 | 1151 | 1148 | |
La17 | 929 | 943 | 930 | 968 | 979 | 968 | |
La18 | 1025 | 1038 | 1025 | 1077 | 1087 | 1077 | |
La19 | 1043 | 1067 | 1053 | 1102 | 1104 | 1102 | |
La20 | 1060 | 1085 | 1060 | 1118 | 1125 | 1118 | |
MRE | 1.7% | 0.18% | 0.36% | 0, 02% |
Table 4.
Our
Instance | BWS | BNS | |||||||
La01 | 10 |
[18,20] 793 | 820 | 780 | 793 | [20,15] 881 | 881 | 881 | |
La02 | 10 |
[8,18,20] 793 | 793 | 793 | 793 | [20,15] 900 | 901 | 900 | |
La03 | 10 |
[18,20] 715 | 740 | 715 | 715 | [20,15] 808 | 810 | 808 | |
La04 | 10 |
[18,20] 743 | 764 | 743 | 743 | [20,15] 859 | 864 | 859 | |
La05 | 10 |
[18,20] 664 | 666 | 670 | 664 | [20,15] 732 | 732 | 732 | |
La06 | 15 |
[18] 1064 | 1180 | 1120 | 1076 | [20] 1225 | 1207 | 1194 | |
La07 | 15 |
[20] 1020 | 1084 | 1052 | 1029 | [20] 1133 | 1138 | 1130 | |
La08 | 15 |
[18] 1062 | 1125 | 1089 | 1060 | [15] 1216 | 1203 | 1173 | |
La09 | 15 |
[20] 1162 | 1223 | 1209 | 1188 | [20] 1311 | 1324 | 1314 | |
La10 | 15 |
[18] 1110 | 1203 | 1142 | 1110 | [20] 1237 | 1252 | 1232 | |
La11 | 20 |
[18] 1466 | 1584 | 1504 | 1475 | [20] 1641 | 1621 | 1577 | |
La12 | 20 |
[20] 1271 | 1391 | 1326 | 1276 | [20] 1465 | 1448 | 1401 | |
La13 | 20 |
[18] 1465 | 1541 | 1474 | 1456 | [20] 1627 | 1586 | 1547 | |
La14 | 20 |
[18] 1506 | 1620 | 1520 | 1472 | [20] 1686 | 1648 | 1586 | |
La15 | 20 |
[18,20] 1517 | 1630 | 1526 | 1490 | [20] 1680 | 1651 | 1620 | |
La16 | 10 |
[20] 1060 | 1142 | 1090 | 1060 | [20,15] 1148 | 1151 | 1148 | |
La17 | 10 |
[20] 929 | 977 | 943 | 930 | [20,15] 968 | 979 | 968 | |
La18 | 10 |
[20] 1025 | 1078 | 1038 | 1025 | [20,15] 1077 | 1087 | 1077 | |
La19 | 10 |
[20] 1043 | 1093 | 1067 | 1053 | [20,15] 1102 | 1104 | 1102 | |
La20 | 10 |
[20] 1060 | 1154 | 1085 | 1060 | [20,15] 1118 | 1125 | 1118 | |
La21 | 15 |
[20] 1490 | 1554 | 1499 | 1467 | [20] 1627 | 1540 | 1501 | |
La22 | 15 |
[20] 1339 | 1458 | 1369 | 1347 | [20] 1426 | 1421 | 1368 | |
La23 | 15 |
[20] 1445 | 1570 | 1477 | 1442 | [20] 1574 | 1564 | 1537 | |
La24 | 15 |
[20] 1434 | 1546 | 1433 | 1398 | [20] 1502 | 1510 | 1447 | |
La25 | 15 |
[20] 1392 | 1499 | 1420 | 1373 | [20] 1533 | 1497 | 1453 | |
La26 | 20 |
[20] 1989 | 2125 | 1950 | 1929 | [20] 2146 | 2023 | 1968 | |
La27 | 20 |
[20] 2017 | 2175 | 2007 | 1960 | [20] 2191 | 2113 | 2047 | |
La28 | 20 |
[18] 2027 | 2071 | 1959 | 1880 | [20] 2245 | 2090 | 2046 | |
La29 | 20 |
[20] 1846 | 1990 | 1846 | 1803 | [20] 2030 | 1942 | 1857 | |
La30 | 20 |
[20] 2049 | 2097 | 1982 | 1965 | [20] 2242 | 2090 | 2033 | |
La31 | 30 |
[18] 2921 | 3137 | 2790 | 2715 | [20] 3219 | 2978 | 2942 | |
La32 | 30 |
[18] 3237 | 3316 | 3019 | 2987 | [20] 3567 | 3163 | 3114 | |
La33 | 30 |
[18] 2844 | 3061 | 2755 | 2672 | [20] 3201 | 2873 | 2845 | |
La34 | 30 |
[18] 2848 | 3146 | 2800 | 2729 | [20] 3202 | 2959 | 2862 | |
La35 | 30 |
[18] 2923 | 3171 | 2828 | 2776 | [15] 3373 | 2961 | 2871 | |
La36 | 15 |
[20] 1755 | 1919 | 1741 | 1713 | [20] 1835 | 1796 | 1767 | |
La37 | 15 |
[20] 1870 | 2029 | 1840 | 1802 | [20] 1931 | 1917 | 1871 | |
La38 | 15 |
[18] 1708 | 1828 | 1652 | 1630 | [20] 1813 | 1770 | 1747 | |
La39 | 15 |
[20] 1731 | 1882 | 1719 | 1697 | [20] 1811 | 1791 | 1758 | |
La40 | 15 |
[20] 1743 | 1925 | 1730 | 1692 | [20] 1815 | 1802 | 1780 |
[1] |
J. Adams, E. Balas and D. Zawack, The shifting bottleneck procedure for job shop scheduling, Management Science, 34 (1988), 391-401.
doi: 10.1287/mnsc.34.3.391.![]() ![]() ![]() |
[2] |
A. AitZai, B. Benmedjdoub and M. Boudhar, A branch and bound and parallel genetic algorithm for the job shop scheduling problem with blocking, International Journal of Operational Research, 14 (2012), 343-365.
doi: 10.1504/IJOR.2012.047094.![]() ![]() ![]() |
[3] |
D. Applegate and W. Cook, A computational study of the job-shop scheduling problem, ORSA Journal on Computing, 3 (1991), 149-156.
![]() |
[4] |
A. Dabah, A. Bendjoudi and A. AitZai, Efficient Multi Start Parallel Tabu Search for the Blocking Job Shop Scheduling Problem, forthcoming.
![]() |
[5] |
F. Glover, Future paths for integer programming and links to artificial intelligence, Computers Operations Research, 13 (1986), 533-549.
doi: 10.1016/0305-0548(86)90048-1.![]() ![]() ![]() |
[6] |
F. Glover, Tabu search-part Ⅰ, ORSA Journal on Computing, 1 (1989), 190-206.
![]() |
[7] |
F. Glover, Tabu search-part Ⅱ, ORSA Journal on Computing, 2 (1990), 4-32.
![]() |
[8] |
H. Groflin and A. Klinkert, A new neighborhood and tabu search for the blocking job shop, Discrete Applied Mathematics, 157 (2009), 3643-3655.
doi: 10.1016/j.dam.2009.02.020.![]() ![]() ![]() |
[9] |
H. Gröflin, D. N. Pham and R. Bürgy, The flexible blocking job shop with transfer and set-up
times, Journal of Combinatorial Optimization, 22 (2011), 121-144.
doi: 10.1007/s10878-009-9278-x.![]() ![]() ![]() |
[10] |
N. G. Hall and C. Sriskandarajah, A survey of machine scheduling problems with blocking
and no-wait in process, Operations Research, 44 (1996), 510-525.
doi: 10.1287/opre.44.3.510.![]() ![]() ![]() |
[11] |
V. Laarhoven, J. M. Peter, E. H. L. Aarts and J. K. Lenstra, Job shop scheduling by simulated
annealing, Operations Research, 40 (1992), 113-125.
doi: 10.1287/opre.40.1.113.![]() ![]() ![]() |
[12] |
S. Lawrence, Resource constrained project scheduling: An experimental investigation of heuristic scheduling techniques (supplement), Graduate School of Industrial Administration, 1984.
![]() |
[13] |
A. Mascis and D. Pacciarelli, Job-shop scheduling with blocking and no-wait constraints, European Journal of Operational Research, 143 (2002), 498-517.
doi: 10.1016/S0377-2217(01)00338-1.![]() ![]() ![]() |
[14] |
Y. Mati, N. Rezg and X. Xie, A taboo search approach for deadlock-free scheduling of automated manufacturing systems, Journal of Intelligent Manufacturing, 12 (2001), 535-552.
![]() |
[15] |
Y. Mati and X. Xie, Multiresource shop scheduling with resource flexibility and blocking, Automation Science and Engineering, IEEE Transactions on, 8 (2011), 175-189.
![]() |
[16] |
C. Meloni, D. Pacciarelli and M. Pranzo, A rollout metaheuristic for job shop scheduling
problems, Annals of Operations Research, 131 (2004), 215-235.
doi: 10.1023/B:ANOR.0000039520.24932.4b.![]() ![]() ![]() |
[17] |
J. F. Muth and G. L. Thompson, eds. Industrial Scheduling, Prentice-Hall, 1963.
![]() |
[18] |
A. Oddi, R. Rasconi, A. Cesta and S. F. Smith, Iterative Improvement Algorithms for the Blocking Job Shop, In ICAPS. 2012.
![]() |
[19] |
D.-N. Pham and A. Klinkert, Surgical case scheduling as a generalized job shop scheduling
problem, European Journal of Operational Research, 185 (2008), 1011-1025.
doi: 10.1016/j.ejor.2006.03.059.![]() ![]() ![]() |
[20] |
M. Pranzo and D. Pacciarelli, An iterated greedy metaheuristic for the blocking job shop
scheduling problem, Journal of Heuristics, (2013), 1-25.
![]() |
[21] |
B. Roy and B. Sussmann, Les problemes d'ordonnancement avec contraintes disjonctives,
Note ds, 9(1964).
![]() |