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

Adel Dabah; Ahcene Bendjoudi; Abdelhakim AitZai

doi:10.3934/jimo.2017029

Article Contents

2017, Volume 13, Issue 4: 2015-2031. Doi: 10.3934/jimo.2017029

This issue Previous Article Prox-dual regularization algorithm for generalized fractional programs Next Article Stability strategies of manufacturing-inventory systems with unknown time-varying demand

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

1.
CERIST Research Center 3 rue des freres Aissou, 16030 Ben-Aknoun, Algiers, Algeria
2.
University of Sciences and Technology Houari Boumedienne (USTHB), Bab Ezzouar 16111, Algiers, Algeria

Received: December 2015

Revised: September 2016

Published: November 2017

Abstract Full Text(HTML) Figure(8) / Table(4) Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

Full Text(HTML)

Figure 1. Alternative pairs between blocking and ideal operations

Download: Full-size image PowerPoint slide

Figure 2. Swap situation between three operations (jobs)

Download: Full-size image PowerPoint slide

Figure 3. Alternative graph for BJSS instance of table 1

Download: Full-size image PowerPoint slide

Figure 4. Schedule for BJSS in Table 1 whit Cmax=26

Download: Full-size image PowerPoint slide

Figure 5. Gantt chart of the schedule in figure 4

Download: Full-size image PowerPoint slide

Figure 6. The proposed neighborhood steps

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

Table 1. BJSS instance with two jobs and three machines

job	sequence	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

Symbol	Description
s	a 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
Instance	$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
Instance	$Size$	$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

Related Papers

Cited by

References

[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).