Permutation flowshop scheduling with periodic maintenance and makespan objective

Permutation Flowshop Scheduling with periodic maintenance and makespan objective ∗ Paz Perez-Gonzalez1† , Victor Fernandez-Viagas1, Jose M. Framinan1 1Industrial Management, School of Engineering, University of Seville, Ave. Descubrimientos s/n, E41092 Seville, Spain, {pazperez, vfernandezviagas, framinan}@us.es March 26, 2020 Abstract In this paper, we address the permutation flowshop scheduling problem with cyclical unavailability periods where no operation can be processed. Under this constraint, all machines must stop at the same time due to the shift calendar (shift changes, nights, weekends, etc.), or due to preventive deterministic and fixed maintenance activities. For this reason, this constraint is known in the literature as periodic maintenance. Although different decision problems dealing with the simultaneous scheduling of jobs and maintenance activities have been studied in the literature, scheduling with periodic maintenance has been only addressed for the single machine and parallel machines layouts, and we are not aware of references tackling the flowshop. In this layout, different scheduling problems arise depending on the assumptions about the preemption of the operations. Here we focus on scheduling jobs in a flowshop with the objective of minimising the makespan assuming that the preemption of operations is not allowed, and therefore, if an operation cannot be finished within the current availability period, then it should be scheduled in the next one. The structure and hardness of the problem depending on the size of the availability periods is studied using Mixed Integer Linear Programming and complete enumeration, in order to determine the range of values for the availability period that makes the problem under consideration to be substantially different than its classical (unconstrained) counterpart. For these cases, specific heuristics with different computational complexity are developed, and an extensive computational experience is carried out to establish the efficiency of the proposed heuristics. ∗This is the Submmited Manuscript of an article published by Elsevier in Computers and Industrial Engineering 143, 106369 available online: https://doi.org/10.1016/j.cie.2020.106369 †Corresponding author. Tel.: +34-954487214. 1 Keywords: Permutation flowshop scheduling, makespan, Heuristics, periodic maintenance, shift calendar, cyclical availability constraint 2 1 Introduction In most manufacturing scheduling literature it is usually considered that machines are available during all the scheduling horizon. However, a number of causes (such as e.g. scheduled stops, machine breakdowns, etc.) may generate unavailability periods in the machines, so the jobs cannot be processed in these periods. In this paper we are interested in a special case of unavailability constraint, quite common in manufacturing companies, where all machines stop periodically after a given time interval. Some examples of these unavailability periods can be produced by periodic maintenance activities, breaks, end of shifts, etc. More specifically, our work is motivated by the natural interruption of work in the factory between one shift and the next one. In this case, a working shift has a constant duration and, since workers may change from a shift to the next one, unfinished operations are not allowed. This is a usual practice in many manufacturing companies with relatively complex manual operations, such as the assembly of wiring harness in the aerospace industry, where shifts are formed by different teams of workers and having one worker to complete the tasks of a previous worker is not desirable in terms of efficiency and quality of the operation. In our research, this periodic unavailability constraint, denoted in the scheduling literature as periodic maintenance, takes place in a flowshop layout where jobs are processed in the machines following all of them the same route. Furthermore, the order of jobs in all machines is the same (permutation assumption). Note that different scheduling problems can be defined depending on the assumption regarding the preemption of the operations. In our paper, operation-related preemption is not allowed, so if an operation cannot be finished in a working shift, then it should be scheduled in the next one. This problem is denoted as Permutation Flowshop Scheduling Problem with Periodic Maintenance (PFSP-PM), and the objective function to be minimised is the maximum completion time of the jobs (makespan), which is known to be related to the maximisation of the production rate (Framinan et al., 2014), being the most-studied objective in the permutation flowshop scheduling literature (Fernandez-Viagas et al., 2017). Although scheduling problems considering unavailability constraints have been widely studied for different layouts (see e.g. Ma et al., 2009 for a review on the topic), this is not the case for the flowshop layout, where only very specific cases have been addressed: Allaoui et al. (2006) and 3 Xu et al. (2018) consider an unavailability period on the first machine in a two-machine flowshop, while Labidi et al. (2018) study the two-machine flowshop scheduling problem with unavailability and additional new constraints such as no-wait and non-zero release dates. Finally, Perez-Gonzalez and Framinan (2009) and Fernandez-Viagas and Framinan (2017) consider the m-machine flowshop with an unavailability period on each machine only at the beginning of the scheduling horizon. On the other hand, focusing on scheduling papers with periodic maintenance, the problem has been studied for a single machine (see e.g. the recent papers by Angel-Bello et al., 2011; Yu et al., 2014; Yazdani et al., 2018; Perez-Gonzalez and Framinan, 2018), and for parallel machines (see e.g. Kaabi and Harrath, 2019). To the best of our knowledge, this constraint has not been considered in the flowshop layout. Note that, since the single machine case with periodic maintenance is NP-hard in the strong sense (Hsu et al., 2010; Low et al., 2010), PFSP-PM is NP-hard even for two machines, in contrast to the classical counterpart (Permutation Flowshop Scheduling Problem or PFSP) where Johnson’s rule is optimal for a two-machine flowshop. However, it is clear that, if the availability periods are sufficiently long, it may be possible to schedule all jobs within the shift, therefore the unavailability constraint would not apply, and efficient methods for PFSP could be used. Therefore, it is of interest to establish the range of values of the availability periods that make the PFSP-PM to be different than the PFSP. For these cases, specific approximate algorithms would have to be developed, as it is foreseeable that borrowing methods from the PFSP may not yield good solutions for PFSP-PM. The remainder of the paper is structured as follows: The PSFS-PM problem is described and formalised in Section 2. Some properties of the problem and a mixed integer linear programming model (MILP) are presented in Section 3 in order to carry out a computational analysis to determine the hardness of the problem and its relation with the classical PFSP. To do so, an extensive testbed with different instance sizes and values of the availability periods is presented in Section 4. The results of the analysis are discussed in Section 5. For the cases where the PFSP-PM is found to be different than the PSFP, specific approximate procedures are proposed in Section 6. These procedures are subsequently tested in an extensive computational experience in Section 7. Finally, the conclusions obtained are presented in Section 8. 4 2 Notation and identification of related decision problems The permutation flowshop scheduling problem consists of scheduling njobs in mmachines, such as each job has an operation on each machine, and the route of the jobs is the same for all of them. Operation of job jin machine ihas a processing time pij . The permutation constraint is considered, i.e. the sequence of jobs is the same for all machines, and the objective is the makespan, Cmax, defined as the completion time of the last job in the last machine. Additionally, jobs are available at the beginning of the scheduling horizon. Without further considerations, the so-defined problem is the Permutation Flowshop Scheduling Problem (PFSP). In our problem, there is an additional constraint related to the availability of the machines: i.e. each Tunits of time, all machines are not available during τunits of time. The most critical assumption with respect to the unavailability constraint considered in the literature (Ma et al., 2009) is related to different hypotheses about the preemption of the jobs if they cannot be completed within an availability period: •Resumable case (rs). If an operation cannot be finished before the unavailability period, it is preempted and it can continue when the machine is available again. •Non-resumable case (nr). Preemption is not allowed and the disrupted operation has to restart completely rather than continue. •Semi-resumable case (sr). The disrupted operation will have to partially restart, usually multiplying the remaining processing time by a factor α > 1. Furthermore, in the permutation flowshop layout, each one of the above preemption-related assumptions can be considered at operation level (see Figure 1), or at job level (see Figure 2). By combining the assumptions and the levels, the following problems can be identified and noted extending the notation by Graham et al. (1979) and Low et al. (2010): •Operation level: 5 Figure 1: Permutation flowshop scheduling with periodic maintenance: Operation level Figure 2: Permutation flowshop scheduling with periodic maintenance: Job level –Resumable periodic maintenance (rs −pm): It is easy to see that the problem Fm|prmu, rs −pm|Cmax is equivalent to the classical problem Fm|prmu|Cmax, which has been widely studied in the literature. –Non-resumable periodic maintenance (nr −pm): In this case, operations cannot be preempted, and if an operation cannot be finished in a shift, then it is scheduled in the following shift. This problem, denoted Fm|prmu, nr −pm|Cmax, is NP-hard in the strong sense as explained previously since 1|nr−pm|Cmax is NP-hard in the strong sense (Hsu et al., 2010; Low et al., 2010). To the best of our knowledge, this problem has not been studied before, and it is the motivation of our research. 6 –Semi-resumable periodic maintenance (sr −pm): The operation may be preempted if it cannot be finished in a shift, and the remaining processing time is modified when it is processed in the following shift. The resulting F m|prmu, sr −pm|Cmax problem has not been considered previously in the literature either. •Job level: –Resumable periodic maintenance at job level (rs−pm(job)): The job can be preempted, although the operations of the jobs cannot be interrupted. I.e. if one operation cannot be finished in a shift, it is scheduled in the following shift, and the job has operations within different working shifts. In this case the problem is denoted Fm|prmu, rs − pm(job)|Cmax. Note that this problem is equivalent to the Fm|prmu, nr −pm|Cmax problem, i.e it is equivalent to the non-resumable case in the operation level, so the optimal solution is the same for both problems. –Non-resumable periodic maintenance at job level (nr−pm(job)): All operations of a job must be scheduled in the same shift, i.e if all operations cannot be finished in a shift, the complete job must be scheduled in the next shift. In this case the problem is denoted as Fm|prmu, nr −pm(job)|Cmax. This problem is different to the resumable case and to the operation level problems defined previously and it has not been considered in the literature. –Semi-resumable periodic maintenance at job level (sr−pm(job)): When all operations of a job cannot be scheduled in the same shift, those operations scheduled in the following shift have a penalty in the processing times. Note that this problem is different to the semi-resumable case in the operation level. This problem, denoted as Fm|prmu, sr − pm(job)|Cmax, has not been studied before. The problems identified are summarized in Table 1. It can be observed that, out of the six possibilities, four new problems are identified: Fm|prmu, nr −pm|Cmax,F m|prmu, sr −pm|Cmax, Fm|prmu, nr −pm(job)|Cmax and F m|prmu, sr −pm(job)|Cmax. Among these problems, in this paper we address the problem Fm|prmu, nr−pm|Cmax, i.e. the problem with machine unavailability non-resumable at the operation level, which is equivalent to resumable at the job level. As explained 7 Level Resumable Non-resumable Semi-resumable Operation Fm|prmu|Cmax Fm|prmu, nr −pm|Cmax Fm|prmu, sr −pm|Cmax Job Fm|prmu, nr −pm|Cmax F m|prmu, nr −pm(job)|Cmax Fm|prmu, sr −pm(job)|Cmax Table 1: Approaches for permutation flowshop scheduling problems with periodic maintenance constraints in Section 1, in the manufacturing process inspiring this problem, unfinished operations are not allowed since working teams change in each shift, and operations started by a working team should be finished by the same working team. In the next section, we analyse this problem in detail. 3 Problem properties and Mathematical programming model The considered problem, F m|prmu, nr −pm|Cmax, is denoted in this paper as PFSP-PM. As explained previously, this problem consists on scheduling a set of njobs within shifts of length T. Between two shifts there is an unavailability period of length τ. Without loss of generality, we consider τ= 0 since τdoes not influence the scheduling decision, although naturally the value of the makespan would be different. The following observations can be done for the PFSP-PM: Observ. 1. T≥max pij = max{1≤i≤m;1≤j≤n}pij, since each operation should fit in a shift, otherwise, the problem is unfeasible. Observ. 2. T < Cmax(S), ∀Sschedule. Otherwise, if Tis too loose, the problem is tantamount to the PFSP. Observ. 3. The number of shifts used for each schedule is a priori unknown. However, the maximal number of shifts is bounded by max{1,dPm i=1 Pn j=1 pij/Te}. Observ. 4. The PFSP-PM is NP-hard even for m= 2 (see previous section). Observ. 5. The concept of critical path of PFSP (see e.g. Pinedo, 2008) does not apply for PFSPPM. 8 Observ. 6. The reversibility property is not satisfied, even in the two machines problem for the resumable case (see Lee, 1997). Observ. 7. As a consequence of the previous observation, Taillard’s accelerations (Taillard, 1990) cannot be implemented to compute the makespan more efficiently. Taking into account observations 1 and 2, it is clear that the structure of PFSP-PM depends on the parameter T. Hence, PFSP-PM can be unfeasible for small values of T(i.e. when T < max pij), or the constraint may have no effect for big values of T, converting the PFSP-PM into its classical counterpart PFSP. In order to determine the differences between these two problems, a Mixed Integer Linear Programming (MILP) model can be developed to optimally solve this problem and to compare it with the solutions of the PFSP. According to Stafford et al. (2005), the most efficient MILP for the PFSP is the TS2 of the Wilson family models. The adaptation of this model to the PFSP-PM is described below, using the same notation than in Stafford et al. (2005). Parameters nnumber of jobs mnumber of machines pij processing time of job jin machine i Tlength of the shifts Mbig number. It can be computed as M=Pm i=1 Pn j=1 pij Smaximal number of shifts. According to the Observ. 3, it can be computed as max{1,dM/Te} Indexes iMachines 1 ≤i≤m jJobs 1 ≤j≤n lPositions 1 ≤l≤n sShifts 1 ≤s≤S 9 n m 100 200 300 400 500 600 700 800 900 1000 C∗ max 5 2 16.978 5.148 3.467 0.000 0.000 0.000 0.000 0.000 0.000 0.000 5 25.470 13.713 5.101 4.566 2.266 0.000 0.000 0.000 0.000 0.000 10 29.731 16.058 8.389 5.534 3.518 3.748 2.589 0.706 0.168 0.000 10 2 16.231 1.891 0.648 0.708 1.076 0.322 0.000 0.000 0.000 0.000 5 20.183 9.368 4.373 2.686 2.635 1.978 1.816 0.215 0.000 0.000 10 29.466* 13.989 8.080 5.158 4.853 2.622 2.141 2.415 2.353 1.383 Total 23.010 10.028 5.010 3.109 2.391 1.445 1.091 0.556 0.420 0.230 CPU PFSP-PM 142.24 13.65 2.15 1.27 0.93 0.86 0.50 0.58 0.51 0.39 UB 5 2 26.551 14.433 5.711 0.000 0.000 0.000 0.000 0.000 0.000 0.000 5 35.805 19.255 8.673 8.255 3.523 0.000 0.000 0.000 0.000 0.000 10 35.159 23.337 12.243 8.518 5.595 6.290 4.232 1.443 0.379 0.000 10 2 33.123 18.792 11.665 6.763 4.409 1.370 0.000 0.000 0.000 0.000 5 38.560 21.261 12.782 9.381 6.534 5.401 3.136 0.286 0.000 0.000 10 39.839 24.653 16.196 12.165 10.798 7.160 6.425 5.890 6.058 4.522 Total 34.840 20.288 11.212 7.514 5.143 3.370 2.299 1.270 1.073 0.754 Table 3: ARPD and CPU time of the optimal solution for PFSP-PM, and ARPD for the evaluation of the optimal solution for PFSP. * Only five instances have been solved optimally solve PFSP-PM for the biggest sizes (n×m= 10 ×10). •The similarity between both problems in specific cases (biggest sizes of T) seems to be clear. However, the decision about to apply or not approximate methods developed for PFSP to PFSP-PM cannot be verified only with the results obtained, since it depends on the distribution of the solutions for both problems. This issue has to be analysed in the following section. 5.2 Empirical distribution of the solutions It is possible to determine the relative frequency (i.e. the estimated distribution) of the values of the objective function for all solutions of the problem by using complete enumeration. By analysing such estimated distribution, it is possible to infer the empirical hardness of the problem, i.e. the likelihood that one solution is close to the optimal solution. This analysis helps to determine which approximate methods should be appropriate to solve the PFSP-PM, since if there are many solutions close to the optimum, then simple methods can be applied to find good solutions, However, if the probability of finding a solution close to the optimum is very low, then sophisticated methods should 16 be developed to efficiently solve the problem. Similar approaches have been conducted by Taillard (1990); Perez-Gonzalez and Framinan (2009); Fernandez-Viagas and Framinan (2015), or Dios et al. (2018). More specifically, we try to determine the values of Tproviding similar empirical distributions for the PFSP and PFPS-PM problems. In this way, if such empirical distributions are similar, we may think about using approximate methods from the extensive literature of PFPS for the PFSP-PM. Otherwise, specific methods for the proposed problem should be developed. To do so, the empirical distribution is plotted by evaluating the n! possible schedules for a given set of instances. For each instance I, the worst makespan value Cw max and the best makespan value C∗ max are computed, and the Relative Deviation Index for each makespan value obtained by evaluating each schedule Sis computed using the following formula: RDI(S) = Cmax(S)−C∗ max Cw max −C∗ max ·100 (11) Once the RDI is obtained for each schedule in an instance, the frequencies of the number of solutions with RDI in each interval [k−1, k) with k= 1,...,100 are represented graphically, providing the empirical probability density function (pdf). Additionally, the cumulative frequencies are represented graphically as well, providing the empirical cumulative distribution function (cdf). As the RDI is normalized by d=Cw max −C∗ max, a solution in the interval [k−1, k) indicates that its makespan is less than d·k% worse than the optimum. Therefore, the higher the frequencies in the right hand of the empirical pdf, the harder the problem is (as more solutions are far from the optimum). The above procedure has been applied to all the instances of the set β2described in Section 4.1. Each instance has been solved using the different values of T∈ {100,200,300,400,500,600,700,800,900,1000, M}. The empirical pdfs are plotted in Figure 3, and empirical cdfs in Figure 4, for all the instances in β2with sizes 5×10, 10×5 and 10×10 respectively. For clarity of presentation, only the results corresponding to T={100,200,400,600,1000, M}are plotted. In Figure 3 and Figure 4, it can be seen that the empirical hardness for T= 100 (blue line) 17 Figure 3: Empirical Density Function Figure 4: Empirical Cumulative Distribution Function and 200 (orange line) are greater than for the PFSP (T=M, red line) for all sizes, presenting a peak in the frequencies of the worst schedules. The behaviour is more clear when the problem size increases. Therefore, T= 100 and T= 200 constitute the hardest cases. This hardness does not seem the same for the three sizes for each value of T. For example, when n6=m, the problem with T= 1000 (brown line) is easier than PFSP, however, for the size 10 ×10, both have a similar pattern. Additionally, for 10 ×10, it can be observed that problems T= 600 (green line) and 1000 (brown line) have the same empirical hardness than T=M(red line), being the case T= 400 (yellow line) empirically easier than T=M. Taking into account the results in Subsection 5.1, and in this section, we can conclude that: •From the empirical distribution, we see that the empirical hardness for T= 100 and T= 200 is greater than for the PFSP. In addition to the difficulty to find good solutions, the previous results show that the evaluation of the optimal solution for PFSP does not provide good 18 solutions for the PFSP-PM in the same cases. Therefore, approximate algorithms developed for PSFP are not expected to provide good makespan values for PFSP-PM. •For T= 300 and T= 400, the empirical distribution for PFSP-PM shows that the problem is easier than PFSP. However, the analysis carried out in Section 5.1 shows that the optimal solutions for PFSP are not good solutions for PFSP-PM. •For T > 400, the empirical distribution for PSFP and PFSP-PM are very similar, and in some cases empirically easier. The evaluation of the optimal solutions provided for PSFP are less than 3% worse than the optimal makespan for PSFP-PM, so in these cases we expect that approximate solutions for PSFP should be good solutions for the PSFP-PM, and therefore, we can expect a good performance of the approximate methods developed for PSFP to be applied to PFSP-PM. As a summary, according to the scope of our analysis, for bigger sizes instances, it is necessary to develop approximate methods for the problem PFSP-PM when Tis tight as compared to the processing times (in the range from one to four times the maximum value of pij , i.e. T∈ {100,200,300,400}). Some efficient heuristics for these cases are presented in the next section. 6 Approximate procedures In line with the conclusions presented in the previous section, it could be interesting to test the performance of approximate methods from the PFSP literature to PFSP-PM. In general, two different approaches can be followed: 1. Adapting the most efficient methods for PFSP to the PFSP-PM. 2. Developing specific methods for the PFSP-PM. Regarding the adaptation of the most efficient methods for the PFSP, different constructive heuristics have been employed, being the NEH by Nawaz et al. (1982) the most used (Framinan et al., 2003; Kalczynski and Kamburowski, 2007, 2008; Fernandez-Viagas and Framinan, 2014). The NEH heuristic, starting from an initial sequence Sini, constructs the best partial sequence S 19 formed by the two first jobs of Sini according to the objective function, and iteratively insert the remaining jobs of Sini in the best position in S. Depending on the procedure to construct Sini and the tie-breaking mechanism (Tie method) in the selection of the best position during the insertion process, different versions of the NEH can be developed. Therefore, in order to adapt this heuristic to the PFSP-PM, we test different initial sequences based on different indicators and criteria as in Framinan et al. (2003). More specifically, 16 indicators have been combined with 8 criteria, providing 54 initial sequences. The best results are obtained by three of them without statistical differences among them. Since one of them is the one used in the original NEH (i.e jobs are arranged in non-ascending order of pj=Pm i=1 pij ∀j= 1, . . . , n), this criterion –denoted as Sini =Sumdecr– has been selected for the subsequent experiments. With respect to the tie-breaking methods, the three most efficient are the original method used by the NEH (i.e. in case of ties, it selects the last evaluated position), the tie breaking method by Dong et al. (2008), and the tie breaking method proposed by Fernandez-Viagas and Framinan (2014). Note that the details of these tie breaking methods are omitted due to the lack of space. Combining these three tie-breaking methods with the best criterion for the initial solution, the following three algorithms are selected as adaptations: •NEH tie0: Sini =Sumdecr and selecting the last evaluated position in case of ties. •NEH tie1: Sini =Sumdecr and the tie breaking method by Dong et al. (2008). •NEH tie2: Sini =Sumdecr and the tie breaking method by Fernandez-Viagas and Framinan (2014). Regarding the development of specific methods for the PFSP-PM, it seems sensible to retain a mechanism similar to that employed by the NEH to construct the solutions, giving its applicability to a wide range of scheduling problems and in order to maintain a similar complexity. However, differences far beyond a mere adaptation are required to incorporate specific knowledge form the PFSP-PM. More specifically, the following heuristics are proposed: •Heuristic H1. This heuristic applies the NEH tie2 starting from an initial solution specifically designed for the problem under consideration. More specifically, this initial solution is constructed as follows: The initial sequence is generated by sorting the jobs in non-descending order of the indicator χj: 20 χj= m X i=1 pij + M X i=2 M·Pi−1 l=1 CTlj i−1 The indicator considers the features of job jin the system in the following way: The first term is the sum of the processing times of this job, giving priority to jobs with shorter sum of processing times. The second term is an estimation of the weighted idle times generated by job j. The weight ( M i−1) provides homogeneity to the values, since the estimation of the idle times are bigger when the index of the machine increases. The terms CTlj are computed for each job jiteratively starting from CT0j= 0 and s0j= 1 as follows: CTlj =        CTl−1,j +plj if CTl−1,j +plj ≤sl−1,j ·T sl,j ·T+plj otherwise l= 1, . . . , M (12) and sl,j =        sl−1,j if CTl−1,j +plj ≤sl−1,j ·T sl−1,j + 1 otherwise l= 1, . . . , M (13) sl,j gives an approximation of the shift where job jwould be processed on machine l, and CTlj approximates the completion times of job jon machine l. In this manner, Pi−1 l=1 Clj is an estimation of the idle time generated by job jin machine iif placed in the first position of the sequence. •Heuristic H2. In the same way than H1, this heuristic applies the NEH tie2 starting from an initial solution, in this case trying to schedule first the jobs with a higher number of operations fitting in a given shift. In this case, the initial solution is constructed as follows: the algorithm starts with all jobs unscheduled in the set Uand an empty sequence Sini. Iteratively, the job σin Uwith more operations fitting into the last current shift (with respect to the first machine) of the partial schedule Sini ∪ {σ}is removed from Uand appended to Sini (ties are broken according to the non ascending order of pj=Pm i=1 pij). The pseudo-code is provided in Algorithm 1. 21 •Algorithm IT. This algorithm is based on the idea that, if a given number of jobs fits in a given shift (i.e. the sum of the processing times of all these jobs is lower than T), then the heuristic NEH can be applied to these jobs as in PFSP (i.e. Tdoes not have influence on the partial sequence formed by these jobs). Therefore, a given initial sequence Sini is divided in partial sequences, each one verifying that the sum of the processing times of all these jobs is lower than T. These partial sequences are merged one by one, and used as initial sequences of increasing sizes for the NEH, in order to fit the jobs in the best possible way (i.e. avoiding idle times). More specifically, the algorithm starts with all jobs unscheduled in the set U, given in the order of a initial sequence, Sini, and an empty sequence S. Iteratively, each job σin Uis removed from Uand appended to Swhile the sum of the processing times (sum) is lower than T. Then, NEH tie2 is applied using Sas initial sequence, and the resulting sequence replaces S(it contains the same jobs in different order). sum is initialized to zero, and the process is repeated, appending to Sthe next jobs from Uthat verify the condition that the sum of their processing times is smaller than T, applying again the NEH tie2 to S. The pseudo-code is provided in Algorithm 2. Three versions of the IT algorithm are tested with the following initial sequences: Sini given by the original NEH (Sumdec), denoted IT NEH; the sequence provided by H1, denoted IT H1; and finally, the sequence provided by H2, denoted IT H2. All methods have the same complexity than the original NEH, O(n3m) (taking into account that Taillard’s accelerations cannot be implemented as explained in Observ. 7 in Section 3) except IT. This method executes iteratively the NEH procedure, a total of K=dPm i=1 Pn j=1 pij/Tetimes, so its complexity is O(Kn3m). 7 Computational experience In order to assess the performance of the heuristics presented in Section 6, they are compared using the testbed for big-size instances developed in Section 4.2. More specifically, the following heuristics have been compared: •Heuristics adapted from the PFSP, i.e. NEH tie0, NEH tie1 and NEH tie2. 22 Algorithm 1 Heuristic H2 1: procedure H2(n,m,T,pij ) 2: Sumdecr = Initial sequence by original NEH (non-increasing order of pj=Pm i=1 pij); 3: U={Sumdecr[1], . . . , Sumdecr[n]}set of unscheduled jobs in the sequence order. 4: k= 1; (Initialization of the position being occupied of Sini) 5: Sini[1] = U[1]; 6: Remove U[1] from Uand dimU =n−1; 7: while k < n do 8: for i= 1, . . . , m do 9: CTicompletion time of machine iby the subsequence Sini 10: end for 11: k+ +; (new position of Sini to be occupied) 12: s=CT1/T + 1; (number of occupied shifts in the first machine by the actual Sini) 13: bestindexU =−1; (Initialization of the best job from U to be inserted in Sini) 14: numbmach =−1; (Initialization of the count of number of machines occupied by a job within the shift s) 15: for j= 1, . . . , dimU do 16: if s·T−CT1> p1U[j]then 17: i= 1; (the first operation fits in the shift sin the first machine) 18: while piU[j]< s ·T−max{CTi−1+pi−1U[j], CTi}and i<M+ 1 do 19: i++; (the operation fits in the shift in the next machine) 20: end while 21: if i > numbmach then 22: numbmach =iand bestindexU =j; 23: end if 24: end if 25: if bestindexU == −1then 26: Sini[k] = U[1]; 27: Remove U[1] from U; 28: else 29: Sini[k] = U[bestindexU]; 30: Remove U[bestindexU] from U; 31: end if 32: end for 33: end while 34: S= NEH tie2(Sini,n); (NEH with tie breaking using Sini with dimension n) return Cmax(S) 35: end procedure 23 Algorithm 2 Algorithm IT 1: procedure IT(n,m,T,pij ,Sini) 2: S=∅,sum = 0 and j= 1; 3: while j < n + 1 do 4: while sum < T and j < n + 1 do 5: for i= 1, . . . , m do 6: sum = +piSini[j]; 7: end for 8: j++; 9: Insert Sini[j] in the last position of S 10: end while 11: S= NEH tie2(S,j); (NEH with tie breaking using Swith dimension jas initial sequence) 12: sum = 0; (Initialization of sum) 13: end while return Cmax(S) 14: end procedure •New heuristics developed for the PFSP-PM, i.e. H1, H2 and IT in its three versions: IT NEH, IT H1 and IT H2. In addition to compare their relative performance, the contribution of each heuristic can be also assessed by comparing these results with the results obtained by its application to the PFSP and the evaluation of the so-obtained schedule for the PFSP-PM. By doing so, it is possible to discern whether the results obtained by each method are due to its suitability for the general PFSP, or not. Therefore, in addition to provide the results for the heuristics, we also provide the results obtained by their application to the PFSP and the subsequent evaluation of the schedule for the PFSP-PM. These results are denoted by the corresponding heuristic with an asterisk, only for the heuristics adapted from the PFSP (note that this is not possible for H1, H2 and IT, as they explicitly require an availability period). As a consequence, the results of the heuristics NEH tie0*, NEH tie1* and NEH tie2* are also presented. We apply each heuristic H∈ {NEH tie0, NEH tie1, NEH tie2, NEH tie0*, NEH tie1*, NEH tie2*, H1, H2, IT NEH, IT H1, IT H2}to an instance Iand compute its RPDHas follows: RPDH=Cmax −CMIN max CMIN max (14) 24 where Cmax is the makespan value of the schedule provided by heuristic Happlied to instance I, and CMIN max the minimum value obtained for instance Iamong all heuristics. All Taillard instances have been solved using different values of Tas previously explained in Section 4. On the one hand, and due to the results obtained in Subsections 5.1 and 5.2, values T∈ {100,200,300,400}have been used in the case with constant T. On the other hand, instances have been solved with variable values of T, depending on parameters rand t. The results are discussed in the next subsections. 7.1 Results with constant T Table 4 shows the Average RPD values for each problem size, and the total in the last row, labelled as Total. The best values obtained are marked in bold. It can be seen that, as expected, the methods applied to the PFSP-PM usually provide better makespan values than the sequence provided for the classical problem evaluated for the PFSP-PM (cases with *) when Tis 100 and 200. In general, NEH tie0*, NEH tie1* and NEH tie2* provide better ARPD values when Tis 300 and 400. These results may be explained by the fact that, in these cases, this problem is more similar to (and easier than) the PFSP than for T= 100 or T= 200 (see Subsections 5.1 and Subsection 5.2). Additionally, it can be seen that the three heuristics developed specifically for the problem provide better results than the adaptations of heuristics from the PFSP, particularly those provided by the algorithm IT (note that the computational cost of this method is higher), being IT H2 the best method with total ARDP of 2.01. Figure 5 shows the 95% confidence intervals, on the left for all methods aggregated for all values of T, and on the right for each value of T. On the left of the figure, it can be seen that IT H2 is the best method, with statistically significant differences with the rest of the methods, except with IT NEH. Among the adapted heuristics, the performance of the NEH tie2 does not have statistical differences with H1 and IT H1, but H2, IT NEH and IT H2 are better with statistical differences. Additionally, on the right, this method has a good performance for all values of T. Similar to the results in Table 4, it can be observed that the methods NEH tie0*, NEH tie1* and NEH tie2* improve as Tincreases, without statistical differences for T= 300 (red) with respect to NEH tie0, NEH tie1 and NEH tie2 respectively, and even better for T= 400 (yellow). NEH tie2 has a good performance for T= 100 (blue), but the differences are not statistically significant with the results 25 Labidi, M., Kooli, A., Ladhari, T., Gharbi, A., and Suryahatmaja, U. S. (2018). A Computational Study of the Two-Machine No-Wait Flow Shop Scheduling Problem Subject to Unequal Release Dates and Non-Availability Constraints. IEEE Access, 6:16294–16304. Lee, C.-Y. (1997). Current trends in deterministic scheduling. Annals of Operations Research, 70:1–41. Low, C., Hsu, C.-J., and Su, C.-T. (2010). A modified particle swarm optimization algorithm for a single-machine scheduling problem with periodic maintenance. Expert Systems with Applications, 37(9):6429–6434. Ma, Y., Chu, C., and Zuo, C. (2009). A survey of scheduling with deterministic machine availability constraints. Computers & Industrial Engineering, 58(2):199–211. Nawaz, M., Enscore, E., and Ham, I. (1982). A Heuristic Algorithm for the m-Machine , n-Job Flow-shop Sequencing Problem. Omega, 11(1):91–95. Perez-Gonzalez, P. and Framinan, J. M. (2009). Scheduling permutation flowshops with initial availability constraint: Analysis of solutions and constructive heuristics. Computers & Operations Research, 36(10):2866–2876. Perez-Gonzalez, P. and Framinan, J. M. (2018). Single machine scheduling with periodic machine availability. Computers & Industrial Engineering, 123:180–188. Pinedo, M. L. (2008). Scheduling: Theory, Algorithms and Systems. Springer Berlin / Heidelberg, third edition. Potts, C. N. and Van Wassenhove, L. N. (1982). A decomposition algorithm for the single machine total tardiness problem. Operations Research Letters, 1(5):177–181. Stafford, E. F. J., Tseng, F. T., and Gupta, J. N. (2005). Comparative evaluation of MILP flowshop models. Journal of the Operational Research Society, 56(1):88–101. Taillard, E. D. (1990). Some efficient heuristic methods for the flow shop sequencing problem. European Journal of Operational Research, 47:65–74. 32 Taillard, E. D. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64:278–285. Vallada, E., Ruiz, R., and Framinan, J. M. (2015). New hard benchmark for flowshop scheduling problems minimising makespan. European Journal of Operational Research, 240(3):666–677. Xu, Z., Xu, D., He, J., Wang, Q., Liu, A., and Xiao, J. (2018). Mixed Integer Programming Formulations for Two-Machine Flow Shop Scheduling with an Availability Constraint. Arabian Journal for Science and Engineering, 43(2):777–788. Yazdani, M., Jolai, F., Taleghani, M., and Yazdani, R. (2018). A modified imperialist competitive algorithm for a two-agent single-machine scheduling under periodic maintenance consideration. International Journal of Operational Research, 32(2):127. Yu, X., Zhang, Y., and Steiner, G. (2014). Single-machine scheduling with periodic maintenance to minimize makespan revisited. Journal of Scheduling, 17(3):263–270. 33