Tabu search for minimizing total tardiness
Full text
Niolau Santos Tabu Searh for Minimizing Total Tardiness in the Permutation Flowshop Departamento de Matemátia Fauldade de Ciênias da Universidade do Porto Novembro de 2012
2
Niolau Santos Tabu Searh for Minimizing Total Tardiness in the Permutation Flowshop Tese submetida à Fauldade de Ciênias da Universidade do Porto para obtenção do grau de Mestre em Engenharia Matemátia Orientador: Professor Doutor João Pedro Pedroso Departamento de Matemátia Fauldade de Ciênias da Universidade do Porto Novembro de 2012
4
to Xana and Leonardo 5
Aknowledgments Tese realizada no âmbito do mestrado em Engenharia Matemátia Departamento de Matemátia Fauldade de Ciênias da Universidade do Porto http://www.f.up.pt/dmat/engmat Agradeço ao Engenheiro Rui Reb elo e a to dos no INESC TEC p elo ap oio no desenvolvimento deste trabalho. Agradeço à Professora Maria do Carmo Vaz Miranda Guedes e ao Professor João Nuno Tavares p ela orientação no meu p erurso aadémio. 6
Abstrat The pratial appliation of ow shop problems puts them among the most widely studied topis in ombinatorial optimization. This work presents a new tabu searh approah to the p ermutation ow shop problem, with the ob jetive of minimizing the total tardiness. Computational exp eriments with reent b enhmark problems onrm the quality of the prop osed algorithm. 7
Contents Abstrat 7 List of Tables 10 List of Figures 11 1 The Permutation Flowshop Problem 12 1.1 Mathematial Formulation ......................... 14 1.2 Literature Review .............................. 15 2 Tabu Searh 17 2.1 Moves and neighb orho o d .......................... 19 2.2 Tabu list and searh strategy ....................... 19 2.3 Sp eedup implementation .......................... 20 2.4 Initialization ................................. 22 2.5 Diversiation, intensiation and alibration .............. 23 3 Computational Results 24 4 Conlusions 34 A Detailed Results 35 8
List of Tables 3.1 Computational times used in the normal runs .............. 25 3.2 Average RDI for the fast tests. ....................... 26 3.3 Average RPD for the fast tests. ...................... 26 3.4 Average RDI for the regular tests. ..................... 27 3.5 Average RPD for the regular tests. .................... 28 3.6 Comparison with the results of [VR10℄ .................. 28 3.7 Comparison with the results of [VR09℄ .................. 29 3.8 Comparison with the results of [KTW10℄ ................. 30 3.9 Average RDImod for the fast tests. ..................... 31 3.10 Average RDImod for the regular tests. ................... 31 3.11 Average eNEH for the regular tests. .................... 32 3.12 Comparison with the results obtained by the Gurobi solver. ....... 33 A.1 Individual results for the instanes with T= 0.2 and R= 0.2 ...... 36 A.2 Individual results for the instanes with T= 0.2 and R= 0.6 ...... 37 A.3 Individual results for the instanes with T= 0.2 and R= 1 ....... 38 A.4 Individual results for the instanes with T= 0.4 and R= 0.2 ...... 39 A.5 Individual results for the instanes with T= 0.4 and R= 0.6 ...... 40 A.6 Individual results for the instanes with T= 0.4 and R= 1 ....... 41 A.7 Individual results for the instanes with T= 0.6 and R= 0.2 ...... 42 9
CHAPTER 1. THE PERMUTATION FLOWSHOP PROBLEM 16 tardiness optimization riterion.
Chapter 2 Tabu Searh Tabu searh (TS) was prop osed in [Glo86℄ as a metho d for guiding heuristis based on solution improvement through the solution spae. Given a solution π the move represents the way in whih we mo dify π to obtain new solutions, N(π) represents the neighb orho o d of π and ontains all the solutions we an obtain by applying a move. The solution π is lo ally optimal if π≤π∗ , ∀π∗∈ N(π) , π is a global optimum if π≤π∗ , ∀π∗∈S , where S denotes the spae of all p ossible solutions. The main ob jetive was to overome the limitations of the traditional desent metho d desrib ed in gure 2.1. pro edure lo al_searh( π ) while π is not lo ally optimal do nd s∈ N(π) with f(s)< f(π) π←s end do return π end pro edure Figure 2.1: Lo al searh pseudoode This lo al searh metho d explores the neighb orho o d of the urrent solution and moves to the b est found neighb or until no improvement is p ossible; however, there is no guarantee of global optimality, and the quality of the obtained solution may b e ratter p o or. TS relies in two main mehanisms to esap e lo al optima: the tabu move and the tabu list. In the tabu move, at eah iteration we evaluate the neighb orho o d 17
CHAPTER 2. TABU SEARCH 18 and move to the b est found neighb or, even if its ob jetive is worse than the urrent solution's. By p erforming these moves to worse solutions TS is able to esap e lo al optima; however this moves ould b e easily reversed in the following iterations. To prevent this seond situation, TS has a tabu list, a short term memory list with the reord of reently p erformed moves. These moves are forbidden for a given numb er of iterations, preventing reversion of reent moves and helping TS to travel through the solution spae while avoiding lo al optima stagnation and yling. Figure 2.2 desrib es the general pro ess of TS. pro edure tabu_searh( π ) πbest ←π while termination riteria not met do nd b est s∈ N(π) π←s up date tabu list if π < πbest then πbest ←π end if end do return πbest end pro edure Figure 2.2: Tabu searh pseudoode Typially the algorithm runs until a given stopping riterion is met. The most ommon riteria are: − maximum CPU allowed; − maximum numb er of iterations reahed; − maximum numb er of iterations without improvement reahed; − a given lower b ound is met. In the literature there are many examples of suessful TS appliations, from the initial works of [HW87℄ in graph oloring to the fast implementation of TSAB [NS96℄, develop ed for the job shop problem. A generi intro dution of TS an b e found in [Gen03℄; detailed information is available in [GL98℄. In the remaining of this hapter we desrib e the harateristis of our TS implementation.
CHAPTER 2. TABU SEARCH 19 2.1 Moves and neighb orho o d TS exploration is based in moving iteratively to a neighb or solution. Throughout the literature, three typ es of moves are used more prominently in sheduling problems, namely: swap-moves (swap job at p osition i with job at p osition i+1 ), exhangemoves (exhange the job at the i-th p osition with the job at the j-th p osition) and insertion-moves (remove the job at the i-th p osition and insert it at the j-th p osition). In our algorithm we use the insertion-move: given a p ermutation π and a pair of p ositions (i, j), i 6=j , the p ermutation π′ is obtained by removing job at p osition i and inserting it at p osition j , i.e., π′=π1,...,πi−1, πi+1,...,πj, πi, πj+1,...,πn if i < j; π′=π1,...,πj−1, πi, πj,...,πi−1, πi+1,...,πn if j < i . Having a set of jobs U we dene N(U, π) as the neighb orho o d that ontains all the p ossible insertion moves of the jobs in U . Besides solution quality, another advantage of using insertion moves is the sp eed up pro edure we an apply. Supp ose we have a p ermutation π= (π1, π2, π3) and we want to evaluate the p ossible insertions of a job π4 ; then we would have to analyze the following p ermutations: I1= (π4, π1, π2, π3) , I2= (π1, π4, π2, π3) , I3= (π1, π2, π4, π3) and I4= (π1, π2, π3, π4) . This ould b e done individually with formulas 1.1 to 1.4; however, by evaluating I4 we are already evaluating the following underlined parts of I2:π1, π4, π2, π3 and I3:π1, π2, π4, π3 . So with prop er data strutures imp ortant omputational savings an b e obtained. This was already observed in [FL08℄ and [VR10℄ but was not explained in detail. In setion 2.3 we desrib e the steps of our sp eed up implementation . With this sp eed up we save approximately half of the omputational time. Still, as the problems size inreases, the omplete neighb orho o d quikly b eomes to o large for full exploitation, so we apply a restrition on the size of the neighb orho o d to b e evaluated. We selet a subset of r randomly hosen jobs suh that rmin ≤r≤rmax (b oth rmin and rmax are parameters of the algorithm). At eah iteration we analyze only the restrited neighb orho o d and selet the job that yields the b est ob jetive for the move. 2.2 Tabu list and searh strategy One of the key elements in TS is the tabu list, a mehanism of short term memory used to reord information of reent moves. Our implementation of the tabu list onsists
CHAPTER 2. TABU SEARCH 20 of an array τ : for eah job i we assign a value τi . At iteration iter we say that job i is tabu if τi> iter . Whenever we selet a job i to p erform the move it b eomes tabu for t iterations, where 1≤t≤tmax , so τi=iter +t . An exeption o urs when the b est known solution is improved; in suh ase we set τk= 0,∀k6=i and τi=iter + 1 to prevent immediate reversion of job i . At eah iteration the TS pro edure an b e summarized in the following steps: − nd the set L of legal (non tabu) moves; − let r b e an integer random numb er suh that, rmin ≤r≤rmax ; dene R as a set of r jobs randomly hosen from L ; − evaluate the moves in the set N(R, π) and p erform the move that yields the b est ob jetive; − taking into onsideration the obtained ob jetive value, up date the tabu list. This restrited neighb orho o d gives TS the ability to navigate very fast through the solution spae, to maintain this harateristi we do not implement aspiration riteria. 2.3 Sp eedup implementation In this setion we desrib e the sp eed up implementation. Considering the generi ase of n jobs to pro ess on m mahines, for eah job i the pro dution time on mahine j is pij and the orresp onding due date is di . Supp ose we have a redued p ermutation π of dimension n−1 and we want to evaluate all the p ossible insertions of a job πt . All alulations are p erformed with two data strutures: an n×m work matrix W and an n dimensional array a . The lines of W are used to alulate job insertions; more preisely, line i will b e used to evaluate the ompletion times of all jobs in the p ermutation where job πt is inserted at p osition i . Array a will b e used for storing the aumulated tardiness of inserting job πt at p osition i . The rst step is to dene the initial state of the mahines and total initial tardiness of the system. We assume all these values to b e zero initially and p erform the following assignments:
CHAPTER 2. TABU SEARCH 21 a1= 0 for j=1 to m do W1j= 0 end do W1j represents the initial state of mahine j and a1 the initial total tardiness. The next step is to evaluate the earliest ompletion time of eah job of the redued p ermutation: for i=1 to n-1 do for j=1 to m do Wi+1,j = max{Wi+1,j−1, Wij}+pπij end do ai+1 =ai+ max{Wi+1,m −dπi,0} end do After these alulations all the underlined partial p ermutations desrib ed in setion 2.3 are evaluated, Now we evaluate the tardiness of inserting job πt at eah p osition: for i=1 to n do for j=1 to m do Wij = max{Wi,j−1, Wij}+pπt,j end do ai=ai+ max{Wim −dπt,0} end do At this p oint the insertion of πt at the nth p osition is ompletely evaluated, now we nish the evaluation of the remaining insertions:
CHAPTER 2. TABU SEARCH 22 for i=1 to n-1 do for j=i to n-1 do for k=1 to m do Wik = max{Wi,k−1, Wik}+pπj,i end do ai=ai+ max{Wim −dπj,0} end do end do Note that in the ab ove presented alulations W0k= 0 and Wk0= 0 , ∀k . The omputational omplexity of the presented sp eed up is O(n2m) whih is the same of evaluating all the insertions with formulas 1.1 to 1.4; however a substantial numb er of alulations is avoided and the used omputational time is approximately halved. 2.4 Initialization There are many ways of initializing TS and other metaheuristis, from random solutions to more sophistiated heuristis. The urrent trend in owshop problems is the initialization using the NEH [NEJH83℄ desrib ed for instane in [RS07℄ for makespan ob jetive. On our algorithm we will use the NEHedd heuristi whih is an adaptation of the original NEH for tardiness ob jetive presented in [KLP96℄. The initial solution is onstruted with the following steps: 1. sort the jobs in non dereasing order of due dates (EDD rule); 2. selet the rst two jobs from EDD and sort them so as to minimize the asso iated total tardiness 3. for k from 2 to n: selet the job k from EDD and insert it in all the k p ossible p ositions of sol; selet the insertion that yields the lowest urrent total tardiness. To alulate the sequene of the EDD we use a stable sorting algorithm, i.e., the relative order of elements with the same value is maintained. When p erforming the insertions, ties are broken in the following way: we test all the insertions from the rst to the last p osition and assigning to the rst found p osition.
CHAPTER 2. TABU SEARCH 23 It is also p ossible to initialize the algorithm with simpler or even random onstrutions, but the onvergene is exp eted to b eome somewhat slower, as the rst desent may b eome very long. 2.5 Diversiation, intensiation and alibration Two reurrent sub jets in TS are diversiation and intensiation. As the name suggests the rst should allow the algorithm to travel through the solution spae in a rih and diversied way; in ontrast, intensiation onsists of fo using the exploration on a partiular region. While studying the b ehavior of our algorithm in test problems it b eame lear that the rmin , rmax and tmax parameters ould eiently mo del the aforementioned situations. It was observed that low values of rmin and rmax ombined with a high value of tmax would at as a diversiation pro ess while high values of rmin and rmax ombined with a small tmax would lo alize the searh and p otentially provoke yling. However the sp ei value that the parameters should assume or the frequeny in whih they should b e hanged seemed to b e problem dep endent. In order to overome this situation we prop ose a three stage searh pro edure. The rst stage onsists of a highly diversied searh with rmin = 2 , rmax = 3 and tmax =n ; the seond stage makes a more thought exploration with rmin = 3 , rmax = 7 and tmax =n ; nally, a third stage with rmin = 3 , rmax = 7 and tmax = 1 is applied as an intensiation pro ess. Computational time is divided evenly among eah of the stages. Whenever a stage transition is applied we restart from the b est found solution and lear the tabu list. These parameters were found exp erimentally and hosen in order to obtain a go o d ompromise b etween solution quality and running time.
Chapter 3 Computational Results The prop osed tabu searh was o ded in mixed Python/Fortran wrapp ed with F2py [Pet09 ℄ and ompiled with gfortran. The tests were p erformed on a omputer with an AMD Athlon 64 Dual Core 3800+ pro essor and 2Gb of RAM running a Linux 64-bit op erating system. We used the b enhmark test suit prop osed in [VRM08℄ available in http://soa.iti.es . The b enhmark was generated with dierent ombinations of the following parameters: numb er of jobs n ; numb er of mahines m ; tardiness fator (T) and due date range (R) . Due dates are generated aording to T and R with uniform distribution b etween P(1 −T−R/2) and P(1 −T+R/2) where P is a tight lower b ound of the makespan prop osed in [Tai93℄. High values of T result in early due dates, and low values of R ause paked due dates. Job pro essing times are integers uniformly distributed b etween 1 and 99. The b enhmark is omp osed of the following ombinations for T, R, n and m: T={0.2, 0.4, 0.6}, R={0.2, 0.6, 1}, n={50, 150, 250, 350} and m={10, 30, 50}. The b enhmark is omp osed of ve instanes of eah ombination of T , R , n and m , resulting in 108 groups and a total of 540 test instanes. To evaluate the quality of the prop osed algorithm we onduted b oth regular and quik tests. In the regular tests we use CPU running times of n.m.45 milliseonds, allowing more omputational time as the numb er of jobs/mahines inreases; a similar approah is also used in [VRM08,VR10,KTW10℄. The regular omputational times (in seonds) for the dierent ombinations of n and m are presented in table 3.1 and we denote the algorithm by TS. In the fast tests we use one tenth of the aforementioned CPU time and denote the algorithm by FTS. In all runs the algorithms are exeuted using a single ore. Due to the sto hasti nature of the implemented algorithms b oth 24
CHAPTER 3. COMPUTATIONAL RESULTS 25 metho ds are exeuted ve times for eah instane, results presented are their average. Usually ow shop algorithms are evaluated with the Relative Perent Deviation (RPD) n\m 10 30 50 50 22.5 67.5 112.5 150 67.5 202.5 337.5 250 112.5 337.5 562.5 350 157.5 472.5 787.5 Table 3.1: Computational times (in seonds) used for the various ombinations of n and m in the normal runs (fast tests used one tenth of the time). dened in equation 3.1; however, when the total tardiness ob jetive is onsidered the optimal value of an instane may b e zero and in that ase a division by zero o urs. To overome this situation one an replae the RPD by zero, if the algorithm nds the optimal solution and evaluate the error E , E=Methodsol −Best otherwise. Another alternative is to use a dierent quality measure suh as the the Relative Deviation Index (RDI) dened in equation 3.2. RPD =Methodsol −Best Best ×100 (3.1) RDI =Methodsol −Best Worst −Best ×100 (3.2) In table 3.2 we present the mean RDI for the fast tests and in table 3.3 we present the mean RPD for the fast tests. We an observe that various instane groups with T= 0.2 and R= 0.6 or R= 1 seem to b e easy to solve as the average RPD and RDI is zero. We an also already identify several groups with negative values, in these ases we are improving, on average, the ob jetive with resp et to previous b est known solutions. The diulties with the RPD also arise as we are getting zero division errors in ve instanes; these results are identied in the tables with the notation a/(b:c) where a in the RPD for the instanes of the group that b ehave normally, b is the numb er of instanes of the group with zero division errors that did not ahieve the optimal value and c is the orresp onding mean error. The tests with regular omputational times show further improvement relatively to the fast tests results. It is now p ossible to identify a large numb er of groups with negative values. Paradoxially, the quality measures suggest dierent interpretations for some groups. As an example onsider the instane group with T= 0.2 , R= 0.6 ,
CHAPTER 3. COMPUTATIONAL RESULTS 32 T 0.2 0.4 0.6 R 0.2 0.6 1 0.2 0.6 1 0.2 0.6 1 average 50 ×10 39.03 0.00 0.00 76.50 66.58 68.84 84.68 86.12 81.38 55.90 50 ×30 70.79 68.15 71.64 89.03 88.43 88.45 93.01 94.13 93.11 84.08 50 ×50 81.21 84.15 84.14 92.27 93.01 93.35 95.54 96.17 93.87 90.41 150 ×10 43.12 0.00 0.00 73.44 47.77 21.60 85.78 80.76 72.15 47.18 150 ×30 52.14 3.00 0.00 76.66 71.46 71.65 90.04 89.09 87.20 60.14 150 ×50 66.50 46.77 25.79 85.08 82.57 82.28 93.24 93.06 92.10 74.15 250 ×10 46.05 0.00 0.00 77.17 53.92 0.24 86.56 78.94 73.61 46.28 250 ×30 46.10 0.00 0.00 75.17 61.24 43.16 89.04 87.05 82.46 53.80 250 ×50 57.41 17.08 0.00 82.80 75.98 72.95 91.76 91.31 88.10 64.15 350 ×10 49.39 0.00 0.00 79.07 52.73 0.31 89.17 82.52 73.99 47.46 350 ×30 44.94 0.00 0.00 76.78 58.82 30.96 88.89 87.04 79.94 51.93 350 ×50 52.88 4.84 0.00 80.91 69.76 59.47 91.15 89.41 85.71 59.35 average 54.13 18.67 15.13 80.41 68.52 52.77 89.91 87.97 83.64 61.24 Table 3.11: Average eNEH for the regular tests. Overall, the quality of the prop osed algorithm is evident: of the 540 b enhmark instanes analyzed, 85 are known to have an optimal (0) solution, of the remaining 455 we were able to improve the b est known upp er b ound in 345. The advantages of using a lo al searh pro edure as Tabu Searh for exploring the instanes' landsap e app ears evident. Probably other metho ds would also b enet from hybridization with a more robust lo al searh. We also emphasize that the Permutation Flow shop Problem with Total Tardiness evaluation riterion is extremely hard to solve. As an example, we tested the integer programming formulation for the rst instanes of the groups with 50 and 150 jobs with the mo dern ommerial solver Gurobi ( http://www.gurobi.om/ ). The solver's CPU time was set to an hour, with the default parameter onguration. Results are presented in table 3.12. Instane is the seleted problem instane, ub and lb resp etively the upp er and lower b ound obtained by the solver, FTS and TS the average total tardiness obtained by the develop ed algorithms. When * is present the solver was not able to nd a solution. It's interesting to observe that in most of the 150 ×30 and 150 ×50 instanes the allowed time is not suient to solve the linear relaxation but in some ases the solver is able to provide a feasible solution (probably derived from an heuristi). The obtained lower b ounds also app ear to b e weak, due to the large dierene to the results obtained by TS.
CHAPTER 3. COMPUTATIONAL RESULTS 33 Instane ub lb FTS TS 0,2_0,2_50_10_1 3417 1554 1990.8 1906.4 0,2_0,2_50_30_1 32677 5974 20142.2 19884.8 0,2_0,2_50_50_1 * 7149 35222.4 34926.4 0,2_0,2_150_10_1 24542 9372 12226.8 11688.2 0,2_0,2_150_30_1 * * 48603.8 44818.0 0,2_0,2_150_50_1 * * 108664.6 104119.2 0,2_0,6_50_10_1 601 0 0.0 0.0 0,2_0,6_50_30_1 47771 88 12798.0 12634.4 0,2_0,6_50_50_1 60287 846 38176.2 37781.6 0,2_0,6_150_10_1 22274 0 0.0 0.0 0,2_0,6_150_30_1 * 0 216.0 61.4 0,2_0,6_150_50_1 * * 61712.0 58344.4 0,2_1_50_10_1 1160 0 0.0 0.0 0,2_1_50_30_1 51361 0 10119.0 9881.0 0,2_1_50_50_1 * 0 28761.2 28344.0 0,2_1_150_10_1 68911 0 0.0 0.0 0,2_1_150_30_1 * 0 0.0 0.0 0,2_1_150_50_1 * * 419.6 208.8 0,4_0,2_50_10_1 15113 9685 12632.8 12401.0 0,4_0,2_50_30_1 67304 26341 50396.8 49965.4 0,4_0,2_50_50_1 102233 39884 79058.4 78934.0 0,4_0,2_150_10_1 124038 62064 75478.6 72935.0 0,4_0,2_150_30_1 * * 163100.8 158071.0 0,4_0,2_150_50_1 * * 289821.2 285155.0 0,4_0,6_50_10_1 16595 5532 13290.8 12934.2 0,4_0,6_50_30_1 59007 19707 45189.2 44934.8 0,4_0,6_50_50_1 98198 39233 78775.0 78107.0 0,4_0,6_150_10_1 72387 11549 16199.6 14922.2 0,4_0,6_150_30_1 * * 166866.4 160808.2 0,4_0,6_150_50_1 * * 287363.6 282891.8 0,4_1_50_10_1 11571 0 8667.0 8523.0 0,4_1_50_30_1 71774 27625 57608.6 57264.0 0,4_1_50_50_1 95939 32369 73867.2 73440.0 0,4_1_150_10_1 98458 0 4000.4 2996.4 0,4_1_150_30_1 390611 0 126796.2 121749.6 0,4_1_150_50_1 490783 * 218022.2 212433.0 0,6_0,2_50_10_1 35055 28167 32468.2 32313.4 0,6_0,2_50_30_1 96185 55295 80988.8 80252.6 0,6_0,2_50_50_1 146602 85132 121950.0 121496.0 0,6_0,2_150_10_1 253127 172733 201106.4 195525.0 0,6_0,2_150_30_1 * * 369856.4 364146.8 0,6_0,2_150_50_1 * * 516077.4 512253.6 0,6_0,6_50_10_1 31477 21344 28953.8 28759.2 0,6_0,6_50_30_1 97258 58119 83213.6 82804.4 0,6_0,6_50_50_1 154159 96556 135733.2 135311.4 0,6_0,6_150_10_1 225404 137711 188192.4 179625.4 0,6_0,6_150_30_1 594939 * 358268.4 353620.0 0,6_0,6_150_50_1 708360 * 511775.4 507309.4 0,6_1_50_10_1 27441 12317 23447.2 23192.8 0,6_1_50_30_1 94816 52081 80000.8 79545.2 0,6_1_50_50_1 124615 72739 108662.8 108206.2 0,6_1_150_10_1 153420 40921 103891.0 97095.4 0,6_1_150_30_1 505894 * 295615.0 290017.8 0,6_1_150_50_1 665697 * 436079.6 430447.6 Table 3.12: Comparison with the results obtained by the Gurobi solver.
Chapter 4 Conlusions In this work we presented a tabu searh metaheuristi for the p ermutation owshop problem with total tardiness ob jetive. The metho d is haraterized by the evaluation of a small neighb orho o d at eah iteration, a dynami tabu list and dynami parameters. This last feature allows the algorithm's parameters to vary during exeution and prevents overtting to the test instanes used in the initial alibration. Tests onduted with reent literature b enhmarks onrm the quality of the metho d. We were able to outp erform literature results with one tenth of the running time regularly used in the rep orted exp eriments, and improve the b est known solution for a large numb er of instanes in the normal runs, when using equivalent CPU. In future work we will apply the develop ed metho d to other problems and exp eriment dierent diversiation and intensiation strategies. 34
App endix A Detailed Results In the following tables we desrib e the results of the develop ed Tabu Searh for the p ossible ombination of the T and R parameters. The following information is available: • Instane : the instane tested; • Best : the b est known solution from http://soa.iti.es ; • Worst : the worst solution provided at http://soa.iti.es ; • NEH : the ob jetive value of the initial heuristi; • runs 1 to 5: the obtained results for eah run of the algorithm. 35
APPENDIX A. DETAILED RESULTS 36 Instane Best Worst NEH run1 run2 run3 run4 run5 I_0,2_0,2_50_10_1 1876 23712 5883 1939 1881 1876 1964 1872 I_0,2_0,2_50_10_2 2202 17290 4811 2255 2255 2255 2255 2255 I_0,2_0,2_50_10_3 2564 18479 7878 2878 2818 2686 2748 2831 I_0,2_0,2_50_10_4 2425 17602 7324 2475 2465 2454 2432 2503 I_0,2_0,2_50_10_5 3056 18746 6604 3135 3115 3030 3057 3101 I_0,2_0,2_50_30_1 19475 47599 26390 19938 19788 19875 19897 19926 I_0,2_0,2_50_30_2 20223 49129 28069 20091 20258 20199 20222 20498 I_0,2_0,2_50_30_3 18701 50315 26731 19158 19148 19392 18827 18995 I_0,2_0,2_50_30_4 19379 51674 28057 19521 19484 19403 19579 19513 I_0,2_0,2_50_30_5 19006 52737 29163 19137 19067 19189 19003 19112 I_0,2_0,2_50_50_1 34368 70188 44328 34971 34722 34898 35029 35012 I_0,2_0,2_50_50_2 36651 78240 45249 37092 37220 37303 36731 37066 I_0,2_0,2_50_50_3 36456 72199 45311 36663 36929 37055 37115 37004 I_0,2_0,2_50_50_4 40150 70384 48697 40525 40289 40249 40325 40108 I_0,2_0,2_50_50_5 30477 60931 38002 30713 30807 30894 30643 30806 I_0,2_0,2_150_10_1 11797 78491 28494 11684 11611 11727 11669 11750 I_0,2_0,2_150_10_2 11727 94910 24644 11666 11876 11826 11660 11768 I_0,2_0,2_150_10_3 11480 96730 26994 11635 11457 11184 11261 11164 I_0,2_0,2_150_10_4 12706 100295 31631 12639 12913 12680 12736 12513 I_0,2_0,2_150_10_5 11107 109474 25452 11548 10895 11577 11472 11444 I_0,2_0,2_150_30_1 47978 198124 86055 44180 44917 44624 45600 44769 I_0,2_0,2_150_30_2 49892 180614 99166 46901 46677 46254 46918 46563 I_0,2_0,2_150_30_3 47882 181826 84241 43366 45836 45075 45482 46087 I_0,2_0,2_150_30_4 48913 180934 80520 47605 46654 46395 45956 45825 I_0,2_0,2_150_30_5 47574 195205 88870 45016 44641 43331 45498 44576 I_0,2_0,2_150_50_1 105825 266518 153000 104515 106183 103907 102839 103152 I_0,2_0,2_150_50_2 86843 260227 130595 86415 86180 86209 86842 86965 I_0,2_0,2_150_50_3 114580 270128 166041 114964 115398 114480 114915 113275 I_0,2_0,2_150_50_4 96298 262860 150556 95208 95961 95966 97369 97489 I_0,2_0,2_150_50_5 95546 259961 144147 94036 92957 93872 94109 94529 I_0,2_0,2_250_10_1 25342 231314 62721 25927 25848 25297 25678 25767 I_0,2_0,2_250_10_2 27091 210819 58155 25872 26606 25927 26448 27015 I_0,2_0,2_250_10_3 21093 204808 63839 23116 23435 22319 22700 23074 I_0,2_0,2_250_10_4 21740 178954 38069 21684 21602 21709 21692 21684 I_0,2_0,2_250_10_5 22983 177430 45026 22908 22870 22830 23451 22965 I_0,2_0,2_250_30_1 86952 369904 169362 73061 72374 74339 75612 73586 I_0,2_0,2_250_30_2 74892 327654 136183 63265 64063 64315 64852 64882 I_0,2_0,2_250_30_3 85247 352604 160729 75054 71175 71298 74689 71923 I_0,2_0,2_250_30_4 90429 366319 170352 79981 82389 81919 82791 79649 I_0,2_0,2_250_30_5 88027 427536 159739 73945 76953 74590 73750 73414 I_0,2_0,2_250_50_1 185323 530460 289849 170954 171151 168569 169085 170755 I_0,2_0,2_250_50_2 190699 513084 302225 173306 176621 177364 172780 176518 I_0,2_0,2_250_50_3 181181 521587 282436 163051 162742 162782 163629 161952 I_0,2_0,2_250_50_4 149165 488095 249403 133645 134757 133179 132941 133135 I_0,2_0,2_250_50_5 182313 538042 277970 165959 163236 165002 163813 164461 I_0,2_0,2_350_10_1 46659 431957 87368 47538 46884 46439 46256 45805 I_0,2_0,2_350_10_2 30425 360053 68512 29929 29346 30252 30036 29753 I_0,2_0,2_350_10_3 47906 370816 99183 47664 46638 47964 47338 48073 I_0,2_0,2_350_10_4 38998 341837 77351 39075 39219 38643 38993 40082 I_0,2_0,2_350_10_5 53116 409730 103491 52504 54375 52791 53528 53048 I_0,2_0,2_350_30_1 144749 631932 274658 122881 126538 124783 128163 125729 I_0,2_0,2_350_30_2 155430 627626 289646 131056 130782 133262 129591 128266 I_0,2_0,2_350_30_3 138584 601559 252453 119467 119629 118990 121590 118600 I_0,2_0,2_350_30_4 110525 644747 227890 93669 91590 98341 98085 97321 I_0,2_0,2_350_30_5 125923 677262 249645 111603 113506 109499 111918 108300 I_0,2_0,2_350_50_1 262910 982825 441742 217541 224135 222510 229978 222734 I_0,2_0,2_350_50_2 271466 827292 421153 238580 227222 240110 234571 236155 I_0,2_0,2_350_50_3 215112 801709 372442 186598 192979 187409 189736 187348 I_0,2_0,2_350_50_4 292824 878444 452490 251539 254987 254626 254447 256310 I_0,2_0,2_350_50_5 239300 819237 394705 200204 199067 202365 202364 202827 Table A.1: Individual results for the instanes with T= 0.2 and R= 0.2 .
APPENDIX A. DETAILED RESULTS 37 Instane Best Worst NEH run1 run2 run3 run4 run5 I_0,2_0,6_50_10_1 0 12839 1452 0 0 0 0 0 I_0,2_0,6_50_10_2 0 16324 1149 0 0 0 0 0 I_0,2_0,6_50_10_3 0 15901 3819 0 0 0 0 0 I_0,2_0,6_50_10_4 0 11776 1242 0 0 0 0 0 I_0,2_0,6_50_10_5 0 15426 2112 0 0 0 0 0 I_0,2_0,6_50_30_1 12325 37372 18796 12686 12577 12633 12643 12633 I_0,2_0,6_50_30_2 10763 37373 18285 11185 10796 11050 10956 11162 I_0,2_0,6_50_30_3 16258 44618 24592 16227 16392 16412 16420 16217 I_0,2_0,6_50_30_4 18977 52444 24867 19537 19538 19592 19477 19474 I_0,2_0,6_50_30_5 21734 51558 31774 21643 21711 21707 21645 21754 I_0,2_0,6_50_50_1 37528 73045 43455 37798 37905 37823 37700 37682 I_0,2_0,6_50_50_2 28642 64313 38109 28965 28827 28753 28937 28969 I_0,2_0,6_50_50_3 34361 66054 41036 34609 34645 34528 34714 34625 I_0,2_0,6_50_50_4 41712 83484 47409 41945 42195 41849 42123 42013 I_0,2_0,6_50_50_5 42073 76945 50038 42610 42469 42520 42352 42649 I_0,2_0,6_150_10_1 0 87589 2246 0 0 0 0 0 I_0,2_0,6_150_10_2 0 81506 2150 0 0 0 0 0 I_0,2_0,6_150_10_3 0 80066 4387 0 0 0 0 0 I_0,2_0,6_150_10_4 0 89737 701 0 0 0 0 0 I_0,2_0,6_150_10_5 0 82183 8698 0 0 0 0 0 I_0,2_0,6_150_30_1 147 150157 22006 35 88 47 75 62 I_0,2_0,6_150_30_2 356 181014 18334 106 112 128 97 120 I_0,2_0,6_150_30_3 3026 183696 35270 2062 2119 1764 1899 2032 I_0,2_0,6_150_30_4 311 167000 28189 47 29 0 4 35 I_0,2_0,6_150_30_5 4874 172061 41354 3593 3613 3521 3369 3355 I_0,2_0,6_150_50_1 59354 321792 113776 60279 56797 58751 56501 59394 I_0,2_0,6_150_50_2 36667 245721 87579 35126 35033 34566 35608 35088 I_0,2_0,6_150_50_3 46185 276083 101252 43728 45704 42631 43582 42952 I_0,2_0,6_150_50_4 76961 332651 132951 75164 76083 75539 76244 76274 I_0,2_0,6_150_50_5 43705 277098 102244 42218 43566 43650 42807 43827 I_0,2_0,6_250_10_1 0 205740 774 0 0 0 0 0 I_0,2_0,6_250_10_2 0 215423 1427 0 0 0 0 0 I_0,2_0,6_250_10_3 0 220854 1271 0 0 0 0 0 I_0,2_0,6_250_10_4 0 176256 0 0 0 0 0 0 I_0,2_0,6_250_10_5 0 228906 155 0 0 0 0 0 I_0,2_0,6_250_30_1 0 421148 44113 0 0 0 0 0 I_0,2_0,6_250_30_2 0 475708 65665 0 0 0 0 0 I_0,2_0,6_250_30_3 0 365053 48704 0 0 0 0 0 I_0,2_0,6_250_30_4 0 335205 42337 0 0 0 0 0 I_0,2_0,6_250_30_5 0 361940 51283 0 0 0 0 0 I_0,2_0,6_250_50_1 37578 528689 169569 26690 24777 24356 25344 25319 I_0,2_0,6_250_50_2 39064 593749 154135 27833 25910 26540 30347 24759 I_0,2_0,6_250_50_3 40105 535353 146257 28117 26954 26946 25363 28562 I_0,2_0,6_250_50_4 16991 571229 131624 10652 10482 9597 10337 11480 I_0,2_0,6_250_50_5 66586 623084 204369 54021 53608 54319 53975 53162 I_0,2_0,6_350_10_1 0 310138 0 0 0 0 0 0 I_0,2_0,6_350_10_2 0 367439 0 0 0 0 0 0 I_0,2_0,6_350_10_3 0 339965 0 0 0 0 0 0 I_0,2_0,6_350_10_4 0 343046 0 0 0 0 0 0 I_0,2_0,6_350_10_5 0 432939 236 0 0 0 0 0 I_0,2_0,6_350_30_1 0 617640 49379 0 0 0 0 0 I_0,2_0,6_350_30_2 0 526825 29676 0 0 0 0 0 I_0,2_0,6_350_30_3 0 700013 55089 0 0 0 0 0 I_0,2_0,6_350_30_4 0 632606 43196 0 0 0 0 0 I_0,2_0,6_350_30_5 0 624905 45069 0 0 0 0 0 I_0,2_0,6_350_50_1 18651 798075 148561 10729 9731 9250 10047 8657 I_0,2_0,6_350_50_2 19076 888818 144754 7227 6594 7250 6842 7971 I_0,2_0,6_350_50_3 18689 836431 170315 9962 8460 8702 9323 10640 I_0,2_0,6_350_50_4 0 723240 92184 0 0 0 0 0 I_0,2_0,6_350_50_5 28824 935621 177512 11114 12836 12047 13252 14707 Table A.2: Individual results for the instanes with T= 0.2 and R= 0.6 .
APPENDIX A. DETAILED RESULTS 38 Instane Best Worst NEH run1 run2 run3 run4 run5 I_0,2_1_50_10_1 0 17990 0 0 0 0 0 0 I_0,2_1_50_10_2 0 15143 0 0 0 0 0 0 I_0,2_1_50_10_3 0 14548 0 0 0 0 0 0 I_0,2_1_50_10_4 0 17714 0 0 0 0 0 0 I_0,2_1_50_10_5 0 21210 2748 0 0 0 0 0 I_0,2_1_50_30_1 9849 39142 16870 9889 9891 9849 9891 9885 I_0,2_1_50_30_2 15478 46369 21577 15672 15650 15730 15733 15766 I_0,2_1_50_30_3 18933 47912 23098 19167 19088 19131 19067 19067 I_0,2_1_50_30_4 11830 44878 16176 11860 11921 11916 11847 11854 I_0,2_1_50_30_5 13839 48686 19677 14012 13839 13941 13839 13919 I_0,2_1_50_50_1 28314 63437 35352 28314 28443 28314 28335 28314 I_0,2_1_50_50_2 34288 69385 40347 34433 34471 34386 34469 34462 I_0,2_1_50_50_3 40409 75858 47261 40673 40848 40572 40682 40902 I_0,2_1_50_50_4 36203 72112 45268 36418 36417 36215 36213 36501 I_0,2_1_50_50_5 38744 74799 43913 38925 38785 38930 39075 38920 I_0,2_1_150_10_1 0 110461 0 0 0 0 0 0 I_0,2_1_150_10_2 0 103435 0 0 0 0 0 0 I_0,2_1_150_10_3 0 107620 0 0 0 0 0 0 I_0,2_1_150_10_4 0 108165 0 0 0 0 0 0 I_0,2_1_150_10_5 0 114979 0 0 0 0 0 0 I_0,2_1_150_30_1 0 224099 5697 0 0 0 0 0 I_0,2_1_150_30_2 0 216782 22611 0 0 0 0 0 I_0,2_1_150_30_3 0 205017 16085 0 0 0 0 0 I_0,2_1_150_30_4 0 173766 0 0 0 0 0 0 I_0,2_1_150_30_5 0 211354 26607 0 0 0 0 0 I_0,2_1_150_50_1 104 268284 35055 215 326 253 126 124 I_0,2_1_150_50_2 25898 291400 64491 23115 23440 24274 23769 23599 I_0,2_1_150_50_3 25805 298456 87863 24312 23313 24094 24344 23552 I_0,2_1_150_50_4 30305 318883 81957 30055 28056 29472 30109 29013 I_0,2_1_150_50_5 23555 321501 78810 21926 23108 23184 22277 22502 I_0,2_1_250_10_1 0 274788 0 0 0 0 0 0 I_0,2_1_250_10_2 0 331706 0 0 0 0 0 0 I_0,2_1_250_10_3 0 270323 0 0 0 0 0 0 I_0,2_1_250_10_4 0 293023 0 0 0 0 0 0 I_0,2_1_250_10_5 0 268106 0 0 0 0 0 0 I_0,2_1_250_30_1 0 430488 0 0 0 0 0 0 I_0,2_1_250_30_2 0 503633 4363 0 0 0 0 0 I_0,2_1_250_30_3 0 450297 0 0 0 0 0 0 I_0,2_1_250_30_4 0 439529 0 0 0 0 0 0 I_0,2_1_250_30_5 0 408469 0 0 0 0 0 0 I_0,2_1_250_50_1 0 673718 44201 0 0 0 0 0 I_0,2_1_250_50_2 0 544049 2689 0 0 0 0 0 I_0,2_1_250_50_3 0 628177 52787 0 0 0 0 0 I_0,2_1_250_50_4 0 679747 11235 0 0 0 0 0 I_0,2_1_250_50_5 0 639995 52516 0 0 0 0 0 I_0,2_1_350_10_1 0 484386 0 0 0 0 0 0 I_0,2_1_350_10_2 0 462932 0 0 0 0 0 0 I_0,2_1_350_10_3 0 542073 0 0 0 0 0 0 I_0,2_1_350_10_4 0 555976 0 0 0 0 0 0 I_0,2_1_350_10_5 0 471445 0 0 0 0 0 0 I_0,2_1_350_30_1 0 748152 0 0 0 0 0 0 I_0,2_1_350_30_2 0 852236 0 0 0 0 0 0 I_0,2_1_350_30_3 0 693495 0 0 0 0 0 0 I_0,2_1_350_30_4 0 718808 0 0 0 0 0 0 I_0,2_1_350_30_5 0 787918 0 0 0 0 0 0 I_0,2_1_350_50_1 0 1198477 39126 0 0 0 0 0 I_0,2_1_350_50_2 0 871316 0 0 0 0 0 0 I_0,2_1_350_50_3 0 987292 28616 0 0 0 0 0 I_0,2_1_350_50_4 0 976823 0 0 0 0 0 0 I_0,2_1_350_50_5 0 981061 0 0 0 0 0 0 Table A.3: Individual results for the instanes with T= 0.2 and R= 1 .
APPENDIX A. DETAILED RESULTS 39 Instane Best Worst NEH run1 run2 run3 run4 run5 I_0,4_0,2_50_10_1 12440 37610 16811 12325 12479 12319 12345 12537 I_0,4_0,2_50_10_2 12246 38317 18154 12364 12418 12316 12542 12264 I_0,4_0,2_50_10_3 13431 35455 16019 13484 13413 13520 13545 13548 I_0,4_0,2_50_10_4 13371 36676 17043 13579 13454 13433 13545 13466 I_0,4_0,2_50_10_5 15666 41246 20482 15710 15762 15866 15809 15777 I_0,4_0,2_50_30_1 49501 86040 55607 50184 49578 49889 50312 49864 I_0,4_0,2_50_30_2 44964 78373 50871 45180 45373 45589 45505 45451 I_0,4_0,2_50_30_3 47698 77497 53331 48150 48120 47894 47994 47693 I_0,4_0,2_50_30_4 44095 75249 51021 44291 44425 44247 45083 44702 I_0,4_0,2_50_30_5 44330 77520 49737 44023 44018 44140 44326 44205 I_0,4_0,2_50_50_1 78504 116088 89285 79156 78971 79034 78983 78526 I_0,4_0,2_50_50_2 76005 112695 81770 76120 76566 75980 76558 76070 I_0,4_0,2_50_50_3 77432 121245 83128 77521 77975 77551 77944 77863 I_0,4_0,2_50_50_4 69271 112466 75851 69888 69527 69737 70024 70011 I_0,4_0,2_50_50_5 81265 123042 86964 81964 81884 81459 81826 81914 I_0,4_0,2_150_10_1 74610 214663 99802 73924 72671 72939 72880 72261 I_0,4_0,2_150_10_2 68060 224570 92253 67083 67033 66569 66953 67593 I_0,4_0,2_150_10_3 68570 195474 90275 67099 67652 66809 66907 66716 I_0,4_0,2_150_10_4 83840 229742 108769 82399 81611 81570 80405 81450 I_0,4_0,2_150_10_5 78297 243266 105001 75790 75113 76551 75472 76558 I_0,4_0,2_150_30_1 160726 344393 208804 157600 158432 159656 156668 157999 I_0,4_0,2_150_30_2 167096 345166 223300 168595 166428 164172 164376 165611 I_0,4_0,2_150_30_3 178896 365357 219686 175745 174282 174546 173993 174777 I_0,4_0,2_150_30_4 181210 384627 227785 174872 175312 177234 173541 174106 I_0,4_0,2_150_30_5 174370 335800 224808 174465 172666 173386 171936 172943 I_0,4_0,2_150_50_1 286315 476649 332744 284121 284489 286619 285315 285231 I_0,4_0,2_150_50_2 277514 498646 330115 276151 278540 276080 275744 277180 I_0,4_0,2_150_50_3 283469 492305 333203 279283 281097 282920 281410 282064 I_0,4_0,2_150_50_4 306611 514098 355256 306111 308062 305498 305296 306970 I_0,4_0,2_150_50_5 293482 485725 342426 294075 292138 290932 292051 289027 I_0,4_0,2_250_10_1 174248 473388 224613 172532 172657 171610 174766 173137 I_0,4_0,2_250_10_2 185652 507837 225149 182781 181780 180717 182675 181796 I_0,4_0,2_250_10_3 176022 523125 225076 172151 172619 174199 172922 174108 I_0,4_0,2_250_10_4 181552 556221 236106 178930 178910 175548 179529 177530 I_0,4_0,2_250_10_5 202280 540373 259155 197588 195437 194507 197740 194946 I_0,4_0,2_250_30_1 328501 702794 423826 309122 310141 311091 308913 314278 I_0,4_0,2_250_30_2 398048 784893 479046 374828 380434 374146 371025 368846 I_0,4_0,2_250_30_3 361399 752581 451264 333830 332690 340463 339982 338848 I_0,4_0,2_250_30_4 343587 707748 431145 322134 323434 321616 318698 317161 I_0,4_0,2_250_30_5 352110 713226 436694 329404 330215 328973 329609 328383 I_0,4_0,2_250_50_1 574459 989756 670647 554288 553915 551234 555632 552660 I_0,4_0,2_250_50_2 529885 925117 628280 510743 511261 507689 506694 510379 I_0,4_0,2_250_50_3 557528 957928 653347 542703 545474 545923 539254 548717 I_0,4_0,2_250_50_4 571225 1002874 671010 554784 553269 559025 550932 554157 I_0,4_0,2_250_50_5 576269 981947 661618 560404 560071 557345 560097 555459 I_0,4_0,2_350_10_1 349812 933840 446812 338964 344163 345080 344324 345167 I_0,4_0,2_350_10_2 352470 1067922 434488 343167 343559 346240 343118 346190 I_0,4_0,2_350_10_3 338175 940785 441832 331646 333391 334844 335687 333613 I_0,4_0,2_350_10_4 379651 954031 461138 378921 378969 374178 376148 379388 I_0,4_0,2_350_10_5 345862 945805 415573 340943 342761 335593 339903 339395 I_0,4_0,2_350_30_1 615029 1343398 758472 569839 564556 570050 573259 567592 I_0,4_0,2_350_30_2 609633 1230165 734810 562879 570739 561401 557258 559306 I_0,4_0,2_350_30_3 650046 1277603 773292 602370 609535 614380 612350 607081 I_0,4_0,2_350_30_4 662634 1295388 803541 624015 615793 614838 616307 618695 I_0,4_0,2_350_30_5 651888 1288047 784830 602223 595797 596591 615329 599366 I_0,4_0,2_350_50_1 917309 1664071 1091924 863279 874983 868497 871527 866825 I_0,4_0,2_350_50_2 857089 1635388 994125 801286 805741 806673 802458 804575 I_0,4_0,2_350_50_3 934951 1674854 1092103 880662 885405 874732 878196 879366 I_0,4_0,2_350_50_4 967417 1677322 1118974 904018 909185 908252 919334 910879 I_0,4_0,2_350_50_5 939405 1697469 1084947 899975 885936 891911 896687 882988 Table A.4: Individual results for the instanes with T= 0.4 and R= 0.2 .
APPENDIX A. DETAILED RESULTS 40 Instane Best Worst NEH run1 run2 run3 run4 run5 I_0,4_0,6_50_10_1 12803 37020 17418 12904 13033 12852 13008 12874 I_0,4_0,6_50_10_2 6575 27566 12154 6598 6653 6645 6611 6622 I_0,4_0,6_50_10_3 9739 30146 14105 9739 9739 9739 9739 9739 I_0,4_0,6_50_10_4 13194 35027 19270 13304 13238 13243 13346 13307 I_0,4_0,6_50_10_5 10625 36276 16157 10678 10748 10664 10664 10685 I_0,4_0,6_50_30_1 44630 72562 52053 44762 44957 44971 44904 45080 I_0,4_0,6_50_30_2 43927 73458 51238 44330 44321 44240 44336 44358 I_0,4_0,6_50_30_3 41842 74353 46450 42184 42101 42097 42224 42149 I_0,4_0,6_50_30_4 45133 78371 49585 45315 45284 45369 45496 45592 I_0,4_0,6_50_30_5 42981 77542 49810 43290 43312 43504 43281 43332 I_0,4_0,6_50_50_1 77609 115099 83228 77825 78085 78278 78182 78165 I_0,4_0,6_50_50_2 79076 110998 84708 79929 79824 79513 79605 79381 I_0,4_0,6_50_50_3 84546 121272 91327 85077 85268 84638 85131 84982 I_0,4_0,6_50_50_4 84872 123673 91409 85270 85048 85096 85279 85244 I_0,4_0,6_50_50_5 69945 103258 77508 70301 70174 70545 70397 70837 I_0,4_0,6_150_10_1 15178 157878 41133 14880 14595 14972 14971 15193 I_0,4_0,6_150_10_2 23359 183459 45973 22674 21902 22202 22202 22149 I_0,4_0,6_150_10_3 29421 198920 56256 27742 27920 27272 27306 28712 I_0,4_0,6_150_10_4 31152 184219 60113 31452 31737 31435 31527 31609 I_0,4_0,6_150_10_5 25000 173228 46892 24908 24517 24625 24240 24415 I_0,4_0,6_150_30_1 165106 378263 216190 163441 160818 157796 161424 160562 I_0,4_0,6_150_30_2 147688 326072 199573 146404 145475 142995 145311 144139 I_0,4_0,6_150_30_3 164307 360565 207354 157660 159920 158788 156527 159918 I_0,4_0,6_150_30_4 130975 323780 176416 126569 126466 126969 128135 128231 I_0,4_0,6_150_30_5 91676 283405 144505 90444 87297 90348 89401 88505 I_0,4_0,6_150_50_1 285036 500241 346602 282755 284020 281676 282935 283073 I_0,4_0,6_150_50_2 244189 463914 299753 241345 244519 239592 243689 242158 I_0,4_0,6_150_50_3 238616 466850 291649 237397 235359 237011 237643 236552 I_0,4_0,6_150_50_4 276152 452533 319758 277086 275517 273648 273642 274538 I_0,4_0,6_150_50_5 263796 475957 315386 261290 264494 261896 262558 262488 I_0,4_0,6_250_10_1 84881 477950 131285 81256 81238 81293 82287 81460 I_0,4_0,6_250_10_2 55435 417834 102121 52739 52061 53759 52133 53055 I_0,4_0,6_250_10_3 56512 465246 118621 55656 55315 56624 53310 54635 I_0,4_0,6_250_10_4 65837 514909 111676 63698 62973 65063 63780 63231 I_0,4_0,6_250_10_5 45659 440122 87017 46118 44992 45925 45825 44802 I_0,4_0,6_250_30_1 245976 748314 350730 220005 219404 222842 221845 220413 I_0,4_0,6_250_30_2 218551 757816 338795 201568 199628 198011 197975 195776 I_0,4_0,6_250_30_3 276265 824945 379680 253397 250075 251637 254487 255772 I_0,4_0,6_250_30_4 208685 795630 317722 183813 184533 182239 183309 183357 I_0,4_0,6_250_30_5 217212 707819 320655 193626 191746 191680 192220 195605 I_0,4_0,6_250_50_1 495156 1041976 621607 478723 474655 478804 471500 468798 I_0,4_0,6_250_50_2 464542 1016157 590112 443309 448731 443668 444570 438976 I_0,4_0,6_250_50_3 484289 1071597 583817 465185 464479 466424 473872 467945 I_0,4_0,6_250_50_4 394318 929416 510423 374321 370038 372241 371438 370388 I_0,4_0,6_250_50_5 453074 1003790 573681 438475 430602 431572 431000 432084 I_0,4_0,6_350_10_1 70159 816426 134122 68542 68428 68731 68007 69196 I_0,4_0,6_350_10_2 135250 990376 252849 130024 132674 132963 137674 132336 I_0,4_0,6_350_10_3 119195 924886 215307 114398 112248 118302 113211 116947 I_0,4_0,6_350_10_4 94824 836207 173376 92523 93982 92395 92037 91011 I_0,4_0,6_350_10_5 75281 788473 139041 73997 73820 73860 73916 73941 I_0,4_0,6_350_30_1 275188 1253296 438180 251602 249077 253476 250550 252530 I_0,4_0,6_350_30_2 305379 1284636 495371 278153 275917 270912 270449 268131 I_0,4_0,6_350_30_3 306374 1249957 489130 280042 280281 295244 281807 286662 I_0,4_0,6_350_30_4 421979 1310128 615684 391693 392117 385052 384816 395977 I_0,4_0,6_350_30_5 352512 1292256 528844 315913 321149 321189 312121 318761 I_0,4_0,6_350_50_1 636032 1574946 868628 590559 608250 597738 600354 599050 I_0,4_0,6_350_50_2 641927 1670527 828873 589017 586207 591737 584359 587851 I_0,4_0,6_350_50_3 664344 1660496 893487 631375 631444 630492 620279 630834 I_0,4_0,6_350_50_4 654106 1832601 860521 596296 607015 605654 606794 590699 I_0,4_0,6_350_50_5 673320 1788567 909174 626555 632301 626320 617103 617779 Table A.5: Individual results for the instanes with T= 0.4 and R= 0.6 .
APPENDIX A. DETAILED RESULTS 41 Instane Best Worst NEH run1 run2 run3 run4 run5 I_0,4_1_50_10_1 8499 33694 10808 8535 8499 8533 8514 8534 I_0,4_1_50_10_2 8208 37102 11864 8372 8208 8238 8229 8254 I_0,4_1_50_10_3 2397 25405 4124 2399 2397 2397 2399 2402 I_0,4_1_50_10_4 7116 32276 12604 7230 7143 7353 7240 7196 I_0,4_1_50_10_5 19526 47690 24646 19732 19729 19823 19810 19704 I_0,4_1_50_30_1 57159 90623 62741 57132 57314 57174 57550 57150 I_0,4_1_50_30_2 53443 90392 60148 53798 53471 53921 53720 53854 I_0,4_1_50_30_3 44839 73827 51589 45196 45202 45085 45034 45184 I_0,4_1_50_30_4 47767 78783 53290 47894 47900 47920 47940 47955 I_0,4_1_50_30_5 40849 68896 48621 40862 41008 40981 40867 40956 I_0,4_1_50_50_1 73137 110040 80116 73321 73557 73498 73492 73332 I_0,4_1_50_50_2 80918 121467 85998 81299 81649 81143 81414 81590 I_0,4_1_50_50_3 81996 115056 87950 82372 82139 82117 82025 81847 I_0,4_1_50_50_4 67534 98399 73992 68189 67824 67997 67814 68418 I_0,4_1_50_50_5 89618 128392 94735 90190 90187 90002 90140 89864 I_0,4_1_150_10_1 3777 215460 29577 3078 2650 2936 2950 3368 I_0,4_1_150_10_2 11540 231415 36284 10721 11135 10840 10624 10067 I_0,4_1_150_10_3 23887 241657 53446 21452 22049 23053 21642 21627 I_0,4_1_150_10_4 0 205585 6831 0 0 0 0 0 I_0,4_1_150_10_5 14904 235131 47298 13069 12813 13200 12956 12684 I_0,4_1_150_30_1 126483 377459 178523 121780 123508 121393 121516 120551 I_0,4_1_150_30_2 114910 357652 164767 113328 111036 108678 109428 109969 I_0,4_1_150_30_3 168363 408862 211491 167281 165416 165789 166041 165399 I_0,4_1_150_30_4 110250 337163 158373 106198 109393 106911 107629 108658 I_0,4_1_150_30_5 155548 383986 199149 152069 151364 153633 153487 150878 I_0,4_1_150_50_1 213902 445887 266053 211185 212414 212773 214558 211235 I_0,4_1_150_50_2 270506 511724 323552 267856 270265 268888 271996 268201 I_0,4_1_150_50_3 254563 497004 288594 252245 251032 251837 251377 253432 I_0,4_1_150_50_4 207909 427569 262388 207396 204880 207478 210016 206558 I_0,4_1_150_50_5 257771 507282 312998 256754 255408 255862 257839 257025 I_0,4_1_250_10_1 0 574682 3258 0 0 0 0 0 I_0,4_1_250_10_2 0 569371 676 0 0 0 0 0 I_0,4_1_250_10_3 0 550596 3199 0 0 0 0 0 I_0,4_1_250_10_4 487 532580 23853 166 464 346 209 243 I_0,4_1_250_10_5 0 524065 2828 0 0 0 0 0 I_0,4_1_250_30_1 89346 753161 192442 81099 81267 80310 80330 78473 I_0,4_1_250_30_2 69611 755430 199380 60949 57764 55595 57876 56257 I_0,4_1_250_30_3 162379 825977 307695 144011 144097 139726 138430 142801 I_0,4_1_250_30_4 103737 809065 213027 91442 93028 92636 93752 93688 I_0,4_1_250_30_5 188176 829173 303290 166115 170102 171479 168021 164887 I_0,4_1_250_50_1 497371 1072043 608800 477064 478594 479421 479001 476969 I_0,4_1_250_50_2 428307 1063575 566625 413363 406797 415592 413889 417024 I_0,4_1_250_50_3 419641 1051571 552506 406743 411007 407906 398613 402378 I_0,4_1_250_50_4 367747 1048571 510512 351289 357465 359685 355347 354904 I_0,4_1_250_50_5 342810 987849 462534 326479 320976 325979 326516 323273 I_0,4_1_350_10_1 0 1107180 10410 0 0 0 0 0 I_0,4_1_350_10_2 0 1160268 1914 0 0 0 0 0 I_0,4_1_350_10_3 0 1006234 880 0 0 0 0 0 I_0,4_1_350_10_4 0 984961 2930 0 0 0 0 0 I_0,4_1_350_10_5 1696 1210101 71250 1642 1153 1055 777 897 I_0,4_1_350_30_1 232344 1536886 413310 199354 195929 200929 193092 199751 I_0,4_1_350_30_2 127685 1455530 332438 101194 98491 102191 99384 106064 I_0,4_1_350_30_3 181957 1420092 413733 170640 168120 160651 163777 160361 I_0,4_1_350_30_4 74992 1395009 348915 56761 60667 59615 61718 62662 I_0,4_1_350_30_5 55787 1477067 231578 46115 40777 46388 44424 46352 I_0,4_1_350_50_1 504134 1791943 715862 461591 459840 469432 462406 461416 I_0,4_1_350_50_2 487355 1802832 706430 445714 429474 441050 427632 436042 I_0,4_1_350_50_3 321590 1611422 569966 286419 281141 285485 285202 279627 I_0,4_1_350_50_4 507325 1804010 742225 468260 462446 459255 467974 477774 I_0,4_1_350_50_5 423172 1729840 663002 390639 386936 389109 382818 383024 Table A.6: Individual results for the instanes with T= 0.4 and R= 1 .
REFERENCES 48 [VRM08℄ E. Vallada, R. Ruiz, and G. Minella. Minimising total tardiness in the m-mahine owshop problem: A review and evaluation of heuristis and metaheuristis. Computers and Operations Researh , 35(4):13501373, 2008.