Iterated-greedy-based algorithms with beam search initialization for the permutation flowshop to minimize total tardiness

See discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/320665899 Iterated-greedy-based algorithms with beam search initialization for the permutation flowshop to minimise total tardiness ArticleinExpert Systems with Applications · October 2017 DOI: 10.1016/j.eswa.2017.10.050 CITATIONS 14 READS 142 3 authors, including: Some of the authors of this publication are also working on these related projects: Collaboration strategies in de centralized supply chains with partial information sharing View project Models and algorithms for the order scheduling problems considering setup times View project Victor Fernandez-Viagas Universidad de Sevilla 34 PUBLICATIONS401 CITATIONS SEE PROFILE Jose M. Framinan Universidad de Sevilla 188 PUBLICATIONS3,131 CITATIONS SEE PROFILE All content following this page was uploaded by Victor Fernandez-Viagas on 01 November 2017. The user has requested enhancement of the downloaded file. Iterated-greedy-based algorithms with beam search initialization for the permutation flowshop to minimise total tardiness∗ Victor Fernandez-Viagas1† , Jorge M. S. Valente2, Jose M. Framinan1 1Industrial Management, School of Engineering, University of Seville, Camino de los Descubrimientos s/n, 41092 Seville, Spain, {vfernandezviagas,framinan}@us.es 2LIAAD - INESC TEC, Faculdade de Economia, Universidade do Porto, Porto, Portugal, jv[email protected] November 1, 2017 Abstract The permutation flow shop scheduling problem is one of the most studied operations research related problems. Literally, hundreds of exact and approximate algorithms have been proposed to optimise several objective functions. In this paper we address the total tardiness criterion, which is aimed towards the satisfaction of customers in a make-to-order scenario. Although several approximate algorithms have been proposed for this problem in the literature, recent contributions for related problems suggest that there is room for improving the current available algorithms. Thus, our contribution is twofold: First, we propose a fast beam-search-based constructive heuristic that estimates the quality of partial sequences without a complete evaluation of their objective function. Second, using this constructive heuristic as initial solution, eight variations of an iterated-greedy-based algorithm are proposed. A comprehensive computational evaluation is performed to establish the efficiency of our proposals against the existing heuristics and metaheuristics for the problem. Keywords: Scheduling, Flowshop, Heuristics, PFSP, tardiness, beam search, iterated greedy algorithm, iterated local search ∗Preprint submitted to Expert Systems with Applications. http://dx.doi.org/10.1016/j.eswa.2017.10.050 †Corresponding author. Email: [email protected] 1 1 Introduction The flow shop is a common manufacturing layout in which a set of njobs has to be processed in a set of mmachines where each job follows the same route through the machines. For simplicity, the problem is denoted by permutation flow shop (PFSP in the following) when the same sequence of jobs is applied on each machine. The PFSP is one of the most studied optimization problems in Operations Research. Among the objectives studied in the literature (see e.g. Pan and Ruiz, 2013; Fernandez-Viagas and Framinan, 2014; Fernandez-Viagas et al., 2016a), the minimisation of the total tardiness is essential for manufacturing systems (Raman, 1995), since due dates play an important role in these systems (Panwalkar et al., 1982) and delays may increase costs and/or the dissatisfaction of customers (resulting in either a poor reputation, or even the loss of customer) (Sen and Gupta, 1984). According to the α|β|γnotation (see e.g. Pinedo, 1995), the PFSP to minimise total tardiness can be denoted as Fm|prmu|PTj. Since this problem is known to be NP-hard (Du and Leung, 1990), during the last years several approximate algorithms –heuristics and metaheuristics– have been proposed in the literature (see e.g. Vallada et al., 2008; Li et al., 2015; Karabulut, 2016). However, these proposals have not been compared against themselves, or the comparison has not been carried out under the same conditions, so the state-of-the-art regarding approximate algorithms for the problem remains unclear. Instead, these methods have been usually compared against either the genetic algorithm proposed by Vallada and Ruiz (2010), the Iterated Greedy (IG) algorithm by Ruiz and Stützle (2007), and/or the NEHedd by Kim (1993), which is the adaptation for the problem of the well-known NEH heuristic by Nawaz et al., 1983. The latter two are considered key methods in the flowshop scheduling literature since the noteworthy papers by Nawaz et al. (1983) and Ruiz and Stützle (2007), respectively. Regarding the NEHedd, it is probably the key constructive heuristic for the problem due to several reasons (Fernandez-Viagas and Framinan, 2015d): aside being an efficient heuristic for the problem, it is used to obtain an initial solution by the rest of efficient constructive or improvement heuristics, and by more than half of the efficient improvement heuristics or metaheuristics. Regarding IG, it remains the cornerstone of subsequent algorithms in the flowshop literature and can be considered as 2 the state-of-the-art algorithm for several scheduling problems (see e.g. Fernandez-Viagas and Framinan, 2015b and Dubois-Lacoste et al., 2017)1. Despite the preeminence of these two algorithms, recent advances in related scheduling problems have shown that they can be improved: On the one hand, some studies (see e.g. Dong et al., 2009 and Pan and Ruiz, 2014) have found better results by varying the destruction-construction phase in the IG for total flowtime minimisation, which is related to the problem under consideration (see Fernandez-Viagas and Framinan, 2015d). On the other hand, recent constructive heuristics based on a non-complete evaluation of the partial sequences have clearly outperformed the original NEH for other objective functions (see e.g. Fernandez-Viagas and Framinan, 2015c; Fernandez-Viagas et al., 2016a; Fernandez-Viagas and Framinan, 2017). To tackle the aforementioned issues, the contribution of this work is twofold: We first implement a beam search algorithm for the problem which constructs several partial sequences in parallel. The algorithm estimates the value of the objective function for each partial sequence based on specific variables of the problem. We then develop several iterated-greedy-based algorithms to improve the pool of sequences generated by the beam search algorithm. To explore the effect of the construction phase in the algorithm, we implement eight different methods based on insertions, exchanges, randomness and optimizations of partial solutions. We finally compare the proposals with the best performing algorithms in the literature in an exhaustive computational evaluation. The remainder of the paper is as follows: In Section 2 we formalise the problem and discuss its background. In Section 3 we propose the beam search and the iterated-greedy-based algorithms. These algorithms are compared with the state-of-the-art methods in Section 4. Finally, in Section 5 we discuss the main conclusions of the paper. 1IG is currently a state-of-the-art algorithm for makespan minimisation (Fm|prmu|Cmax). As stated by Fernandez-Viagas et al. (2017), the speed up proposed by Taillard (1990) is probably one of main reason of the good-performance of insertion phases -constructing jobs following a greedy method for that scheduling problemas compared to randomized ones. 3 2 Problem Statement and Background The problem under study can be set as follows: a set Nof njobs have to be processed in a flowshop composed of a set Mof mmachines. Each job j∈ {1, . . . , n}has a due date dj and a processing time pij on each machine i∈ {1, . . . , m}. Given a sequence of jobs Π := (π1, . . . , πr, . . . , πn)where r∈ {1, . . . , n}is an index of the position in a sequence, let Cij(Π) (abbreviated to Cij whenever it does not lead to confusion) be the completion time of job jon machine iaccording to sequence Π. Obviously, Cmj(Π) is the completion time of job jon the last machine, and Cmπn(Π) = Cmax is the maximum completion time or makespan of the sequence. The tardiness (earliness) of job jis defined as Tj= max{Cmj −dj,0}(Ej= max{dj−Cmj,0}). Analogously, total tardiness, whose minimisation is the goal of our problem, is defined as PTj= Pn j=1 max{Cmj −dj,0}, while total earliness is defined as PEj=Pn j=1 max{dj−Cmj,0}. Note that the completion times can be computed recursively as follows: Ciπj=max{Ci−1,πj, Ci,πj−1}+piπj(1) where C0πj=Ciπ0= 0. A number of approximate procedures have been proposed in the literature to provide good solutions for this problem in reasonable computation times. A review and evaluation of these algorithms prior to 2008 is given in Vallada et al. (2008). From this review, it turns out that the NEHedd proposed by Kim (1993), the ENS2 by Kim et al. (1996), and the simulated annealing algorithms by Hasija and Rajendran (2004) and Parthasarathy and Rajendran (1997) (denoted as HR and SAH, respectively) are the most promising algorithms for the problem. Using the same computer conditions, Framinan and Leisten (2008) propose a hybrid algorithm (denoted as HA) which outperforms both the HR and the SAH0(proposed by Parthasarathy and Rajendran, 1998)2. This algorithm combines the iterated greedy and the variable neighbourhood search algorithms using a partial (adjacent-pairwise-exchange) local search in its construction phase, as well as an insertion local search improvement. In addition, Framinan and Leisten (2008) have 2This SAH0algorithm was not included in the computational evaluation of Vallada et al. (2008) due to the resemblance of it with SAH. 4 also proposed a speed up mechanism to decrease the complexity of the evaluation3. Recently, Karabulut (2016) have found around 50% time saving when applying it to the NEH. In parallel to the contribution by Framinan and Leisten (2008), Vallada and Ruiz (2010) propose three genetic algorithms (GAPR, GAPR2, and GADV) that also outperform the HR and SAH in a fair comparison, and using a similar speed up mechanism for the problem. The best results were obtained by the GAPR version, although this algorithm was not compared to HA. Laterly, several contributions have outperformed the GAPR algorithm. First, Cura (2015) proposes an evolutionary algorithm (EA in the following), that outperforms both GAPR and SAH. The algorithm includes a mating procedure to diversify the solutions. Two local search methods with different neighbourhood sizes are employed, although the comparison is not performed using the same conditions, i.e. the algorithms used for comparison were not reimplemented. Secondly, several trajectory scheduling methods are proposed by Li et al. (2015) using six different composite heuristics (denoted as CHi) and three perturbation methods. Let us denote as TSMij the trajectory scheduling methods composed of composite heuristic CHiand perturbation method j. Among these methods, the best results are found by TSM63. On the one hand, under the same stopping criterion and the same computer conditions, TSM63 outperforms the three genetic algorithms by Vallada and Ruiz (2010), i.e. GAPR, GAPR2, and GADV. On the other hand, the proposed composite heuristics outperform the NEHedd but require additional CPU times. Regarding NEHedd, Fernandez-Viagas and Framinan (2015d) analyse the structure of the problem, finding that there are a high number of ties in the selection procedure of NEHdd. Eight tie-breaking mechanisms are then proposed and compared with the original one, resulting that each tie-breaking mechanism (with the exception of the random one) statistically outperforms NEHedd. The most promising tie-breaking mechanisms are NEHedd(TBIT1) and NEHedd(TBMS-Taillard, IT1)(these heuristics are denoted in the following as TBIT1 and TBTa, 3The speed up mechanism is a very common practice in the flowshop layout with permutation sequences. Taillard (1990) have proposed the first one for Fm|prmu|Cmax. Since then, several other mechanisms have been proposed for different constraints and/or objectives. Naderi and Ruiz (2010), RiosMercado and Bard (1998) and Fernandez-Viagas and Framinan (2015b) have successfully adapted them for the DF |prmu|Cmax,F m|sijk, prmu|Cmax and Fm|prmu|(Cmax/Tmax)problems, respectively. With some modifications and lesser decrease in CPU times, they have been also adapted for the Fm|prmu|PCj, Fm|prmu|PTj,Fm|prmu|PEj+PTjand Fm|block|PCjproblems by Li et al. (2009), Framinan and Leisten (2008), Fernandez-Viagas et al. (2016a) and Fernandez-Viagas et al. (2016b), respectively. 5 respectively). In addition, they also statistically improve GAPR when used as an initial solution instead of the traditional NEHedd. Recently, Karabulut (2016) propose KIG, an iterated greedy algorithm that incorporates a random local search method instead of the traditional insertion local search method. The search randomly performs insertion and exchanges using the speed up mechanism proposed by Framinan and Leisten (2008), until no more improvement is achieved in niterations. In addition, it uses a simple annealing-like acceptance criterion with a constant temperature based on the makespan and the due dates of the jobs. Although the authors do not compare their proposal with algorithms specifically developed for the problem, they compare it with the original iterated greedy algorithm proposed by Ruiz and Stützle (2007) –originally designed for the PFSP to minimise makespan–, which has been reimplemented for the problem under consideration. It is to note that such iterated greedy algorithm was found to be outperformed by GAPR for the problem under study. To summarise, several algorithms have been proposed in the literature to solve the problem under consideration. However, the new picture of the efficient metaheuristics for the problem remains unclear due to the following issues: 1. The most promising metaheuristics found by Vallada et al. (2008) have been outperformed by GAPR and HA, but there is no comparison among these two latter algorithms and, to the best of our knowledge, contributions after 2008 do not include HA in their comparisons. 2. There is no computational comparison among the recent iterative algorithms proposed in the literature, i.e. EA, TSM63, and KIG. 3. Some metaheuristics are tested either under different computer conditions or versus nonstate-of-the-art metaheuristics (see e.g. Cura, 2015; Karabulut, 2016). In this paper, in Section 3 we first propose both a beam search algorithm with a fixed stopping criterion, and a set of eight different iterated-greedy-based algorithms varying their construction phase. In addition, we perform a comprehensive computational evaluation of the heuristics and metaheuristics in Section 4. By doing so, we establish the set of efficient algorithms for the problem. 6 3 Proposed algorithms: beam search and iteratedgreedy-based algorithms In this section, we propose several approximate procedures to solve the problem. The first proposal is a population-based constructive heuristic, which constructs several partial sequences in parallel, appending jobs, one by one, at the end of the sequences (see Subsection 3.1). Secondly, we propose several iterative improvement algorithms based on a single solution. Using the previous heuristic as initial solution, these algorithms iteratively search for the local optimum of a sequence obtained by a destruction-construction-based phase (see Subsection 3.2). Note that the division between heuristics and metaheuristics is unclear in the literature and several classifications have been proposed (see e.g. Zanakis et al., 1989; Zäpfel et al., 2010). In this paper, we adopt the same definition as in Ruiz and Maroto (2005) and Fernandez-Viagas et al. (2017), where metaheuristics are defined as iterative improvement algorithms with stopping criteria depending on CPU time or number of iterations. In contrast, heuristics naturally stop when their steps are finished. 3.1 Beam search algorithm In this subsection we present a beam search algorithm, denoted by BS(γ), with an advance priority evaluation function. Similarly to the B&B algorithm, this approximate procedure constructs a search tree, where each node is formed by a partial sequence and the child nodes are obtained by adding one of the unscheduled jobs at the end of the parent node. However, only the most γpromising nodes (denoted as beam width in the following) are kept for the next iteration. Beam search has been successfully applied to several scheduling problems in the literature (see e.g. Valente and Alves, 2005, 2008). Traditionally, two different functions have been applied to evaluate the nodes (Valente, 2010): •Priority evaluation function. The node is evaluated by estimating the influence of the last job in the partial sequence. This evaluation of just one job in the node (omitting the influence of the other jobs) implies both that computing this function requires a low 7 complexity order and that it is node-dependent, i.e. only children from the same parent node can be compared. •Total cost evaluation function. The final objective function value to be achieved for this node is estimated taking into consideration all unscheduled jobs. Obviously, this function is node-independent as complete sequences are estimated. In addition, its complexity increases significantly. Recently, Fernandez-Viagas et al. (2016b) and Fernandez-Viagas and Framinan (2017) have achieved excellent results using a node-independent priority evaluation function. The idea is to assign to each node a “genetic” code which keeps the historical behaviour of that node. By means of both this code and the influence of the last element, child nodes from different parents can be compared. This approach is applied in our proposal. The proposed beam search algorithm is composed of several nodes in ndifferent levels. Let us denote by Sk lthe partial sequence of the lth node in iteration k, with l∈[1, γ]. Each node is then formed by a partial sequence Sk l,Sk l:= (sk 1,l, ..., sk k,l), of kjobs, and by a set Uk l(with Uk l:= {uk 1,l, ..., uk n−k,l}) of n−kunscheduled jobs. Whenever it does not lead to confusion, let us also denote that node by Sk l. For each iteration k,n−kchild nodes are created from each partial sequence Sk lby adding one job from set Uk lat the end of the sequence. The best γchild nodes are selected to be the partial sequences of the nodes for the next iteration, i.e. Sk+1 l, ∀l∈ {1, ..., γ}. More specifically, the steps of the proposed algorithm are as follows: Step 1 Initialization Step 2 While k= 2, . . . , n −1, repeat: Step 2.1 Branching Step 2.2 Node evaluation Step 2.3 Node selection Step 3 Final evaluation To clarify both the branching and candidate selection phases, a simple example with five jobs and γ= 2, i.e. BS(2), is shown in Figure 1. 8 4. Greedy general swap (IAGGS). In this procedure, a job is randomly chosen from Πiand exchanged with each job of the sequence. Sequence Πiis replaced by the exchange yielding the lowest total tardiness. The procedure is repeated dtimes for ddifferent jobs. 5. Random adjacent swap (IARAS). This procedure randomly chooses a job and exchanges it with the next job of the sequence. The procedure is repeated dtimes. 6. Greedy insertion + Partial adjacent-swap-based local search method (IAGI_ALS). This procedure is based on Framinan and Leisten (2008). Thereby, each job removed πr i,∀i∈ {1, . . . , d}is inserted in the position of Πdyielding the lowest total tardiness (denoted as position b), as in the greedy insertion procedure. After that, an adjacent pairwise exchange is performed for the jobs between the last position of the partial sequence and position b+ 1. 7. Insertion-based Local search + Greedy insertion (IAILS_GI). This procedure adapts the procedure of destruction and construction proposed by Dubois-Lacoste et al. (2017). The method performs an insertion-based local search on the partial sequence Πd, i.e. each job of the sequence is removed and inserted in the best position. The procedure is repeated until there is no improvement in a complete iteration. The best sequence found by the algorithm replaces Πd. After that, the traditional construction phase (i.e. greedy insertion) is applied. 8. Greedy insertion + Local search insertion(IAGI_ILS). This procedure is an adaptation of the method proposed by Pan and Ruiz (2014) and Pan et al. (2017). Similarly as IAGI_ALS, each removed job πr i,∀i∈ {1, . . . , d}is inserted in the position bof Πdyielding the lowest total tardiness. After that, jobs in positions b−1and b+ 1 are removed and reinserted in the position yielding the lowest total tardiness. After the destruction-construction procedure, a local optimum of sequence Πcis obtained in the local search phase. This phase iteratively removes each job in sequence Πcand inserts it in the position with the lowest vaue of the objective function. The phase is stopped after a complete iteration without any improvement. Finally, the simulated annealing-like acceptance 15 criterion proposed by Karabulut (2016) is applied due to its excellent performance. This simple criterion is a variation of the proposal of Ruiz and Stützle (2007) for Fm|prmu|Cmax, which has been successfully applied to other several objectives and/or scheduling problems (see e.g. Fernandez-Viagas and Framinan, 2015a,b; Ribas et al., 2017). The criterion uses a constant Temperature which depends on parameter Tof the algorithm: Temperature =T·Pn j=1(LBCmax −dj) n·10 (10) where LBCmax is the lower bound of the makespan following the procedure established by Taillard (1993). The pseudo-code of the proposed metaheuristic is shown in Figure 3. Note that BS is used as the initial solution of the proposed iterated-greedy-based algorithms. 16 Procedure IAX(d, γ, T) //Initial solution Π := BS(γ, a, b, c, e); //Best solution Πb:= Π; while stopping criterion is not reached do Πi:= Π; //Destruction phase Πd:= randomly remove djobs from Πiand insert it in Πr; //Construction phase Πc:= ConstructionPhase(Πd,Πr); //Local search phase Πl:= LS(Πc); //Simulated annealing criterion if PTj(Πl)<PTj(Π) then Π=Πl; if PTj(Πl)<PTj(Πb)then Πb= Πl; end else if random ≤exp{−(Cmax(πl)−Cmax(π))/Temperature}then Π=Πl; end end end Figure 3: Proposed iterated-greedy-based algorithms 17 4 Computational Experience In this section we compare the state-of-the-art algorithms against our proposals. Prior to performing this computational evaluation, we establish the conditions adopted to achieve a fair comparison. Firstly, in Subsection 4.1 we present the sets of instances generated. Secondly, the measures to evaluate both the quality of the solutions and the computational requirements of each algorithm are shown in Subsection 4.2. Regarding our proposals, two full experimental parameter tunings are described in Subsection 4.3. Next, in Subsection 4.4, the state-of-the-art algorithms, which are fully re-implemented, are shown. We compare them against our proposals by carrying out two different computational evaluations for heuristics and metaheuristics, see Subsections 4.5 and 4.6, respectively. 4.1 Sets of instances In this paper, two benchmark testbeds, denoted as β1and β2, are generated for the experiments of our study. β1is used for the calibration of the parameters of the proposed algorithms. The computational evaluations of both heuristics and metaheuristics are carried out on benchmark β2. By doing so, we avoid an over calibration of the parameters of our algorithms in the benchmark of comparison. •Benchmark β1: This benchmark is generated by the procedure described in Vallada and Ruiz (2010). It contains 108 different sizes of the problem varying the parameters n,m,Tand R. Ten instances are generated for each combination of parameters n∈ {50,150,250,350},m∈ {10,30,50},T∈ {0.2,0.4,0.6}, and R∈ {0.2, .0.6,1.0}, i.e. a total of 1,080 instances are generated in this benchmark. Tand Rare parameters to generate different types of due dates for each size of the problem (see Potts and Van Wassenhove, 1982). They generate the processing times and the due dates with a uniform distribution [1,99] and [P·(1 −T−R/2, P ·(1 −T+R/2], respectively, where Pis the lower bound for the makespan proposed in Taillard (1993). •Benchmark β2: This benchmark is composed of the 540 instances of Vallada et al. (2008). It contains 108 combinations of parameters n∈ {50,150,250,350},m∈ {10,30,50},T∈ 18 {0.2,0.4,0.6}, and R∈ {0.2, .0.6,1.0}, with five instances for each combination. Processing times and due dates are generated following the same distributions than in benchmark β1. 4.2 Performance indicators In our study, two computational evaluations are carried out to compare the most promising heuristics and metaheuristics. As a result, 23 algorithms are tested. To conduct a fair comparison among them, the algorithms are compared under the same conditions. More specifically, the following aspects are considered: •We use the same computer (an Intel Core i7-3770 with 3.4 GHz, 16 GB RAM, and with Microsoft Windows 8.1 64 bit operating system). •We re-code each algorithm using the same programming language (C# under Visual Studio 2013). •We use the same computational skills, libraries and common functions. •We use the same stopping criteria for each metaheuristic. In addition, each algorithm typically requires a different CPU time and obtains a different solution. In order to compare both the quality of the solutions and the computational efforts of the implemented algorithms, the indicators for comparison have to be established. On the one hand, heuristics are compared using the Average Relative Deviation Index (denoted as ARDI1h for heuristic h) and the Average Relative Percentage computation Time (denoted as ARPThfor heuristic hfollowing the recommendation established by Fernandez-Viagas and Framinan (2015c) and Fernandez-Viagas et al. (2017) (see Equations 11 and 12, respectively). On the other hand, metaheuristics are only compared using the ARDI1has the same CPU times are used. ARDI1h= I X i=1 RDI1ih I,∀h= 1, . . . , H (11) ARPTh= 1 + I X i=1 RPTih I,∀h= 1, . . . , H (12) 19 Let Ibe the number of instances, and Hbe the number of considered heuristics. The Relative Deviation Index of heuristic hin instance i,RDI1ih, and the Relative Percentage computation Time, RPT1ih, are defined by the following expressions, respectively: RDI1ih =OFih −Besti Worsti−Besti ,∀i= 1, . . . , I, h = 1, . . . , H (13) RPTih =Tih −ACTi ACTi ,∀i= 1, . . . , I, h = 1, . . . , H (14) where Bestiand Worstiare the best and worst known solution for one run in instance i5, respectively. Let Tih and OFih be the CPU time and the objective function value obtained by heuristic hin iteration i, respectively. Finally, ACTiis the average CPU time required by all compared algorithms in iteration i, which is defined by: ACTi=PH h=1 Tih H,∀i= 1, . . . , I (15) Regarding the experimental parameter tuning on benchmark β1, we apply a different indicator of the quality of the solution. More specifically, we used ARDI2, which is a small modification of ARDI1: ARDI2h= I X i=1 RDI2ih I,∀h= 1, . . . , H (16) RDI2ih =OFih −Best0 i Worst0 i−Best0 i ,∀i= 1, . . . , I, h = 1, . . . , H (17) where Best0 iand Worst0 iare the best and worst total tardiness among the algorithms tested in the calibration, respectively. 5These values are presented as on-line materials, which are taken from http://soa.iti.es/probleminstances. 20 4.3 Experimental parameter tuning In this subsection, two full factorial design of experiments are presented to determine the best combinations of parameters for the proposed algorithms. Both experiments are evaluated on benchmark β1. Regarding BS, firstly four parameters (a,b,cand e) have been proposed to balance the contributions in the evaluation of partial sequences. In addition, parameter γ(beam width) directly influences its complexity, O(max{γ·n2·m, γ2·n2}), and consequently the CPU time of the proposed beam search. For each value of γ, there is a trade-off between the quality of solutions and the computational effort. Thus, this parameter is removed of this experimental parameter tuning (see e.g. Liu and Reeves, 2001; Fernandez-Viagas and Framinan, 2015c; Fernandez-Viagas et al., 2016b for similar approaches) to avoid a calibration of each parameter γ, and its value is set to 15. So the following levels of the parameters are tested: •a∈ {0,0.25,0.5,0.75,1,1.25} •b∈ {0,0.15,0.3} •c∈ {0.25,0.5,0.75,1,1.25,1.5} •e∈ {2,3,4,5} Regarding the proposed iterated-greedy-based algorithms, they use three parameters: d,γ, and T. Firstly, we use in this test d∈ {4,5,6}for the number of destructed jobs. Regarding the parameter γ, the CPU time of IAidepends on its stopping criterion instead of γ, since BS is applied as its initial solution. So, different values of γonly perturbs its objective function value, i.e. we may now measure the influence of γin the quality of the solutions of the metaheuristics without altering its CPU time. In this calibration test, we use the following levels, γ∈ {2, n/10, n/m, 10,15, n}. For parameter T, we use the best value found by Karabulut (2016), i.e. T= 1.0, since its influence has not been found to be statistically significant in several previous studies (see e.g. Pan and Ruiz, 2014; Fernandez-Viagas and Framinan, 2015a). The calibration test is carried out for IARI and using n·(m/2) ·60 ms. In this paper, we carry out two non-parametric Kruskal-Wallis analyses to determine the statistical differences between the levels of the parameters. Note that the normality and ho21 Parameter aParameter bParameter cParameter eParameter dParameter γ Level ARDI2 Level ARDI2 Level ARDI2 Level ARDI2 Level ARDI2 Level ARDI2 0.00 27.68 0.00 27.59 0.25 43.23 2 30.98 4 36.75 2 54.36 0.25 28.37 0.15 26.22 0.50 30.65 3 29.17 5 39.84 n/10 32.22 0.50 28.27 0.30 34.29 0.75 26.08 4 28.61 6 42.82 n/m 42.85 0.75 29.33 1.00 24.93 5 28.72 10 38.50 1.00 30.70 1.25 24.67 15 35.55 1.25 32.14 1.50 27.05 n35.33 Table 1: Average results of RDI2 for each tested parameter. moscedasticity assumptions were not satisfied. In addition, the indicator ARDI2has been used to evaluate the quality of the solutions. The results show that there are statistically significant differences between the level of each parameter (a,b,c,e,d, and γ), since each p-value obtained in the tests is 0.000. The best combination of parameters has been found for a= 0,b= 0.15, c= 1.25,e= 4,d= 4, and γ=n/10. These values of the parameters are used in the next sections. The average results for each level of the parameters, in terms of ARDI2, are shown in Table 1. 4.4 Implemented algorithms The proposed algorithms, BS and IAi, are compared against the state-of-the-art algorithms in two different computational evaluations. Following the discussion in Section 2, the following heuristics and metaheuristics are implemented in this study: •Heuristics –NEHedd proposed by Kim (1993). –TBIT1 and TBTa proposed by Fernandez-Viagas and Framinan (2015d). –CHi∀i= 1,...,6proposed by Li et al. (2015). –The BS(γ) algorithms proposed in Subsection 3.1, with γ∈ {2,5, n/10,15, n/m, n}. •Metaheuristics –The hybrid algorithm HA proposed by Framinan and Leisten (2008). 22 –The genetic algorithm GAPR proposed by Vallada and Ruiz (2010). –The evolutionary algorithm EA proposed by Cura (2015). –The trajectory scheduling method TSM63 proposed by Li et al. (2015). –The iterated greedy algorithm KIG proposed by Karabulut (2016). –The IAi(with i∈ {RI,GI,RGS,GGS,RAS,GI_ALS,ILS_GI,GI_ILS}) algorithms proposed in Subsection 3.2. Note that the speed up procedure, proposed by Framinan and Leisten (2008), is applied in each insertion and exchange phase of all the implemented algorithms. 4.5 Heuristics The computational results of the constructive heuristics are shown in Table 2, and in Figure 4. Table 2 shows the results of the ARDI1hfor each heuristic hgrouped by nand m. The average results in terms of ACTh,ARPTh, and ARDI1hare shown in the last three rows. The dominance of each heuristic can be graphically seen in Figure 4 (X-axis and Y-axis indicate the ARPThand ARDI1hof each heuristic h). The results show that the BS(2), BS(5), BS(10), BS(n/10), and BS(15) algorithms are efficient for the problem (see red line in Figure 4). To statistically support it (i.e. to discard that they are not statistically better), we perform a non-parametric Wilcoxon signed-rank test for each one of the following hypotheses: BS(5)=BS(n/m); BS(15)=NEHedd; BS(15)=TBTa; and BS(15)=TBIT1, where each efficient beam search algorithm has been compared against the closest heuristic. The p-value found for each one was 0.000 rejecting each one of the previous hypotheses. In addition, several of the proposed beam search algorithms, BS(5), BS(10), BS(n/10), and BS(15), clearly outpeform the NEHedd and TBIT1 heuristics both in terms of ARDI1and ARPT (or ACT). Note that, as stated in Section 1, both heuristics are the key heuristics for the problem under consideration (the NEHedd heuristic is used as initial solution for most of the algorithms developed for the problem). The excellent performance of the proposed beam search heuristic probably lies in the reduction of the complexity of the evaluation. The complexity of 23 evaluating a full sequence in the Fm|prmu|PTjproblem is O(nm), while in the proposed algorithm it is only O(m)since the jobs are inserted, one by one, at the end of a partial sequence. By reducing the complexity of this evaluation, the algorithm can evaluate much more sequences in the same CPU time. Regarding the six proposals by Li et al. (2015), which also use the NEHedd as initial solution, they perform better than each other one in terms of quality of the solution (ARDI1) but requiring much higher CPU times. nxmNEHedd TBTa TBIT1 CH1 CH2 CH3 CH4 CH5 CH6 BS(2) BS(5) BS(10) BS(15) BS(n/10) BS(n/m) BS(n) 50 x 10 17.46 14.53 13.72 6.26 7.72 5.30 5.35 5.88 5.46 15.29 11.20 10.70 10.22 11.20 11.20 16.52 50 x 30 19.79 18.68 18.61 11.12 14.43 9.84 10.17 10.51 10.40 24.26 19.11 15.90 15.95 19.11 30.13 25.09 50 x 50 18.17 17.97 17.57 10.94 14.34 10.66 10.99 10.61 10.75 22.96 18.47 16.14 15.78 18.47 29.15 26.86 150 x 10 13.80 10.69 9.91 3.67 4.14 2.86 2.87 3.04 2.82 8.89 6.17 5.22 5.58 5.58 5.58 8.96 150 x 30 20.70 17.02 15.81 8.21 10.35 7.51 7.20 8.04 7.15 18.93 11.23 9.22 8.50 8.50 11.23 12.55 150 x 50 22.04 19.64 18.57 9.62 12.57 9.02 8.83 9.15 8.75 23.93 15.90 12.56 10.70 10.70 19.74 16.98 250 x 10 10.06 7.26 6.70 2.23 1.97 1.28 1.08 1.81 1.37 6.51 4.81 4.11 4.14 4.14 4.14 7.33 250 x 30 17.81 13.29 11.62 4.72 6.10 4.38 4.05 4.37 4.17 13.33 8.02 5.43 4.48 3.75 6.76 6.80 250 x 50 20.21 15.90 13.96 6.20 8.76 5.84 5.67 5.95 6.02 19.28 11.76 8.68 6.97 5.36 11.76 8.86 350 x 10 9.01 6.65 6.14 1.98 1.12 0.80 0.67 1.06 0.69 4.81 2.76 2.45 2.31 2.49 2.49 4.91 350 x 30 15.74 11.40 9.84 3.34 3.95 2.65 2.38 3.09 2.49 10.26 5.07 3.27 2.52 1.58 3.04 3.82 350 x 50 17.38 13.11 11.10 3.99 5.78 3.50 3.53 3.83 3.61 15.68 9.52 6.27 5.43 3.18 8.31 4.84 ARDI1h16.85 13.84 12.80 6.02 7.60 5.30 5.23 5.61 5.31 15.34 10.34 8.33 7.71 7.84 11.96 11.96 ACTh1.56 1.53 1.56 119.94 10.01 66.74 63.78 139.59 88.35 0.05 0.12 0.26 0.40 0.84 0.27 17.16 ARP Th0.13 0.13 0.13 2.93 0.41 2.13 2.07 3.63 2.51 0.01 0.03 0.06 0.10 0.08 0.04 1.60 Table 2: ARDI1hfor each constructive heuristics grouped by the number of jobs and machines in each factory. Last three files represent the average results of ARDI1h,ACTh, and ARPThfor constructive heuristics. 24 permutation flowshops. Computers and Industrial Engineering, 98:300–307. Kim, Y.-D. (1993). Heuristics for flowshop scheduling problems minimizing mean tardiness. Journal of the Operational Research Society, 44(1):19–28. Kim, Y.-D., Lim, H.-G., and Park, M.-W. (1996). Search heuristics for a flowshop scheduling problem in a printed circuit board assembly process. European Journal of Operational Research, 91(1):124–143. Li, X., Chen, L., Xu, H., and Gupta, J. (2015). Trajectory scheduling methods for minimizing total tardiness in a flowshop. Operations Research Perspectives, 2:13–23. Li, X., Wang, Q., and Wu, C. (2009). Efficient composite heuristics for total flowtime minimization in permutation flow shops. OMEGA, The International Journal of Management Science, 37(1):155–164. Liu, J. and Reeves, C. (2001). Constructive and composite heuristic solutions to the P|| Pci scheduling problem. European Journal of Operational Research, 132:439–452. Naderi, B. and Ruiz, R. (2010). The distributed permutation flowshop scheduling problem. Computers & Operations Research, 37(4):754–768. Nawaz, M., Enscore Jr., E., and Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. OMEGA, The International Journal of Management Science, 11(1):91–95. Pan, Q.-K., Gao, L., Li, X.-Y., and Gao, K.-Z. (2017). Effective metaheuristics for scheduling a hybrid flowshop with sequence-dependent setup times. Applied Mathematics and Computation, 303:89–112. Pan, Q.-K. and Ruiz, R. (2013). A comprehensive review and evaluation of permutation flowshop heuristics to minimize flowtime. Computers & Operations Research, 40(1):117–128. Pan, Q.-K. and Ruiz, R. (2014). An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem. Omega (United Kingdom), 44:41–50. Pan, Q.-K., Tasgetiren, M., and Liang, Y.-C. (2008). A discrete differential evolution algorithm for the permutation flowshop scheduling problem. Computers and Industrial Engineering, 55(4):795–816. Panwalkar, S., Smith, M., and Seidmann, A. (1982). Common due date assignment to minimize total penalty for the one machine scheduling problem. Operations Research, 30(2):391–399. Parthasarathy, S. and Rajendran, C. (1997). A simulated annealing heuristic for scheduling to minimize mean weighted tardiness in a flowshop with sequence-dependent setup times of jobs-a case study. Production Planning and Control, 8(5):475–483. Parthasarathy, S. and Rajendran, C. (1998). Scheduling to minimize mean tardiness and weighted mean tardiness in flowshop and flowline-based manufacturing cell. Computers and Industrial Engineering, 34(2-4):531–546. Pinedo, M. (1995). Scheduling: Theory, Algorithms and Systems. Prentice Hall. Potts, C. and Van Wassenhove, L. (1982). A decomposition algorithm for the single machine total tardiness problem. Operations Research Letters, 1(5):177–181. Rad, S. F., Ruiz, R., and Boroojerdian, N. (2009). New high performing heuristics for minimizing makespan in permutation flowshops. OMEGA, The International Journal of Management Science, 37(2):331–345. 31 Raman, N. (1995). Minimum tardiness scheduling in flow shops: Construction and evaluation of alternative solution approaches. Journal of Operations Management, 12(2):131–151. Ribas, I., Companys, R., and Tort-Martorell, X. (2017). Efficient heuristics for the parallel blocking flow shop scheduling problem. Expert Systems with Applications, 74:41–54. Rios-Mercado, R. and Bard, J. (1998). Heuristics for the flow line problem with setup costs. European Journal of Operational Research, 110(1):76–98. Ruiz, R. and Maroto, C. (2005). A comprehensive review and evaluation of permutation flowshop heuristics. European Journal of Operational Research, 165(2):479–494. Ruiz, R. and Stützle, T. (2007). A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 177(3):2033– 2049. Sen, T. and Gupta, S. (1984). A state-of-art survey of static scheduling research involving due dates. OMEGA, The International Journal of Management Science, 12(1):63–76. Taillard, E. (1990). Some efficient heuristic methods for the flow shop sequencing problem. European Journal of Operational Research, 47(1):65–74. Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2):278–285. Valente, J. (2010). Beam search heuristics for quadratic earliness and tardiness scheduling. Journal of the Operational Research Society, 61(4):620–631. Valente, J. and Alves, R. (2005). Filtered and recovering beam search algorithms for the early/tardy scheduling problem with no idle time. Computers and Industrial Engineering, 48(2):363–375. Valente, J. and Alves, R. (2008). Beam search algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setups. Computers and Operations Research, 35(7):2388–2405. Vallada, E. and Ruiz, R. (2010). Genetic algorithms with path relinking for the minimum tardiness permutation flowshop problem. OMEGA, The International Journal of Management Science, 38(1-2):57–67. Vallada, E., Ruiz, R., and Minella, G. (2008). Minimising total tardiness in the m-machine flowshop problem: A review and evaluation of heuristics and metaheuristics. Computers & Operations Research, 35(4):1350–1373. Zanakis, S., Evans, J., and Vazacopoulos, A. (1989). Heuristic methods and applications: A categorized survey. European Journal of Operational Research, 43(1):88–110. Zäpfel, G., Braune, R., and Bögl, M. (2010). Metaheuristic Search Concepts. Springer. 32 View publication statsView publication stats