Efficient constructive and composite heuristics for the Permutation Flowshop to minimise total earliness and tardiness

Ecient constructive and composite heuristics for the Permutation Flowshop to minimise total earliness and tardiness ∗ Victor Fernandez-Viagas 1 , Manuel Dios 1 , Jose M. Framinan 1† 1 Industrial Management, School of Engineering, University of Seville, Camino de los Descubrimientos s/n, 41092 Seville, Spain, {vfernandezviagas,mdios,framinan}@us.es May 19, 2016 Abstract In this paper we address the problem of scheduling jobs in a permutation owshop with a just-in-time objective, i.e. the minimization of the sum of total tardiness and total earliness. Since the problem is NP-hard, there are several approximate procedures available for the problem, although their performance largely depends on the due dates of the specic instance to be solved. After an in-depth analysis of the problem, dierent cases or sub-problems are identied and, by incorporating this knowledge, four heuristics are proposed: a fast constructive heuristic, and three dierent local search procedures that use the proposed constructive heuristic as initial solution. The proposed heuristics have been compared on an extensive set of instances with the best-so-far heuristic for the problem, as well as with adaptations of ecient heuristics for similar scheduling problems. The computational results show the excellent performance of the proposed algorithms. Finally, the positive impact of the ecient heuristics is evaluated by including them as seed sequences for one of the best metaheuristic for the problem. Keywords: Scheduling, Flowshop, Heuristics, PFSP, earliness, tardiness ∗ Preprint submitted to Computers & Operations Research. http://dx.doi.org/10.1016/j.cor.2016.05.006 † Corresponding author. Tel.: +34-954487214; fax: +34-954487329. 1 1 Introduction The owshop is a common manufacturing layout of a shop (Storer et al., 1992) in which a set of machines are visited by a number of jobs following each one the same route. The owshop scheduling problem deals with establishing the sequence of jobs before each machine in the shop. If the sequence of jobs before each machine is dierent, extensive use of manpower or advance machines would be needed to reorder the jobs between each pair of machines. To avoid this, the most common simplication of the problem is the so-called Permutation Flowshop Scheduling Problem (denoted as PFSP) where the sequence of jobs is the same for all machines. The PFSP is one of the most studied Operations Research problems in the literature (see e.g. reviews in Reza Hejazi and Saghaan, 2005, Framinan et al., 2004 and Ruiz and Maroto, 2005). Among the goals usually employed for this optimisation problem, the most commonly used are the minimisation of makespan (see e.g. Pan et al., 2008, Nawaz et al., 1983 and Fernandez-Viagas and Framinan, 2014), the minimisation of total completion time (see e.g. Pan and Ruiz, 2013, Fernandez-Viagas and Framinan, 2015c and Dong et al., 2013) and the minimisation of total tardiness (see e.g. Vallada et al., 2008, Framinan and Leisten, 2008 and Fernandez-Viagas and Framinan, 2015d). The rst two objectives are related to both a balanced use of the machines and the fast processing of the jobs, whereas total tardiness focuses on customers' satisfaction. None of them ts into a just-in-time philosophy where both the excess of inventory in the shop and the delays on the due dates should be avoided, due to the fact that just-in-time approaches aim to reduce the following aspects (Vollman et al., 1997): • the complexity of detailed material planning, • the need for shop-oor control, • the work-in-process and nal inventories, and • the transactions associated with shop-oor and purchasing systems. Given the acceptance of just-in-time systems in practice, there is a growing interest in the last decades in analysing scheduling problems where both earliness and tardiness are penalised (see e.g. reviews Baker and Scudder, 1990, Lau and Werner, 2004, Józefowska, 2007 2 and Shabtay and Steiner, 2012). This type of problems is collectively known as E/T problems. More specically, the problem under consideration is the PFSP to minimise total earliness and tardiness, which is denoted as Fm|prmu|∑Ej+∑Tj according to the notation in e.g. Pinedo, 1995. Furthermore, insertion of idle time is not allowed, which represents a common assumption in the literature due to its undesirable eects in certain production environments (see e.g. Józefowska, 2007 and Schaller and Valente, 2013). Some exact approaches and approximate algorithms have been proposed in the literature for the problem under study. However, both the NP-hard nature of the problem (see M'Hallah, 2014) and the huge computation times required by the optimal approaches even for small instances (not more than 20 jobs) justify the need to develop fast approximate algorithms. Thereby, several algorithms have been proposed for the problem, such as those by Zegordi et al. (1995) and by M'Hallah (2014). In this paper, four new ecient heuristics (one constructive heuristic and three composite heuristics) are proposed. These heuristics incorporate several properties and a speed up procedure in order to reduce and accelerate the search space of the heuristics. The subsequent computational experience shows that the proposed heuristics outperform the best-so-far heuristics for the problem, as well as adaptations of other state-of-the-art heuristics for related problems. The rest of the paper is organised as follows. The background of the problem is discussed in Section 2. In Section 3, the problem under study is described and some properties are established. The proposed algorithms are explained in Section 4. A speed up procedure for the insertion phase of the heuristics as well as a complete comparison among the implemented heuristics is performed in Section 5. Additionally, the inuence of using the heuristics as seed sequences in the best so-far metaheuristic (ILS) is discussed. Finally, in Section 6, conclusions are presented. 2 Literature Review As explained in Section 1, there are several contributions to our problem. Since the heuristics proposed in Section 4 use a speed-up procedure and are based on particular properties of the instance depending on the its due dates, the literature review is divided in the following items: • Procedures for E/T problems on a permutation owshop where idle time cannot be inserted. 3 • Identication of similar instances of the scheduling problem depending on their due dates. • Speed-up procedures for related PFSP. Regarding owshop scheduling problems with E/T objective without insertion of idle times, Moslehi et al. (2009) propose an optimal algorithm for the PFSP with two machines to minimise the sum of maximum earliness and tardiness. Dierent branch-and-bound algorithms are developed by Madhushini et al. (2009) for several multi-objective functions including total earliness and tardiness. Zegordi et al. (1995) was rst in proposing an approximate algorithm (a simulated annealing algorithm) to solve the PFSP to minimise the sum of weighted earliness and tardiness. Schaller and Valente (2013) propose a genetic algorithm (GA) that outperforms several metaheuristics for related problems, also yielding favourable results regarding the CPU times when compared to the algorithm proposed by Zegordi et al. (1995). Finally, M'Hallah (2014) proposes an Iterated Local Search (ILS) where a variable neighborhood descent is iteratively repeated after a perturbation mechanism. This algorithm is shown to yield better results than the GA. It is worth noting that both the GA and the ILS algorithms use the NEHedd (originally proposed for the Fm|prmu|∑Tj by Kim, 1993) and the Earliest Due Date or EDD rule respectively, which are either very simple seed sequences or simple adaptations from another research problems. The NEHedd is an adaptation of the NEH heuristic, originally proposed by Nawaz et al. (1983) for the PFSP to minimise makespan. The main steps of the NEH are: 1. An initial order vector, ΠIO := (πIO 1, . . . πIO n) , is formed by sorting the jobs according to a given order. In the original formulation for makespan minimisation, jobs are sorted in non-increasing order of the sum of their processing times. If jobs are ordered according to dierent criteria such as the EDD rule, or in ascending order of the sum of their processing times, the algorithm is denoted NEHedd or NEH-owtime, respectively. 2. A partial sequence, Π1 , is constructed with the rst job of the initial order, i.e. Π1= (π1 1) = (πIO 1) . 3. For k= 2 to k=n the following procedure is repeated: Job πIO k is inserted in each position of Πk−1 ( k positions are tested) and the corresponding objective function value is evaluated. 4 Then, the πIO k job is inserted in the partial sequence Πk−1 in the position with the lowest objective function value, denoted as l , Πk= (πk−1 1, . . . πk−1 l−1, πIO k, πk−1 l, . . . πk−1 k−1 ). Regarding the characterization of the problem depending on the due dates of the instance, Bagchi et al. (1986) have divided the single-machine E/T problem with common due date in two dierent single-machine problems depending on the common due date. Chandra et al. (2009) have extended the argumentation for the PFSP with common due dates and classify the problem into three dierent cases. Fernandez-Viagas and Framinan (2015b) have divided the Fm|prmu|∑Tj with dierent due dates for each job in four areas depending on the means and variances of the due dates, each area representing a dierent optimization problem. Finally, due to the NP-hard nature of PFSP, researchers have substantially improved their results by using speed-up procedures. The most well-known of these procedures is the speed-up algorithm for the NEH developed by Taillard (1990), employed for the FPSP with makespan objective. Using this speed-up procedure, the complexity of the insertion step decreases an order of n (i.e. from n2·m to n·m ) and therefore, the complexity of the NEH decreases from O(n3m) to O(n2m) . This speed-up procedure has been successfully adapted to similar scheduling problems involving makespan minimisation (see e.g. Naderi and Ruiz, 2010, Fernandez-Viagas and Framinan, 2015a, Rios-Mercado and Bard, 1998 and Fernandez-Viagas and Framinan, 2015b), although it cannot be directly applied for other objectives in the PFSP since it computes the completion time of the last job in the last machine (i.e. makespan), but not the completion time of each job. Nevertheless, Li et al. (2009) take advantages of the invariance of the completion times of jobs prior to the insertion position for the PFSP to minimise owtime,so saving between 30-50% of CPU time are achieved. A similar procedure is also proposed by Vallada and Ruiz (2010) for the Fm|prmu|∑Tj . This procedure can be directly applied for the problem under consideration and therefore is introduced in each insertion mechanism of the algorithms implemented in this paper. 5 3 Analysis of the problem The problem under consideration can be stated as follows: n jobs have to be scheduled in a owshop composed of m machines. Each job j has a processing time on each machine denoted as tij , and a due date dj . Given a sequence of jobs Π := (π1, . . . πn) , let us denote Cij(Π) the completion time of job j on machine i according to sequence Π . The completion time of the last job on the last machine, Cm,πn(Π) = Cmax(Π) , is denoted as makespan or maximum completion time of the sequence. Note that Cij(Π) can be recursively calculated as follows: Cij(Π) = max{Ci−1,j(Π), Ci,j−1(Π)}+tij The tardiness and earliness of job j in sequence Π are dened as Tj(Π) = max{Cmj(Π)−dj,0} and Ej(Π) = max{dj−Cmj(Π),0} respectively. Finally, the total tardiness (earliness) is dened as ∑Tj(Π) = ∑∀jmax{Cmj(Π) −dj,0} ( ∑Ej(Π) = ∑∀jmax{dj−Cmj(Π),0} ). It is clear that extremely tight or loose due dates in one instance may lead to a dierent problems. For the problem under study ( Fm|prmu|∑Ej+∑Tj ), this fact is evident according to the following two properties: Property 3.1. Let I be an instance of the Fm|prmu|∑Ej+∑Tj problem, and WM the worst (maximum) makespan for the instance. If dj≥WM ∀j , an optimal solution for I is obtained by solving the corresponding Fm|prmu| − ∑Cj problem for I . Proof. Since each due date is greater or equal than the worst makespan WM , then each due date dj is greater or equal than its completion time, Cmj(Π) (i.e. dj≥WM ≥Cm,j(Π),∀j, Π ). Hence, minimising ∑∀jmax{Cm,j(Π) −dj,0}+∑∀jmax{dj−Cm,j(Π),0}= 0 + ∑∀jdj−Cm,j(Π) = ∑∀jdj−∑∀jCm,j(Π) = const −∑∀jCm,j(Π) . Property 3.2. Let I be an instance of the Fm|prmu|∑Ej+∑Tj problem verifying that dj≤ ∑m i=1 tij ∀j . Then, an optimal solution for I can be obtained by solving the corresponding Fm|prmu|∑Cj problem for I . Proof. Considering dj≤tj∀j , each completion time Cm,j(Π) ( ∀Π ) is greater or equal than its due date, dj , since tj is a lower bound of the makespan of the job j . Hence ∑∀jmax{Cm,j(Π) − 6 dj,0}+∑∀jmax{dj−Cm,j(Π),0}=∑∀j(Cm,j(Π) −dj) + 0 = ∑∀jCm,j(Π) −∑∀jdj= ∑∀jCm,j(Π) + const . From these properties, it is clear that extremely loose due dates transform the problem into a PFSP with the objetive of owtime maximization. Extremely tight due dates lead to a problem similar to the PFSP with owtime minimisation. Both bounds represent opposite objective functions and therefore, algorithms specically focused on yielding good solutions for instances with loose due dates would necessarily perform bad for tight due dates. Thereby, depending on the due dates, three dierent scheduling problems can be solved: the Fm|prmu|∑Cj problem in case of tight due dates, the Fm|prmu|−∑Cj problem in case of loose due dates and the original Fm|prmu|∑Ej+∑Tj problem in the rest of the cases. This fact speaks for the diculties to nd constructive heuristics that perform well for the problem, which in our opinion is reected by the fact that the NEH an algorithm not designed for this specic problem is the only constructive heuristic proposed so far. Typically, the good performance of a constructive heuristic is due to the fact that the objective computed in the iterations of the algorithm is similar to the objective function of the problem. Thereby, when minimising e.g. total owtime in the PFSP, the choice of a partial sequence fullling the minimisation of total owtime clearly seems to have a good performance when the sequence is completed. This is a consequence of having a regular measure as objective. Since this is not the case for our problem, the algorithm may not work well. In fact, the aforementioned properties conrm this fact and show how the objective of the constructive heuristics in their iterations could be distorted: A partial sequence could have loose due dates but, once completed, these due dates would become tight and thus, the algorithm would solve a completely dierent objective during its iterations than the objective function. This fact could also explain the good performance of composite heuristics as compared to constructive heuristics (as discussed in Section 5.5). In order to overcome the aforementioned problems, ecient heuristics for the problem under consideration should be designed according to the following ideas: • They should be very fast in order to work as soon as possible with complete sequences. In 7 this manner, it is easier to identify whether the instance has loose due dates, or tight ones. • They should incorporate an analysis of both sequenced and non-sequenced jobs in each iteration. • They should avoid the use of local search procedures operating with non-complete sequences. Based on these ideas and on the properties discussed before, a number of algorithms are proposed. These are discussed in the next section. 4 Proposed Algorithms Following the recommendations in the previous section regarding very fast heuristics and complete local search methods, four heuristics are proposed for the Fm|prmu|∑Ej+∑Tj problem: • an adaptive constructive heuristic (see Section 4.1), denoted as ACH1, • a composite heuristic (see Section 4.2), denoted as ACH2, composed by ACH1 plus a bounded local search procedure labelled BLS, • a composite heuristic (see Section 4.2), denoted as ACH3, formed by ACH1 plus an iterative bounded relative local search method, iBRLS, • a composite heuristic (see Section 4.2), denoted as ACH4, formed by ACH1 and an iterative local search method, iLS. Additionally, a speed-up procedure is described in Section 4.3 to accelerate the insertion phases of all implemented algorithms. 4.1 Proposed Constructive Heuristic ACH1 tries to nd a good solution using very short computational times so it can embedded in more sophisticated constructive and composite heuristics such as the ones proposed in the next subsections. The procedure of this heuristic is relatively simple: Beginning with a partial 8 sequence with a single job, the procedure constructs a nal sequence appending one by one jobs at the end of the partial sequence according to an index ξujk (Π) . Let us denote by Πk:= (π1, ..., πk) the partial sequence in iteration k and by Uk the set of unsequenced jobs of that sequence ( ujk the j th unsequenced job with j∈[1, n −k] ). Additionally, let NTk be the number of tardy jobs in iteration k in Uk . The algorithm chooses the job from Uk with the lowest value of ξujk (Πk) and places it at the end of sequence Πk , i.e. in position k+ 1 , forming the sequence Πk+1 of the next iteration. This procedure has been shown to be very ecient for other decision problems, being the appropriate choice of the index the critical issue for the eciency of the algorithm (see e.g. Fernandez-Viagas and Framinan, 2015c). This diculty increases in our case due to the strong dependence of the best solutions on the due dates of the jobs. The index must be adapted to solve dierent problems depending on the due dates (loose due dates, tight ones, or neither of them). In Section 3, three dierent situations have been identied: tight due dates ( Fm|prmu|∑Cj decision problem), loose due dates ( Fm|prmu| − ∑Cj decision problem) and normal due dates ( Fm|prmu|∑Ej+∑Tj ). Therefore, at each iteration, the algorithm would check whether the sequence is within one of these cases: • Case 1: Tight due dates (i.e., the problem is similar to the Fm|prmu|∑Cj ). There are hundred of heuristics solving the Fm|prmu|∑Cj in the literature. Particularly, Fernandez-Viagas and Framinan (2015c) designed an ecient constructive heuristic following a similar procedure of insertion in last position of the partial sequence. There, jobs are chosen according to the ξ1 ujk (Πk) index, Equation (1), which considers the minimization of the completion time and the weighted idle time of the candidates jobs (i.e. uik with j∈[1, n −k] ) to be inserted: ξujk (Πk) = ξ1 ujk (Πk) = (n−k−2) 4·ITujk (Πk) + Cm,ujk (Πk) (1) where ITj(Πk) are: ITujk (Πk) = m ∑ i=2 m·max{Ci−1,ujk (Πk)−Ci,πk(Πk),0} i−1 + k·(m−i+ 1)/(n−2) (2) 9 Procedure ACH4() (Π,∑Ej+∑Tj) = ACH1() ; (Π,∑Ej+∑Tj) = iLS(Π,∑Ej+∑Tj) ; end Figure 6: ACH4 Procedure iLS ( Π, OF ) OFb=OF flag := false; while flag = false do flag := false; for j= 1 to n do Π0:= remove job πj from Π ; Test job πj in each position of Π0 ; Π := permutation obtained by inserting πj in the position j of Π0 with less total earliness and tardiness, OF′ ; if OF′< OFb then OFb=OF′ ; Πb:= Π ; flag := true; end end end return Πb and OFb ; end Figure 7: Iterative Local Search, iLS heuristic. This local search method simply tries to place each job πj in the rest of positions of the current sequence and has been extensively used in the literature (see e.g. Ruiz and Stützle, 2007, Li and Wu, 2005 and Pan and Wang, 2012). The procedure is repeated until there are no more improvements. Pseudo codes for ACH4 and iLS methods are shown in Figures 6 and 7. 4.3 Speed Up Procedure In this Section, a simple speed-up procedure to accelerate the insertion phases of the algorithms for the Fm|prmu|∑Ej+∑Tj problem is described. Let Πk be a partial sequence with k jobs and l the job which is to be inserted in position j∈[1, k + 1] . Similarly to the speed up methods proposed by Li et al. (2009) and Vallada and Ruiz (2010), this method stores the completion 16 time of each job on each machine of the partial sequence Πk . When the job l is inserted in each position j of the partial sequence, the completion times of the jobs prior to this position j are already known and do not have to be recomputed. According to several studies, this procedure reduces the CPU times between 30% and 50% and is therefore introduced in each insertion phase of all algorithms implemented in this paper. 5 Computational Experience In this paper, the proposed algorithms are compared against the most ecient heuristics in the literature. The procedure adopted to evaluate the algorithms is the following: First, we introduce the set of instances used for both the experimental parameter tuning and the comparison among heuristics. In Section 5.2, a full factorial design of experiments is carried out to nd the best values of the parameters of the algorithms proposed. The algorithms under comparison are listed in Section 5.3. The indicators to dene the ecient heuristics are introduced in Section 5.4. Using these indicators, constructive and composite heuristics are compared in Section 5.5, leading to the identication of the set of ecient heuristics for the problem. Finally, in Section 5.6, the ecient heuristics are compared as seed sequences of one of the best metaheuristic for the problem. 5.1 Benchmark In this Section, the following two dierent sets of instances are presented to evaluate the algorithms. Note that dierent sets of instances are used in order to avoid an over calibration of the proposed heuristics when the parameters a , b and c are dened. These sets are: • Benchmark B1 for the calibration of the proposed heuristics. This benchmark is composed of a set of 1,080 instances generated according to the procedure by Vallada and Ruiz (2010). The benchmark is formed by 10 instances for each combination of n={50,150,250,350} , m={10,30,50} , T={0.2,0.4,0.6} and R={0.2,0.6,1.0} , where T and R are parameters related to the mean and standard deviation of the due dates respectively. These due dates are generated using the procedure described by Potts and Van Wassenhove (1982), i.e. following a uniform distribution between P·(1 −T−R/2) and P·(1 −T+R/2) , where 17 P is a lower bound for the makespan. Processing times are generated using a uniform distribution [1, 99]. • Benchmark B2 for comparison among the implemented heuristics. This benchmark is composed of a set of 540 instances of Vallada et al. (2008) (available in http://soa.iti.es) and is the most extended benchmark for the PFSP with due dates. This benchmark consists of ve instances for each combination of n={50,150,250,350} , m={10,30,50} , T={0.2,0.4,0.6} and R={0.2,0.6,1.0} . Processing times are generated using a [1,99] uniform distribution. 5.2 Experimental Parameter Tuning The proposed heuristic ACH1 uses three parameters: a , b and c . In this section, a full factorial design of experiments is carried out to determine their best values on the set of instances B1 . The following values are chosen for the experiments: •a={0.8,0.85,0.9,0.95,1} , •b={0.4,0.45,0.5,0.55,0.6} , •c={25,30,35,40,45,50,55} In each instance, the ACH1 heuristic is evaluated according to Equation (7): RPD1 = OF −Base Base ·100 (7) where OF and Base are the solutions obtained by the ACH1 heuristic and a reference algorithm (NEHedd) respectively. Since normality and homoscedasticity assumptions are not fullled, a non-parametric KruskalWallis test is carried out. The p -values are 0.267, 0.865 and 0.000 for parameters a , b and c respectively. Results show that there is statistically signicant dierences only between the levels of parameter c . Additionally, among the 175 combinations of a , b and c , the best results are found for a= 0.90 , b= 0.55 and c= 30 . These values are subsequently used in each heuristic which incorporates the ACH1, i.e. ACH2, ACH3 and ACH4. 18 5.3 Implemented algorithms The performance of the proposed heuristics is tested against the most ecient heuristics for the problem, as well as for some of the most ecient heuristics for similar scheduling problems. More specically, due to their excellent performance (see computational evaluations by Pan and Ruiz, 2013 and Rad et al., 2009), the following heuristics are considered: • NEHedd or : NEHedd or is the NEHedd heuristic proposed by Kim (1993) for Fm|prmu|∑Tj . The speed up procedure described in Section 4.3 is not applied to maintain its original version. • NEHedd et : Heuristic NEHedd or using the speed up procedure in Section 4.3. Additionally, the evaluation of total tardiness in each iteration is replaced by the evaluation of the sum of total earliness and tardiness. • Raj: Adaptation of the Raj heuristic by Rajendran (1993), originally proposed for the Fm|prmu|∑Cj problem. To adapt the heuristic to our problem, the speed up procedure in Section 4.3 is applied, and the original evaluation of total owtime is replaced by the evaluation of total earliness and tardiness. Additionally, the original initial order is replaced by the EDD rule. • RZ: Adaptation of the RZ heuristic by Rajendran and Ziegler (1997) proposed for the Fm|prmu|∑Cj problem, with the initial order replaced by the EDD rule. The speed up procedure is applied, and the evaluation of total owtime is replaced by the evaluation of total earliness and tardiness. • RZ_LW: Adaptation of the RZ_LW heuristic by Rajendran and Ziegler (1997), originally proposed for the Fm|prmu|∑Cj problem. The speed up procedure is applied and the evaluation of total owtime is replaced by the evaluation of total earliness and tardiness. Furthermore, the EDD rule is used as initial order. • FRB4 k : Adaptation of the FRB4 k heuristic by Rad et al. (2009), originally proposed for the Fm|prmu|Cmax problem. The evaluation of the makespan is replaced by the evaluation of 19 the total earliness and tardiness, and the speed up procedure by Taillard (1990) is replaced by the proposed one. As in the NEHedd et , the original order is replaced by the EDD rule. All heuristics are fully recoded for the Fm|prmu|∑Ej+∑Tj problem under the same computer conditions, which means: • Under the same computer (an Intel Core i7-3770 with 3.4 GHz and 16 GB RAM). • Using the same programming language (algorithms have been coded in C#). • Using the same libraries and common functions. 5.4 Indicators to evaluate the heuristics Since each heuristic requires dierent CPU time, their comparison is not straightforward, as there is a trade-o between the quality of the solutions (usually measured by means of the Average Relative Percentage Deviation ARPD ) and the computational eort required (usually measured using the Average Computational Eort ACT ). These indicators are dened as follows: ACTi=∑∀jTi,j J (8) ARPDi=∑∀jRP D2i,j J (9) with Ti,j the average computational time (in seconds) required by heuristic i in instance j among 5 independent runs, J is the number of instances, and ARPDi is the average RPD2i,j of heuristic i over all instances, which is dened by Expression (10): RPD2i,j =OFi,j −BestConstj BestConstj ·100 (10) with OFi,j the total earliness and tardiness for heuristic i in instance j and BestConstj is the best value found among the implemented constructive heuristics (see bounds in online materials). The use of both indicators to compare heuristics is very extended in the literature. However, a direct comparison between both indicators presents several problems related to the weight of each problem size, as shown by Fernandez-Viagas and Framinan (2015c). To avoid them, in addition 20 to report the results in terms of ACT , we also use the average relative percentage time, ARPTi indicator of heuristic i , dened by (11) (note that 1 is added to the quotient to avoid negative numbers). ARPTi=∑∀jRP Ti,j J+ 1 (11) with RPTi,j the relative percentage time of heuristic i in instance j , dened by Equation (12). RPTi,j =Ti,j −ACTj ACTj (12) In the following, we assume that one heuristic outperforms another in an instance if both their RPD and RPT are lower. A heuristic e is thus denoted ecient for an instance if it outperforms the rest of heuristics in this instance. Similarly, one heuristic is labelled ecient is there is no other heuristic with lower values of both ARPD and ARPT measured over a full testbed. The set of ecient heuristics is denoted as A . 5.5 Ecient set of heuristics In this section, all implemented heuristics are compared using benchmark B2 . Average results in terms of ARPD are shown in Table 2 for each combination of n and m , and in Table 4 for each value of the parameters. The CPU time required by each heuristic is shown in Table 3 for each n and m . The last two rows show the ACT and the ARPT of each heuristic. A summary of the results is graphically shown in Figure 8 using ACT to evaluate the computational eort, while ARPT is used as indicator in Figure 9. In view of the results, the NEHedd et heuristic clearly outperforms the NEHedd or in terms of quality of the solution and computational eort. The best ARPDs are clearly found by the proposed heuristic ACH4 (1.19), and by the RZ_LW heuristic (2.40). Regarding heuristics adapted from other problems, the best results are found by Raj, RZ and RZ_LW, which are either very fast heuristics, or local search methods (using dispatching rules as seed sequences). The good performance achieved by the composite heuristics RZ, RZ_LW, ACH2, ACH3, and ACH4 conrms the conclusions obtained after the analysis of the problem in Section 3 which advocated for fast heuristics employing as soon as possible local 21 search methods of full sequences. This fact is also conrmed by the performance of the family of heuristics FRB4 k . Each of these heuristics is outperformed in terms of quality of the solutions and computational eort by RZ and ACH3. According to Figure 9, the ecient heuristics (set A ) are: ACH1, Raj, NEHedd et , ACH2, RZ, ACH3 and ACH4. To statistically justify this statement, we perform a Holm's procedure (Holm, 1979) with the following hypotheses: • H 1 : ACH2 = NEHedd or . • H 2 : RZ = FRB4 2 . • H 3 : RZ = FRB4 4 . • H 4 : RZ = FRB4 6 . • H 5 : ACH3 = FRB4 8 . • H 6 : ACH3 = FRB4 10 . • H 7 : ACH3 = FRB4 12 . • H 8 : ACH4 = RZ_LW. Results are shown in Table 5, where the p -values have been calculated using a non-parametric Mann-Whitney test since the normality and homoscedasticity assumptions were not conrmed (see e.g. Pan et al., 2008). Assuming a condence of 0.95, only two hypotheses (H2 and H3) are not rejected and the proposed heuristics (ACH2, ACH3 and ACH4) can be therefore considered as statistically ecient. The heuristics of the sets A are shown in Figure 9. 22 Instance Raj NEHedd et NEHedd or RZ FRB4 2 FRB4 4 FRB4 6 FRB4 8 FRB4 10 FRB4 12 RZ_LW ACH1 ACH2 ACH3 ACH4 50x10 26.52 22.38 44.23 13.53 14.16 11.62 10.00 9.91 8.79 8.07 2.53 30.15 13.65 8.74 1.41 50x30 20.61 14.20 12.27 10.55 7.86 6.22 5.39 4.56 4.41 4.14 2.59 18.33 9.31 6.11 1.81 50x50 15.06 7.94 6.89 8.03 4.54 3.68 2.85 2.84 1.76 1.60 2.11 11.49 5.95 4.00 1.40 150x10 41.36 37.56 66.72 14.39 25.56 24.13 23.19 21.88 21.59 19.33 1.69 46.12 18.06 9.83 1.65 150x30 31.16 25.09 39.50 14.76 15.89 15.07 14.15 13.07 11.49 11.04 2.53 37.47 15.88 7.40 1.19 150x50 30.61 24.40 25.86 14.93 18.92 17.11 16.36 14.73 14.02 13.10 3.18 33.14 14.33 5.23 0.44 250x10 36.04 29.13 76.55 13.94 22.63 20.62 19.42 18.69 17.61 17.25 2.31 50.20 13.88 7.85 1.09 250x30 40.84 35.95 57.49 15.95 24.08 23.16 21.62 21.04 20.13 18.94 2.50 45.28 19.56 8.96 1.14 250x50 32.37 26.65 39.12 15.29 17.54 16.23 15.34 15.13 13.28 11.87 2.69 37.35 16.44 5.99 1.29 350x10 38.57 30.75 77.89 13.37 23.70 23.05 22.46 20.94 20.71 20.09 1.41 56.46 14.83 8.76 0.82 350x30 48.71 41.83 66.24 18.72 32.40 29.66 28.60 27.43 26.10 26.66 2.83 51.33 22.34 9.05 1.02 350x50 32.56 26.18 47.91 13.49 18.94 16.45 16.34 15.17 15.51 13.08 2.44 39.64 17.25 7.44 0.98 Average 32.87 26.84 46.72 13.91 18.85 17.25 16.31 15.45 14.61 13.76 2.40 38.08 15.12 7.45 1.19 Table 2: Relative Percentage Deviation ( RPD ) for the implemented heuristics under the set of instances of Vallada et al. (2008) Instance Raj NEHedd et NEHedd or RZ FRB4 2 FRB4 4 FRB4 6 FRB4 8 FRB4 10 FRB4 12 RZ_LW ACH1 ACH2 ACH3 ACH4 50x10 0.00 0.00 0.00 0.01 0.02 0.02 0.02 0.03 0.03 0.04 0.03 0.00 0.00 0.02 0.03 50x30 0.00 0.01 0.01 0.02 0.04 0.05 0.07 0.09 0.10 0.11 0.09 0.00 0.01 0.06 0.08 50x50 0.00 0.01 0.02 0.03 0.06 0.09 0.11 0.14 0.16 0.19 0.17 0.00 0.02 0.08 0.13 150x10 0.01 0.06 0.10 0.13 0.26 0.41 0.55 0.68 0.80 0.91 0.98 0.00 0.09 0.56 0.95 150x30 0.04 0.16 0.35 0.41 0.82 1.30 1.75 2.17 2.56 2.92 3.42 0.01 0.28 1.74 3.20 150x50 0.07 0.26 0.61 0.72 1.44 2.31 3.12 3.89 4.58 5.26 5.84 0.02 0.49 2.64 5.27 250x10 0.06 0.21 0.46 0.56 1.12 1.81 2.47 3.09 3.68 4.24 4.93 0.01 0.38 2.84 4.73 250x30 0.18 0.64 1.60 1.82 3.67 5.92 8.00 9.93 11.80 13.58 19.33 0.03 1.25 10.24 18.88 250x50 0.31 1.13 2.80 3.24 6.50 10.50 14.22 17.74 21.06 24.30 33.00 0.06 2.21 18.64 32.80 350x10 0.15 0.53 1.24 1.52 3.02 4.91 6.72 8.46 10.12 11.73 14.74 0.02 1.03 8.88 14.33 350x30 0.46 1.69 4.30 4.88 9.90 16.15 21.96 27.51 32.70 37.91 55.90 0.06 3.33 31.85 61.23 350x50 0.81 2.98 7.54 8.60 17.37 28.02 38.17 47.65 57.07 65.66 95.51 0.09 5.88 55.56 96.84 ACT 0.17 0.64 1.59 1.83 3.68 5.96 8.10 10.12 12.06 13.90 19.49 0.03 1.25 11.09 19.87 ARP T 0.03 0.11 0.24 0.30 0.61 0.96 1.27 1.57 1.85 2.12 2.43 0.01 0.21 1.33 2.32 Table 3: Average Computational Eort ( ACT ) (in seconds) and Average Relative Percentage Time ( ARPT ) of the implemented heuristics under the set of instances of Vallada et al. (2008) 23 Parameter Raj NEHedd et NEHedd or RZ FRB4 2 FRB4 4 FRB4 6 FRB4 8 FRB4 10 FRB4 12 RZ_LW ACH1 ACH2 ACH3 ACH4 T 0.2 49.71 38.62 92.83 16.45 28.60 26.05 24.71 23.59 21.92 19.90 1.60 65.76 25.09 13.01 2.49 T 0.4 31.61 29.44 36.71 15.93 20.61 19.15 18.10 17.18 16.76 16.40 2.72 36.04 14.30 6.15 0.71 T 0.6 17.28 12.46 10.63 9.36 7.34 6.55 6.12 5.58 5.16 5.00 2.88 12.44 5.98 3.19 0.36 R 0.2 18.40 16.25 21.39 9.35 11.14 10.06 9.60 9.31 8.95 8.83 2.31 22.21 8.93 5.05 0.43 R 0.6 24.85 18.31 35.67 12.50 12.01 11.05 10.27 10.02 9.63 9.26 2.59 28.50 11.52 6.62 0.86 R 1 55.35 45.95 83.11 19.89 33.40 30.64 29.07 27.02 25.27 23.20 2.30 63.53 24.92 10.68 2.27 n 50 20.73 14.84 21.13 10.70 8.85 7.17 6.08 5.77 4.98 4.60 2.41 19.99 9.64 6.28 1.54 n 150 34.38 29.02 44.03 14.69 20.12 18.77 17.90 16.56 15.70 14.49 2.47 38.91 16.09 7.49 1.09 n 250 36.42 30.57 57.72 15.06 21.42 20.00 18.79 18.29 17.00 16.02 2.50 44.28 16.63 7.60 1.17 n 350 39.95 32.92 64.01 15.19 25.01 23.05 22.47 21.18 20.77 19.94 2.23 49.14 18.14 8.42 0.94 m 10 35.62 29.95 66.34 13.81 21.51 19.85 18.77 17.85 17.17 16.19 1.99 45.73 15.11 8.80 1.24 m 30 35.33 29.26 43.88 15.00 20.06 18.53 17.44 16.52 15.53 15.20 2.61 38.10 16.77 7.88 1.29 m 50 27.65 21.29 29.95 12.93 14.99 13.37 12.72 11.97 11.14 9.91 2.60 30.40 13.49 5.67 1.03 Table 4: Average relative percentage deviation ( ARPD ) for each heuristic grouped by the values of the parameters 24 Figure 8: ARPD vs ACT of implemented heuristics. X-axis ( ACT in seconds) is shown logarithmic scale. 5.6 Comparison among ecient heuristics As there is a trade-o between quality of the solution and computational eort, heuristics in set A cannot be directly compared in terms of ARPD due to their dierent computational eorts. In this Section, they are included as initial solution for one of the best metaheuristic for this problem, i.e. the ILS by M'Hallah (2014), replacing the original seed sequence of the metaheuristic (EDD rule). Thus, the metaheuristic is run using eight dierent initial sequences (EDD rule and each heuristic in set A ) where the EDD rule is included in the comparison as it is the original seed sequence of the metaheuristic. Each variation of the metaheuristic is run under the same computational conditions described in Section 5.3 using the benchmark in Section 5.1. In this case, ve runs are performed per instance and the average values are recorded. The variations of the ILS are stopped depending on the size of the problem according to expression n·m·t/2 (milliseconds) where t= 5,10,15,20,25,30 (see e.g. Ruiz and Stützle, 2007 for a similar stopping criterion). Obviously, the CPU time required by each heuristic is included in the CPU time of the metaheuristic, i.e. the clock starts before applying the heuristic. Results of the ILS metaheuristic using dierent heuristics as initial solution are shown in terms of ARPD in Table 6. Note that 25