An iterated greedy algorithm for the parallel blocking flow shop scheduling problem and sequence-dependent setup times

Expert Systems With Applications 184 (2021) 115535 Available online 8 July 2021 0957-4174/© 2021 The Author(s). Published by Elsevier Ltd. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/). An iterated greedy algorithm for the parallel blocking flow shop scheduling problem and sequence-dependent setup times Imma Ribas a , * , Ramon Companys b , Xavier Tort-Martorell c a Departament d’Organitzaci´ o d’Empreses, DOE – ETSEIB - Universitat Polit` ecnica de Catalunya. BarcelonaTech, Avda. Diagonal, 647, 7th Floor, 08028 Barcelona, Spain b Universitat Polit` ecnica de Catalunya, BarcelonaTech, Spain c Departament de Estadística e investigaci´ on OperativaETSEIB - Universitat Polit` ecnica de Catalunya. BarcelonaTech, Avda. Diagonal, 647, 6th Floor, 08028 Barcelona, Spain ARTICLE INFO Keywords: Parallel Flow Shop Sequence-dependent Setup times Makespan Distributed Flow Shop Blocking ABSTRACT This paper deals with the problem of scheduling jobs in a parallel flow shop configuration under the blocking constraint, in which the setup time of machines depends not only on the job to be processed but also on the previously processed one, i.e., there are sequence-dependent setup times. The performance analysis of several iterated greedy algorithms with different initial solution procedures and local searches lets us define an efficient algorithm to minimize the maximum job completion time. Moreover, the computational evaluation showed the efficiency of searching in different neighborhood structures and noted the significant influence of the initial solution. However, contrary to other scheduling problems, starting with a high quality solution does not guarantee better performance of the algorithm. 1. Introduction There are several productive systems in which more than one flow shop (line) is available to process the products, such as in the glass industry (He et al., 1996), the production process of industrial supplies (Jiang and Wan, 2011) or reprocessing lines (Kim et al., 2015). In other environments, parallel lines are used to increase production capacity in many manufacturing systems. In these productive systems, the scheduling of jobs consists of assigning the products (jobs) to a line and to sequence the products allocated to each line. This problem is known as the Parallel Permutation Flow Shop Scheduling Problem (PPFSP). The PPFSP is different from the classical permutation flow shop scheduling problem (PFSP). PFSP focuses in ordering n jobs that have to be processed in m machines in the same order whereas in the PPFSP two decisions have to be made: assignment of jobs to the lines and sequence the allocated jobs to each line. Hence, it is necessary to design specific methods to solve this problem, especially if some additional constraints are considered in order to bring the problem closer to the reality of production environments. In this paper, we consider the PPFSP with blocking and sequencedependent setup times, known as the Parallel Blocking Flow Shop Problem (PBFSP). The blocking constraint appears in several manufacturing environments, such as in productive systems without any intermediate space between machines, where an already processed job by one machine must wait until the next machine is free; or in those where robots move the products and the treated parts must wait in the machine until they can be picked up and moved to the next machine (Sethi et al., 1992). Other examples are found in the iron and steel industry (Gong et al., 2010), industrial waste processing and the production of metallic parts (Martinez et al., 2006). Recently, Miyata & Nagano, (2019) published a comprehensive review of the blocking flow shop problem. On the other hand, setup times appear when the machines have to be prepared, adjusted, or cleaned between two consecutive jobs. Setup times can be sequence-independent or sequence-dependent. In the former case, the setup time depends on the job to be processed; in the latter, the amount of time also depends on the job that was previously processed in that machine. Setup activities mean a loss of available capacity. Trovinger and Bohn (2005) reported direct savings of $1.7 million per year due to reduced setup times in a printed circuit board assembly plant. According to Allahverdi (2015), considering setup times in scheduling decisions can help increase productivity, reduce both waste and non-value-added activity, improve the use of resources and meet deadlines; yet it is dealt with by only about 10% of the existing * Corresponding author. E-mail addresses: [email protected] (I. Ribas), [email protected] (R. Companys), [email protected] (X. Tort-Martorell). Contents lists available at ScienceDirect Expert Systems With Applications journal homepage: www.elsevier.com/locate/eswa https://doi.org/10.1016/j.eswa.2021.115535 Received 7 March 2021; Received in revised form 29 May 2021; Accepted 29 June 2021 Expert Systems With Applications 184 (2021) 115535 2 literature on scheduling. Hence, in this paper we contribute to reduce this gap by proposing an efficient heuristic to solve the problem of scheduling jobs in a parallel flow shop with blocking and sequence dependent setup times. To design a procedure to for scheduling jobs in a line with blocking and setup times two aspects should be considered: when the machines can be set up and when the jobs processed by one machine can move on to the next one. There are three possible moments for beginning the setup. Let h be the job being processed by the considered machine and i the next job to be processed in that machine, so the three cases are: (1) when job h has finished, (2) when job h has left the machine, (3) when job i has arrived at the machine. Concerning the moment in which a job can move from its current machine to the next one, two possibilities exist: when job h has left the machine or when the setup for processing job i has finished. In this work, we consider that setup can be performed when job h has left the machine (option 2) and job i can move on to the next machine once job h has left it, even though the setup is not finished. To the best of our knowledge, the PBFSP with sequence-dependent setup times has only been studied before by Ribas & Companys (2021), who tested several constructive heuristics to solve the problem. Although constructive heuristics allow finding a solution quickly, improvement heuristics allow this solution to be further enhanced. Hence, this paper aims to propose a simple but effective heuristic to find an efficient solution for the problem, by analyzing the performance of different local searches in the neighborhood of the whole solution (product allocation to lines and line sequence). The remainder of the paper is organized as follows. Section 2 is devoted to the literature review, Section 3 to the problem definition. Section 4 describes the initial solution methods considered. Section 5 describes different improvement methods. The computational results and comparisons are shown in Section 6. Finally, Section 7 concludes and proposes future lines of research. 2. Literature review The PPFSP has not been extensively studied. The simple case, where lines have only two machines, was studied by He et al. (1996) who proposed mixed integer programming and an efficient heuristic to minimize the maximum completion time of jobs. With the same criterion in mind, Cao & Chen (2003) developed a mathematical model and a tabu search algorithm; Al-Salem (2004) proposed a new polynomial-time heuristic; Zhang & Van De Velde (2012) presented approximation algorithms with worst-case performance guarantees and Dong et al., (2020) proposed a polynomial-time approximation scheme. The general case (i.e., m-machine PPFSP for the makespan minimization) was studied by Jiang & Wan (2011), who proposed a quantum algorithm; Ribas et al. (2017) who compared the performance of an iterated local search algorithm and an iterated greedy algorithm in order to minimize the makespan in the presence of blocking constraints; Tong et al., (2018) , who proposed a polynomial-time approximation algorithm and Ribas & Companys (2021) who proposed constructive heuristics to solve the Parallel Blocking Flow Shop problem (PBFSP) with sequence-dependent setup times. Regarding other performance criteria, Ribas et al. (2019) proposed an iterated greedy algorithm for the PBFSP for the total tardiness minimization. The solution approach for the PPFSP is similar to that for the Distributed Permutation Flow Shop Scheduling Problem (DPFSP) (i.e., in both problems jobs have to be allocated to a line or factory and then have to be sequenced in the assigned lines or factory), therefore, we also review the methods proposed for solving this problem. The DPFSP has mainly been addressed for minimizing total makespan since Naderi & Ruiz (2010) first presented the problem, for which various metaheuristics have been proposed as solutions. A Variable Neighborhood procedure was proposed by Naderi & Ruiz (2010) and Genetic Algorithms by Gao & Chen (2012), Gao et al. (2012) and Xu et al., (2013). A Tabu Search algorithm was proposed by Gao et al. (2013), a scatter search method by Naderi & Ruiz (2014), a discrete electromagnetism algorithm by Liu & Gao (2010). Additionally, Shao et al., (2020) proposed a fruit fly algorithm for the problem under the blocking constraint and Zhao et al., (2020) an ensemble discrete differential evolution algorithm for the same situation. One of the most frequently proposed algorithm to solve scheduling problems is the Iterated Greedy which, despite its simplicity, has been very effective to find good solutions in several productive configurations. Similarly, some authors have suggestid modified versions for the DBFSP, for example, Fernandez-Viagas & Framinan (2014) proposed bounding the local search, Ruiz et al., (2019) suggested different local searches, Lin et al., (2013) proposed removing a variable number of jobs from the solution as well as a new acceptance scheme. Recently, Huang et al., (2020) recommended to discard the acceptance scheme and to restart the search with an scheme with six operators to deal with the DPFSP with sequence-dependent setup times. Regarding other criteria, Fernandez-Viagas et al., (2018) developed an iterative improvement algorithm to minimize the total flow time. On the other hand, few papers deal with the scheduling problem taking into account sequence-dependent setup times and machine blockage and most of the research done considers the flow shop configuration and the makespan criterion (Costa et al., 2020; Newton et al., 2019; Shao et al., 2018; Takano & Nagano, 2019). However, Aqil & Allali (2021) and Han et al., (2020) took into account more than one performance criterion during the scheduling. Regarding more complex productive configurations, Zandieh & Rashidi (2009) and Moccellin et al. (2018) considered the hybrid flow shop scheduling problem with blocking and setup to minimize the maximum completion time of jobs. Rashidi et al. (2010) considered not only the makespan minimization but also the maximum tardiness of jobs for the hybrid flow shop scheduling problem with unrelated parallel machines. Finally, Ribas & Companys(2021) considered the Parallel Blocking Flow Shop problem with setup times. Notice that most of these papers have been published very recently, which shows an increasing interest of researchers in putting the scheduling problems closer to reality. In this way, this paper proposes an effective iterated greedy algorithm to scheduling jobs in a parallel flow shop without buffers considering sequence-dependent setup times. It is worth mentioning that special attention is required when the set up times are considered, because the machines’ idle time and the total completion time can increase considerably without efficient scheduling. 3. Problem description The parallel blocking flow shop scheduling problem (PBFSP) consists of scheduling a set of n jobs in F identical flow shops (lines). Each flow shop has m machines. Jobs must be allocated to one of the f lines. The jobs assigned to a line have to be processed on all machines in the same order. Each job i, i ∊ {1, 2, …, n} requires a fixed processing time p j,i and a setup time, which depends on the previous job processed on every machine j, j ∊ {1, 2,…, m}. Jobs and machines are available from time zero onwards. The objective is to schedule the jobs in order to minimize the maximum makespan (C max ) between lines. Let n f be the set of jobs assigned to line f; σ f the sequence of the n f jobs assigned to line f; and f max the line with the maximum C max . Hence, a solution Π is composed of the sequence of jobs in each line (Π=( σ 1 , σ 2 , …, σ F )). Additionally, we denote as [k] the index of the job in the kth position in the sequence and S j,i,k as the sequence-dependent setup times (SDST) needed in machine j after processing job i and before processing job [k]. This setup can be done once job i has left the machine. Let S j,0,k be the setup time required to process the first job in the sequence; σ k,f is the job [k] in line f and c j,k,f is the departure time of job [k] from machine j of line f. Note that if machine j +1 is available, job i can leave machine j when it is completed. In this situation, c j,k,f is the completion time of job [k] in machine j of line f. The outline of the makespan calculation is I. Ribas et al. Expert Systems With Applications 184 (2021) 115535 3 shown in Fig. 1. In Fig. 2, for example, it can clearly be observed that it is necessary to design scheduling methods to minimize setup times, blockages and idle times to minimize the total completion time. When the sequence is J 1 , J 2 , J 3 the completion time is 19, whereas when the sequence is J 2 , J 1 , J 3 the C max is 21. This is due to the increase in the setup times required to change from one job to the other, but we can also observe a blockage in M2 due to J 1 not being finished in M3, whereas J 3 has already finished in M2. 4. Iterated greedy algorithm for the PBFSP with sequencedependent setup times The PPFSP is an NP-Hard problem if (n >F). Therefore, the PBFSP with sequence-dependent setup times is also NP-Hard. As a result, it is necessary to design heuristic methods for obtaining good solutions in a reasonable CPU time. In this paper, an Iterated Greedy (IG) algorithm is proposed because it is a simple local search method that has proved very efficient for different scheduling problems. It was first applied to the permutation flow shop problem to minimize the makespan by (Ruiz & Stützle, 2007). The good performance showed and its simplicity (IG has very few parameters to calibrate) animated the implementation of this algorithm to other scheduling problems. In particular, it was successfully applied to both the DPFSP (Fernandez-Viagas & Framinan, 2014; Ruiz, Pan & Naderi, 2019) and the PBFSP (Ribas et al., 2017, 2019). IG algorithm starts with a high quality solution which is improved in an iterative procedure until the stopped criterion is met. The iterative method starts by perturbing the incumbent solution with a destruction and construction phase (perturbation phase). Next, the new solution is tried to be improved by a local search and, finally, the new solution is submitted to the acceptance criterion to decide if it replace the incumbent solution. Fig. 3 shows the outline of the main structure of the Iterated Greedy (IG) algorithm where Π is the set of sequences in each of the parallel line (Π =( σ 1 , σ 2 ,…, σ F )) and C max (Π) is the maximum makespan value among lines (C max (Π) =Max f {C max ( σ f )}). 4.1. Initial solution procedures Five constructive procedures were used to test the influence of the initial solution on the performance of the algorithms base in the results obtained by Ribas & Companys (2021). The procedures were selected considering both the quality of the solution and the CPU time required since, as is stated in Ruiz et al., (2019), the effect of the initial solution is quickly neutralized by the improvement phase. Hence, the chosen candidates were TRA5, LPT5, RCP0, HPF3 and PF23, ordered according to their performance. The description of each method is as follows: •LPT5 sequences the jobs in non-increasing order of their total processing time (the sum of the processing time in each machine). Next, for i =1 to n, assign job i to the line that would finish it at the earliest time if located at the end of its sequence. Place job i at the position that minimizes its C max . •TRA5 calculates two indexes for each job (S1i and S2i) according to (1) and (2), respectively. Next, Johnson’s algorithm (Johnson, 1954) is used to sequence the jobs by considering S1i and S2i as the processing time of job i in the first and second machine, respectively. S1i=∑ m j=1 (m−j+1)⋅pj,i(1) S2i=∑ m j=1 (j−1)⋅pj,i(2) Finally, for i =1 to n, assign job i to the line that would finish it at the earliest time if located at the end of its sequence. Place job i at the position that minimizes its C max . •PF23 creates a sequence in each line by assigning a similar load (ΣP i / F). This process starts in one of the lines (all of which are identical) by assigning jobs until it reaches the mean load. The process is repeated for each line. The sequence is created by adapting the PF rule (McCormick, Pinedo, Shenker & Wolf, 1989) to the problem at hand. Therefore, the idle time is calculated by considering that a machine is only idle when it is not processing any job but not when it is being set up. Therefore, the total timeout of machines is calculated as in (3), where i denotes the job, k the position, σ the sequence of jobs already sequenced, and σ *i the partial sequence plus job i: Tmk(i) = ∑ m j=1 (cj,k+1( σ ∗i) − cj,k( σ ) − pj,i)(3) The job selected is the one that leads to the minimum timeout. •HPF3 is quite similar to PF23, the main difference being in the timeout calculation. In this procedure the sequence in each line is created in order to minimize both the timeout of machines and the total flowtime, which is carried out with the index ind1(i, k) calculated according to (4). ind1(i,k) = μ ⋅∑ m j=1 (cj,k( σ *i) − cj,k−1( σ ) − pj,i) + (1− μ )⋅(cm,k( σ *i) −cm,k−1( σ )) (4) The job selected is the one that has the minimum value of index ind1 (i, k). •RCP0 builds the solution by choosing a job and a line at the same time. At each iteration, the line that has the last machine available soonest is selected. Next, the job that leads to the minimum timeout, which is calculated by equation (3), is chosen. This process is repeated until all jobs have been assigned. 4.2. Local searches Since this research aims to define an efficient algorithm for the problem, two type of local searches, with different neighborhood structures, were used to analyze their performance. The first local search, SSA, is designed to improve the sequence of each line in order to diminish its C max , whereas the second is designed to reduce the maximum makespan among lines by trying to move jobs from the critical line (f max ), the one with the maximum C max , to other lines. Fig. 1. Outline of makespan calculation. I. Ribas et al. Expert Systems With Applications 184 (2021) 115535 4 This second local search was called MIL. In both searches, the insertion and swap neighborhood were tested, as well as the combination of both. 4.2.1. Line improvement: SSA In this improvement the local search is performed, in each line, by exploring the neighborhood of the current sequence. An analysis was made of the effectiveness of using the swap procedure, the insertion procedure or a combination of both. The swap procedure is described as follows. For each job in the sequence, neighbors are generated by swapping a job with all the jobs that follow it in the sequence. If the best neighbor ( σ f ′) is better than the current solution ( σ f ), it becomes the new current solution σ f , and the process continues until all jobs have been considered. To prevent the neighborhoods from always being explored in the same order, the jobs are selected randomly. Notice, in Fig. 4, that swap ( σ , k 1 , k 2 ) indicates that jobs placed in positions k 1 and k 2 , in sequence σ , exchange their positions and shuffle( σ ) creates a randomized sequence with the jobs in σ . The insertion procedure functions as follows. For each job in the sequence, neighbors are generated by removing the job from its position and inserting it into all the other possible positions. If the best neighbor ( σ f ′) is better than the current solution ( σ f ), it becomes the new current solution σ f , and the process continues until all jobs have been considered. As in the swap procedure, jobs are selected randomly. Notice that reinsert( σ , k 1 , k 2 ) indicates that job in position k 1 , in sequence σ , is placed in position k 2 In the case of using both methods, the neighborhood to be explored first is selected randomly (50% probability each). After exploring the neighboring solutions of current solution σ f , the local optimum σ f ′is compared with σ f . If the solution has improved, σ f ′replaces σ f and the search continues in the other neighborhood. This process continues until the current solution is no longer improved. 4.2.2. Redistribution of jobs between lines: MIL This phase tries to assign the jobs allocated to the critical line f max , the one with a maximum C max , to another line by either reassigning a job to another line or exchanging a job with another job of a different line. We named these procedures Reassignment and Permutation, respectively. The reassignment procedure consists of swapping two jobs: one from f max and one from another randomly selected line. If the maximum makespan among lines (C max ) diminishes, the change is kept and the procedure is repeated with the line that now has the maximum makespan. If the movement does not improve the C max , a new job from f max is selected and the process starts again. The search finishes either when all the jobs in the critical line have been selected or after a limited number of iterations (nlimir) are reached. Then the process iterates over each neighborhood to find improvements. The outline of this procedure is shown in Fig. 5. The Permutation procedure involves selecting a job randomly from the line which has the maximum makespan (f max ) and then inserting it into the best position of another randomly selected line, i.e., the position that leads to a minimum makespan of this line. If the C max diminishes, the sequence is kept and the procedure is repeated again with the line that now has the maximum makespan. In the same way as the Fig. 2. Makespan comparison between scheduling. Fig. 3. Outline of the algorithm. I. Ribas et al. Expert Systems With Applications 184 (2021) 115535 5 Reassignment procedure, if the movement does not improve the C max , a new job is selected from f max and the process starts again. This part finishes either when all the jobs in the critical line have been selected or after a limited number of iterations (nlimip) are reached. The outline of this procedure is shown in Fig. 6. 4.3. Perturbation mechanism The perturbation mechanism prevents the solution from being trapped in a local optimum. The implemented method is similar to the one proposed by Fernandez-Viagas & Framinan (2014). It tries to diversify the search by removing d randomly selected jobs from its current line, attempting to assign each job to all the other lines in order to find the factory and position that leads to the minimum global makespan. The outline of this procedure can be seen in Fig. 7. Fig. 4. Outline of the Swap and Insert procedures. Fig. 5. Outline of the Reassignment procedure. Fig. 6. Outline of Permutation procedure. I. Ribas et al. Expert Systems With Applications 184 (2021) 115535 6 4.4. Acceptance Function The Acceptance Function allows the search to be diversified, as does the perturbation mechanism. The scheme used, see equation (5), is similar to that used in Fernandez-Viagas & Framinan (2014), inspired by the mechanism used in the simulated annealing algorithm. Parameter T allows calibrating the interval of the worst solution accepted. Temperature =T⋅∑n i=1∑m j=1pi,j n⋅m⋅10 (5) 4.5. Experimental parameter adjustment of heuristic The proposed algorithm has four parameters to be calibrated: the number of jobs considered in the perturbation mechanism (d); the maximum number of iterations conceded to the reassignment process (nlimr) and perturbation process (nlimp); and the temperature (T) used to calibrate the acceptance mechanism. Each parameter was tested with three levels: d={3, 4, 5}, nlimr={10, 15, 20}, nlimp={10, 15, 20} and T= {0.3, 0.4, 0.5}. This results in 3x3x3 =27 algorithm configurations. The instances used in this test were combinations of n={25, 50, 75, 100 } and m={5, 10, 15, 20}. There were 16 sets with 5 instances in each that were solved for F={2, 3, 4 ,5}. Therefore, a total of 320 instances were used in this test. The setup time was generated according to a uniform distribution between [1, 50] and the processing time of jobs according to distribution in a range interval [1, 99], as in the scheduling literature. The algorithms were stopped after 20·n 2 ·m ּ ·10 -5 s. Each one of the 320 calibration instances was run for five different replicates in each algorithm configuration. The experiments’ response variable is the Relative Percentage Deviation (RPD), which calculates the difference between the solution obtained by a specific algorithm configuration and the best solution found, over the same instance, by any of the possible combination of values of parameter. The index RPD is calculated as in (6): RPD =Soli,j−Besti Besti ∙100 (6) where Sol i,j is the makespan value obtained by algorithm j (i.e. the algorithm with a determined value of parameters) in calibration instance i, and Best i is the minimum makespan obtained during the evaluation over the same instance. The algorithm was coded in QB64 and tested on a computer 3.40 GHz Intel Core i7-3770 CPU with 8 GB of RAM. Both instances and solutions are available from the authors on request. The initial solution used was TRA5, which according to (Ribas & Companys, 2021) showed the best performance in terms of solution quality. The results were analyzed by an ANOVA and the residual analysis did not show any important violation of the model hypothesis. As can be seen in Table 1, only parameters d and nlimp are significant. Note the interaction between d and n, m, F, nlimp; the interaction between nlimp and n, F is also significant. Fig. 8 shows that the best values are obtained when d =4 and nlimp =15, whereas Figs. 9 and 10 show the two most significant interactions: n*d and F*nlimp. Notice that the interaction between n and d is due to n =25, which has a different behavior to the others. In this case there is no difference between d =4 and d =5, whereas for the other values of n it is clear that the best value is d =4. The same happens with the interaction between F and nlimp, which is due to F =2, since the nlimp =15 is the best value for all values of F, except when the number of lines is 2. A slightly better behavior is observed if nlimp is 10, although it can be seen that the difference between the Mean RPD values reached when selecting 10 or 15 is very small. Hence, our algorithm is set with d =4, nlimr =10, nlimp =15 and T =0.4. 5. Computational evaluation In this section, we first evaluate the contribution of each local search and neighborhood structure to the performance of the IG algorithm. Then, we test the algorithm with different initial solution procedures, as well as, against an adaptation of the Iterated Greedy algorithm with a Restart scheme (IGR) proposed in (Huang et al., 2020) for the Distributed Flow shop problem with sequence-dependent setup times. These tests were conducted on a set of ad-hoc generated instances. Notice that this set of instances is different than the one used for calibrating the parameters in order to avoid any overfitting. 5.1. Performance evaluation of local searches This test is performed to define the most effective structure for the local searches. Specifically, we aim to analyze whether it is better to explore one of the defined neighborhoods or both, either in the improvement of the sequence in each line (SSA) or in the improvement of product allocation to lines (MIL). We run an almost full factorial design of experiments with two factors: SSA and MIL with three levels each (the only combination we did not run was not doing any local search). In the case of SSA the levels are: Swap, Insert, Both. For MIL the Fig. 7. Perturbation mechanism of IGA. Table 1 Anova: ARPD versus n, m, F, d, T, nlimr and nlimp. Source DF SS MS F P n 3 800.36 266.788 4044.13 0.000 m 3 1212.68 404.226 6127.50 0.000 F 3 183.16 61.054 925.49 0.000 d 2 13.43 6.717 101.81 0.000 nlimr 2 0.06 0.032 0.49 0.611 nlimp 2 3.98 1.992 30.19 0.000 T 2 0.01 0.007 0.11 0.900 n*m 9 21.81 2.423 36.73 0.000 n*F 9 75.89 8.432 127.82 0.000 n*d 6 19.47 3.245 49.20 0.000 n*nlimr 6 0.20 0.034 0.52 0.796 n*nlimp 6 3.82 0.637 9.65 0.000 n*T 6 0.19 0.032 0.48 0.825 m*F 9 45.14 5.016 76.04 0.000 m*d 6 1.80 0.300 4.54 0.000 m*nlimr 6 0.12 0.020 0.30 0.937 m*nlimp 6 0.66 0.110 1.67 0.124 m*T 6 0.11 0.019 0.29 0.943 F*d 6 0.85 0.141 2.14 0.045 F*nlimr 6 0.40 0.067 1.01 0.417 F*nlimp 6 12.92 2.154 32.64 0.000 d*nlimr 4 0.01 0.003 0.05 0.996 d*nlimp 4 3.24 0.810 12.28 0.000 d*T 4 0.07 0.018 0.28 0.892 nlimr*nlimp 4 0.23 0.059 0.89 0.469 nlimr*T 4 0.14 0.034 0.52 0.721 nlimp*T 4 0.08 0.020 0.31 0.874 Error 25,785 1701.02 0.066 Total 25,919 4101.89 I. Ribas et al. Expert Systems With Applications 184 (2021) 115535 7 levels are: Reassignment, Permutation, Both. For this test we used a set of instances that combined values of n ×m, with n={25, 50, 75, 100, 150, 200} and m={5, 10, 15, 20}. There were 24 groups of instances and 10 instances per group, for a total of 240 instances solved for F={2, 3, 4, 5} and three levels of setup times. Hence, the test was conducted on 2880 instances. The processing time was generated as before, using a uniform distribution in the range [1,99]. The three levels of setup were also generated according to a uniform distribution with the range intervals [1, 20] for the low level, [1, 50] for the medium level and [1, 120] for the high level. The algorithms were stopped after 30·n 2 ·m ּ ·10 -5 s. Algorithms were run 5 times per instance. The response variable was the RPD calculated as equation (6) where Sol i,j is the makespan obtained by heuristic j (i.e. specific combination of SSA and MIL levels) in instance i, and Best i the minimum makespan obtained by any of the configurations tested over the same instance. The results were analyzed by an ANOVA. The model hypotheses were tested by a residual analysis that did not show any violation. From the result shown in Table 2 it can be seen that the main factors and their interaction are significant (p-value =0). Moreover, column F shows that MIL has a greater influence than SSA in improving the solution, as was expected. SSA only improves the sequence of each line, whereas MIL moves jobs from a critical line to another one to reduce the total C max . Notice that SSA and MIL interaction is significant but really small (F value). In fact, it confirms that the best combination is when the two neighborhoods, in the two types of local searches, Insert-Swap and Reassignment-Permutation, are used and shows that this solution is a bit better than the addition of the two individual effects. To better visualize the contribution to each type of local search structure in SSA and MIL, we separate the analysis in two graphs. Fig. 11 Fig. 8. Main effect plot for d, nlimr, nlimp and T. Fig. 9. Interaction plot for n and d. I. Ribas et al. Expert Systems With Applications 184 (2021) 115535 8 shows the interval plot of RPD considering the effect of setup times and swap and insert procedures, which are the two tested in SSA. Note that, in Fig. 9, in the Insert level, if the insert neighborhood is included in the local search it is denoted by 1, if not it is denoted by −1 and, at the SWAP level, it is denoted as Yes - No if the swap neighborhood is included or not. Hence, in the level SWAP =yes we can find two values of Insert: −1 means that only the swap neighborhood is considered and 1 means that both neighborhoods (Swap and Insert) are considered. In this figure, it can be observed that the insert procedure is more effective than the swap one, but using both produces better results. It is worth noting that for larger setup times the performance of searching in the swap neighborhood decreases, as can be seen by comparing the interval RPD between level 1 and level 2 or levels 2 and 3 of setup times. A similar analysis is made for the local Search MIL. In this case the reassignment neighborhood (Reassigment in Fig. 12) is the one with the poorest performance, but, as can be seen in this figure, the combination of both neighborhoods leads to better performance. This confirms our choice for setting nlimp with a higher number of iterations than nlimr, in order to give more time to search in the best-performing neighborhood. Here again, we can see that the level of setup time is significant. The longer the setup time, the poorer the performance of the reassignment procedure. In Fig. 12 it is hard to see if the differences between the variants are significant, due to poor performance from using only the reassignment procedure that forces a large scale in the Mean RPD axis. Therefore, it has been excluded from the analysis. In Fig. 13 it is evident that the Reassignment and Permutation procedure is highly recommended for low levels of setup times, whereas when the setup times increase, the difference between using only the permutation procedure or both is reduced. Finally, Fig. 14 shows the significant but, almost irrelevant, interaction between SSA and MIL. It is clear that the two local searches used, inside and between lines, perform better when the two neighborhood (Insert-Swap and Reassignment-Permutation) are used. It is also clear that Insert and Permutation are more efficient than Swap and Reassignment. 5.2. Computational evaluation of the IG In this second test, we start comparing the 5 simple constructive heuristic proposed for the initial solution procedure: LPT5, TRA5, RCP0, PF23 and HPF3. These are very fast methods that require little CPU time. The test instances used were the same that in the previous test and, as mentioned before, they are different from the calibration instances. The 5 constructive procedures were coded in QB64 and tested on a computer 3,40 GHz Intel Core i7-3770 CPU with 8 GB of RAM. The response variable was the RPD calculated as in equation (6) where, in this case, Sol i,j is the makespan obtained by constructive heuristic j in instance i, and Best i is the minimum makespan obtained by any of these constructive methods over the same instance. Table 3 shows the average RPD (ARPD) obtained by number of lines and level of setup time. The fourth column is the overall average by line and the fifth the overall average by method. From these results one can see that the best performing method is TRA5, as it was already showed in (Ribas & Companys, 2021). PF23 and HPF3 shows a poor performance compared to the others and RCP0, specially designed for this problem, is Fig. 10. Interaction plot for F and nlimp. Table 2 Anova: ARPD versus n, m, setup, F, SSA and MIL. Source DF SS MS F P n 5 601.1 120.21 1040.48 0.000 m 3 1681.3 560.44 4850.82 0.000 setup 2 923.9 461.97 3998.49 0.000 F 3 104.6 34.87 301.80 0.000 SSA 2 236.6 118.32 1024.08 0.000 MIL 2 9140.1 4570.06 39555.64 0.000 n*m 15 34.8 2.32 20.09 0.000 n*setup 10 75.6 7.56 65.43 0.000 n*F 15 178.7 11.92 103.14 0.000 n*SSA 10 127.6 12.76 110.41 0.000 n*MIL 10 271.8 27.18 235.28 0.000 m*setup 6 167.2 27.87 241.25 0.000 m*F 9 18.1 2.01 17.39 0.000 m*SSA 6 29.2 4.86 42.07 0.000 m*MIL 6 402.4 67.07 580.53 0.000 setup*F 6 10.7 1.79 15.47 0.000 setup*SSA 4 106.9 26.74 231.42 0.000 setup*MIL 4 81.5 20.38 176.42 0.000 F*SSA 6 21.5 3.58 30.98 0.000 F*MIL 6 1153.5 192.26 1664.04 0.000 SSA*MIL 4 33.1 8.27 71.57 0.000 Error 25,785 2979.1 0.12 Total 25,919 18379.5 I. Ribas et al. Expert Systems With Applications 184 (2021) 115535 9 in the third position. It is worth noting that the ARPD of TRA5, LPT5, PF23 and HPF3 increases when setup time increases whereas RCP0 shows the contrary behavior. Although all these methods take little CPU time, it is interesting to observe the time difference between them. Fig. 15 shows the scatterplot between the average RPD (ARPD) and the average CPU (ACPU) time used by each procedure. In it can be observed, that the best performing methods (TRA5 and LPT5) require about 4 times more than the other three methods. This is so because both methods include an improvement phase embedded in the process. Notice that for each job, once the line is selected, it is tested in all positions in the sequence and placed in the position which results in its minimum C max . This fact leads them to obtain better solutions but with higher CPU time. RCP0, which was especially designed for the problem dealt with, obtains solutions of certain quality with a little CPU time. Finally, PF23 and HPF3, although as constructive methods do not reach good solutions, they can be also good candidates to help IG to reach better solutions because are very fast methods and both create a sequence considering the minimization of timeout of machines. Therefore, the next step is to analyze the effect of the initial solution procedure in the performance of the IG algorithm and to establish the best method to be implemented in the proposed IG algorithm. The set of instances used in this test are the same as in the second test. The response variable was the RPD calculated as in equation (6) where, Sol i,j is the makespan obtained by variant j of IG algorithm in instance i, and Best i is the minimum makespan obtained during this research over the same instance. The results were analyzed by means of an ANOVA (Table 4) where Algorithms are the variants of IG with the different initial solutions. Here, one can see that all the factors and their interactions are significant. Fig. 11. interval plot of RPD by setup times, swap and insert levels. Fig. 12. Interval plot of RPD by Setup times, Reassignment and Permutation levels. I. Ribas et al.