\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

An efficient Tabu Search neighborhood based on reconstruction strategy to solve the blocking job shop scheduling problem

Abstract Full Text(HTML) Figure(8) / Table(4) Related Papers Cited by
  • 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.

    Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  Alternative pairs between blocking and ideal operations

    Figure 2.  Swap situation between three operations (jobs)

    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

    Figure 6.  The proposed neighborhood steps

    Figure 7.  Variation of the relative errors from the optimal solution over times for La17 instance

    Figure 8.  The behaviour of both TS methods over times for the La17 instance

    Table 1.  BJSS instance with two jobs and three machines

    jobsequence processing times
    $J1$ $M1, M2, M3 $ 5, 3, 8
    $J2$ $M2, M1, M3 $ 8, 2, 7
     | Show Table
    DownLoad: CSV

    Table 2.  The description of the symbols used in our TS

    SymbolDescription
    sa feasible schedule (solution) for the BJSS problem.
    $s*$ The best solution found by TS.
    $Cost(s)$ The Cost (makespan) of the solution s.
    $sc$ Best solution in Cand(s).
    $TL$ Tabu List.
    $Cand(s)$ a set of unforbidden neighbor solutions of the schedule s.
    $N(s)$ a set of all neighbor solutions of schedule s.
     | Show Table
    DownLoad: CSV

    Table 3.  Comparison of the obtained Makespan results with the optimal solutions of the (10 $\times$ 10) Instances

    Instance BWS BNS
    $C_{optimal}$ $C_{mean}$ $C_{best}$ $C_{optimal}$ $C_{mean}$ $C_{best}$
    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%
     | Show Table
    DownLoad: CSV

    Table 4.  Our $TS_{IN}$ makespan results Vs. the best known solutions for both BJSS cases (BWS, BNS)

    Instance $Size$ BWS BNS
    $Best$ $TS_{gr} $ $C_{mean}$ $C_{best}$ $Best$ $C_{mean}$ $C_{best}$
    La01 10$\times$5 [18,20] 793 820 780 793 [20,15] 881 881 881
    La02 10$\times$5 [8,18,20] 793 793 793 793 [20,15] 900 901 900
    La03 10$\times$5 [18,20] 715 740 715 715 [20,15] 808 810 808
    La04 10$\times$5 [18,20] 743 764 743 743 [20,15] 859 864 859
    La05 10$\times$5 [18,20] 664 666 670 664 [20,15] 732 732 732
    La06 15$\times$5 [18] 1064 1180 1120 1076 [20] 1225 1207 1194
    La07 15$\times$5 [20] 1020 1084 1052 1029 [20] 1133 1138 1130
    La08 15$\times$5 [18] 1062 1125 1089 1060 [15] 1216 1203 1173
    La09 15$\times$5 [20] 1162 1223 1209 1188 [20] 1311 1324 1314
    La10 15$\times$5 [18] 1110 1203 1142 1110 [20] 1237 1252 1232
    La11 20$\times$5 [18] 1466 1584 1504 1475 [20] 1641 1621 1577
    La12 20$\times$5 [20] 1271 1391 1326 1276 [20] 1465 1448 1401
    La13 20$\times$5 [18] 1465 1541 1474 1456 [20] 1627 1586 1547
    La14 20$\times$5 [18] 1506 1620 1520 1472 [20] 1686 1648 1586
    La15 20$\times$5 [18,20] 1517 1630 1526 1490 [20] 1680 1651 1620
    La16 10$\times$10 [20] 1060 1142 1090 1060 [20,15] 1148 1151 1148
    La17 10$\times$10 [20] 929 977 943 930 [20,15] 968 979 968
    La18 10$\times$10 [20] 1025 1078 1038 1025 [20,15] 1077 1087 1077
    La19 10$\times$10 [20] 1043 1093 1067 1053 [20,15] 1102 1104 1102
    La20 10$\times$10 [20] 1060 1154 1085 1060 [20,15] 1118 1125 1118
    La21 15$\times$10 [20] 1490 1554 1499 1467 [20] 1627 1540 1501
    La22 15$\times$10 [20] 1339 1458 1369 1347 [20] 1426 1421 1368
    La23 15$\times$10 [20] 1445 1570 1477 1442 [20] 1574 1564 1537
    La24 15$\times$10 [20] 1434 1546 1433 1398 [20] 1502 1510 1447
    La25 15$\times$10 [20] 1392 1499 1420 1373 [20] 1533 1497 1453
    La26 20$\times$10 [20] 1989 2125 1950 1929 [20] 2146 2023 1968
    La27 20$\times$10 [20] 2017 2175 2007 1960 [20] 2191 2113 2047
    La28 20$\times$10 [18] 2027 2071 1959 1880 [20] 2245 2090 2046
    La29 20$\times$10 [20] 1846 1990 1846 1803 [20] 2030 1942 1857
    La30 20$\times$10 [20] 2049 2097 1982 1965 [20] 2242 2090 2033
    La31 30$\times$10 [18] 2921 3137 2790 2715 [20] 3219 2978 2942
    La32 30$\times$10 [18] 3237 3316 3019 2987 [20] 3567 3163 3114
    La33 30$\times$10 [18] 2844 3061 2755 2672 [20] 3201 2873 2845
    La34 30$\times$10 [18] 2848 3146 2800 2729 [20] 3202 2959 2862
    La35 30$\times$10 [18] 2923 3171 2828 2776 [15] 3373 2961 2871
    La36 15$\times$15 [20] 1755 1919 1741 1713 [20] 1835 1796 1767
    La37 15$\times$15 [20] 1870 2029 1840 1802 [20] 1931 1917 1871
    La38 15$\times$15 [18] 1708 1828 1652 1630 [20] 1813 1770 1747
    La39 15$\times$15 [20] 1731 1882 1719 1697 [20] 1811 1791 1758
    La40 15$\times$15 [20] 1743 1925 1730 1692 [20] 1815 1802 1780
     | Show Table
    DownLoad: CSV
  • [1] J. AdamsE. 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. AitZaiB. 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öflinD. 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. LaarhovenJ. M. PeterE. 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. MatiN. 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. MeloniD. 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).
  • 加载中

Figures(8)

Tables(4)

SHARE

Article Metrics

HTML views(1434) PDF downloads(309) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return