New efficient constructive heuristics for the two-stage multi-machine assembly scheduling problem

New efficient constructive heuristics for the two stage multi-machine assembly scheduling problem Carla Talens Fayos1∗ , Victor Fernandez-Viagas1, Paz Perez-Gonzalez1, Jose M. Framinan1 1Industrial Management, School of Engineering, University of Seville, Camino de los Descubrimientos s/n, 41092 Seville, Spain, April 9, 2019 Abstract In this paper, we adress the two-stage multi-machine assembly scheduling problem where there are several dedicated parallel machines in the first stage and more than one identical parallel machines in the second stage. The objective considered is the minimisation of the total completion time. This problem is NP-hard and the literature surveys indicate that the problem considering several assembly machines has not received much attention. In our paper, we first review the existing solution procedures for the problem under consideration and for related problems, adapt them to our problem and develop two efficient heuristics. The first heuristic constructs a solution taking into account some specific knowledge of the problem domain. This algorithm is embedded into a beam search-based constructive heuristic and its behaviour when the beam width takes different values is analysed. The computational experience carried out shows that the proposals are more efficient than the existing heuristics. Keywords: Scheduling, Assembly, Total completion time, Constructive Heuristics ∗Corresponding author. Email: 1 1 Introduction The two-stage multi-machine assembly scheduling problem has many applications in industry since many products are made up of different components that need to be manufactured in the first stage and then assembled into final products in the second stage, which may consists of several parallel machines. These decision problems are receiving an increasing attention of researchers due to its applications in industry, such as personal computer manufacturing (Potts et al., 1995), fire engine assembly plant (Lee et al., 1993), or distributed database systems (Allahverdi and Al-Anzi, 2006; Al-Anzi and Allahverdi, 2006b, 2007). In this paper we focus on a two-stage multi-machine assembly scheduling problem where there are several dedicated machines in the first stage (e.g. to manufacture the different components of the final product) and more than one identical (parallel) machines in the second stage (e.g. to assembly the components into the final product). Clearly, processing a job in a second stage –which can be done by any of the parallel machines in the second stage– can start only after all operations for this job in the first stage have been completed. The objective is to minimize the total completion time so, according to the classification and notation in Framinan et al. (2018), it can be denoted as the DPm→Pm|| PjCjproblem. This problem is connected to other scheduling problems, i.e. as mentioned in Sung and Kim (2008) and Framinan and Perez- Gonzalez (2017b), it can be seen as a generalisation of the two-machine flowshop problem. For the case with only one machine at the first stage and one assembly machine at the second stage, it is equivalent to scheduling in a flowshop with two machines. Since Gonzalez and Sahni (1978) proved that the Fm|| PjCjis NP-hard in the strong sense, it is clear that the problem under study is strongly NP-hard. While the two-stage assembly problem with only one machine in the second stage has been widely discussed in the literature (see e.g. the recent review on the topic by Framinan et al., 2018), to the best of our knowledge, the problem considering several (identical) assembly machines has received much less attention. Most works addressing this problem consider at maximum two assembly machines in the second stage. Some properties of this problem have been stated in Al-Anzi and Allahverdi (2007) and Lee (2018), while heuristics have been proposed by Al-Anzi 2 and Allahverdi (2006a), Sung and Kim (2008) and Al-Anzi and Allahverdi (2012), and different metaheuristics have been designed and compared in Al-Anzi and Allahverdi (2007), Allahverdi and Al-Anzi (2009) and Al-Anzi and Allahverdi (2012). The main contribution of this paper is to improve the performance of the approximate solution procedures for the problem under consideration by proposing two new constructive heuristics that explicitly use knowledge of the problem domain to construct the solutions. More specifically, we propose a fast constructive heuristic which applies to our problem some dominance properties by Framinan and Perez-Gonzalez (2017b) derived for the case where there is only one assembly machine. In light of the excellent results of this heuristic in negligible computation times, it is embedded into a beam search-based constructive heuristic. This type of heuristic has been developed originally by Fernandez-Viagas and Framinan (2017) for the permutation flowshop scheduling problem, but for our problem we use the idea of keeping only the most promising nodes in each iteration to boost its performance, an idea successfully employed for different scheduling problems (see e.g. Della Croce and T’kindt, 2003, Valente and Alves, 2008, and Valente, 2010). An extensive computational evaluation is performed to show that the proposals are found to be more efficient than existing solution procedures for the problem. The remainder of the paper is organised as follows: the problem is formally described and the state of the art is presented in Section 2. In Section 3, we explain in detail the proposed heuristics: The constructive heuristic is presented in Section 3.1, while in Section 3.2 the beam search heuristic is explained. The computational experiments are conducted in Section 4 and, finally, conclusions are discussed in Section 5. 2 Problem statement and background The problem studied in this paper can be stated as follows: There are njobs to be scheduled in a layout composed of two stages. Each job has m1+ 1 operations. In the first stage, there are m1dedicated parallel machines, in which the first m1operations are conducted, while in the assembly stage there are m2identical parallel machines. Only after all m1operations are completed, the assembly operation may start in the first available machine. A job jhas a 3 processing time pij on machine iin the first stage and an assembly processing time atjin the second stage. The decision problem consists on scheduling the jobs in the two machines so the sum of the completion times of the jobs is minimised. A solution for this problem is determined by giving a sequence of jobs indicating the order in which the jobs are processed (see e..g. Al-Anzi and Allahverdi, 2006a and Al-Anzi and Allahverdi, 2012). Therefore, given a sequence, let [j]denote the job processed in position jin the sequence. C1jthe maximum completion time of job in position jin the first stage can be computed as follows: C1j= max i=1,...,m1    j X k=1 pi[k]   (1) In order to know the first available assembly machine, the completion time of job [j] in each assembly machine is computed as: Ci∗j= max {Ci∗j−1, C1j}+at[j], where i∗= arg mini=1,··· ,m2{Ci,j−1}. Otherwise, Cij =Ci,j−1. Then, Cjthe completion time of the job processed in position jcan be computed as: Cij =Ci∗j(2) As mentioned in Section 1, literature surveys indicate that two-stage assembly scheduling problems have been tackled with respect to different objectives. Lee et al. (1993) and Potts et al. (1995) addressed this problem regarding the minimisation of the makespan. Other objectives are the minimisation of the maximum lateness (Al-Anzi and Allahverdi, 2006b and Allahverdi and Al-Anzi, 2006), additional constraints such as setup times (Al-Anzi and Allahverdi, 2007) or additional stages for the transportation of components (Koulamas and Kyparisis, 2001 and Shoaardebili and Fattahi, 2015). Regarding the aim of our paper, there are few references addressing the case with several machines in the second stage, namely the work by Sung and Kim (2008) and Al-Anzi and Allahverdi (2012). Sung and Kim (2008) develop an heuristic, denoted SAK from now on, applying a processing-time-based pairwise exchange mechanism, while in Al-Anzi and Allahverdi (2012), a mathematical model of the problem with two assembly machines is proposed, together with three new metaheuristics. 4 In view of the relationship of the problem under consideration with other scheduling problems, it is worth also to analyse the existing solution procedures for related problems, namely for the assembly scheduling problem with one machine in the last stage (DPm→1|| PjCjproblem) and the customer order scheduling problem (DPm→0|| PjCjproblem). Regarding the DPm→1|| PjCjproblem, the first reference addressing it is Tozkapan et al. (2003), where the authors prove that permutation schedules are optimal for the DPm→1 problem and propose two heuristics, labelled TCK1and TCK2in the following, to find an upper bound for their branch and bound algorithm. Al-Anzi and Allahverdi (2006a) also address this problem and derive a number of theoretical properties.They propose three simple constructive heuristics (S1,S2and S3) based on the idea of ordering the jobs according to the Shortest Processing Time (SPT) rule, and two additional constructive heuristics, labelled A1and A2in the following. Recently, Framinan and Perez-Gonzalez (2017b) also address this problem and review the problem properties studied by Al-Anzi and Allahverdi (2006a). The authors develop a constructive heuristic, denoted FAP in the following, which outperforms the existing constructive heuristics. The last reference where this problem is considered is Lee (2018). Six lower bounds are proposed and tested in a branch and bound algorithm. They also propose four greedy-type constructive heuristics, labelled G1,G2,G3and G4. Regarding the DPm→0|| PjCjproblem, note that this problem is tantamount to the one under consideration if the processing times of the jobs in the assembly stage are zero. Even if this is not the usual case, both problems would be similar e.g. if the processing times in the first stage largely influence the value of the objective function. Therefore, solution methods for the customer order scheduling problem could be applied to the problem under consideration, hence the interest in reviewing the related literature. For this problem, Sung and Yoon (1998) propose two constructive heuristics based on the SPT rule. The first one schedules the order with the smallest total processing time across all mmachines, labelled ST PT in the following, and the second one selects the order with the smallest maximum amount of processing time on any of the mmachines, denoted as SMPT. Leung et al. (2005) propose a constructive heuristic that selects as the next order to be sequenced the one that would be completed the earliest, that is, the order with the Earliest Completion Time (ECT). Based on this idea and including some 5 look-ahead concepts, Framinan and Perez-Gonzalez (2017a) propose a constructive heuristic and two specific local search mechanisms for the problem, labelled SHIFTkand SHIFTkOP T . After this review, it can be seen that, despite some solution procedures exist for the problem, the performance of the adaptation of procedures from related problems has not been tested so far. Furthermore, there is some opportunity to improve existing methods for the problem by incorporating some knowledge of the problem domain. These methods are presented in the next section. 3 Proposed Constructive heuristics In this section, we propose two heuristics for this problem. First, a constructive heuristic is detailed (Section 3.1) and then we propose a beam search based constructive heuristic (Section 3.2). 3.1 Constructive Heuristic 1 The idea of the proposed heuristic consists of iteratively constructing a sequence by selecting one job among the unscheduled jobs and adding it at the end of the partial sequence, an idea that has been addressed for different scheduling problems by Framinan and Perez-Gonzalez (2017b,a) and Fernandez-Viagas and Framinan (2017) with excellent results. A key issue for the performance of this type of heuristics is the development of a problem-specific indicator ψwhich adequately represents the suitability of an unscheduled job to be appended since, once a job is added to the sequence, its position cannot be modified in the subsequent iterations. Thence, the algorithm starts with a set Ucontaining all (unscheduled) jobs and an empty schedule S. For each iteration j∈(1,· · · , n), each unscheduled job ωl∈ U is analysed as a candidate to be added to position jin S, and its suitability is measured by computing the indicator ψl, and the job in Uwith the lowest value of ψis selected. In our problem, two main aspects are considered to assess the suitability of appending a candidate job ωlat the end of the partial sequence, i.e.: 1. If its inclusion implies that the first available machine in the second stage has to wait for 6 processing the candidate job at the second stage. Therefore, the idle time induced by the insertion of job ωlis computed. Let us ITjdenote the idle time induced by scheduling job jat the end of the sequence. Clearly, ITjis computed as follows: ITj= max {C1j−(Cj−atj),0}(3) Note that Cj−atjcomputes the workload of the first available machine in the second stage before scheduling job j(i.e. the machine in the second stage where the candidate job will be processed). If the idle time induced by scheduling a job is greater than 0, then the completion times in first stage dominate the completion time of this job when it is evaluated as candidate to be scheduled. Otherwise, the completion time of the candidate job is largely influenced by the second stage. As we are minimising the total completion time, it is clear that the lower the idle time caused by a job, the more suitable it is to be scheduled. 2. The contribution of the candidate job to the total completion time. As it can be seen, the idle time takes into account the suitability of the job until its processing in the second stage starts. In addition, its contribution to the total completion time would depend on the processing time in the second stage, i.e. atwl, which roughly measures the influence of the second stage. We weight this influence according to the number of assembly machines (m2) since, with a higher number of machines in the second stage, the next jobs have a lower probability of not being affected by the second stage. Furthermore, to take into account the fact that, the higher the number of components in the first stage, the less likely is for the processing time in the second stage to dominate the completion time, CTl the expected contribution of job wlto the total completion time is measured as follows: CTl=atwl m1·m2 (4) By taking into account the two aspects, we will ensure that the jobs to be first sequences are those with lower values of idle time and assembly time. Therefore, the indicator ψl, which 7 estimates the suitability of appending a candidate job ωlat the end of S, is computed as follows: ψl=a·ITl+CTl(5) where ais a parameter to weight the influence of the two terms and that would be determined via callibration of the algorithm. Note that the complexity of this heuristic is O(n·(n−k)·m1·log m1)∼O(n2·m1·log m1), since the main loop in the algorithm performs niterations. In each iteration, n−kjobs are evaluated, each evaluation consisting on obtaining the maximum processing time in the first stage, i.e. sorting m1elements. The pseudo-code of the proposed heuristic is shown in Figure 1. 3.2 Beam Search Constructive Heuristic The heuristic proposed in Section 3.1 provides excellent results with negligible processing times (see Section 4), proving that the indicator ψproperly captured the suitability of a job to be appended. Therefore, we embed the components of this indicator into a new beam search -based constructive heuristic for the problem, labelled BSCHMMA. This type of heuristic has been considered to solve different scheduling problems, such as in Sotskov et al. (1996) (where some constructive heuristics based on insertion techniques are combined with beam search for the permutation flowshop scheduling problem), Erenay et al. (2010) (for the single machine bicriteria scheduling problem), and Fernandez-Viagas and Framinan (2017) (also for the permutation flowshop scheduling problem). In this type of heuristics, a number of candidate nodes, denoted by a parameter x, are maintained in each iteration. In iteration k, each node l(l∈ {1,· · · , x}) is formed by a partial sequence, i.e. a set of kscheduled jobs, Sl k, and a set of unscheduled jobs, Ul k. Then, all unscheduled jobs in Ul kare inserted in position k+1 of Sl k, thus obtaining x·(n−k) candidate nodes. Out of these nodes, the xmost suitable ones are selected as candidates for the next iteration. Therefore, the ideas behind the use of the indicator ψcould be used in this heuristic. However, an additional complication arises because candidates from different nodes may have to be compared. More specifically, the heuristic may have to deal with one of the following situations: 8 Procedure Proposed Constructive Heuristic NEW // All jobs are initially unscheduled Π := ∅; // Completion times on stages 1 and 2 of sequence S: C1∗ i:= 0 i= 1, . . . , m1 C2∗ i:= 0 i= 1, . . . , m2 s:= arg min1≤i≤m2C2∗ i; Obtain a sequence U:= (ω1, . . . , ωn)by applying algorithm S2; for j= 1 to ndo for each ωl∈ U do // Compute the completion times in the first stage after selecting ωlas candidate: C1(ωl) := max1≤i≤m1{C1∗ i+piωl} // Compute the idle time induced if job ωlis inserted at the end of the partial sequence: ITl= max {C1(ωl)−C2∗ s,0} // Compute the additional completion time induced when job ωlis inserted at the end of the partial sequence: CTl=atwl m1·m2 // Compute the indicator considering the idle time: ψl:= a·ITl+CTl end r:= arg min1≤k≤n−j+1 ψk; Append ωrat the end of Π, i.e. Π := (π1, . . . , πj−1, ωr); Extract ωrfrom U, i.e. U:= (ω1, . . . , ωr−1, ωr+1, . . . , ωn−j+1); // Update values of the constructive sequence: C1∗ i:= C1∗ i+piωr C2∗ i:= max {C2∗ s,max1≤i≤m1C1∗ i}+atwl end return C2∗ i end Figure 1: Pseudo-code of the proposed heuristic NEW. 9 are tested: a∈ {1,2,5,10,15,20,50,200}. •Parameters a0and bfor the BSCHMMA heuristic described in Section 3.2. The following levels for each parameter are tested (in total, there are 56 combinations): –a0∈{0.25, 0.5, 1, 2, 5, 10, 15, 20} –b∈{0, 1, 2, 3, 4, 5, 6} To determine the best combination of parameters, ten instances have been generated for the different values of n,m1and m2, as explained in section 4.3. The processing times of each job in each stage are generated as described in Section 4.2. With this testbed, it has been found that the best results correspond to a= 5. Regarding the BSCHMMA heuristic, it has been assumed that x=nand the so-obtained results compared. The first two levels of a0are discarded due to their poor performance. After proving that the normality and homoscedasticity assumptions are not fulfilled, a non parametric Kruskal-Wallis test is performed. The results indicate that there are significant differences between parameters a0and bsince the significance of both parameters is equal to 0.000. The best combination is obtained for a0=2 and b=2. These values are used for the different versions of BSCH in Section 4.4 and Section 4.5 regardless the value of x. 4.4 Comparison of the different versions of BSCH Prior to conducting a full comparison with existing heuristics, the best variant of the beam-search based heuristics is selected. To do so, the versions of BSCH presented in Section 3.2.1 have been run on the 2,400 instances generated in Section 4.2. The results are summarised in Table 2 using the indicators defined in Section 4.1. The ARP D values range from 1.3196 (BSCHMMA (x= 2)) to 0.5227 (BSCHMMA (x=n+n/2)) whereas ACPU values range from 0.9969 to 0.004. Results are graphically shown in Figure 3 where the y-axis represents the ARPD for each heuristic and the x-axis represents the ACPU. In view of these results, the following conclusions can be derived: •BSCHP(x= 2) with ARPD = 0.6174 improves the variants BSCHMMA (x= 2,x= 5,x =n/10) with ARPD equal to 1.3196, 0.8064 and 0.7708 respectively, using approximately 16 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Average Computational Time 0.5 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 1.4 ARPD Pareto´s frontier BSCHMMA BSCHASC BSCHDESC BSCHV BSCHP Figure 3: ARPD versus average CPU times of the different versions of BSCH with the Pareto frontier. a similar computational effort. •BSCHV(x= 2) with ARPD = 0.5458 outperforms variants BSCHMMA (x= 10), BSCHASC (x= 2) and BSCHP(x= 5), with ARPD equal to 0.6437, 0.6145 and 0.5777 respectively. •BSCHDESC (x= 2) with ARPD = 0.5499 improves variant BSCHMMA (x= 15) using the same ACPU. •BSCHV(x= 5) with ARPD = 0.5324 outperforms variants BSCHP(x= 10) and BSCHASC (x= 5), with ARP D equal to 0.5626 and 0.5760, respectively using the same computational effort. •BSCHV(x=n/10) with ARPD = 0.5295 outperforms variants BSCHDESC (x= 5) and BSCHASC (x=n/10), with ARPD equal to 0.5467 and 0.5815, respectively using the same computational effort. •For x=n, variants BSCHMMA (x=n) and BSCHP(x=n) yield a similar performance, 17 being its ARPD equal to 0.5382 and 0.5348, respectively. Moreover, version BSCHV (x= 10) obtains a similar ARPD = 0.5349 with less computational effort. •The minimum ARPD is achieved by BSCHMMA (x=n+n/2), being the rest of the variants worse with respect to the quality of the solutions. •The Pareto frontier (i.e. the efficient variants with respect to the quality of solutions and the computational effort) is formed by BSCHMMA (x=2), BSCHMMA (x=5), BSCHP (x=2), BSCHV(x=2), BSCHV(x=5), BSCHV(x=n/10) and BSCHMMA (x=n+ n/2). •The performance of BSCHMMA get worse for x= 2n. For this value of x, this heuristic selects 2ncandidates in each iteration, so there are more candidates since the first iteration. Due to this poor results, it has not been considered. To establish the statistical significance of the results, a Holm’s procedure (Holm, 1979) is performed where each hypothesis is evaluated using a non-parametric Wilcoxon signed-rank test assuming a 0.95 confidence level, i.e. α= 0.05. In Holm’s test, the hypotheses are sorted in non-descending order of the p-values obtained in the Wilcoxon test. Each hypothesis is rejected if p < α/(k−i+ 1) where kis the total number of hypotheses. The results can be seen in Table 1, where Rmeans that the hypothesis is rejected by Wilcoxon and/or Holm’s procedure. As can be seen, hypothesis BSCHMMA (x=10) = BSCHASC (x=2) is the only one that cannot be rejected by Holm’s procedure, but it has to be noted that the ARPD achieved by the latter version, equal to 0.6145, is considerably lower than the one obtained by BSCHMMA (x=10). In summary, it can be concluded that the variants in the Pareto frontier in Figure 3 are efficient for the problem. However, as no variant obtains the best performance for all values of x, it can be also concluded that, if x≤nthe best variant is BSCHV, and if x > n, then BSCHMMA is the most efficient one. 4.5 Comparison of heuristics In order to determine the performance of the proposed heuristics (NEW and the best variants of the beam-search based heuristic), these have been compared with existing heuristics for 18 i Hip-value Wilcoxon α/(k−i−1) Holm’s Procedure 1BSCHMM A (x=10) = BSCHASC (x=2) 0.015 R 0.0083 A 2BSCHMM A (x=5) = BSCHV(x=2) 0.001 R 0.0100 R 3BSCHMMA (x=5) = BSCHP(x=2) 0.000 R 0.0125 R 4BSCHMMA (x=10) = BSCHP(x=5) 0.000 R 0.0167 R 5BSCHMMA (x=10) = BSCHV(x=2) 0.025 R 0.0125 R 6BSCHMMA (x=15) = BSCHDESC (x=2) 0.000 R 0.0500 R Table 1: Holm’s procedure for comparison of the different versions of BSCH. x2 5 n/10 10 15 n n+n/2 2n ARPD ACPU ARPD ACPU ARPD ACPU ARP D ACPU ARPD ACPU ARPD ACPU ARP D ACPU ARPD ACPU BSCHMMA 1.3196 0.0040 0.7708 0.0104 0.8064 0.0173 0.6437 0.0279 0.5874 0.0430 0.5382 0.1220 0.5227 0.2685 0.5408 0.5026 BSCHASC 0.5499 0.0268 0.5467 0.0568 0.5360 0.0874 0.5423 0.1229 0.5524 0.1648 0.5282 0.2803 0.5452 0.4638 0.5568 0.7294 BSCHDESC 0.5499 0.0439 0.5467 0.0916 0.5360 0.1406 0.5423 0.1962 0.5436 0.2602 0.5543 0.4189 0.5736 0.6593 0.5790 0.9969 BSCHV0.5458 0.0251 0.5324 0.0522 0.5295 0.0796 0.5349 0.1100 0.5359 0.1442 0.5425 0.2199 0.5576 0.3305 0.5646 0.4821 BSCHP0.6174 0.6482 0.5777 0.6084 0.5825 0.6133 0.5626 0.5934 0.5540 0.5848 0.5348 0.5656 0.5498 0.5806 0.5617 0.5924 Table 2: Summary of results of the different versions of BSCH. the problem, as well as with heuristics adapted from similar problems. More specifically, the heuristics used for the comparison are the following: •Heuristics from the DPm→Pm|| PjCjproblem: –New heuristics proposed in Section 3, i.e. heuristic NEW in Section 3.1 and the variants of the BSCH proposed in Section 3.2 that are in the Pareto frontier found in 4.4: BSCHV(x=2), BSCHV(x=n/10), BSCHV(x=5), BSCHV(x=10), BSCHV (x=15), BSCHMMA (x=n) and BSCHMMA (x=n+n/2). –SAK (Sung and Kim, 2008): This heuristic sorts the jobs in non decreasing order of psumj=Pi=1,...,m1pij +atj. Set k=1 and m=k+1, it exchanges the kth job and the mth job. If the total completion time is improved, it keeps the exchange. If not, m=m+1. –NSDE (Al-Anzi and Allahverdi, 2012): This algorithm has been coded and run, but it has been discarded due to its computational effort is far from the rest of heuristics and the quality of its solution is poor. •Heuristics adapted from the DPm→1|| PjCjproblem. Since this problem is closely related to the one addressed in this paper, it is interesting to test whether heuristics 19 specifically designed for the problem with one assembly machine can be adapted to the problem under consideration. These adaptations are: –TCK1and T CK2(Tozkapan et al., 2003): The original T CK1constructs m1+1 indices for each job, according to PTFij =tij and PTSj=atj. So, m1+1 sequences are obtained by sorting the jobs in non decreasing order of these indicators, and the sequence with the lowest TCT is selected. The index PTSjhas been adapted to our problem so that PTSj=atj/m2. Similarly, T CK2 computes three indices for each job, so three sequences are obtained by sorting the jobs in non decreasing order of these indices, and the sequence yielding the lowest TCT is selected. The indices have been adapted to our problem taking into account m2, i.e.: MP Tj= min{p1j, p2j,· · · , pm1j, atj/m2};APTj=1 m1+m2Pm1 i=1 pij +atj/m2; and MXPTj= max{p1j, p2j,· · · , pm1j, atj}. –A1and A2(Al-Anzi and Allahverdi, 2006a): These algorithms construct a sequence by iteratively appending a job at the end of a partial sequence. For algorithm A1, the job is chosen so that the following indicator is minimised: A1j= max i=1,...,m1    j−1 X r=1 pi[r]+pij   (14) Note that this indicator does not require any adaptation to our problem. However, for algorithm A2the indicator is adapted by dividing the assembly time by the number of assembly machines m2, so the modified index is: A2j= max i=1,...,m1    j−1 X r=1 pi[r]+pij   +atj m2 (15) –S1,S2and S3(Al-Anzi and Allahverdi, 2006a): S1sorts the jobs in non decreasing order of atj. Heuristic S2is obtained by sorting the jobs in non decresing order of maxi=1,...,m1{pij}and, finally, heuristic S3orders the jobs in non decreasing order of maxi=1,...,m1{pij}+atk. As with the previous heuristics, S1and S3have been adapted by dividing atjby m2. 20 –G1,G2,G3and G4(Lee, 2018): Each of these heuristics constructs a sequence by inserting the job with the smallest value of one of the following indicators: G1j= C[j]−C∗ 2;G2j=C1∗ j−C1∗ j−1;G3j=C1∗ j−C∗ 2and G4j=C[j]−C1∗ j. These indicators can be used for our problem in an straightforward manner. –FAP (Framinan and Perez-Gonzalez, 2017b): This heuristic appends one by one the unscheduled jobs at the end of a partial sequence by computing an estimate of the completion times of the unscheduled jobs which takes into account which stage is more important. This estimate has been adapted considering the number of assembly machines so, if the first stage is dominant, then FAPl=C1∗ j+n−j+1 n(C1•+p• m1+m2). Otherwise, FAPl=pωl m1+m2+n−j+1 n(C1•+p• m1+m2). Where C1•is the completion time of and artificial job, composed of the unscheduled jobs, in the first stage, and p•is the processing times of the artificial job in the second stage. •Heuristics adapted from DPm→0|| PjCjproblem. As mentioned before, the order scheduling problem is identical to the problem under consideration if the processing times of the second stage are zero. Therefore, it is also of interest to test how the adaptation of their best methods perform in our case. The most relevant methods for the order scheduling problem are: –STPT (Sung and Yoon, 1998): A sequence is constructed sorting the jobs in ascending order of their sum of their processing times on the m1machines. In our case, m1+m2machines are considered. –SMPT (Sung and Yoon, 1998): A sequence is constructed sorting the jobs in ascending order of their maximum processing time on the m1machines. As with the previous heuristic, m1+m2machines are considered. –ECT (Ahmadi et al., 2005; Leung et al., 2005): In this heuristic, the order with the earliest completion time is selected as the next to be sequenced. This heuristic does not require adaptation, as for each order, the completion time is computed according to Eq. (??). 21 –SHIFTkand SHIFTkOP T (Framinan and Perez-Gonzalez, 2017a): SHIFTkobtains iteratively a partial sequence using the ECT heuristic. Then, the jobs are iteratively removed from their position and re-inserted. The procedure is repeated until the so-obtained partial sequence does not returns a lower total completion time. SHIFTkOP T restarts the reinsertion phase whenever a better sequence is found and repeats the process until no improvement is found. These heuristics have been employed to solve the instances from the testbed in Section 4.2. The ARPD and ACPU are computed according to Eqs. (8) and (10), while indicator ARPT is computed using Eq. (13). The detailed results of ARPD in terms of n×m1×m2are shown in Table 5 and 6. The average results in terms of ARPD,ACPU, and ARPT are shown in Table 3 and graphically in Figure 4. Note that, in this figure, the dispatching rules are not displayed in order to have a clearer interpretation of the results. In view of the results, a number of conclusions can be noted: •NEW (ARP D=1.8742) clearly outperforms heuristics A1,A2,G1,G2,G3and G4using a similar computational effort. It can be seen that NEW obtains very good results evaluating only one job at each iteration and, consequently, consuming less computational time. Furthermore, NEW obtains a similar ARPD than FAP, but our proposal requires much less CPU time. •S2and TCK2with ARPD equal to 15.2527 and 7.5253 respectively are the best dispatching rules. Although the quality of the solution is low, these rules obtain a solution very fast. •BSCHV(x= 2) with ARPD=0.5458 outperforms NEW, with ARPD equal to 1.8742, using the same computational effort, as it can be checked in Figure 4. •BSCHMMA (x=n) with ARPD =0.5382 outperforms SHIFTk,SHIFTkOP T and SAK with ARPD equal to 14.1752, 9.3225 and 12.6792, respectively. Moreover, it can be pointed that this version of the BSCHMMA obtains the best result in terms of quality of the solution, ARPD. 22 Heuristic ARPD ACPU ARPT Heuristic ARP D ACPU ARPT NEW 1.8742 0.001901 625.07 SAK 12.6792 0.359579 102534.03 FAP 1.6644 0.011425 3358.46 STP T 15.8731 0.000005 1.64 G117.4028 0.001870 615.74 SMPT 21.6706 0.000007 2.36 G26.1421 0.001845 605.78 ECT 17.4028 0.036756 10559.23 G36.8172 0.001799 590.66 SHIFTk14.1752 0.122583 34958.62 G417.4652 0.001778 583.61 SHIFTkOP T 9.3225 0.158947 45640.85 A16.0290 0.001816 595.67 BSCHV(x=2) 0.5458 0.025120 7482.71 A29.2572 0.001812 593.95 BSCHV(x=5) 0.5324 0.052197 15574.12 S119.2741 0.000003 1 BSCHV(x=n/10) 0.5295 0.079588 23690.42 S215.2527 0.000006 2.13 BSCHV(x=10) 0.5349 0.110005 32796.73 S316.6488 0.000007 2.3 BSCHV(x=15) 0.5359 0.144172 43052.43 TCK115.3131 0.000764 242.55 BSCHMMA (x=n) 0.5382 0.121981 36705.90 TCK27.5253 0.000344 109.24 BSCHMMA (x=n+n/2) 0.5227 0.268500 78987.16 Table 3: Summary of results of the different heuristics. i Hip-value Mann-Whitney α/(k−i−1) Holm’s Procedure 1NEW =A10.000 R 0.0100 R 2S2=S30.000 R 0.0125 R 3TCK2=TCK10.000 R 0.0167 R 4BSCHV(x=2) = NEW 0.000 R 0.0250 R 5BSCHMMA (x=n) = SHIFTkOP T 0.000 R 0.0500 R Table 4: Mann-Whitney’s procedure. •Taking into account these results and those obtained in the previous section, the group of most efficient heuristics is formed by the dispatching rule S2, the existing heuristic TCK2 and the proposed versions of the beam search constructive heuristic: BSCHV(x=2), BSCHV(x=n/10), BSCHV(x=5), BSCHV(x=10), BSCHV(x=15), BSCHMMA (x=n) and (x=15), BSCHMMA (x=n+n/2). In order to check the statistical significance of these results, Holm’s procedure is used as in the previous computational experience. However, each hypothesis is now analysed using a non-parametric Mann-Whitney test assuming a 95% confidence level (i.e. α=0.05) to establish de p-value of each hypothesis. The results are shown in Table 4. Each p-value is 0.000, so all hypotheses can be rejected. In summary, it can be concluded that the proposed heuristics outperform the existing algorithms for the problem under consideration, as well as the adaptations of efficient algorithms for related problems. 23 10-3 10-2 10-1 100 Average Computational Time 0 2 4 6 8 10 12 14 16 18 ARPD NEW FAP G1 G2 G3 G4 A1 A2 ECT SHIFTk SHIFTkOPT Pareto´s Frontier S1 S2 S3 TCK1 TCK2 SMPT STPT SAK Figure 4: ARP D versus ACP U.ACPU (x-axis) is shown in logarithmic scale. Poner Efficient BSCH versions en vez de border 24 Table 5: RPD of heuristics (I). x=2 x=5 x=n/10 x=10 x=15 x=n x=n+n/2 n m1m2A1A2S1S2S3TCK1T CK2G1G2G3G4ECT STPT SMPT SHIF TkSHIF TkOP T SAK FAP NEW BSCHVBSCHVBSCHVBSCHVBSCHVBSCHMMA BSCHMMA 30 2 2 9.36 9.33 24.48 11.25 12.84 19.16 7.36 16.30 9.56 10.62 16.70 16.30 13.55 22.31 10.81 6.01 9.78 1.66 1.88 0.66 0.53 0.64 0.47 0.54 0.52 0.55 30 2 4 5.33 9.44 19.74 7.93 12.39 15.15 5.98 19.17 5.40 6.26 19.34 19.17 18.24 23.27 14.52 7.00 13.37 1.51 1.55 0.64 0.68 0.65 0.71 0.62 0.70 0.59 30 2 6 3.85 7.15 18.30 6.45 11.07 13.53 5.77 18.86 3.98 4.78 18.97 18.86 18.87 21.98 13.71 4.13 13.70 1.54 1.45 0.49 0.59 0.51 0.56 0.54 0.53 0.59 30 2 8 3.31 6.94 15.44 5.32 10.73 13.37 6.29 18.86 3.34 3.69 18.89 18.86 18.69 20.97 14.02 4.30 13.52 1.34 1.14 0.45 0.39 0.42 0.39 0.49 0.36 0.50 30 4 2 7.34 10.58 22.35 18.75 21.02 16.01 8.84 16.17 7.50 7.18 16.39 16.17 13.69 23.08 12.57 10.34 9.93 1.65 1.85 0.72 0.71 0.83 0.76 0.78 0.75 0.70 30 4 4 5.54 7.86 17.95 17.39 17.55 13.70 6.99 15.98 5.35 4.61 16.06 15.98 14.10 20.98 11.91 6.62 10.28 1.43 1.65 0.52 0.53 0.54 0.55 0.74 0.54 0.68 30 4 6 3.39 7.62 15.93 14.67 15.38 12.21 6.44 15.34 3.65 3.83 15.37 15.34 15.54 18.41 11.54 6.61 11.32 1.46 1.68 0.49 0.61 0.58 0.64 0.57 0.57 0.64 30 4 8 1.95 6.39 14.51 12.74 13.40 11.33 5.83 13.48 2.10 2.21 13.52 13.48 13.06 15.45 10.17 5.54 9.30 1.12 1.23 0.52 0.52 0.45 0.46 0.41 0.50 0.41 30 6 2 5.61 9.00 19.89 18.05 18.27 13.80 8.67 13.27 5.64 5.78 13.40 13.27 11.13 19.52 10.33 8.69 8.14 1.18 1.82 0.69 0.81 0.79 0.68 0.80 0.73 0.77 30 6 4 4.60 7.97 16.08 16.23 16.69 11.84 8.43 14.94 4.85 4.36 15.00 14.94 14.05 18.50 11.16 7.20 10.01 1.52 1.51 0.80 0.85 0.87 0.86 0.90 0.83 0.83 30 6 6 2.80 6.73 15.47 14.18 13.91 11.10 6.31 13.27 2.99 2.85 13.30 13.27 12.65 15.58 9.74 6.46 9.26 1.14 1.16 0.43 0.53 0.46 0.46 0.61 0.53 0.68 30 6 8 2.64 6.18 13.49 12.68 12.38 9.86 5.39 11.64 2.89 3.18 11.65 11.64 11.12 13.58 8.60 5.50 7.97 1.49 1.06 0.43 0.55 0.43 0.36 0.38 0.45 0.52 30 8 2 4.03 8.04 17.86 17.18 17.04 11.80 7.94 12.57 4.18 4.24 12.65 12.57 9.66 19.45 9.32 7.63 6.96 1.32 1.68 0.80 0.85 0.76 0.94 0.80 0.84 0.99 30 8 4 3.31 7.36 14.90 14.87 15.35 10.30 8.39 13.85 3.20 3.87 13.88 13.85 12.82 17.48 10.61 6.85 9.31 1.34 1.67 0.70 0.58 0.64 0.71 0.75 0.74 0.68 30 8 6 2.72 6.13 14.98 13.68 14.58 9.57 6.13 12.69 2.73 3.16 12.72 12.69 11.99 14.85 9.29 5.68 8.21 1.17 1.29 0.59 0.50 0.47 0.50 0.49 0.57 0.65 30 8 8 2.33 5.91 13.14 11.94 12.61 8.87 6.26 11.57 2.27 2.25 11.58 11.57 11.33 13.45 8.61 5.64 8.16 1.19 1.27 0.58 0.57 0.58 0.69 0.62 0.62 0.60 40 2 2 11.38 10.86 27.11 12.82 15.34 22.84 9.06 19.26 11.43 11.99 19.60 19.26 16.73 26.12 15.02 10.36 13.04 2.05 2.25 0.58 0.46 0.57 0.48 0.56 0.48 0.52 40 2 4 9.22 9.29 24.33 10.82 12.77 19.74 7.26 20.49 9.55 9.96 20.62 20.49 19.25 25.13 15.74 7.53 15.07 1.65 1.64 0.77 0.58 0.80 0.56 0.56 0.59 0.55 40 2 6 6.13 7.85 19.13 7.71 11.36 16.44 5.95 20.92 6.38 6.39 20.95 20.92 20.30 24.63 16.33 4.42 16.08 1.85 1.25 0.61 0.55 0.59 0.58 0.54 0.62 0.65 40 2 8 4.87 7.45 19.46 6.72 10.32 16.60 5.86 19.14 5.12 5.54 19.22 19.14 19.10 21.94 14.95 4.57 14.93 1.67 1.37 0.45 0.50 0.54 0.50 0.56 0.51 0.56 40 4 2 8.46 11.07 22.56 22.37 22.90 17.55 8.98 17.06 8.51 9.01 17.21 17.06 13.22 23.88 13.58 11.44 10.16 1.66 2.35 0.55 0.58 0.58 0.66 0.67 0.63 0.52 40 4 4 4.92 9.47 20.19 18.49 19.50 15.50 8.51 18.81 5.07 6.43 18.89 18.81 16.77 23.70 15.06 8.68 13.13 1.46 1.83 0.64 0.54 0.60 0.57 0.67 0.58 0.59 40 4 6 3.58 8.34 18.17 15.52 15.49 13.02 5.61 15.87 3.87 4.24 15.90 15.87 15.00 18.67 12.51 7.69 12.12 1.46 1.40 0.52 0.60 0.61 0.59 0.54 0.69 0.49 40 4 8 3.31 7.01 16.22 15.26 14.30 12.72 6.53 15.03 3.53 3.84 15.06 15.03 14.81 17.24 11.62 7.07 11.35 1.63 1.60 0.58 0.57 0.50 0.55 0.57 0.63 0.49 40 6 2 5.92 10.02 20.21 18.75 19.99 15.51 9.43 15.00 5.93 6.42 15.09 15.00 12.05 22.19 12.42 9.92 9.08 1.50 2.05 0.69 0.67 0.60 0.75 0.73 0.72 0.72 40 6 4 3.57 8.71 17.10 16.59 17.55 13.15 7.10 15.11 3.81 4.77 15.13 15.11 13.64 19.06 12.16 9.22 10.37 1.63 1.63 0.63 0.58 0.57 0.60 0.57 0.55 0.58 40 6 6 2.86 7.54 16.58 15.53 17.83 11.85 7.30 15.65 2.92 4.86 15.69 15.65 15.48 18.86 12.40 7.81 11.73 1.52 1.65 0.74 0.65 0.59 0.69 0.74 0.70 0.53 40 6 8 2.89 7.58 14.79 15.21 15.44 11.56 6.40 15.14 3.33 4.01 15.16 15.14 14.34 17.43 11.78 7.35 11.14 1.42 1.38 0.56 0.48 0.51 0.55 0.56 0.59 0.58 40 8 2 5.22 10.57 17.48 17.67 18.60 13.33 9.45 14.42 5.15 6.42 14.51 14.42 11.36 20.20 11.86 10.86 8.42 1.35 2.08 0.61 0.68 0.58 0.60 0.76 0.65 0.78 40 8 4 4.23 8.73 17.99 16.60 17.62 12.62 7.74 14.61 4.24 4.84 14.62 14.61 13.01 18.59 11.75 9.03 10.01 1.61 1.77 0.60 0.63 0.63 0.66 0.52 0.68 0.51 40 8 6 3.28 7.25 14.88 13.83 14.39 11.41 7.27 13.33 3.33 4.15 13.34 13.33 12.37 16.30 10.53 7.43 9.33 1.29 1.46 0.51 0.52 0.45 0.57 0.58 0.62 0.63 40 8 8 3.16 6.88 14.54 14.53 13.91 10.41 6.67 13.36 2.97 3.70 13.38 13.36 12.87 15.18 10.53 6.48 9.66 1.40 1.51 0.65 0.52 0.57 0.56 0.60 0.56 0.70 50 2 2 13.65 11.44 28.81 14.56 16.52 23.83 8.69 21.17 13.63 13.97 21.43 21.17 18.07 28.37 16.70 11.51 14.51 1.94 2.31 0.48 0.39 0.39 0.41 0.41 0.28 0.39 50 2 4 9.01 9.32 22.68 10.80 14.45 20.56 6.63 23.75 9.43 9.59 23.86 23.75 22.54 29.50 19.17 8.28 18.63 2.09 1.90 0.58 0.44 0.44 0.47 0.43 0.49 0.43 50 2 6 7.78 8.71 21.55 9.70 11.89 18.34 6.06 23.05 8.14 8.39 23.11 23.05 22.27 26.76 18.70 7.76 18.40 1.98 1.64 0.59 0.59 0.59 0.53 0.55 0.55 0.47 50 2 8 6.11 8.32 21.09 8.14 12.15 16.47 6.17 21.82 6.26 6.57 21.85 21.82 21.62 24.27 17.55 5.56 17.63 1.64 1.53 0.52 0.48 0.48 0.42 0.46 0.46 0.50 50 4 2 8.52 11.62 23.51 20.39 22.21 19.35 9.24 17.46 8.76 9.75 17.57 17.46 13.06 25.33 14.74 12.91 10.56 1.81 2.63 0.50 0.47 0.47 0.47 0.41 0.40 0.44 50 4 4 6.92 10.35 21.46 19.96 20.58 16.82 7.25 18.59 7.07 8.35 18.65 18.59 16.96 23.38 15.17 10.85 13.86 1.63 2.18 0.57 0.53 0.53 0.51 0.53 0.46 0.42 50 4 6 4.99 9.48 19.46 17.44 18.16 14.94 7.15 18.35 5.32 6.26 18.38 18.35 17.86 21.62 15.11 9.00 14.59 1.74 1.84 0.49 0.38 0.38 0.39 0.56 0.51 0.47 50 4 8 4.40 8.23 18.10 15.77 17.20 14.46 6.86 18.02 4.28 5.19 18.05 18.02 17.43 20.43 14.62 7.67 14.27 1.67 1.45 0.49 0.50 0.50 0.51 0.46 0.46 0.49 50 6 2 7.28 10.97 20.47 19.16 20.66 16.19 9.43 16.60 7.12 8.77 16.70 16.60 11.98 23.53 13.75 12.19 9.44 1.78 2.36 0.45 0.61 0.61 0.63 0.49 0.53 0.47 25