Constructive heuristics for the unrelated parallel machines scheduling problem with machine eligibility and setup times

Constructive Heuristics for the Unrelated Parallel Machine Scheduling Problem with Machine Eligibility and Setup Times∗ Paz Perez-Gonzalez1† , Victor Fernandez-Viagas1, Miguel Zamora2, Jose M. Framinan1 1Industrial Management, School of Engineering, University of Seville, Ave. Descubrimientos s/n, E41092 Seville, Spain, {pazperez,framinan}@us.es 2CIAT Air Thermodynamics R & D Department, Cordoba, Spain Abstract This work considers a scheduling problem identified in a factory producing customised Heating, Ventilation and Air Conditioning (HVAC) equipment. More specifically, the metal folding section is modelled as unrelated parallel machines with machine eligibility and sequence-dependent setup times. The objective under consideration is the minimisation of the total tardiness. The problem is known to be NP-hard so approximate methods are needed to solve real-size instances. In order to embed the scheduling procedure into a decision support system providing high-quality solutions in nearly real time, our goal is to develop fast, efficient constructive heuristics for the problem. To this end, we select existing heuristics for related problems and adapt them to the problem under consideration. In addition, we propose a set of heuristics with novel repair and improvement phases. The performance of the methods adapted and our proposals are compared with the optimal/approximate solutions obtained by a solver for an MILP in two sets of instances with small and medium sizes. Additionally, big-size instances (representing more realistic cases for our company) have been solved using the proposed constructive heuristics, providing efficient solutions in negligible computational times. Keywords: Scheduling, Constructive Heuristics, Unrelated Parallel Machines, Setup times ∗This is the Submmited Manuscript of an article published by Elsevier in Computers and Industrial Engineering 131, May 2019, pp. 131-145, available online: http://dx.doi.org/10.1016/j.cie.2019.03.034 †Corresponding author. Tel.: +34-954487214. 1 1 Introduction Manufacturing highly customised products requires machines capable to efficiently perform a large number of different operations. Although, in many cases, these machines exhibit a varying degree of flexibility (usually at the expense of requiring relatively high setup times among operations), there may be operations that must be carried out using specific machinery. At the shop-floor scheduling level, this translates into a manufacturing scenario where a job can be only processed on a subset of all machines available –machine eligibility–, and where, in these eligible machines, there may be substantial setup times depending on the specific characteristics of the job to be processed. In this paper, we address the problem of scheduling jobs in unrelated parallel machines with sequence-dependent setup times where not all jobs can be processed on all machines, with the objective of minimising the total tardiness of the jobs. Our work is motivated by a scheduling problem identified in the metal folding section of a factory producing customised Heating, Ventilation and Air Conditioning (HVAC) equipment for large facilities (i.e. airports, shopping malls, etc.). We focus on a particularly complex problem within this factory (see Section 2 for details), which is the manufacturing of the different metal pieces that constitute the boxes and ducts of the air handling units. Given their specific characteristics –size, shape, thickness, etc.– (in some cases they are one- of-a-kind product) together with the large number of these pieces per box, the folding process is carried out by a mix of automated/manual machines, each one with different characteristics and performance, arranged in parallel. A due date for each metal piece can be established by offsetting the equipment’s due date according to the estimated assembly –last step in the process– time, which operates on a FIFO basis. However, it is not advantageous to fold the pieces using FIFO, as the time required to prepare the tools in the folding machines –usually much higher than the processing time itself– is clearly highly sequence-dependent. It is then convenient to process consecutively products with similar shapes so tool changes are minimised. At the same time, not all folding machines can process the dimensions and thickness of the different pieces. All these characteristics conform a scheduling problem on unrelated parallel machines with setup times and machine eligibility. In the company, this problem was being solved according to the experience of the section’s foreman, although, in view of the high number of pieces that have to be scheduled in a shift –around 200–, rather simple rules were used to assign the jobs to the machines, and the schedule of the jobs within each machine was later carried out by each machine supervisor on each shift, who most of the times tried to minimise setup times without a real visibility of the due date of the jobs. As a consequence, delays and expediting ‘hot jobs’ were not uncommon. The initial idea of our research was to explore whether a more formal, model-based, approach for the problem could be used to obtain better schedules. A primary objective of the company is that the jobs are completed not later than their due date, however, the tightness of some of the due dates may render the problem infeasible, so the problem has been modelled with total tardiness objective minimization. The scheduling problem in parallel machines with total tardiness objective is already NP-hard, so it is the problem under 2 consideration and, as a consequence, we focus on developing procedures to provide high-quality (but not necessarily optimal) solutions for a large number of jobs in very short time intervals. More specifically, we propose very fast constructive heuristics that outperform the available heuristics for related problems, which were adapted to the problem under consideration. The structure of the paper is as follows. The motivation is described in Section 2, while the description of the problem and the related literature is presented in Section 3. The problem is modelled as a Mixed Integer Linear Programming (MILP) model in Section 4, so small instances can be solved to assess the performance of the heuristics proposed in Section 5. More specifically, we propose adapted versions of two heuristics from the related literature and new heuristics. All methods are tested on different sets of instances with small-, medium- and big-size instances in Section 6. The computational experience is shown in Section 7. Finally, conclusions and future research lines are presented in Section 8. 2 Background As mentioned in the introduction, the problem under consideration takes place in a HVAC factory located in Southern Spain. The equipments are manufactured in the facility which is divided in two main parts: Metal Manufacturing and Assembly. The first part is devoted to manufacture the different metal pieces of the equipment, while in the second the equipment is build by assembling the metal parts together with the expansion valves, coils, compressors, and the electrical and control systems. The main competitive advantage of the company is to provide the customers with highly customized equipment in very short lead times. Therefore, Sales Managers promise very tight due dates and, once a customer order arrives, the Engineering Department produces a bill of material for each equipment. Since the assembly process is rather stable, due date fulfilment heavily depends on the performance of the Metal Manufacturing Area. Figure 1 shows a scheme of the layout of the Metal Manufacturing Area. Metal sheets enter in the process as raw material using an Automatic Store and Retrieval System (AS/RS), where it is buffered until it is cut in one of the three automated cutting machines. After the cut, each piece obtained can be considered as a reference (job) and is placed in the AS/RS waiting to be folded. The folding section is formed by three stations: the first one is composed by two Automatic Folding machines fed by Robots (AFR), supervised by one or two workers who introduce the technical drawing in the machines to carry out the corresponding folding; the second one is composed of two Automatic Folding machines fed Manually (AFM), with one or two workers feeding and supervising them; and finally, the third station is formed by five manual folding machines fed manually (MFM). Each MFM is fed, operated and supervised by one worker. Depending on the characteristic of the reference (thickness, size, complexity of the folding, ...), it can be folded only in a specific subset of all/some AFR, AFM or MFM. For example, AFR are not able to fold long pieces of sheets, and very small pieces should be processed by MFM. Furthermore, machines of the same type are 3 Figure 1: Scheme of the metal manufacturing process/layout not equal, since they are from different suppliers and age, therefore the processing times of each machine within a type is not the same. Most of the time consumed in the folding process is devoted to setup (i.e. changing tools, feeding, and loading the folding sequence in the case of AFR/AFM). These setup times are not only dependent of the processing sequence –references with similar design require the same tools and consequently less setup time is needed if processed consecutively– but also on the specific machine: For example, the setup activities required for MFM (essentially tool changing) are different to those for AFR (loading the folding programme). If a reference is to be folded in one of the AFR, then it is moved from the AS/RS to the corresponding station, where a robot feeds it to the AFR. Once folded, the robot removes the piece and places it in a buffer. In contrast, the references to be folded in AFM or MFM are moved to the picking area by the AS/RS, where one operator places them in the corresponding AFM or in the buffer for MFM. Once folded, all references are transported in batches to the Painting Section. The Painting Section consists of two painting lines operating under a FCFS policy, as the treatment is usually the same for all references. Painted references are stored in the warehouse, where the references wait to the assembly. If the reference must be insulated, it is moved to the corresponding insulation workstation prior to be transported to the assembly area. A preliminary analysis of the data reveals that the Folding Section constitutes the bottleneck of the Metal Manufacturing Area given the higher capacity of the Cutting and Painting sections. The main problems in the Folding Section stem from two causes: First, cutting is carried out using a machine-proprietary cutting algorithm that optimises the number of pieces that can be obtained 4 from a metal sheet without taken into account further constraints in the Folding Section. Secondly, the scheduling of the references in the Folding section is carried out according to the experience of the section’s foreman, using simple rules to assign jobs to machines and leaving the schedule of jobs within each machine to the machine supervisor on each shift. The idea is then to redesign the process so the scheduling in the Folding Section drives the cutting process and not vice versa. By offsetting the estimated time of the assembly process and that of painting/insulation –which operate under a FIFO policy– internal due dates for completing the folding of each reference can be obtained. The fulfilment of these due dates is critical to ensure that the assembly takes place on time. Therefore, the scheduling problem to be considered contains the following characteristics: •Unrelated parallel machines, implying different processing times for each job (reference) on each machine (folding machine); •Machine eligibility, as each job can be processed in a subset of all available machines; •Machine- and sequence-dependent setup times; •Total tardiness minimisation objective. Note that, although the goal is to finish the jobs before their due date, job tardiness is allowed in order to avoid infeasibility issues. Once the scheduling problem has been identified and the corresponding data gathered/estimated, the decision support system should be implemented by devising solution procedures adapted for the problem, also taking into account the required decision interval (Dios and Framinan, 2016). In our case, decision makers require fast methods to be able to iterate using different sets of jobs. Therefore, we focus on fast, constructive heuristic methods that can be implemented in the decision support system. 3 Problem Statement and Related literature Using the notation by Graham et al. (1979), the problem under consideration can be denoted as Rm|Mj, sijk|PTj. In this scheduling problem, njobs have to be assigned to (and subsequently sequenced on) a set Mof mparallel machines. Each job jhas a different processing time on each machine i, denoted as pij, and a due date dj. Not all jobs can be processed on all machines, so for each job jwe have a subset of machines, denoted as Mj, where it can be processed. Additionally, there are setup times for each machine and each job which are sequence-dependent. Therefore, if job jis processed before job kin a machine ieligible for both jobs, the setup time is sijk. The objective of the problem is to minimize the total tardiness, i.e. PTjwhere Tj= max{Cj−dj,0}, with Cjthe completion time of job j. This problem is NP-hard unless there is a solution where no more than one job is assigned to each machine. Clearly, this case should verify that n≤m, which does not constitute a case of interest. If this rather special case does not happen, then there is at least one machine for which more than one job is assigned. Scheduling jobs in this machine with 5 PTjobjective is well-known to be NP-hard (see e.g. Framinan et al., 2014), so our problem is also NP-hard. A number of papers related to scheduling on parallel machines based on real-world problems have been published in the last years. Gravel et al. (2000) solve a parallel machine scheduling problem inspired in an aluminium foundry considering objectives related to the metal flow; Dolgui et al. (2010) consider a problem related to multi-product metal foundries; or more recently Fu et al. (2017) tackle, in a metal packaging industry, an unrelated parallel machines scheduling problem with job splitting and sequence-dependent setup times. To the best of our knowledge, the problem has not been addressed in the literature, with the exception of a very preliminary work by Carrasco et al. (2017). Some papers address the unrelated parallel machines problem with machine eligibility and setup times with additional constraints. Rambod and Rezaeian (2014) consider the Rm|Mj, sijk|Cmax problem with an additional constraint related to the production of imperfect items and rework processes to achieve an acceptable quality level for these imperfect items. They present an integer (non linear) programming model, and apply Genetic and Bees Algorithms to provide approximate solutions for the problem. Afzalirad and Rezaeian (2015) propose an integer (non linear) programming model to optimally solve the Rm|Mj, sijk, rj, prec|PLjproblem –for small instances–, as well as a Genetic Algorithm and an Ant Colony Optimization algorithm to solve approximately large instances. Later, Afzalirad and Rezaeian (2016) tackle the same problem but considering makespan objective, proposing a Genetic Algorithm and an Artificial Immune System algorithm. Chen (2006) considers machine eligibility and setup times dependent on the job family, i.e. when a job is scheduled after a job of a different type. A Tabu Search based heuristic is proposed to solve the Rm|Mj,family-setup|max Tjproblem. Shahvari and Logendran (2017) consider the Rm|Mj,family-setup, rj, ai, LBf|Fl(PwjCj,PwjTj) problem with sequence and family dependent setup times, where aiindicates initial unavailability periods for machines, and LBfimplies a minimum size (lower bound) for batches. They present an MILP model to solve the problem optimally. Additionally, they develop a metaheuristic based on Tabu Search which solves problems with up to three families, 5 machines and 24 jobs. Regarding unrelated parallel machine scheduling literature considering machine eligibility constraint (without setup times), Al-Salem and Armacost (2002) compare the optimal solutions for the Rm|Mj|Cmax problem to those provided by a constructive heuristic for small instances. Afzalirad and Shafipour (2015) propose a mathematical programming model and two Genetic Algorithms for Rm|Mj|Cmax including resource constraints, i.e. additional resources must be available to process jobs. Small-size instances of the Rm|Mj|Cmax problem with controllable processing times are solved optimally by Low and Wu (2016) with an integer linear programming model, and big size instances are solved approximately by two Ant Colony Optimization metaheuristics. Finally, regarding unrelated parallel machine problems with setup times constraints (without machine eligibility), the Rm|sijk|Cmax problem has been tackled using metaheuristics in the following references: Rabadi et al. (2006) propose a metaheuristic, denoted as Meta-RaPS, Arnaout 6 et al. (2010) provide an Ant Colony Optimization algorithm; Vallada and Ruiz (2011) present two Genetic Algorithms; Ying et al. (2012) a Simulated Annealing method; and finally, Diana et al. (2015) present an Immune-inspired algorithm, using instances by Al-Salem and Armacost, 2002 to compare their proposal to previous methods from the literature. A different objective and approach is considered by Rocha et al. (2008) with an integer linear programming model to solve optimally the Rm|sijk|Cmax +PwjTjproblem for small-size instances. Summarizing, there are some contributions that address scheduling in parallel machines with machine eligibility and setup times, but consider additional constraints that make the problem very different, so adapting these solution procedures does not produce efficient methods for the problem under consideration. Furthermore, most of them do not propose fast, constructive heuristics, which is the focus of our research. On the other hand, from the analysis of the literature with machine eligibility without setup times, Al-Salem and Armacost (2002) provide a constructive heuristic for the Rm|Mj|Cmax problem which can be adapted to our case. We are not aware of constructive heuristics in the literature on parallel machines considering setup times and, among the procedures used to generate the initial schedules for the metaheuristics, the one proposed by Rabadi et al. (2006) for Meta-RaPS metaheuristics is developed for Rm|Mj|Cmax and it seems the heuristic amenable to be adapted for our problem, since Ying et al. (2012) generates the initial solutions randomly, and Arnaout et al. (2010), Diana et al. (2015) and Vallada and Ruiz (2011) use initial solutions specifically designed for other scheduling problems. Therefore, the methods that will be be adapted to our problem are the construction method by Rabadi et al. (2006), and the heuristic by Al-Salem and Armacost (2002). Both methods will be presented in Section 5 but, in order to check the performance of these adaptations, we first present a MILP model in the next section. 4 Mixed Integer Linear Programming Model In this section we present a Mixed Integer Linear Programming (MILP) model adapting the MILP proposed by Vallada and Ruiz (2011) for Rm|sijk|Cmax, which in turn is based on Guinet (1993). The data of the model is presented in the following: iIndex for the machines j,kIndex for the jobs NSet of jobs N∗Set of jobs union a dummy job 0 MSet of machines pij Processing time of job jin machine i sijk Sequence-dependent setup time on machine i if job jis scheduled before job k djDue date of job j VBig number Decision variables are: 7 Xijk      1 if job jprecedes job kon machine i 0 otherwise Cij Completion time of job jon machine i TjTardiness of job j min X j∈N Tj(1) s.t. Tj≥Cij −dj ∀i∈M, ∀j∈N(2) X i∈MX j∈N∗ j6=k Xijk = 1 ∀k∈N(3) X i∈MX k∈N j6=k Xijk ≤1∀j∈N(4) X k∈N Xi0k≤1∀i∈M(5) X h∈N∗ h6=j Xihj ≥Xijk ∀j, k ∈N, j 6=k, ∀i∈M(6) Cik +V(1 −Xijk)≥Cij +sijk +pik ∀j∈N∗,∀k∈N, j 6=k, ∀i∈M(7) Ci0= 0 ∀i∈M(8) Xijk ∈ {0,1} ∀j6=k∈N∗,∀i∈M(9) Tj≥0∀j∈N(10) Cij ≥0∀j∈N, ∀i∈M(11) Equation (1) computes the total tardiness to be minimized. Constraint set (2) computes the tardiness of each job j. Constraint set (3) ensures that each job has only one predecessor and it is assigned to only one machine. Constraint set (4) imposes that the maximum number of successors of job jis one. Constraint set (5) ensures that at least one job is assigned for each machine i. Constraint set (6) checks, for each machine i, if job jis scheduled before job kon that machine, jhas at least one predecessor (i.e. at least the dummy job). Constraint set (7) imposes that a job must not start to be processed until its predecessor has been completed. Constraint set (8) guarantees that the dummy job is the first one to be assigned on each machine i. Constraint set (9) defines the binary variables representing the precedences between jobs. Remaining sets (10 and 11) define the continuous variables of the model. Note that the model presented is valid for the Rm|sijk|PTjproblem, and the machine eligibility constraint is not imposed in the model, but in the data by assigning a very large processing times to those jobs on the machines where they cannot be processed. 8 5 Constructive heuristics Although the MILP model presented previously may provide optimal solutions for small-size instances in reasonable computational times, this is not possible for realistic sizes due to the NP-hard nature of the problem. In this section, we focus on the development of fast heuristics to obtain good (but not necessarily optimal) solutions. As the proposed problem has not been tackled previously (see Section 3), we adapt the existing constructive heuristics by Al-Salem and Armacost (2002) and Rabadi et al. (2006) in Section 5.1. Al-Salem and Armacost (2002) address the Rm|Mj|Cmax problem, so their constructive heuristic focuses on the assignment to the machines, since the scheduling of jobs within each machine is not relevant for makespan. Therefore, we adapt their proposal by considering PTjas objective and schedule the jobs in the machines according to the machine- and sequence-dependent setup times considerations. In contrast, the heuristic by Rabadi et al. (2006) addresses the Rm|sijk|Cmax problem and does not consider machine eligibility, so it has been adapted to our problem avoiding infeasible solutions, and the objective has been modified accordingly. Additionally, we also develop specific constructive heuristics for the problem under consideration, which are described in Section 5.2. Before describing these methods in detail, let us present the notation used in all the heuristics: Mj:= {i∈M:jcan be processed on machine i}is the set of machines eligible for job j, whereas Ni={j∈N:i∈Mj}is the set of jobs that can be processed on machine i. Therefore, |Mj| is the number of machines eligible for jand |Ni|is the number of jobs that can be processed on machine i. Furthermore, we can define Jh={j∈PJ :|Mj|=h}as the set of jobs with heligible machines, with PJ ⊆Nthe set of pending jobs to be scheduled. These sets allow us to classify the jobs according to their flexibility to be processed on the machines. For each machine iand tuple of jobs kand j, the following two indicators SPikj and spij can be defined, where Bis a big number: SPikj =     sikj +pij if i∈Mj∪Mk Bin the opposite case (12) spij =     pij +1 |Ni−1|Pk6=j/i∈Mksikj if i∈Mj Bin the opposite case (13) Note that SPikj gives an indicator of the total processing times (i.e. including setup times) for job jif this job is processed on machine iafter job k.spij thus represents an aggregated estimate of the total processing times of job jon machine i. Furthermore, the following two indices for the machines can be defined: i1=arg min i∈Mj spij (14) 9 Algorithm 4 New Construction 2 1: procedure H4 2: Step 0 3: Set Jh={j∈N/|Mj|=h} 4: Tsum = 0 5: for i= 1, . . . , m do 6: Ci= 0 7: end for 8: Step 1 9: for h= 1, . . . , m do 10: Let Πhbe the sequence of jobs in Jhin non-increasing order of dj 11: for each j∈Πhdo 12: if h= 1 then 13: Let i∗be the eligible machine of j 14: if Ci∗= 0 then 15: Assign jto i∗ 16: Ci∗=pi∗j 17: else 18: k∗=BestPosition(j,i∗) 19: Update Ci∗ 20: end if 21: else 22: (k∗, i∗)=BestPosition Total(j) 23: Update Ci∗ 24: end if 25: Update Tsum 26: end for 27: end for 28: end procedure 16 R/2),e Cmax(1 −τ+R/2)] (see for example Chen (2006), Lin et al. (2010) and Lee et al. (2013)) considering the parameters τ∈ {0.2,0.4}and R∈ {0.2,0.4}where e Cmax = max j∈N Pi∈Mjpij +Pn k=1 sikj n |Mj|·n m The procedure adopted for the generation of machine eligibility is described in Algorithm 5. This method is a combination of the proposals by Alag¨oz and Azizo˘glu (2003) and Gokhale and Mathirajan (2012), so we control the probabilities by a constant, denoted p, and the number of eligible machines for each job. Values of pare taken from {50,80,100}. Algorithm 5 Machine eligibility procedure 1: procedure Machine Eligibility Procedure(p) 2: for j= 1, . . . , n do 3: Generate a random number k∈[1,100] 4: if k≤pthen 5: |Mj| ∈ U[1, m/2] 6: else 7: |Mj| ∈ U[1, m] 8: end if 9: Select randomly |Mj|machines eligible for j 10: end for 11: if ∃i∈Msuch as i /∈Mj∀j∈Nthen 12: Assign randomly a job to i 13: end if 14: end procedure We have considered different values of nand mto generate three sets of instances depending on these parameters. 10 instances per combination have been constructed. •Small-size instances: n={6,8,10,12}and m={2,3,4,5}in the same way than in Vallada and Ruiz (2011). In total, a set of 3,840 instances have been solved optimally using the MILP model to provide an exact comparison for the constructive heuristics proposed. •Medium-size instances: n={15,20,25,30,35,40}and m={2,4,6,8}. This set of 5,760 instances has been generated to test the limits of the MILP model, as it was able to solve the small instances given by Vallada and Ruiz (2011) in negligible computational time (see Section 7). •Big-size instances: n={50,100,150,200,250}and m={10,15,20,25,30}, in the same way than Vallada and Ruiz (2011). This set contains 6,000 instances with sizes similar to the ones described in Section 3. 17 7 Computational Experiments In this section, the MILP (Section 4) and the constructive heuristics (Section 5) are evaluated using the sets of instances described in Section 6. Heuristics have been implemented in C#. Additionally, the MILP model has been implemented in C# using the solver Gurobi (Gurobi Optimization Inc., 2017) with a time limit of 100 seconds. In order to determine the best method among those proposed, we compare FOIM the objective value for each method Mfor each instance Iusing the relative deviation index (Fernandez-Viagas and Framinan, 2015) as follows: RDIIM =F OIM −BestI WorstI−BestI Where BestIand WorstIare the best and worst total tardiness value provided by all methods respectively. Additionally, for each instance Iand for each method Mwe have registered the computational time. The average RDI for a given method for a given set of instances is denoted ARDI. We have carried out a Design of Experiments (DoE) for each set of instances with the following factors: Method, n,m,setup,p,τand R. Therefore, the experiments consist of a full factorial design with 10 observations per combination and response variable RDI. The levels for each factor are the following: •Method (different levels depending on the set of instances): –Small and Medium sizes instances (17 levels): MILP, AA(0.5), AA(0.7), AA(0.9), AA RL(0.5), AA RL(0.7), AA RL(0.9), AA RI(0.5), AA RI(0.7), AA RI(0.9), RMA, RMA2, H1, H2, H3, H4, H5. –Big sizes instances (16 levels): AA(0.5), AA(0.7), AA(0.9), AA RL(0.5), AA RL(0.7), AA RL(0.9), AA RI(0.5), AA RI(0.7), AA RI(0.9), RMA, RMA2, H1, H2, H3, H4, H5. •n(different levels depending on the set of instances): –Small sizes instances (4 levels): 6, 8, 10, 12 –Medium sizes instances (6 levels): 15, 20, 25, 30, 35, 40 –Big sizes instances (5 levels): 50, 100, 150, 200, 250 •m(different levels depending on the set of instances): –Small sizes instances (4 levels): 2, 3, 4, 5 –Medium sizes instances (4 levels): 2, 4, 6, 8 –Big sizes instances (5 levels): 10, 15, 20, 25, 30 18 •setup (2 levels): U[1,49], U[1,124] •p(3 levels): 50, 80, 100 •τ(2 levels): 0.2, 0.4 •R(2 levels): 0.2, 0.4 7.1 Small-size instances All 3,840 instances have been solved in 0.15 seconds on average. In order to test the performance of the constructive heuristics against the optimal solutions, we have solved the instances using all heuristic methods. The CPU times have been less than one millisecond per instance for all methods. Table 2 shows the ARDI values provided for each level of the factors. It can be observed that the best method for this set of instances is H5, with a total average of 5.863% respect to the optimum. This is the best method for all levels of all factors as it can be observed in Table 2. AA RI(0.5), AA RI(0.7) and H3 have similar performance but they provide an ARDI over 72% worse than H5. RMA and RMA2 have the worst performance, so seems better to adapt methods designed for machine eligibility constraint. Note that AA(α) is improved including the algorithm by Lee (1997), AA RL(α), but the performance is better with the Repair and Improvement phases described in Section 5, i.e. AA RI(α). In fact, all the best methods include the proposed Improvement and Repair phases. Figure 2 contains four graphics with Tukey 95% confidence intervals to analyse the influence of the levels of the factor Method on the variable RDI. Figure 2(a) shows the global performance for all methods. It can be seen that H5 is clearly the best method with statistically significant differences. Additionally, Figures 2(b), 2(c) and 2(c) include the results for the factors presenting the most relevant influence (n, setup and τ) and considering only the best methods in order to have a more detailed view of the statistical differences among them. Hence, in Figure 2(b) it can be observed that H5 improves its performance when nincreases, with statistical differences for all levels of this factor to the rest of methods. From Figure 2(c) we conclude that all methods provide better results when setup times are generated in U[1,124], being again H5 the best method statistically different to the others for both levels. In the same way, in Figure 2(d) we can observe that all methods are more efficient when τis 0.2. H5 is the best for both levels with statistic differences. 7.2 Medium-size instances This set of instances has been solved using the MILP solver with a time limit of 100 seconds, and also using the constructive heuristics to compare the results. In this case the RDI values are computed with respect to the minimum obtained for all methods since not all instances (5,699 out of 5,760, 98.96%) have been solved optimally within the time limit. For this reason, in Table 3 the ARDI of the MILP is different to zero. Taking into account that for some instances the solver has 19 AA(0.5) AA(0.7) AA(0.9) AA RL(0.5) AA RL(0.7) AA RL(0.9) AA RI(0.5) AA RI(0.7) AA RI(0.9) H1 H2 H3 H4 H5 RMA RMA2 n 6 30.307 34.023 39.690 21.375 21.863 25.870 10.885 11.095 14.535 21.930 15.144 12.460 13.182 6.883 54.368 42.391 8 26.829 31.654 39.055 21.571 25.098 32.324 10.464 10.314 15.343 20.546 13.178 11.676 12.455 6.225 58.421 43.971 10 25.409 29.418 36.470 21.965 25.432 32.107 10.245 10.353 15.875 18.431 11.616 10.545 12.551 5.465 57.184 43.613 12 23.406 26.728 33.824 20.940 24.127 31.385 9.795 8.617 16.001 16.619 9.263 8.219 12.569 4.877 56.804 45.547 m 2 23.181 23.847 25.855 22.226 22.944 25.299 11.781 11.328 14.367 14.275 8.405 8.042 20.852 7.356 52.872 52.806 3 25.339 30.047 36.746 21.767 25.631 32.759 9.786 8.511 14.992 18.316 12.642 9.348 11.372 5.159 53.142 42.662 4 29.437 33.579 42.252 22.479 25.331 32.968 10.365 10.067 16.329 21.315 14.096 12.200 10.955 5.911 58.113 42.302 5 27.993 34.351 44.185 19.379 22.615 30.660 9.457 10.473 16.066 23.619 14.058 13.310 7.578 5.025 62.649 37.751 p 50 23.617 28.112 37.589 18.326 21.800 30.392 8.279 7.892 14.391 18.775 11.735 10.285 9.437 4.341 55.667 41.147 80 25.783 29.611 36.031 20.948 23.567 29.618 10.076 9.513 15.197 19.628 11.560 10.244 12.270 5.455 56.401 43.853 100 30.063 33.644 38.159 25.114 27.024 31.255 12.686 12.879 16.729 19.740 13.605 11.645 16.361 7.791 58.014 46.642 setup U[1,49] 24.256 28.682 35.307 20.057 23.183 28.659 12.039 10.599 16.831 23.635 15.097 13.305 15.136 6.946 54.051 39.323 U[1,124] 28.719 32.230 39.212 22.869 25.077 32.184 8.655 9.591 14.046 15.128 9.503 8.145 10.242 4.779 59.337 48.438 R0.2 28.391 32.608 41.100 23.366 25.776 33.889 11.089 10.901 16.368 18.391 12.485 10.602 10.789 5.555 56.622 40.425 0.4 24.584 28.304 33.419 19.560 22.485 26.954 9.606 9.289 14.509 20.372 12.115 10.848 14.590 6.170 56.766 47.336 τ0.2 18.013 21.941 28.432 13.862 16.377 22.255 6.089 6.020 10.137 11.634 5.918 4.977 7.752 2.775 48.395 33.545 0.4 34.963 38.970 46.087 29.064 31.884 38.588 14.605 14.170 20.740 27.129 18.682 16.473 17.626 8.950 64.993 54.216 Total 26.488 30.456 37.260 21.463 24.130 30.422 10.347 10.095 15.439 19.381 12.300 10.725 12.689 5.863 56.694 43.880 Table 2: Average RDI: Small Sizes Instances 20 (a) Average RDI (b) Average RDI depending on n (c) Average RDI depending on setup (d) Average RDI depending on τ Figure 2: Tukey confidence intervals 95% Small Sizes Instances reached the time limit of 100 seconds, its average computational time is 7.98 seconds (see the last row in Table 3), with an average of 48.19 seconds for the biggest size (n= 40 and m= 8). Regarding constructive heuristics, in Table 3 it can be observed that H5 is the best heuristic for this set of instances, with 1.654% of Average RDI. The second best performance is provided by H3 with 4.701% of ARDI. In the same way that the results for small-size instances, RMA and RMA2 do not provide good results. Average CPU times needed for all constructive heuristics are almost negligible as it can be observed in the last row of Table 3. Figure 3 shows the Tukey 95% confidence intervals. Figure 3(a) shows that H5 is the best constructive heuristic. In Figure 3(b) it can be seen that H5 presents the best performance for all values of nsignificantly different to the rest of constructive heuristics, and for the biggest value 21 n= 40 there are not statistical differences between MILP and H2, H3 and H5. Regarding setup times, Figure 3(c) shows that H5 is the best method and significantly different to the rest of the methods for the two levels. However, Figure 3(d) shows a very good performance of H5 when the parameter τis 0.4, with statistical differences with the rest of the methods, but there are not differences between H2 and H3 when τ= 0.2. (a) Average RDI (b) Average RDI depending on n (c) Average RDI depending on setup (d) Average RDI depending on τ Figure 3: Tukey confidence intervals 95% Medium Sizes Instances 7.3 Big-size instances This set of instances has not been solved by the MILP model due to the computational requirements, so the results regarding RDI are computed with respect to the minimal value obtained for all methods. It can be observed in Table 4 that the best method for this set of instances is AA RI(0.5) 22 AA(0.5) AA(0.7) AA(0.9) AA RL(0.5) AA RL(0.7) AA RL(0.9) AA RI(0.5) AA RI(0.7) AA RI(0.9) H1 H2 H3 H4 H5 RMA RMA2 MILP n 15 22.954 26.304 34.938 19.853 22.903 30.582 9.025 10.938 14.492 18.152 9.474 7.692 9.758 3.521 61.053 47.013 0.000 20 18.684 23.060 32.320 16.882 21.163 30.952 6.376 8.865 14.666 15.090 6.898 6.485 7.543 2.444 60.787 46.261 0.000 25 15.137 17.709 27.703 14.093 16.854 26.806 4.421 6.678 12.222 12.375 4.982 4.896 5.445 1.609 57.205 48.553 0.004 30 15.329 17.141 26.300 14.368 16.351 25.785 4.428 5.976 11.094 11.057 3.875 4.319 4.272 0.979 53.452 48.608 0.000 35 12.616 14.519 21.143 12.156 14.072 20.777 3.556 4.915 8.530 8.109 2.426 2.752 2.992 0.753 52.389 50.531 0.004 40 12.228 13.823 19.688 11.465 13.494 19.419 3.330 4.339 7.696 7.122 1.528 2.063 3.632 0.617 48.424 53.432 1.283 m 2 12.386 11.504 11.843 12.315 11.451 11.774 5.052 5.033 5.903 3.257 1.135 1.190 7.282 1.012 47.145 55.879 0.010 4 18.606 20.242 25.948 17.930 19.585 25.615 5.737 7.259 11.229 9.001 3.335 3.042 6.741 1.856 50.936 49.779 0.001 6 17.678 21.787 33.147 15.822 20.019 31.601 5.198 7.936 14.171 15.023 6.236 6.182 5.310 2.139 59.966 46.665 0.002 8 15.961 21.504 37.124 13.145 18.836 33.890 4.771 7.579 14.497 20.655 8.749 8.391 3.096 1.610 64.158 43.942 0.847 p 50 13.633 15.186 24.372 12.361 13.994 23.055 3.329 4.815 9.273 12.932 4.962 5.173 2.999 0.873 51.484 47.450 0.068 80 17.320 19.963 27.845 15.920 18.704 26.655 5.358 7.087 11.741 11.426 4.670 4.346 5.706 1.593 56.811 47.925 0.253 100 17.521 21.129 28.830 16.128 19.721 27.450 6.881 8.953 13.336 11.594 4.960 4.586 8.116 2.496 58.360 51.824 0.324 setup U[1,49] 12.750 15.503 22.068 11.885 14.643 21.028 5.011 6.857 10.580 16.202 6.357 6.478 8.471 2.360 49.121 43.117 0.119 U[1,124] 19.566 22.016 31.963 17.720 20.303 30.412 5.368 7.047 12.321 7.766 3.371 2.924 2.743 0.948 61.982 55.015 0.311 R0.2 16.434 20.818 32.633 15.183 19.538 31.140 5.942 8.160 13.795 9.252 4.703 4.275 4.000 1.355 52.966 45.642 0.323 0.4 15.881 16.700 21.398 14.422 15.408 20.301 4.437 5.743 9.105 14.716 5.025 5.128 7.214 1.953 58.138 52.491 0.107 τ0.2 6.914 9.735 17.212 6.099 8.815 16.173 1.970 2.895 5.528 3.607 0.828 0.763 2.360 0.569 43.485 34.378 0.069 0.4 25.402 27.784 36.819 23.507 26.131 35.267 8.409 11.008 17.372 20.360 8.899 8.639 8.854 2.739 67.618 63.754 0.361 Total 16.158 18.759 27.016 14.803 17.473 25.720 5.189 6.952 11.450 11.984 4.864 4.701 5.607 1.654 55.552 49.066 0.215 CPU time 0.0004 0.0004 0.0004 0.0015 0.0015 0.0014 0.0023 0.0022 0.0021 0.0020 0.0031 0.0040 0.0035 0.0042 0.0000 0.0000 2.5131 Table 3: Average RDI and CPU times (seconds): Medium Sizes Instances 23 with 1.377% of ARDI, being H5 very close with 1.460%. It can be observed that, for example, for the factor τ, when it is 0.2, AA RI(0.5) is better than H5, and the opposite occurs when τ= 0.4. Average CPU times in seconds have been included for all the methods in the last row of the Table 4, being all of them very fast. Figure 4 shows the different graphics with Tukey 95% confidence intervals for the RDI. It can be seen in Figure 4(a) that H5 and AA RI(0.5) do not present significant differences. Figure 4(b) shows that AA RI(0.5) has a better performance than H5 for high number of jobs, being statistically different when n= 250. However, there are not differences between these methods for the two levels of the factor setup, as it can be observed in Figure 4(c). The conclusions observed in the Table 4 can be seen clearly in Figure 4(d), with H5 significantly better than AA RI(0.5) when τ= 0.4 being the opposite for τ= 0.2. 8 Conclusions In this paper we consider a scheduling problem identified in a manufacturing company where more than 200 jobs must be scheduled in a set of unrelated parallel machines every day. Taking into account the different constraints of the manufacturing process, the machine layout and the company’s objectives, the problem can be modelled as Rm|Mj, sijk|PTj, i.e. unrelated parallel machines with machine eligibility and machine and sequence dependent setup times with objective the total tardiness. In addition, the company for which this problem is being studied required very fast methods to be embedded in a decision support system, so we focus on near real-time procedures to solve the scheduling problem, more specifically on constructive heuristics given the NP-hard nature of the problem. First, the problem is modelled using an MILP model in order to be able to assess the performance of the heuristic solutions with respect to the optimal values, at least for those (small) instances that can be optimally solved in reasonable CPU times. Second, we adapt constructive heuristics found in the literature for similar problems trying to include the characteristics of our problem. More specifically, we have adapted the following methods: •The constructive heuristic proposed by Al-Salem and Armacost (2002) for the Rm|Mj|Cmax problem, denoted AA(α) in this paper, with αa parameter of the original algorithm; •A refinement of the AA(α) heuristic that includes an improvement phase based on the constructive heuristic developed by Lee (1997) for the 1|sijk|PwjTjproblem, denoted AA RL(α), and •The constructive heuristic proposed by Rabadi et al. (2006) as initial schedule for their metaheuristic for the Rm|sijk|Cmax problem. Third, we propose different constructive heuristics, labelled H1-H5, where H2, H3 and H5 include two phases named Improvement and Repair. In view of the good performance of AA(α), we have also 24 AA(0.5) AA(0.7) AA(0.9) AA RL(0.5) AA RL(0.7) AA RL(0.9) AA RI(0.5) AA RI(0.7) AA RI(0.9) H1 H2 H3 H4 H5 RMA RMA2 n 50 8.782 13.642 31.135 7.522 12.165 27.265 2.294 4.111 10.807 28.808 6.502 6.637 9.405 0.699 69.973 38.660 100 7.828 8.445 18.309 6.922 7.886 17.959 0.888 1.925 6.970 22.697 3.327 4.120 7.098 0.790 58.791 41.536 150 8.916 6.787 11.089 8.412 6.412 10.955 1.028 1.208 4.537 19.830 2.149 2.595 5.168 1.576 46.404 46.466 200 11.455 7.932 7.645 11.051 7.595 7.569 1.170 1.158 2.919 16.450 1.769 1.679 3.297 1.554 40.236 50.939 250 13.437 8.835 6.442 13.232 8.648 6.394 1.505 1.236 2.155 15.089 1.112 1.697 3.069 2.683 36.780 44.047 m 10 15.514 11.250 11.112 15.064 11.005 10.989 2.447 2.083 3.989 9.959 1.597 1.968 7.338 0.368 39.655 49.761 15 11.523 9.287 13.965 11.084 8.809 13.674 1.418 1.767 5.409 16.891 2.602 3.016 7.291 0.562 43.965 48.303 20 9.519 9.138 16.256 8.774 8.500 15.549 1.244 2.035 6.048 20.743 3.335 3.561 5.905 1.126 50.093 46.858 25 7.052 7.506 15.685 6.391 6.852 14.620 0.854 1.552 5.683 25.104 3.447 3.884 4.049 2.147 55.456 44.370 30 6.808 8.459 17.601 5.824 7.541 15.311 0.922 2.200 6.258 30.176 3.879 4.299 3.453 3.098 63.016 32.355 p 50 10.612 9.163 13.972 9.882 8.539 13.019 1.346 1.716 5.174 23.219 2.912 3.399 3.075 1.838 48.004 41.765 80 11.131 9.390 14.908 10.472 8.771 14.101 1.382 1.996 5.573 20.163 2.802 3.539 5.937 1.437 50.486 43.870 100 8.507 8.832 15.891 7.929 8.314 14.965 1.403 2.070 5.685 18.342 3.201 3.099 7.810 1.105 52.820 47.354 setup U[1,49] 2.457 3.591 7.875 2.292 3.393 7.194 0.675 1.194 3.098 30.571 4.378 5.144 9.066 0.977 34.673 43.161 U[1,124] 17.710 14.665 21.973 16.564 13.690 20.863 2.079 2.661 7.857 10.579 1.566 1.547 2.148 1.944 66.201 45.498 R0.2 6.977 7.782 18.429 6.571 7.339 17.400 1.088 2.084 7.192 13.712 2.531 2.871 4.516 1.626 46.794 45.031 0.4 13.189 10.474 11.419 12.284 9.744 10.657 1.666 1.771 3.763 27.438 3.413 3.820 6.698 1.294 54.080 43.628 τ0.2 1.470 2.583 9.372 1.349 2.434 8.532 0.294 0.616 2.687 4.375 0.297 0.288 3.016 2.448 38.498 37.480 0.4 18.696 15.673 20.476 17.506 14.648 19.524 2.460 3.239 8.268 36.775 5.647 6.403 8.199 0.473 62.375 51.179 Total 10.083 9.128 14.924 9.428 8.541 14.028 1.377 1.927 5.477 20.575 2.972 3.346 5.607 1.460 50.437 44.330 CPU Time 0.0109 0.0108 0.0108 0.0121 0.0120 0.0120 0.0132 0.0132 0.0130 0.0024 0.0039 0.0044 0.0064 0.0073 0.0320 0.1473 Table 4: Average RDI and CPU times (seconds): Big Sizes Instances 25