A new vision of approximate methods for the permutation flowshop to minimise makespan: State-of-the-art and computational evaluation

A new vision of approximate methods for the permutation flowshop to minimise makespan: state-of-the-art and computational evaluation Victor Fernandez-Viagas1∗ , Rubén Ruiz2, Jose M. Framinan1 1Industrial Management, School of Engineering, University of Seville, Ave. Descubrimientos s/n, E41092 Seville, Spain, {vfernandezviagas,framinan}@us.es 2Grupo de Sistemas de Optimización Aplicada, Instituto Tecnológico de Informática Ciudad Politécnica de la Innovación, Edifico 8G, Acc. B. Universitat Politècnica de València Camino de Vera s/n, 46021, València, Spain, [email protected].es August 7, 2016 Abstract The permutation flowshop problem is a classic machine scheduling problem where n jobs must be processed on a set of mmachines disposed in series and where each job must visit all machines in the same order. Many production scheduling problems resemble flowshops and hence it has generated much interest and had a big impact in the field, resulting in literally hundreds of heuristic and metaheuristic methods over the last 60 years. However, most methods proposed for makesan minimisation are not properly compared with existing procedures so currently it is not possible to know which are the most efficient methods for the problem regarding the quality of the solutions obtained and the computational effort required. In this paper, we identify and exhaustively compare the best existing heuristics and metaheuristics so the state-of-the-art regarding approximate procedures for this relevant problem is established. Keywords: Scheduling, Flowshop, Heuristics, Metaheuristics, Makespan, Review, Computational evaluation ∗Corresponding author. Tel.: +34-954487220. 1 1 Introduction The flowshop is a common manufacturing layout where njobs have to be processed on mmachines, with each job following the same route at the machines. The so-called flowshop scheduling problem involves the determination of the sequence of jobs at each machine. When the sequence of jobs is the same for all machines, the problem is denoted as Permutation Flowshop Scheduling Problem (PFSP in the following). The PFSP is one of the most studied problems in the Operations Research literature (e.g. see the reviews by [21,71,74]). In the related literature, the minimization of makespan, Cmax, (also denoted as maximum completion time or maximum flowtime) has been commonly chosen by researchers as the objective to optimize in the PFSP (e.g. see [36], [20], [87], [51], [22] or [81] for other objectives in the PFSP). According to the notation of [63], this problem is denoted as Fm|prmu|Cmax. Since [73] showed the problem to be NP-complete for more than two machines, most researchers have focused on implementing approximate methods to find good solutions without excessive computation times. There has been a vast number of papers published with algorithms and procedures. [74] carried out an exhaustive review and computational evaluation of the heuristics and metaheuristics published until 2004 for the PFSP to minimize makespan. A total of 18 heuristics and 7 metaheuristics were implemented and tested under the same conditions. Among them, two of these methods turned out to be the most efficient ones: the NEH heuristic [55] was clearly the most efficient among the constructive heuristics for the problem, and the Iterated Local Search [80] presented itself as the most efficient metaheuristic for the problem. Since the publication of the work by [74], more than 100 new algorithms have been proposed in the literature over the last 10 years. Some of these methods –such as the iterated greedy (IG) of [76]– have improved the best existing algorithms in [74]. However, the new state-of-the-art remains unclear due to the lack of a homogeneous framework to conduct the comparison among algorithms. More specifically, the following problems can be detected: •Many algorithms are compared under different conditions: –Tested under different computer conditions (different programming languages and/or different computers, operating systems, etc.). 2 –Comparison of algorithms with different CPU time usages. –Use of different benchmarks (see Section 2). •Many algorithms are compared in a non-conclusive way: –Lack of comparison against the state-of-the-art (e.g. without comparing with the iterated greedy proposed by [76]). –Among the several runs performed in each instance to increase the power of the results, the best runs are used instead of the average for some algorithms. •New advances in the evaluation of the algorithms: –A more extensive benchmark of instances has been recently proposed by [88]. This testbed can be used to establish statistical differences among algorithms in a sound way, differently from what can be done with older benchmarks (such as those by [83], [3], [70], [90], [14], [26]). –A new indicator has been proposed by [19] to measure the CPU requirements of the algorithms in relative terms. This indicator improves the deficiencies of the most common indicator (i.e. average CPU time) for the evaluation of efficient heuristics. •Finally, a special effort should be made when comparing efficient heuristics against the best metaheuristics under the same stopping criterion since the CPU time required by some heuristics is relatively high in comparison with some metaheuristics. As a conclusion, a new review and evaluation of the approximate methods for the Fm|prmu|Cmax problem is pertinent and may serve firstly to establish a clear picture of the state-of-the-art within this important problem, and secondly, to give indications of possible avenues for future research. This twofold objective is the goal of our research. The remainder of the paper is as follows: in Section 2, heuristics and metaheuristics published in the literature from [74] are analysed and summarised. The most promising ones are chosen to be evaluated and compared. A description of the evaluation and comparison is carried out in Section 3. Computational results of the comparisons between heuristics and metaheuristics are described in Section 4. Finally, in Section 5 conclusions are discussed and some indications and ideas for future research are shown. 3 2 Background The problem under consideration is the permutation flowshop scheduling problem to minimise the maximum completion time or makespan. The problem consists of the determination of the sequence of n jobs which achieves the minimal makespan when all jobs are processed (in the order indicated by the sequence) on the mmachines of a shop. The following additional hypotheses are usually assumed for the PFSP: •Processing times, denoted as pij where i= 1, ..., m and j= 1, ..., n, are known and deterministic. •No preemption is allowed. •Release times are set to 0. •Sequence-dependent set-up times are considered insignificant. •Sequence-independent setup times are considered as non-anticipatory, and therefore can be added to the processing time of the jobs on the machines. •Transportation times can be considered either insignificant or constant. •Each job can be processed by at most one machine at the same time. •Each machine can process only one job at the same time. •Unlimited in-process inventory is considered. •All machines are available on the whole scheduling horizon. As mentioned in the previous section, the NP-hard nature of the problem has led the vast majority of research towards the proposal of approximate solutions, usually classified either as heuristics or metaheuristics. The division between heuristics and metaheuristics is ambiguous and different classifications have been proposed in the literature (see e.g. [103], [95]). For an in-depth classification of the Fm|prmu|Cmax problem, we refer to [21]. However, in this paper we use the same division as in [74], where heuristics and metaheuristics are analysed separately. There, heuristics (constructive and improvement ones) naturally stop when the procedure is finished whereas metaheuristics typically stop after a 4 given number of iterations or elapsed CPU time. This fact naturally leads to perform different computational experiments in Section 4, since the efficiency of the metaheuristics can be compared by running them for the same CPU time whereas heuristics should be compared by means of a Pareto-efficient frontier using the quality of the solution and the CPU time as indicators. In order to maintain the readability of the paper, the same division is considered when analysing the state-of-the-art in this Section. 2.1 Heuristics Traditionally divided into constructive and improvement types, heuristics have been extensively developed for Fm|prmu|Cmax either to yield a good solution in less CPU time or to find a seed sequence for metaheuristics. Since the computational evaluation of [74], several constructive heuristics have been proposed in the literature, most of them variants of the NEH heuristic by [55]. This heuristic consists of two phases: 1. First, jobs are ordered according to an initial order (decreasing sum of processing times). 2. The first job is removed from the initial order and placed in a partial sequence, initially without any job. Next, following this order, each job is removed and tried to be inserted in each possible position of the partial sequence. The position that minimizes the makespan is chosen for the job. The procedure is repeated n-1 times until all jobs are placed in the partial sequence. The computational complexity of the NEH is O(n3m). However, the method proposed by [82] (denoted as Taillard’s acceleration in the following) reduces its original complexity to O(n2m). The different variants of the NEH heuristic can be unified using the following notation formed by three fields: NEH(a|b|c)where the fields a,band care defined by: •a: Initial order used by the NEH. In the computational evaluation, the following sorting criteria have been considered: –rand: Jobs are randomly ordered. This order is used by [72] in RAER and RAER-di heuristics as comparison heuristics. –SD: Non decreasing sum of processing times (original order of the NEH) of the jobs. This 5 order is used by the following heuristics: NEHR [72], NEHR-di [72], NEH [55], NEH- di [72], NEH1 [30] and NEH1-di [72]. –AD: sum of the mean and deviation of the processing times (proposed by [15]). –NM: order proposed by [52] and used in NEMR and NEMR-di heuristics by [72]. –KK1: Sorting criterion proposed by [31]. This initial order is applied in NEHKK1 [31] and NEHKK1-di [72] heuristics. –KK2: Sorting criterion proposed by [32] in NEHKK2 heuristic. •b: Once a job is selected for insertion in all positions of a partial sequence, the same makespan can be obtained for several positions causing ties in each iteration. These ties have a great influence on the performance of the constructive heuristics (see [30]). In the original proposal, the first slot (denoted as FS) for which the minimum makespan is achieved is kept as the best sequence. This bfield then defines the type of tie-breaking mechanism implemented in the NEH. The following mechanisms have been considered: TBKK1, proposed by [30]; TBKK2, proposed by [31]; TBKK3, proposed by [32]; DCH, proposed by [15]; RCT, proposed by [72]; and the FF, proposed by [18]. •c: This field is associated with the reversibility property of the problem (see [72]). It establishes that the makespan of the permutation Π := (π1, . . . , πn)in instance I(instance formed by njobs and mmachines with processing times equal to pij) is the same as the makespan of the reverse permutation Π0:= (πn, . . . , π1)in instance I0(instance formed by njobs and mmachines with processing times equal to p0 ij =pm−j+1,i). Therefore, the value dindicates that the NEH is applied on the direct instance Iwhereas iis used when the algorithm is applied on the inverse instance I0. Accordingly, di indicates that both the direct and the inverse are used, and the best sequence is retained. This notation has been employed to classify the different variants of the original NEH heuristic – which can be denoted as NEH(SD|FS|d)in our notation– proposed in the literature. These are summarized in Table 1. Among the heuristics proposed, some of them –i.e. NEH1, NEHKK1, NEHKK2, NEHD and NEHFF by [30], [31], [32], [15], and [18] respectively – maintain the original complexity of O(n2m). Other 6 variants with a greater complexity have been proposed by [72], see Table 1 (the heuristics implemented in this research are indicated in bold, see Section 3). Two different variants with a greater complexity have been proposed by [94] and are denoted as CLWOTS and CLWTS. In CLWOTS, a new mechanism (denoted as backward shift mechanism) is added to the traditional insertion phase of the NEH. This mechanism increases the sequences to be evaluated in each iteration by means of a movement of the jobs of the partial sequence. When the tie-breaking mechanism of [72] is added to the CLWOTS, the heuristic is denoted as CLWTS Furthermore, 10 heuristics that also modify the insertion phase of the NEH algorithm have been proposed by [66]. These heuristics are denoted as: FRB1, FRB2, FRB3, FRB42, FRB44, FRB46, FRB48, FRB410, FRB412 and FRB5. Among then, the FRB1 heuristic is statistically outperformed by several heuristics (e.g. FRB42and FRB44) with shorter average CPU times. Finally, [89] proposed a constructive NEH-based heuristic, NEHI, which also considers different interpretations for the ties in the initial order of the NEH. 2.2 Metaheuristics As explained in Section 1, numerous metaheuristics have been published in the literature since 2004. A summary of them is shown in Tables 2 and 3, where the metaheuristics implemented in this research are indicated in bold (see Section 3). The first, second, third and fourth columns indicate the year of publication, the bibliographical reference, the type of metaheuristic and the acronym (maintaining the same acronym as in the original papers) respectively. The fifth column shows the papers proposing metaheuristics that outperform the referenced one. In the sixth column, the benchmark(s) used for the computational evaluation are shown (the following notation is used: T1, [83]; T2, non-complete set of instances of [83]; R, [70], C, [3]; D, [14]; W, [90]; H, [26]; O, Other set of instances). The seventh column shows the ARPD values of the metaheuristics when tested on Taillard’s benchmark [83]. Average Relative Percentage Deviation values of algorithm jare denoted as ARPDjand are calculated as follows: ARPDj=P∀iRPDi,j I(1) where Iis the number of instances for which the RPD (Relative Percentage Deviation) values are 7 Table 1: Summary of heuristics Heuristic NEH Notation Paper RAER NEH(rand|RCT |d)[72] RAER-di NEH(rand|RCT |di)[72] KKER NEH(KK1|RCT|d)[72] KKER-di NEH(KK1|RCT|di)[72] NEHR NEH(SD|RCT|d)[72] NEHR-di NEH(SD|RCT|di)[72] NEMR NEH(NM|RCT|d)[72] NEMR-di NEH(NM|RCT|di)[72] NEH NEH(SD|FS|d)[55] NEH-di NEH(SD|FS|di)[72] NEH1 NEH(SD|TBKK1|d)[30] NEH1-di NEH(SD|TBKK1|di)[72] NEHKK1 NEH(KK1|TBKK2|d)[31] NEHKK1-di NEH(KK1|TBKK2|di)[72] NEHKK2 NEH(KK2|TBKK3|d)[32] NEHD NEH(AD|DHC|d)[15] NEHD-di NEH(AD|DHC|di)[72] NEHFF NEH(AD|FF|d)[18] CLWTS NEH(SD|F S|d)with a backward shift mechanism in the insertion phase [94] CLWOTS NEH(SD|RCT|d)with a backward shift mechanism in the insertion phase [94] NEHI Best of several runs of NEH(−| − |−)[89] FRB1 Similar to the NEH(SD|F S|d)including a local search method in the insertion phase [66] FRB2 Similar to the NEH(SD|F S|d)including a local search method in the insertion phase [66] FRB3 NEH(SD|F S|d)including a local search method in the insertion phase [66] FRB4kNEH(SD|F S|d)including a local search method in the insertion phase [66] FRB5 NEH(SD|F S|d)including a local search method in the insertion phase [66] 8 obtained (i.e. the testbed size). RPDij is the relative percentage deviation obtained by algorithm jwhen applied to instance iand is typically calculated as follows: RPDi,j =Cmax,i,j −Besti Besti ·100 (2) where Cmax,i,j is the makespan of the algorithm jin instance iand Bestiis the upper bound (best solution known) for that instance. When the raw makespan value for each instance is given in the paper, the ARPD is computed again using (2) and the best known value for those instances (see on-line materials) in order to have a common reference. Otherwise, the ARPD values of the paper are reported. Note that these papers could have used different upper bounds (Besti) and the values are therefore only approximations. For papers using the same upper bounds as in [83], a factor of 0.565 is added to correct the ARPDs. This value is the difference in ARPD between the actual upper bounds and the upper bounds of [83]. The eight and ninth columns indicate the programming languages used for coding the algorithms as well as the raw speed of the processors used for the evaluation. Finally, the average CPU time on Taillard’s instances as a function of the size of the problem (i.e. nand m) is calculated, when possible, in the last column in order to analyze the CPU requirements of the algorithms. This value is expressed in terms of tjfor metaheuristic j, a variable traditionally used in the literature to measure its stopping criterion as n·m·tj/2milliseconds (see e.g. [76]). When tjis not indicated and/or other stopping criteria are used, tjis calculated as follows: tj=X ∀i tij and tij =2·CPUij ni·mi where CPUij is the CPU time in milliseconds required by algorithm jin instance i.niand miand the number of jobs and machines in instance i. Therefore, tij balances the CPU time with the size of the problem, and tj–average of tij– can be seen as an indicator of the average CPU time requirements of an algorithm, since, given an instance, niand miare constants for different algorithms. For clarity, when a paper proposes several metaheuristics, these methods are included in the table as 9 good solution quality (ARPD < 0.4), or a reasonable solution quality in short-medium computational times (ARPD < 0.6 and tparameter ≤90). 12 metaheuristics fulfil these requirements: EXTS by [79]; HGA_RMA by [75]; MSSA by [60]; IG_RSLS by [76]; IGRIS by [62]; DDERLS by [62]; 3XTS by [16]; EDAACS by [86]; PSO by [100]; IG_RSLS(TBFF) by [18]; IGRIS(TBFF) by [18]. Among them, EXTS and HGA_RMA, are discarded since they are outperformed in statistically and/or sound comparisons by [16] and [76] respectively. Additionally, the H-CPSO algorithm by [29] has been implemented due to its promising results despite being outperformed by [62] under different stopping criteria and conditions. Metaheuristic HCS by [38] has also been included in the comparison since the ARPD is very close to 0.4 and has not been shown to be outperformed by any other metaheuristic. Finally, we include the TSAB tabu search algorithm by [59] in the comparisons, given its excellent performance and the fact that it was not included in the last computational evaluation by [74]. The reason behind this omission is explained in [76] which is mainly the difficulty in reproducing the results of the TSAB algorithm. As a matter of fact, we had to contact the authors of the method, which kindly provided the source code used for checking our reimplementation. Hence, a total of 12 metaheuristics have been chosen (indicated in bold in Tables 2 and 3). Note that all selected algorithms are implemented and tested under the same conditions which means: •Using the same computer. This means same processor speed, bus speed, memory speed and size, etc. •Using the same programming language. •Using the same operating system. •Using the same libraries and common functions. •Using the same stopping criteria for the metaheuristics. When reimplementing the algorithms, doubts relating to the implementation were transmitted to the corresponding authors of the papers. All questions were successfully answered by the authors with the exception of [100], where no answer was received after several tries. Other specifics considered in order to carry out a fair comparison of the algorithms are the following: 16 •The order of the instances was randomly chosen in the experiments to avoid systematic errors in the tests. •The algorithms to be run in each instance are similarly randomized. •For each instance, ten independent runs were performed for each heuristic to better fit the required CPU time (the average CPU time is kept). •For each instance, five independent runs were carried out for each metaheuristic keeping the average values. Note that even recently published, this computational evaluation follows many of the practices highlighted in [33]. The results of these experiments –that have required a total CPU time effort of 393.03 days– are presented in the next section. 4 Computational Results 4.1 Constructive and Improvement Heuristics The 19 heuristics implemented in this evaluation are first compared under the classic benchmark set of Taillard with 120 instances. The detailed results in terms of ARPD,ACPU and ARPD, ordered by problem size, are presented as on-line materials. The overall results are summarised in Table 4. The second, third and fourth columns represent the ARPD,ACPU and ARPT values for each algorithm in the set of instances of Taillard. ARPD values range from 3.89 (RAER heuristic) to 1.48 (FRB5 improvement heuristic) while ARPT values range from 0.02 to 7.23. Results are graphically shown in Figures 1 and 2 where the y-axis represents the ARPD for each heuristic and x-axis, respectively, represents ACPU and ARPT in logarithmic scale. Although results obtained for the different time indicators are, in general, similar, there are also differences in the performance of the heuristics. Therefore, considering ACPU as a measure of the computational effort as compared to ARPT, FRB42is faster than KKER-di, NEHR-di and RAER-di in addition to the CLWTS being slower than the FRB2 heuristic. According to indicators ARPD and ARPT, the efficient heuristics are NEHKK2, NEHFF, NEHR-di (this last one would not be efficient considering ARPD and ACPU), FRB42, FRB44, FRB46, FRB410, 17 Figure 1: ARP D versus ACP U of heuristics in logarithmic scale on Taillard’s instances. FRB412, FRB3 and FRB5 (shown with a black circle in Figure 2). To be able to compare heuristics with different stopping criteria, they are grouped into clusters with similar ARPT values (see Figure 2). Then, the heuristics of each cluster are compared with the best heuristic in terms of ARPD of that cluster, i.e. NEHFF, FRB42, FRB44, FRB46and FRB412, respectively, for clusters 1, 2, 3, 4 and 5. The hypotheses to statistically check the efficiency of the heuristics are shown in Table 5, ordered by these clusters of heuristics. Since each heuristic is based on the original NEH algorithm and the same set of instances is used, the hypotheses of independence (denoted by H0,t,i) of the random variables (RDI) can be rejected (see third and fourth columns in Table 5). The non-parametric Friedman two-way analysis of variance for paired samples is used to check the statistical significance of the differences among the heuristics in each cluster (being the null hypothesis –denoted H0,t,f – that there are no differences). Additionally, to establish the significance of the differences between the best heuristic of the cluster and the rest, the nonparametric Wilcoxon signed-rank test in a post-hoc analysis is employed (being H0,t,w the corresponding null hypothesis). Results are shown in Table 5. Assuming a level of confidence of 0.95, several H0,t,w null hypotheses of the NEHFF heuristic (Cluster 1) have not been rejected (see e.g. NEHFF vs NEHR or NEHFF vs NEH-di). Additionally, there is not enough statistical evidence to state that FRB46and FRB412 outperform FRB48and FRB2 respectively. A similar Pareto set is found when the heuristics are compared under the new set of instances VRF 18 Table 4: Summary of heuristics Algorithm Taillard VRF ARPD ACPU ARPT ARPD ACPU ARPT NEHKK2 3.09 0.02 0.12 3.21 0.47 0.02 NEHFF 2.90 0.02 0.13 2.95 0.46 0.02 NEH-di 3.03 0.04 0.20 3.18 0.91 0.04 NEH1-di 3.11 0.04 0.20 3.15 0.91 0.04 NEHKK1-di 3.15 0.04 0.20 3.19 0.93 0.04 RAER 3.89 0.06 0.20 3.46 0.88 0.04 NEHR 3.05 0.06 0.21 3.16 0.93 0.04 KKER 3.15 0.06 0.21 3.15 0.93 0.04 NEMR 3.16 0.10 0.31 3.22 1.64 0.07 RAER-di 3.53 0.13 0.40 3.33 1.71 0.07 NEHR-di 2.85 0.13 0.40 3.02 1.82 0.07 KKER-di 2.86 0.12 0.42 3.00 1.79 0.07 NEHD-di 2.84 0.16 0.48 2.86 2.06 0.08 FRB422.33 0.11 0.48 2.57 2.81 0.13 NEMR-di 2.97 0.18 0.52 3.05 2.53 0.10 FRB442.13 0.18 0.68 2.31 4.65 0.20 CLWTS 3.02 0.86 0.73 3.11 26.63 0.68 FRB461.91 0.25 0.89 2.17 6.42 0.28 FRB481.95 0.31 1.06 2.07 8.09 0.35 FRB410 1.87 0.37 1.20 1.97 9.87 0.43 FRB412 1.79 0.42 1.34 1.94 11.42 0.49 FRB2 1.93 0.64 1.68 1.74 37.97 1.40 FRB3 1.61 5.08 3.61 1.32 198.31 4.34 FRB5 1.48 14.59 7.23 1.04 753.56 14.36 Figure 2: ARP D versus ARP T of heuristics in logarithmic scale on Taillard’s instances. 19 Table 5: Hypotheses, analysis of dependence and Friedman two-way analysis on Taillard’s instances Clusters Comparison Analysis of Dependence Friedman Wilcoxon Correlation Sig. Sig. Sig. Cluster 1 (green) NEHFF vs NEHKK2 0.891 0.000 0.000 0.015 NEHFF vs NEH-di 0.923 0.000 0.054 NEHFF vs NEHKK1-di 0.895 0.000 0.001 NEHFF vs NEHR 0.893 0.000 0.055 NEHFF vs NEH1-di 0.910 0.000 0.021 NEHFF vs KKER 0.884 0.000 0.010 NEHFF vs NEMR 0.869 0.000 0.006 NEHFF vs RAER 0.830 0.000 0.000 Cluster 2 (blue) FRB42vs RAER-di 0.842 0.000 0.000 0.000 FRB42vs NEHR-di 0.880 0.000 0.000 FRB42vs KKER-di 0.877 0.000 0.000 FRB42vs NEHD-di 0.860 0.000 0.000 FRB42vs NEMR-di 0.864 0.000 0.000 Cluster 3 (orange) FRB44vs CLWTS 0.868 0.000 0.000 0.000 Cluster 4 (red) FRB46vs FRB480.937 0.000 0.604 — Cluster 5 (yellow) FRB412 vs FRB2 0.927 0.000 0.107 — of [88]. Average results are shown in Table 4. The last three columns represent the ARP D,ACPU and ARPT of each heuristic in that set of instances. Clearly, heuristics of complexity O(n3m)(CLW T S, FRB2, FRB3 and FRB5) need proportionally more computational effort since this set of instances considers higher values of nand mthan in Taillard’s instances. This increase in the computational effort also results in a decrease in the ARPD of the heuristics with the exception of CLW T S. Results are graphically shown in Figure 3 comparing ARPD versus ACPU, and in Figure 4 comparing ARPD versus ARPT. In terms of ARPD and ARPT, efficient heuristics are shown with a black circle in Figure 4. Note that regarding the NEH-based heuristics of [72] with direct and inverse approach, the best ARPD is now found by the NEHD-di heuristic instead of the NEHR-di. In order to compare the heuristics, we group them according to their ARPT (see Figure 4) and perform the same Friedman two-way analysis of variance to identify the differences among the heuristics in each cluster (being H0,v,f the corresponding null hypothesis), since hypotheses of independence (H0,v,i) can be rejected again). In a post-hoc analysis, a non-parametric Wilcoxon signed-rank test is applied to establish the statistical significance of the differences between the best heuristic of each cluster (H0,v,w being the null hypothesis). Note that heuristics FRB4kare not compared together as they are the same heuristic with a different input parameter. Results are shown in Table 6. Each p-value is 0.000 and all H0,v,f and H0,v,w hypotheses are rejected. Thus, according to ARPD and ARPT, there is no statistical reason to affirm that the NEHFF, FRB4k, FRB2, FRB3, FRB5 heuristics are not efficient within each cluster. 20 Table 6: Hypotheses, analysis of dependence and Friedman two-way analysis on VRF instances Comparison Analysis of Dependence Friedman Wilcoxon Correlation Sig. Sig. Sig. Cluster 1 (green) NEHFF vs NEHKK2 0.950 0.000 0.000 0.000 NEHFF vs NEH-di 0.954 0.000 0.000 NEHFF vs NEHKK1-di 0.952 0.000 0.000 NEHFF vs NEHR 0.946 0.000 0.000 NEHFF vs NEH1-di 0.939 0.000 0.000 NEHFF vs KKER 0.952 0.000 0.000 NEHFF vs RAER 0.945 0.000 0.000 Cluster 2 (blue) FRB42vs NEMR 0.943 0.000 0.000 0.000 FRB42vs RAER-di 0.946 0.000 0.000 FRB42vs NEHR-di 0.958 0.000 0.000 FRB42vs KKER-di 0.953 0.000 0.000 FRB42vs NEHD-di 0.948 0.000 0.000 FRB42vs NEMR-di 0.952 0.000 0.000 Cluster 3 (orange) FRB412 vs CLWTS 0.942 0.000 0.000 0.000 Figure 3: ARP D versus ACP U of heuristics in logarithmic scale on VRF instances. 21 Figure 4: ARP D vs ARP T of heuristics in logarithmic scale on VRF instances. 4.2 Metaheuristics In Section 3, 12 metaheuristics were defined as the most promising according to the results shown in their papers. In this section, these metaheuristics are compared using the sets of instances of [83] and [88]. Each metaheuristic is stopped using the same stopping criterion based on CPU time. More specifically, three different stopping criteria are applied, t·n·m/2milliseconds with t∈ {30,60,90}, which depends on the number of jobs and machines. Results are shown in Table 7. For both sets of instances, the best metaheuristics are those based on the Iterated Greedy (IG_RSLS) proposed by [76], see the results found by IG_RSLS, IGRIS, IG_RSLS(TBFF) and IGRIS(TBFF) for example. These results are also confirmed by the DDERLS, a discrete differential evolution algorithm which uses similar phases. Regarding Taillard’s instances, the ARPDs of Iterated Greedy metaheuristics for t= 90 is between 0.28 and 0.38 which clearly outperforms non IG-based metaheuristics (the ARPDs of 3XTS, H-CPSO, HCS and PSO are, respectively, 1.24, 0.70, 1.35 and 0.84 for t= 90). The best ARPD value is obtained by IG_RSLS(TBFF) proposed by [18], with 0.37, 0.32 and 0.37 for t= 30,t= 60 and t= 90 on Taillard’s instances respectively. Let us highlight the fast convergence behaviour of IG_RSLS(TBFF) where the ARPD obtained for t= 30 is lower than or equal to every other metaheuristic for t= 90. Metaheuristics are compared with IG_RSLS(TBFF) using the non-parametric Wilcoxon signed-rank test (see Table 8). Note that each p-value on the Taillard’s instances is less than or equal to 0.003 regardless 22 Table 7: Summary of ARP Ds of the metaheuristics Metaheuristic Ref. Taillard VRF t=30 t=60 t=90 t=30 t=60 t=90 TSAB [59] 0.97 0.87 0.84 2.16 1.96 1.85 MSSA [60] 1.00 0.91 0.84 2.17 1.96 1.84 IG_RSLS [76] 0.47 0.40 0.37 0.96 0.77 0.67 IGRIS [62] 0.49 0.42 0.38 0.85 0.67 0.56 DDERLS [62] 0.52 0.47 0.43 0.92 0.77 0.69 3XTS [16] 1.64 1.34 1.24 2.89 2.65 2.47 H-CPSO [29] 0.84 0.75 0.70 1.65 1.41 1.28 EDAACS [86] 0.60 0.51 0.47 1.43 1.25 1.16 HCS [38] 1.55 1.42 1.35 2.54 2.35 2.27 PSO [100] 1.09 0.95 0.84 2.51 2.14 1.93 IG_RSLS(TBFF) [18] 0.37 0.32 0.28 0.60 0.46 0.37 IGRIS(TBFF) [18] 0.42 0.34 0.31 0.61 0.47 0.38 the value of t. Regarding the VRF instances, the superiority of the IG-based algorithms is more clear, as VRF instances include a wider range of values of nand m. Thereby, the differences between the ARPD values of the metaheuristics greatly increase with respect to the IG_RSLS(TBFF) metaheuristic (see the difference of ARPD between 3XTS and IG_RSLS(TBFF) is 0.96 on Taillard’s instances and 2.10 on VRF instances for t= 90 for example). Statistical significance has been found for all metaheuristics (maximum pvalue equal to 0.000) with the exception of IGRIS(TBFF) (see Table 8). In view of the results, although there are many papers proposing metaheuristics, only the Iterated Greedy variants proposed by [18] statistically outperform IG_RSLS on both Taillard’s and VRF instances. We have already commented that many metaheuristics have been published since the last computational evaluation and review of meheuristics proposed by [74] (see Tables 2 and 3) and since the original Iterated Greedy algorithm proposed by [76]. On one hand, in view of Tables 2 and 3, only 12 metaheuristics have promising results in terms of quality of solutions and computational effort. On the other hand, in view of the results in this Section, only the IGRIS(TBFF) and the IG_RSLS(TBFF) algorithms are state-of-the-art methods. It follows that many metaheuristics were not state-of-the-art even at the time on their publication, a fact that strongly highlights the need for a review and framework for computational evaluation such as the one proposed in this paper. 23 Table 8: Comparison of metaheuristics using Wilcoxon signed-rank tests Comparison Taillard (Sig.) VRF (Sig.) t=30 t=60 t=90 t=30 t=60 t=90 TSAB vs IG_RSLS(TBFF) 0.000 0.000 0.000 0.000 0.000 0.000 MSSA vs IG_RSLS(TBFF) 0.000 0.000 0.000 0.000 0.000 0.000 IGRIS vs IG_RSLS(TBFF) 0.000 0.000 0.000 0.000 0.000 0.000 IG_RSLS vs IG_RSLS(TBFF) 0.000 0.000 0.000 0.000 0.000 0.000 DDERLS vs IG_RSLS(TBFF) 0.000 0.000 0.000 0.000 0.000 0.000 3XTS vs IG_RSLS(TBFF) 0.000 0.000 0.000 0.000 0.000 0.000 H-CPSO vs IG_RSLS(TBFF) 0.000 0.000 0.000 0.000 0.000 0.000 EDAACS vs IG_RSLS(TBFF) 0.000 0.000 0.000 0.000 0.000 0.000 HCS vs IG_RSLS(TBFF) 0.000 0.000 0.000 0.000 0.000 0.000 PSO vs IG_RSLS(TBFF) 0.000 0.000 0.000 0.000 0.000 0.000 IGRIS(TBFF) vs IG_RSLS(TBFF) 0.000 0.003 0.000 0.155 0.220 0.137 4.3 Comparison of heuristics with metaheuristics Traditionally, researchers have focused either on finding efficient heuristics, or on obtaining the best metaheuristic for the problem. The former are implemented to find a good fast solution and/or a good initial seed sequence for the problem, while the latter are typically implemented to find better solutions using longer CPU times. As a consequence, typically both heuristics and metaheuristics have been separately evaluated and compared. In this Section, we analyse both heuristics and metaheuristics together, as there are several heuristics requiring long CPU times and vice versa. Therefore, each heuristic is compared with one of the best metaheuristics, i.e. the iterated greedy IG_RSLS(TBFF). In order to have a fair comparison, the metaheuristic is stopped at the CPU time used by each heuristic. These comparisons are performed using the sets of instances of [83] and [88]. A summary of the results is shown in Table 9 as well as in Figures 5 and 6 for these benchmarks, respectively, where the dotted lines represent logarithmic trend lines for the heuristics and the red squares represent all values obtained by IG_RSLS(TBFF). Note that IG_RSLS(TBFF) starts with the sequence obtained by NEHFF and therefore, NEHKK2 and NEHFF are not included in the comparison as they need shorter CPU times. For all other heuristics, the metaheuristic outperforms them in terms of ARPD. All compared heuristics are outperformed by IG_RSLS(TBFF), especially when compared on the VRF instances. The statistical significance of these comparisons is established by means of the non-parametric Wilcoxon signed-rank test since the normality 24 and homoscedasticity assumptions are not fulfilled. Note that statistical significances are found for each comparison on the Taillard instances, even against the heuristics proposed by [66] which have ARPD values similar to or even better than those obtained by IG_RSLS(TBFF) for several problem sizes. Similarly, each corresponding null hypothesis is rejected on VRF instances, 0.001 being the highest pvalue. This Section highlights the exceptional performance of IG-based algorithms for short periods of time and also serves to classify IG_RSLS(TBFF) as a state-of-the-art method for constructive and improvement heuristics. 25 [27] C.-Y. Hsu, P.-C. Chang, and M.-H. Chen. A linkage mining in block-based evolutionary algorithm for permutation flowshop scheduling problem. Computers and Industrial Engineering, 83:159– 171, 2015. [28] W.Q. Huang and L. Wang. A local search method for permutation flow shop scheduling. Journal of the Operational Research Society, 57(10):1248–1251, 2006. [29] B. Jarboui, S. Ibrahim, P. Siarry, and A. Rebai. A combinatorial particle swarm optimisation for solving permutation flowshop problems. Computers and Industrial Engineering, 54(3):526–538, 2008. [30] P. J. Kalczynski and J. Kamburowski. On the NEH heuristic for minimizing the makespan in permutation flow shops. OMEGA, The International Journal of Management Science, 35(1):53– 60, February 2007. [31] P. J. Kalczynski and J. Kamburowski. An improved NEH heuristic to minimize makespan in permutation flow shops. Computers and Operations Research, 35(9):3001–3008, 2008. [32] P. J. Kalczynski and J. Kamburowski. An empirical analysis of the optimality rate of flow shop heuristics. European Journal of Operational Research, 198(1):93 – 101, 2009. [33] G. Kendall, R. Bai, J. Błazewicz, P. De Causmaecker, M. Gendreau, R. John, J. Li, B. McCollum, E. Pesch, R. Qu, N. Sabar, G. Vanden Berghe, and A. Yee. Good laboratory practice for optimization research. Journal of the Operational Research Society, 67(4):676–689, 2016. [34] I.-H. Kuo, S.-J. Horng, T.-W. Kao, T.-L. Lin, C.-L. Lee, T. Terano, and Y. Pan. An efficient flowshop scheduling algorithm based on a hybrid particle swarm optimization model. Expert Systems with Applications, 36(3 PART 2):7027–7032, 2009. [35] D. Laha and U.K. Chakraborty. An efficient hybrid heuristic for makespan minimization in permutation flow shop scheduling. International Journal of Advanced Manufacturing Technology, 44(5-6):559–569, 2009. [36] R. Leisten and C. Rajendran. Variability of completion time differences in permutation flow shop scheduling. Computers and Operations Research, 54:155–167, 2014. [37] X. Li and M. Yin. A discrete artificial bee colony algorithm with composite mutation strategies for permutation flow shop scheduling problem. Scientia Iranica, 19(6):1921–1935, 2012. [38] X. Li and M. Yin. A hybrid cuckoo search via Lévy flights for the permutation flow shop scheduling problem. International Journal of Production Research, 51(16):4732–4754, 2013. [39] X. Li and M. Yin. An opposition-based differential evolution algorithm for permutation flow shop scheduling based on diversity measure. Advances in Engineering Software, 55:10–31, 2013. [40] Z. Lian, X. Gu, and B. Jiao. A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan. Applied Mathematics and Computation, 175(1):773– 785, 2006. [41] Z. Lian, X. Gu, and B. Jiao. A novel particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan. Chaos, Solitons and Fractals, 35(5):851–861, 2008. [42] C.-J. Liao, Chao-Tang Tseng, and P. Luarn. A discrete version of particle swarm optimization for flowshop scheduling problems. Computers and Operations Research, 34(10):3099–3111, 2007. 32 [43] Q. Lin, L. Gao, X. Li, and C. Zhang. A hybrid backtracking search algorithm for permutation flow-shop scheduling problem. Computers and Industrial Engineering, 85:437 – 446, 2015. [44] B. Liu, L. Wang, and Y.-H. Jin. An effective pso-based memetic algorithm for flow shop scheduling. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 37(1):18–27, 2007. [45] H. Liu, L. Gao, and Q.-K. Pan. A hybrid particle swarm optimization with estimation of distribution algorithm for solving permutation flowshop scheduling problem. Expert Systems with Applications, 38(4):4348–4360, 2011. [46] R. Liu, C. Ma, W. Ma, and Y. Li. A multipopulation pso based memetic algorithm for permutation flow shop scheduling. The Scientific World Journal, 2013. [47] Y. Liu, M. Yin, and W. Gu. An effective differential evolution algorithm for permutation flow shop scheduling problem. Applied Mathematics and Computation, 248:143–159, 2014. [48] Y.-F. Liu and S.-Y. Liu. A hybrid discrete artificial bee colony algorithm for permutation flowshop scheduling problem. Applied Soft Computing Journal, 13(3):1459–1463, 2013. [49] C. Low, J.-Y. Yeh, and K.-I. Huang. A robust simulated annealing heuristic for flow shop scheduling problems. International Journal of Advanced Manufacturing Technology, 23(9-10):762–767, 2004. [50] Y. Marinakis and M. Marinaki. Particle swarm optimization with expanding neighborhood topology for the permutation flowshop scheduling problem. Soft Computing, 17(7):1159–1173, 2013. [51] R. M’Hallah. An iterated local search variable neighborhood descent hybrid heuristic for the total earliness tardiness permutation flow shop. International Journal of Production Research, 52(13):3802–3819, 2014. [52] M.S. Nagano and J.V. Moccellin. A high quality solution constructive heuristic for flow shop sequencing. Journal of the Operational Research Society, 53(12):1374–1379, 2002. [53] M.S. Nagano, R. Ruiz, and L.A.N. Lorena. A constructive genetic algorithm for permutation flowshop scheduling. Computers and Industrial Engineering, 55(1):195–207, 2008. [54] S. Nanz and C. A. Furia. A comparative study of programming languages in rosetta code. In Proceedings of the 37th International Conference on Software Engineering, volume 1, pages 778– 778, 2015. [55] M. Nawaz, E.E. Enscore Jr., and I. Ham. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. OMEGA, The International Journal of Management Science, 11(1):91–95, 1983. [56] A.C. Nearchou. The effect of various operators on the genetic search for large scheduling problems. International Journal of Production Economics, 88(2):191–203, 2004. [57] A.C. Nearchou. Flow-shop sequencing using hybrid simulated annealing. Journal of Intelligent Manufacturing, 15(3):317–328, 2004. [58] A.C. Nearchou. A novel metaheuristic approach for the flow shop scheduling problem. Engineering Applications of Artificial Intelligence, 17(3):289–300, 2004. 33 [59] E. Nowicki and C. Smutnicki. A fast tabu search algorithm for the permutation flow-shop problem. European Journal of Operational Research, 91(1):160–175, 1996. [60] E. Nowicki and C. Smutnicki. Some aspects of scatter search in the flow-shop problem. European Journal of Operational Research, 169(2):654–666, 2006. [61] G. Onwubolu and D. Davendra. Scheduling flow shops using differential evolution algorithm. European Journal of Operational Research, 171(2):674–692, 2006. [62] Q.-K. Pan, M.F. Tasgetiren, and Y.-C. Liang. A discrete differential evolution algorithm for the permutation flowshop scheduling problem. Computers and Industrial Engineering, 55(4):795– 816, 2008. [63] M. Pinedo. Scheduling: Theory, Algorithms and Systems. Prentice Hall, fourth edition, 2012. [64] G. Prabhaharan, B.S.H. Khan, and L. Rakesh. Implementation of GRASP in flow shop scheduling. International Journal of Advanced Manufacturing Technology, 30(11-12):1126–1131, 2006. [65] B. Qian, L. Wang, R. Hu, W.-L. Wang, D.-X. Huang, and X. Wang. A hybrid differential evolution method for permutation flow-shop scheduling. International Journal of Advanced Manufacturing Technology, 38(7-8):757–777, 2008. [66] S. F. Rad, R. Ruiz, and N. Boroojerdian. New high performing heuristics for minimizing makespan in permutation flowshops. OMEGA, The International Journal of Management Science, 37(2):331–345, 2009. [67] C. Rajendran and H. Ziegler. Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. European Journal of Operational Research, 155(2):426– 438, 2004. [68] R. Rajkumar and P. Shahabudeen. An improved genetic algorithm for the flowshop scheduling problem. International Journal of Production Research, 47(1):233–249, 2009. [69] T.R. Ramanan, R. Sridharan, K.S. Shashikant, and A.N. Haq. An artificial neural network based heuristic for flow shop scheduling problems. Journal of Intelligent Manufacturing, 22(2):279–288, 2011. [70] C.R. Reeves. A genetic algorithm for flowshop sequencing. Computers and Operations Research, 22(1):5–13, 1995. [71] S. Reza Hejazi and S. Saghafian. Flowshop-scheduling problems with makespan criterion: A review. International Journal of Production Research, 43(14):2895–2929, 2005. [72] I. Ribas, R. Companys, and X. Tort-Martorell. Comparing three-step heuristics for the permutation flow shop problem. Computers and Operations Research, 37(12):2062–2070, 2010. [73] A. H. G. Rinnooy Kan. Machine Scheduling Problems: Classification, Complexity and Computations. Martinus Nijhoff, The Hague, 1976. [74] R. Ruiz and C. Maroto. A comprehensive review and evaluation of permutation flowshop heuristics. European Journal of Operational Research, 165(2):479–494, 2005. [75] R. Ruiz, C. Maroto, and J. Alcaraz. Two new robust genetic algorithms for the flowshop scheduling problem. OMEGA, The International Journal of Management Science, 34(5):461–476, 2006. 34 [76] R. Ruiz and T. Stützle. A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 177(3):2033–2049, 2007. [77] M. Saravanan, A. Noorul Haq, A.R. Vivekraj, and T. Prasad. Performance evaluation of the scatter search method for permutation flowshop sequencing problems. International Journal of Advanced Manufacturing Technology, 37(11-12):1200–1208, 2008. [78] M.K. Sayadi, R. Ramezanian, and N. Ghaffari-Nasab. A discrete firefly meta-heuristic with local search for makespan minimization in permutation flow shop scheduling problems. International Journal of Industrial Engineering Computations, 1(1):1–10, 2010. [79] M. Solimanpur, P. Vrat, and R. Shankar. A neuro-tabu search heuristic for the flow shop scheduling problem. Computers and Operations Research, 31(13):2151–2164, 2004. [80] T. Stütze. Applying iterated local search to the permutation flow shop problem. Technical report, AIDA-98-04, FG Intellektik, FB Informatik, TU Darmstadt, 1998. [81] Y. Sun, C. Zhang, L. Gao, and X. Wang. Multi-objective optimization algorithms for flow shop scheduling problem: A review and prospects. International Journal of Advanced Manufacturing Technology, 55(5-8):723–739, 2011. [82] E. Taillard. Some efficient heuristic methods for the flow shop sequencing problem. European Journal of Operational Research, 47(1):65–74, 1990. [83] E. Taillard. Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2):278–285, 1993. [84] M.F. Tasgetiren, Y.-C. Liang, M. Sevkli, and G. Gencyilmaz. A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. European Journal of Operational Research, 177(3):1930–1947, 2007. [85] L.-Y. Tseng and Y.-T. Lin. A hybrid genetic local search algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 198(1):84–92, 2009. [86] Y.-R. Tzeng and C.-L. Chen. A hybrid eda with acs for solving permutation flow shop scheduling. International Journal of Advanced Manufacturing Technology, 60(9-12):1139–1147, 2012. [87] E. Vallada and R. Ruiz. Genetic algorithms with path relinking for the minimum tardiness permutation flowshop problem. OMEGA, The International Journal of Management Science, 38(1- 2):57–67, 2010. [88] E. Vallada, R. Ruiz, and J.M. Framinan. New hard benchmark for flowshop scheduling problems minimising makespan. European Journal of Operational Research, 240:666–677, 2015. [89] D. Vasiljevic and M. Danilovic. Handling ties in heuristics for the permutation flow shop scheduling problem. Journal of Manufacturing Systems, 35:1–9, 2015. [90] J.P. Watson, L. Barbulescu, L.D. Whitley, and A.E. Howe. Contrasting structured and random permutation flow-shop scheduling problems: Search-space topology and algorithm performance. INFORMS Journal on Computing, 14(2):98–123, 2002. 35 [91] Z. Xie, C. Zhang, X. Shao, W. Lin, and H. Zhu. An effective hybrid teaching-learning-based optimization algorithm for permutation flow shop scheduling problem. Advances in Engineering Software, 77:35–47, 2014. [92] B. Yagmahan and M.M. Yenisey. Ant colony optimization for multi-objective flow shop scheduling problem. Computers and Industrial Engineering, 54(3):411–420, 2008. [93] K.-C. Ying and C.-J. Liao. An ant colony system for permutation flow-shop sequencing. Computers and Operations Research, 31(5):791–801, 2004. [94] K.-C. Ying and S.-W. Lin. A high-performing constructive heuristic for minimizing makespan in permutation flowshops. Journal of Industrial and Production Engineering, 30(6):355–362, 2013. [95] S.H. Zanakis, J.R. Evans, and A.A. Vazacopoulos. Heuristic methods and applications: A categorized survey. European Journal of Operational Research, 43(1):88–110, 1989. [96] C. Zhang, J. Ning, and D. Ouyang. A hybrid alternate two phases particle swarm optimization algorithm for flow shop scheduling problem. Computers and Industrial Engineering, 58(1):1–11, 2010. [97] C. Zhang and J. Sun. An alternate two phases particle swarm optimization algorithm for flow shop scheduling problem. Expert Systems with Applications, 36(3 PART 1):5162–5167, 2009. [98] C. Zhang, J. Sun, X. Zhu, and Q. Yang. An improved particle swarm optimization algorithm for flowshop scheduling problem. Information Processing Letters, 108(4):204–209, 2008. [99] J. Zhang, C. Zhang, and S. Liang. The circular discrete particle swarm optimization algorithm for flow shop scheduling problem. Expert Systems with Applications, 37(8):5827–5834, 2010. [100] L. Zhang and J. Wu. A PSO-based hybrid metaheuristic for permutation flowshop scheduling problems. The Scientific World Journal, 2014. [101] T. Zheng and M. Yamashiro. Solving flow shop scheduling problems by quantum differential evolutionary algorithm. International Journal of Advanced Manufacturing Technology, 49(5-8):643– 662, 2010. [102] G.I. Zobolas, C.D. Tarantilis, and G. Ioannou. Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm. Computers and Operations Research, 36(4):1249–1267, 2009. [103] G. Zäpfel, R. Braune, and M. Bögl. Metaheuristic Search Concepts. Springer, 2010. 36 View publication statsView publication stats