Flowshop Scheduling Problem with TCIT minimization

Proyecto Fin de Carrera Ingeniería de Telecomunicación Formato de Publicación de la Escuela Técnica Superior de Ingeniería Autor: F. Javier Payán Somet Tutor: Juan José Murillo Fuentes Dep. Teoría de la Señal y Comunicaciones Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2013 Master thesis Industrial Engineering Master Degree Flowshop Scheduling Problem with TCIT minimization Author: Paula Sánchez de los Reyes Tutor: Paz Pérez González Dept. of Industrial Organisation and Business Management School of Engineering University of Seville Sevilla, 2023 Master thesis Industrial Engineering Master Degree Flowshop Scheduling Problem with TCIT minimization Author: Paula Sánchez de los Reyes Tutor: Paz Pérez González Dept. of Industrial Organisation and Business Management School of Engineering University of Seville Seville, 2023 Master thesis: Flowshop Scheduling Problem with TCIT minimization Author: Paula Sánchez de los Reyes Tutor: Paz Pérez González The selection board appointed to judge the above-mentioned work is composed of the following professors: President: Vowel/s: Secretary: agree to grant the qualification of: The secretary of the court: Date: Acknowledgements To my family, especially my parents, my sister and my couple, thank you for the unconditional support you have always given me. To my tutor, for accompanying me and giving me all her help. Sevilla, 2023 I Resumen El Trabajo Fin de Máster presentado aborda la minimización del tiempo total de espera de las máquinas (Total Core Idle time) dentro de un problema determinista de programación del taller de flujo permutado. El interés de la minimización de este objetivo viene estrechamente ligado con la minimización del consumo energético del problema. En este Trabajo Fin de Máster se presenta la adaptación de los métodos más eficientes desarrollados para objetivos clásicos (makespan y total completion time o total flowtime), para la minimización del Total Core Idle time. En cuanto a las heurísticas, NEH, NEH M , LR-NEH y PFH-NEH son las heuristicas adaptadas a nuestro problema. Por otro lado, IG, IGALL y VBIH son las metaheurísticas adaptadas. Además, se aplica una búsqueda local basada en una primera mejora con intercambios generales en todas las heurísticas y metaheurísticas que la contienen. El primer objetivo del documento es la calibración de cada uno de los métodos adaptados, eligiendo así cada uno de los parámetros en cuestión para cada una de las heuristicas y metaheuristicas. Para ello se utilizan las instancias de Taillard. A continuación, una vez calibrados los métodos, se comparan las heurísticas y metaheurísticas utilizando las instancias de Vallada. Finalmente, la conclusión que se obtiene de dicho estudio es la elección de la heuristica construcitva NEH M como las más eficientes dentro de las estudiadas y la VBIH dentro de las metaheuristicas. Por último, cabe señalar que este documento se ha redactado en Latex, el código del método se ha escrito en C, el tratamiento de los datos en Excel y el análisis estadístico en SPSS. III 2Chapter 1. Introduction [ 16 ] explained, it is necessary to understand that scheduling does not it a problem, is a process that is conducted by people to make decisions. Sumarizing, scheduling manufacturing is the decision-making process consisting on assigning the set of operations/tasks required to manufacture a set of products to the existing resources in the shop floor, as well as the time periods to initiate these operations/tasks. Due to the complexity of the scenary, a mathematical model must be used to make decisions. For this purpose, it is necessary to develop scheduling models, methods to solve scheduling problems, and tools and systems to facilitate this. Then, an abstraction of reality to the solved model is assumed. For example, we will assume that it is possible to identify units of resources that can perform these operations/tasks and we will refer to them simply as machines. To the best understanding of the method developed to the manufacturing scheduling, as [ 16 ] mentioned, some concepts must be introduced. The first one is the the definition of the unit to be executed previously mentioned. It is a task, that can be a product, part of a product, or others and is named as job. Some characteristics of these jobs can be whether jobs have the order of operations fixed in advance, the possibility of preemption in operations, or if a precise machine must do a job or can do the job at a different speed than the others. These characteristics that constrain the model cause certain schedules to be unfeasible and therefore, the aim of scheduling is to find at least one feasible schedule. Then, among the feasible schedules, a way of finding the best on must be defined by selecting a criterion or various criteria to compare them. About the criteria, the most common is the non-decreasing function of the completion times of the jobs, as makespan or total flow time. It is a brief intruduction which will be explained with more details throughout the document. Finally, about the representation of this model, is usually represented by a Gantt diagram. This Gantt diagram can be machine-oriented or job-oriented. While in both cases time is represented on the x-axis, machines (first one) or jobs are represented on the vertical axis. Either one of the two represents the schedule of jobs in each one of the machines. For a better understanding, we can look at the figures 1.1. 1.2 Notation As previously introduced, scheduling is a decision process to solve a real problem by a model. Through a model we achieve focus on a certain problem of reality or a simplification of reality that can be solved. There are several types of models: •Mathematical model. 1.2 Notation 3 Figure 1.1 Machine-oriented and job-oriented Gantt diagrams [16]. •Graphical models. •Statistical models. •Simulation models. •Algorithmic models. A scheduling model is a formal abstraction of a (manufacturing) scheduling decision-making problem which is described by considering the system of tasks/operations, the processing constraints and the criteria. It is assumed that a scheduling model contains several numbers of jobs and machines. More specifically we assume that there are N jobs and M machines (N=1,2,...,n M =1,2,...,m). These jobs and machines are independent and all the following data is deterministic: • Task or Operation ( Oi j ): The number of tasks or operations for each job that must be scheduled. According to the scheduling, there are a star time ( SOi j ) and a finish time (EOi j) . • Processing route( Rj ): This is the predefined route that each of the jobs must follow, in other words, the machines order for each job. • Processing time( pi j ): The time that needs each machines to process each job. pi j ≤EOi j-SOi j. • Ready dates ( rj ): The instant of time in which the job is available to schedule. ∀j∈N,i∈M SOi j ≥rj . If is necessary to use a ready date ri j ∀j∈N,i∈ M,SOi j ≥ri j. •Due dates (dj): The instant of time in which ideally must be processed. • Mandatory due dates or deadlines ( dj ): The instant of time it is mandatory to be processed. 4Chapter 1. Introduction •Due windows s [[d− j,d+ j]]: A time interval where a job should be delivered. • Costs, priorities, importance, or weights ( wj ): Is used by models who need to prioritize or give importance to a job. • Release dates for machines ( rmi ): The time in which the machine is available. ∀i∈M,j∈N,SOi j ≥rmi The triplet α|β|γ represents the type shop floor, the restrictions, and the criteria. The α describes the machine environment, which for the case of study is flowshop and is denoted as Fm. The β field represents the constraints. At last, γ field represents the objective to minimize. These three classifications will be explained deeply in the following sections. 1.3 Flowshop The literature classifies the scheduling problems according the machine layout, and according to how the different job processing routes Rjare specified. Flow Shop or flowshop is the layout where every job has a number of operations to be processed on a set of machines. For the best understanding, we can see the Figure 1.2. In this layout there are some assumptions: •The machines are arranged in series, each one with a different purpose. •Each job must visit each machine, in the same specific order. • Each machine can only process a job at the same time. For this reason, there are several jobs waiting for the same machine. •Each job can be processed by one machine at the same time. •The transportation time between stages is considered null. • The order of the jobs in each machine could be different. In many cases, for reasons of simplicity in scheduling it is assumed that the processing sequence is the same for all machines. In a permutation flow shop model all jobs must follow the same machine order (i.e. the first machine is the first one for every job). Solving the non-permutation problem is also more difficult as the possible schedules are (n!) m towards the n! possible sequences for the permutation problem. In order to get a visual idea of the difference, we can see the following figures 1.3 and 1.4 1.4 Problem description Summarising the considered problem involves is the classical PFSP (permutation flowshop scheduling problem), which considers n jobs to be scheduled on m machines arranged in series, and all jobs will follow the same sequence 1.4 Problem description 5 Figure 1.2 Flow layout of flowshop [16]. Figure 1.3 Flow layout of flowshop [16]. Figure 1.4 Flow layout of flowshop [16]. (permutation assumption). Jobs and machines are available at time zero. Preemption of jobs is not allowed. The objective function is to minimize the Total Core idle time (TCIT). The Total Core Idle Time is defined by [ 22 ] as the idle time between two consecutive jobs in a flowshop schedule (see Figure 1.5). It is demonstrated by [ 22 ], who shows that problem PFSP with TCIT is NP-hard in the strong sense. In this master thesis, the interest of this objective function is that, the core idle time is the time that the machine should be in 6Chapter 1. Introduction standby status, consuming less energy than during the processing time of the jobs. The core idle time minimization in the PFSP opens a new line of research in the literature about Energy Efficiency PFSP, due to the relation of this objective with the energy consumption of the system when the machines are idle (stand-by status). As in the classical PFSP, the speed of the machine is not configurable, and the processing times are constant. Additionally, machines may be turned-on once the first job is going to be processed, and turned-off when the last job is finished, so during front and back idle times machines are off instead of the standby mode. Before the definition of the objective function, the components of idle time must be presented: – Front Idle Time of machine i, FITi,2≤i≤m : time before machine i processes the job in the first position. – Core Idle Time of job in position k of machine i, CITi,[k],2≤i≤m,2≤ k≤n : time between the completion time of job in position k 1 and the starting time of job in position k in machine i. – Back Idle Time of machine i, BITi,1≤i≤m−1 : time after the machine i has finished the last job before the completion of the overall schedule. Formally, the core idle time of machine iis defined as CITi= n ∑ k=2 (Ci,[k]−pi[k]−Ci,[k−1])(1.1) Where, pi[k] is the given processing time of job scheduled in position k in machine i , and Ci,[k] is the variable providing the completion time of job scheduled in position kin machine i. Therefore, Total Core Idle Time is defined as TCIT = m ∑ i=1 CITi(1.2) The relation between TCIT and makespan is deeply analysed by [ 22 ]. Taking into account the conclusions from that study, the optimal solution provided by makespan minimization is not the optimal solution for TCIT. However, the relation between both measures is that TCIT minimization provides better results for makespan than the opposite (makespan minimization is not efficient 1.5 Objective of the master thesis 7 Figure 1.5 Front/Core/Back Idle Times (FIT/CIT/BIT) in a PFSP [5]. for TCIT). This means that specific approximate methods from the literature developed for makespan may not provide directly good solutions for TCIT, and specific methods for this new objective should be developed. 1.5 Objective of the master thesis The deterministic permutation flowshop scheduling problem (PFSP) has been widely studied considering different (single) objective functions, usually makespan (see e.g. [ 6 , 24 , 2 , 10 , 12 , 17 ]), total completion time (see e.g. [ 11 , 9 ]), and due-date related objectives (see e.g. [ 32 , 11 , 3 , 13 ]). As, to the best of our knowledge, approximate methods have not been applied to the PFSP with TCIT minimization, in this master thesis, the main idea is to test methods proposed in the literature for related problems, in order to check their efficiency for this objective. Related problems can be PFSP with makespan and total completion time, due to the relation between these objectives and machine idle times [ 22 ]. We have adapted the following approximate methods in the literature developed for makespan to TCIT: the constructive heuristic NEH [ 25 ], and the metaheuristics IG ([ 30 ]), IGALL [ 7 ] and VBIH [ 34 ]. It has not been possible to include in this work the state-of-the-art method by [ 10 ], due to the high computational effort needed by this method in the adaptation, since the accelerations and critical path methods applied to the makespan are not adaptable to the TCIT with similar complexity to the total completion time, see e.g. [ 11 ]. Additionally, we have adapted one approximate methods developed for total completion time: the LR-NEH, since, according to [ 29 ], it is the best constructive heuristic with respect to the quality of the solution. 1.6 Document structure As we have already seen, the document starts with an Introduction (Chapter 1). It is composed of an introduction of the main characteristics of Scheduling 8Chapter 1. Introduction (Section 1.1), contextualizing the notation used (Section 1.2), and following with a description of Flow shop layout (Section 1.3). The next section is the definition of the problem (Section 1.4), and finally, this section in which the document structure is summarized. After this, a literature review is presented (Chapter 2). It is composed by a introduction of the same in which manufacturing scheduling en general terms is presented. After that’s the literature review of the classical problems is developed. Finally, a more specific review of the considered problem is presented. The next chapter details the construcitve heuristics (Chapter 3). More specifically the presented method are NEH, NEH M , PFH-NEH and LR-NEH. The metaheuristics are presented in Chapter 4 . The metaheuristics are IG, IGALL and VBIH. In Chapter 5, the computational results of these heuristics and metaheuristics are presented. The chapter starts with a description of the testbed used as set of instances (Section 6.1), following with the calibration of the heuristics (Section 6.2) and the comparison of the same (Section 6.3). The two following sections are the calibration and comparison of the metaheuristics (Section 6.3 and Section 6.4). Finally, the last chapter of the document presents the conclusions (Chapter 6). 2 Literature Review 2.1 Introduction Manufacturing scheduling has been widely studied in recent times due to its applicability to real cases. Can be found a large number of papers about this topic. More specifically flow shop scheduling has great importance within the scope. The most studied problems are permutation flowshop minimizing makespan (Fm|prmu|Cmax) and permutation flowshop minimizing total flowtime (Fm|prmu|n ∑ j=1 Cj ). For this reason, we can find a lot of heuristics and metaheuristics proposed for these two problems. Another problem studied in the literature and which is related to the objective of our problem is the permutation flowshop minimizing total energy consumption. With regard to the problem addressed in the master thesis, the (Fm|prmu|TCIT ) , the scenario is totally different. Idle times-related objectives have been scarcely considered in the literature. It is clear that the minimization of the makespan is directly related to the minimization of the idle times (see [ 20 ]). However, [ 22 ] analyze the relation between total core idle time (TCIT), defined as the idle times between jobs, avoiding including the front idle time generated by the first job in a given schedule, and the makespan. Taking into account the conclusions from that study, the optimal solution provided by makespan minimization is not the optimal solution for TCIT. However, the relation between both measures is that TCIT minimization provides better results for makespan than the opposite (makespan minimization is not efficient for TCIT). 9 10 Chapter 2. Literature Review 2.2 Fm|prmu|Cmax and Fm|prm|∑Cj In this section, we focus on some of the main methods developed for the classical objectives of makespan and total flow time. [ 25 ] developed the most influential algorithm in the literature for the permutation flowshop problem with makespan minimization i.e. Fm|prmu|Cmax , the NEH. This has marked the entire scheduling investigation. Many papers have been based on improving the proposed algorithm. It should be noted that one of the most important algorithms of the master thesis is the NEH. It was [ 33 ] was improved the complexity of the NEH algorithm, reducing it from O( n3 m) to O( n2 m). [ 15 ]) studied the implementation of different initial sequences for the NEH. It showed that the best initial sequence is the one used in the classical NEH approach (i.e. no increasing order of the sum of the processing). Another heuristic studied in this master thesis is the NEH M proposed by [ 27 ]. It is one of the clear examples of the influence of the NEH in the rest of the heuristics proposed. This method is applied to a hybrid flow shop (multiple parallel machines per stage) minimizing the Total Energy Consumption (TCE). Focused on the total flow time minimization, the LR-NEH proposed by [ 29 ] is implemented. As is noted in this paper is a good trade-off between CPU time and quality. It is a constructive heuristic based on the NEH and the LR proposed by [ 21 ]. Following the total flow time minimization, the PFH-NEH proposed by [ 27 ] is implemented. As the LR-NEH, it is based on the combination of the PF [23] and the NEH already mentioned. Metaheuristic algorithms for the PFSP appeared much later than the heuristic. Among the earliest approaches, we find the simulated annealing algorithm of [ 26 ], which is fairly simple in the sense that it uses a constant temperature and an insertion neighborhood. About the metaheuristics developed in the master thesis the first and more important is the Iterated greedy proposed by [ 30 ] to the makespan objective. IG generates a sequence of solutions by iterating over greedy constructive heuristics using two main phases: destrution and construction. Another metaheuristic developed in this master thesis with Core idle time minimization is the IGALL proposed by [ 7 ]. It is based on the same concept of the Iterated Gready with optimization of partial solutions. The last one method adapted from the PFSP with Total Flow time minimization is the VBIH. It is developed by [ 34 ] based on a variable block insertion. 2.3 Core idle time 11 To summarize all the methods applied, the article of reference and the adaptation made is the table 2.1 Table 2.1 Summarize of the methods applied. Method Reference Problem Adaptation NEH [25] Fm|prmu|Cmax Objective function NEHM[28] HFm|prmu|Cmax,TCE Objective function and type of shop floor LR-NEH [29] Fm|prmu|∑CjObjective function PFH-NEH [27] Fm|prmu|TCE,∑CjObjective function IG [30] Fm|prmu|Cmax Objective function IGALL [7] Fm|prmu|Cmax Objective function VBIH [34] Fm|prmu|∑CjObjective function Along these studies, the most widely used benchmark has been the one proposed by [ 33 ]. Lately [ 35 ] carried out a study of problem instances to develop a new hard benchmark with difficult problems, which shows significant differences between algorithms. This master thesis uses these two benchmarks, the first one for the calibration and the second one for the comparison. 2.3 Core idle time As already mentioned, since the first work published by [ 19 ] a lot of studios are published about makespan and total flow time objectives. However, as we already mentioned, other measures are more suitable in some industrial environments, such as idle and waiting times. In flow shop scheduling, waiting time of jobs and idle time of machines are often considered because of their impact on many manufacturing environments and applications. In the literature, no-wait and no-idle constraints are considered for problems minimizing Cmax mainly. Core Idle time is found in the literature introduced in the objective function, in some heuristics method and as constraints. Related with the objective function, idle time is usually found in the minimization of the total machine completion time. [ 18 ] developed efficient solutions method for the minimization of the 18 Chapter 3. Constructive heuristics –A weight calculates as: wi=m i+j(m−i)/(n−2)(3.10) –The weighted sum of the idle times of job πjon all machines: ITj= m ∑ i=2 wjmax(Cπj,i−1−Cπj−1,i,0)(3.11) Then, the cost function is computed as: cFj= (n−j−1)ITj+Cπj,m(3.12) About procedure, the PF heuristic part of a initial sequence ( π ) and a job index. The first step is to remove of the π sequence the job in the position indicate by the job index. Then, the cost function is calculated for the remaining jobs. The job with the minimum value of the cost function is removed and inserted in the final sequence ( Π ). These steps are repeated until a n−size sequence is formed. Once the PF heuristic is explained, let us now to understand the PFH − NEH(x).The pseudo-code of the method is presented in in 13. The PFH − NEH(x) is based on generate x sequences applying both algorithm. Next, this procedure is explained. The initial order is determined by calculating the f Di values as given below: f Dj=2 m−1 m ∑ i=1 (m−i)pπj,i+ m ∑ i=1 pπj,i(3.13) Then the body of the algorithm is repeated x times. In the h−th iteration, the PF heuristic is applied based on the input of this initial order and the hth position as job index. Once a n−size sequence is obtained applying the PF algorithm, the NEH heuristic is applied. The NEH starts by the sequence formed by the PF method. Then a one-size sequence with the first job is generated. The remaining jobs are inserted in the position in which suppose the minimum core idle time. Then the sequence with the minimum value of the objective function is selected as output of the method. The last step is to apply the insertion local search with general swaps to the complete solution as long as it is improved. The pseudo-code of the local search is presented in10] 3.5 Local search 19 3.5 Local search About the local search, a first improvement with general swaps is applied in all heuristics and metaheuristics that contain it. It starts with a initial sequence previously generated. Then the body of the algorithm is applied. It is based on insert a determinate job in all position until a improvement of the objective function is found. The procedure stars by removing the first job of the sequence and inserting in all possible position on the sequence. This procedure is repeated for all the jobs in all positions. The algorithm ends when one of these two options occurs: – The algorithm ends when a better solution is reached, even if it has not been tested with the remaining works – When all the jobs in the sequence have been inserted in all possible position of the sequence. Then, the best solution is selected. Algorithm 1: NEH [27] Input: instance data Output: Πb,ob jb 1begin 2Pj:=total processing time o f each job j ; 3Π0:=sort the jobs in descending order o f Pj; 4π1:=π0 1; 5for k=2to ndo 6Π=Insert π0 kin the best position of Π; 7Πb:=Π; 8ob jb:=Ob j(Πb); 9return Πb,ob jb 20 Chapter 3. Constructive heuristics Algorithm 2: NEH-M [28] Input: instance data, x Output: Πb,ob jb 1begin 2Pj:=total processing time o f each job j ; 3Π0:=sort the jobs in descending order o f Pj; 4Π′:=Π0; 5for h=1to xdo 6Swap the positions of jobs π′ 1and π′ h; 7πh 1:=π′ 1; 8for k=2to ndo 9Πh=Insert π′ kin the best position of Πh; 10 Πb:=The best solution among (Π1,Π2...Πx); 11 ob jb:=Ob j(Πb); 12 return Πb,ob jb 3.5 Local search 21 Algorithm 3: LR Input: instance data,x Output: Πb,ob jb 1begin 2α0:=sort the jobs in ascending order o f ξj0; 3for l=1to xdo 4πl 1:=αl; 5U:=Remove αlf rom α; 6for k=2to ndo 7Calculate ξjk f or all the jobs f rom U; 8πl k:=Take the job with minimum ξjk; 9Remove job j f rom U; 10 Πb:=The best solution among (Π1,Π2...Πx); 11 ob jb:=Ob j(Πb); 12 return Πb,ob jb Algorithm 4: LR-NEH Input: instance data,x Output: Πb,ob jb 1begin 2α0:=sort the jobs in ascending order o f ξj0; 3for l=1to xdo 4πl 1:=αl; 5U:=Remove αlf rom α; 6for k=2to ddo 7Calculate ξjk f or all the jobs f rom U; 8πl k:=Take the job with minimum ξjk; 9Remove job j f rom U; 10 β:=sort U in ascending order o f total processing times; 11 for k=1to n−ddo 12 Πl=Insert βkin the best position of Πl; 13 Πb:=The best solution among (Π1,Π2...Πx); 14 ob jb:=Ob j(Πb); 15 return Πb,ob jb 22 Chapter 3. Constructive heuristics Algorithm 5: PF [27] Input: instance data, Π∗,Index Output: Πb,ob jb 1begin 2U:=Π∗; 3π1:=uindex; 4U:=Remove uindex f rom U; 5for j=2to ndo 6for k=1to n−jdo 7πj=Uk; 8Calculate Cπj,i∀i; 9Itj=∑m 2wjmax(Cπj,i−1−Cπj−1,i,0); 10 cF j=(n−j−1)xItj+Cπj,m; 11 if k=1 then 12 job=πj; 13 BestCoe f =cF j; 14 BestI=Itj; 15 if cF j ◁BestCoe f then 16 job=πj; 17 BestCoe f =cF j; 18 BestI=Itj; 19 if cF j=BestCoe f then 20 if Itj◁BestI then 21 job=πj; 22 BestCoe f =cF j; 23 BestI=Itj; 24 πj=job; 25 Remove pijf rom U; 26 Πb:=Π; 27 ob jb:=Ob j(Πb); 28 return Πb,ob jb 3.5 Local search 23 Algorithm 6: PFH-NEH [27] Input: instance data Output: Πb,ob jb 1begin 2Π0:=sort the jobs in ascending order o f f Dj; 3if n◁=100 then 4x=n; 5else 6x=1; 7for k=1to xdo 8Π′=PF(π0 ,k); 9Π′′=NEH(Π′); 10 Πk=LocalSearch(Π′′); 11 Πb:=The best solution among (Π1,Π2...Πx); 12 ob jb:=Ob j(Πb); 13 return Πb,ob jb Algorithm 7: Local search Input: instance data, Π0,ob j0 Output: Πb,ob jb 1begin 2Πb:=Π0; 3ob jb:=ob j0for j=1to ndo 4for k=1to ndo 5if k!=jthen 6ΠV=Insert π0 jin the k position of Π0; 7if Ob jΠV◁objbthen 8k:=n j =:nΠb:=ΠV; 9ob jb:=Ob j(Πb); 10 return Πb,ob jb 4 Metaheuristics The next step, with the purpose of obtaining better solutions than with the previous heuristics and enrich the problem evaluation, the implementation of a metaheuristic seems appropriate. In this section, IG, IGALL and VBIH are presented as the metaheuristics adapted for our problem. Note that, the main adaptation besides the objective function, is the initial sequence. Has been decided to tested each of the metaheuristics with all the heuristics as initial sequence. The objective is to make a complete analysis of the problem. 4.1 Iteraty Greedy The first metaheuristic adapted is the original Iterated Greedy (IG) algorithm. The pseudo-code of the method is presented in 22.The algorithm is composed of two phases. The destruction phase removes some jobs from a previously input sequence and the construction phase consists on the application of a greedy constructive heuristic to complete the sequence generated by the destruction phase. Then, a selection criterion must be applied to decide to apply the iteration to the sequence recently formed or to the previous one. This procedure is repeated until a stopping criterion is met. To a best understanding, should be explained the original method developed by [ 30 ] for Fm|prmu|Cmax . This original IG starts with a initial solution obtained by the NEH heuristic. The destruction phase is based on eliminate d jobs of the sequence π , generating a partial sequence πD with n-d jobs and another sequence πRwith these djobs removed. Then the construction phase is applied. It is based on insert the removes jobs applying the NEH mechanism. Each job of the πp partial sequence is inserted in all positions of the π partial sequence. The position in which the 25 26 Chapter 4. Metaheuristics best objective function is obtained, is definitively inserted. The job inserted in the πD sequence is removed from the πp sequence. It is repeated until there are no any jobs in the πp sequence and the piD reaches to be a complete solution. Additionally, a local search method is added to improve the solution quality, choosing a local search algorithm based on searching a neighborhood by insertion. This is, a job is removed of the sequence and inserted into every possible position on the sequence from the previous solution, when a improvement of the objective function is reached the job is inserted in that position, else no insertion is applied. This step is applied on every job with a randomly order of until an improvement occurs or every job had inserted. The last step an acceptance criterion to decide whether or not the new sequence is accepted as the initial solution for the next iteration. [ 30 ] decides to implement the temperature extracted from the simulated annealing procedure, specifically the temperature that [ 26 ] proposed for their simulated annealing algorithm to solve the problem Fm|prmu|Cmax: Temperature =T m ∑ i=1 n ∑ j=1 Pi j nm10 (4.1) T was empirically tested and decided to be T=0.5 . The stopping criterion has been decide to be time-based, related with the size of the instance. It is computed as: t=n(m/2)20 milliseconds.(4.2) Once the original IG is explained should be indicated the adaption on our problem. As mentioned above, as the initial sequence has been tested all the heuristic adapted in our master thesis (NEH, NEH M , LR − NEH and PFH − NEH). The comparison will be shown in the next chapter. Another adaptation has been the local search applied. Has been compared some local search and has been decided what provides the best results for our problem. The local search implemented is the based on first improvement with general swaps. Should be noted that it is the local search applied in all heuristics and metaheuristics that contain each. Finally, the main adaption is the objective function computed, being the already mentioned Fm|prmu|TCIT problem. About the dparameter, is will be decided in the calibration phase. 4.2 IGALL 27 4.2 IGALL The next metaheuristic adapted is the IGALL developed by [ 7 ]. The pseudo-code of the method is presented in 23. It is a variation of the original IG added a local search to the partial sequence. The first step is the destruction phase, d jobs are removed by the initial sequence and stored in a partial sequence. It is time to apply the modification of the Iteraty Greedy. The next step is to implement a local search to the partial solution. The application of this phase can lead to different search directions. Then the construction phase based on insert the removes jobs applying the NEH mechanism is apply to the improved partial sequence. Each job of the πR improve partial sequence is inserted in all positions of the π partial sequence. The position in which the best objective function is obtained, is definitively inserted. Additionally, as the IG, the local search [10] is applied to improve the quality of the solution. As mentioned above, a local search based on first improvement with general swaps is implemented. The last step an acceptance criterion to decide whether or not the new sequence is accepted as the initial solution for the next iteration. The same criteria based on temperature extracted from the simulated annealing procedure is used. Temperature =T m ∑ i=1 n ∑ j=1 Pi j nm10 (4.3) T was empirically tested in the next chapter and the stopping criterion is the same as is explained. 4.3 VBIH The third and last metaheuristic adapted is the VBIH algorithm developed by [ 34 ] for the PFSP with total completion time and blocking constraint. Worth mentioning that it is similar to the IG and IGALL already explained. The pseudo-code of the method is presented in 25. In the original VBIH, the initial sequence considered is obtained by the application of the PFH-NEH heuristic. In our adaptation will be tested with all the heuristics developed in the master thesis. About the body, as in 34 Chapter 5. Computational results generated between 1 and 99. Each size has 10 instances, in total 120 instances. The benchmark set of instances from Vallada has been used to compare all the heuristics and metaheuristics. It consists of 240 large instances and 240 small instances. Small instances are a set of 240 with the following combinations of number of jobs (n) and number of machines (m) : n={10,20,30,40,50,60} , m={5,10,15,20} . It could be seen in 5.2. For each combination 10 instances are generated, so in total, we have 6×4×10 =240 small instances. Regarding the large instances, they are also a set of 240 where n={100,200,300,400,500,600,700,800} and m={20,40,60} . It could be seen in 5.3 Table 5.2 Number of instances by size of Vallada’s small instances. n x m 5 10 15 20 10 10 10 10 10 20 10 10 10 10 30 10 10 10 10 40 10 10 10 10 50 10 10 10 10 60 10 10 10 10 Table 5.3 Number of instances by size of Vallada’s big instances. n x m 20 40 60 100 10 10 10 200 10 10 10 300 10 10 10 400 10 10 10 500 10 10 10 600 10 10 10 700 10 10 10 800 10 10 10 The reason why we selected Vallada to compare the different methods is that Taillard’s instances are not equidistant, which means, the difference between the number of jobs/machines between two consecutive instances is not the same. In order to make a best statistical analysis the equidistant set of instances generated by [35] is selected. 5.2 Evaluation of the results 35 5.2 Evaluation of the results To calibrate using the Taillard instances and to compare using the Vallada instances the Relative Deviation Index (RDI) has been selected as the performance measure. It is a indicator used to size the result obtained compared to the best and worst results reached. It is computed by the following equation: RDIi=TCITim −TCITimin TCITimax −TCITimin (5.1) with TCITim the objective value for instance i obtained by method m , TCITimax the maximum value obtained for instance i across all the methods, and TCITimin the minimum. 5.3 Heuristics calibration In this section, the constructive heuristics (NEH M , LR-NEH, and PFH-NEH) have been calibrated. To calibrate the parameter of the constructive heuristics, we carry out a design of experiments. For this purpose, we use Taillard’s benchmark set. As mentioned above, due to the importance of the first job of the sequence on the objective function, all of the constructive heuristics is based on repeated some procedures changing their initial job. In each iteration, when the first the job is selected the body of the algorithm is applied. This process is repeated xtimes. In the design of experiments, the proposed heuristics have one parameter: the number of solutions generated ( x ). The main characteristic of the parameter x is the dependence of the number of jobs of the instance. If x is set as a function of n, as n grows, so does the number of iterations. Is clearly remarkable that as n increases, x increases then the CPU inverted increases. For this reason, the decision of the value of the parameter x should be made checking if the CPU inverted compensates or not. Regarding these considerations, the cases are shown in Table 5.4. Table 5.4 Cases of constructive heuristics. CASE 1 CASE 2 CASE 3 CASE 4 X=nif n≤100 X=nif n≤200 X=nif n≤100 X=nif n≤200 X=1if n>100 X=1if n>200 X=20 if n>100 X=20 if n>200 36 Chapter 5. Computational results To the best knowledge of the parameter, the 2 criteria to be taken into account will be explained below: –The number of job from which the number of job change. –The value of xthat assume since the change. Then, each of the cases will be explained: – CASE 1: x is set as n for all the instances with a number of jobs less than 100. At the moment the number of jobs exceeds 100, xis set as 1. – CASE 2: x is set as n for all the instances with a number of jobs less than 200. At the moment the number of jobs exceeds 200, xis set as 1. – CASE 3: x is set as n for all the instances with a number of jobs less than 100. At the moment the number of jobs exceeds 100, xis set as 20. – CASE 4: x is set as n for all the instances with a number of jobs less than 200. At the moment the number of jobs exceeds 200, xis set as 20. It should be noted that is the combination of two variation of the two criteria: – The number of job from which the number of job change can be 100 or 200. –The value of xthat assume since the change can be 1 or 20. In order to compare the cases, we calculate the ARDI (Average Relative Deviation Index) and The average computation time (Avg. CPU), in which the algorithm finds the final solution. 5.3.1 NEHM The parameter to be calibrated is x , i.e. the number of iterations. The decision of the parameter should be taken on the basis of the relation of the CPU inverted and the quality of the solution. As shown Figure 5.1 the case that obtain the best results is the Case 4. Figures 5.2 and 5.1 clearly indicate that the cases with high CPU levels result in better ARDI values. However, no great improvement is obtained compared to the increase in time spent. The plots demonstrate no statistically significant difference between the four cases. Should be highlighted the power of the original NEH to reach a good solution in few iterations. That repeating the algorithm not improve to a great extend the solution only shows the capacity to reach a good solution in few time. Due to this considerations, Case 1 ( x=n if n≤100 and x=1 if n>100 ) is selected for being the fastest in terms of CPU and provide a good solution. 5.3 Heuristics calibration 37 Figure 5.1 95% Confidence Intervals for NEHM. Figure 5.2 CPU average for NEHM. 5.3.2 LR-NEH The parameter to be calibrated is x , i.e. the number of iterations. The decision of the parameter should be taken on the basis of the relation of the CPU inverted and the quality of the solution. As we can see in Figures 5.3 and 5.4, 38 Chapter 5. Computational results Figure 5.3 95% Confidence Intervals for LR-NEH. Figure 5.4 CPU average for LR-NEH. the results clearly indicate that the cases with high CPU levels result in better ARDI values. However, in this heuristic, the difference between the time spent and 5.4 Heurisics comparison 39 Figure 5.5 95% Confidence Intervals for PFH-NEH. the improvement of results is even greater. The plots demonstrate no statistically significant difference between the four cases. Therefore, Case 1 ( x=n if n≤100 and x=1 if n>100 ) is selected for being the fastest in terms of CPU. 5.3.3 PFH-NEH The parameter to be calibrated is x , i.e. the number of iterations. The decision of the parameter should be taken on the basis of the relation of the CPU inverted and the quality of the solution. As we can see in Figures 5.5 and 5.6, the results clearly indicate that the cases with high CPU levels result in better ARDI values. However, no great improvement is obtained compared to the increase in time spent. The plots demonstrate no statistically significant difference between the four cases. Therefore, as in the other heuristics Case 1 ( x=n if n≤100 and x=1 if n>100 ) is selected for being the fastest in terms of CPU. 5.4 Heurisics comparison Once the constructive heuristics are calibrated, is time to compare the results with Vallada test best. In order to compare all the heuristics, we must set the parameter xlike in Case 1. As we can see in 5.7, the plots demonstrate statistically significant differences 40 Chapter 5. Computational results Figure 5.6 CPU average for PFH-NEH. Figure 5.7 95% Confidence Intervals for Heuristics. between NEH M and NEH, and between PFH-NEH and LR-NEH. However, there are no significant differences between NEH and PFH-NEH. The best result is provided by the NEHMheuristic. 5.5 Metaheuristics calibration 41 5.5 Metaheuristics calibration 5.5.1 IG Summing up the procedure, it starts with a initial sequence an then the algorithm is applied. All the experiments for the metaheuristics are carried out fixing a stopping criterion of maximum time t=n(m/2)20 milliseconds, so efficiencies will be easy and fast to compare. The parameters of which depends are: –The initial sequence obtained by one of the heuristics adapted. – The parameter T : The parameter of which depend the temperature proposed for the simulated annealing algorithm. –The parameter d: The number of jobs removed in the destruction phase. Although NEH M is the best heuristic and we have just decided to choose the parameter x like Case 1, is should be to compare again for one reason: The NEH M is the best in terms of RPI but is the most CPU-heavy. We must check if the time invested in the initial sequence is beneficial to the final result. Taking each of the heuristics as a starting sequence, the first step is to compare all heuristics setting Case 1. The first parameter to calibrate is heuristic. The results in terms of RDI are shown 5.8. As we can see, the plots demonstrate statistically significant differences between LR-NEH and PFH-NEH, but not between NEHMand LR-NEH. If we focus on comparing the NEH M with the LR-NEH, we draw the following conclusions – If we choose the NEH M as the initial sequence, we get slightly better results. – The above conclusion reflects that the more time invested in the initial sequence (NEHMcompare with LR-NEH), the better results we obtain. The NEH M is chosen as the initial sequence. The next step is to calibrate the parameter T . The values taken for calibration are T={0.1,0.2,0.3,0.4,0.5} . Therefore we have 5 different combinations to be tested. As we can see in the graph of 5.9 the best result is provided by the T=0.2 . Although we can state that T=0.2provides the best results, there are no significant differences. 42 Chapter 5. Computational results Figure 5.8 95% Confidence Intervals for IG for different Heuristics as the initial sequence. Figure 5.9 95% Confidence Intervals for IG for different values of T. Finally, the last parameter to tune is the number of jobs removed in the destruction phase. To calibrate the parameter d, we make the same process as for the parameter T . The values taken for calibration are d=2,3,4 . Attending to the Figure 5.10, we can state that for d=3 we obtain the best results without significant differences. 5.5 Metaheuristics calibration 43 Figure 5.10 95% Confidence Intervals for IG for different values of d. Figure 5.11 95% Confidence Intervals for IGALL for different Heuristics as the initial sequence. 5.5.2 IGALL Summing up the procedure, it starts with a initial sequence and then the algorithm is applied. 6 Conclusions In this master thesis a set of heuristics, constructive heuristics and metaheuristics has been tested to the Fm|prmu|TCIT problem. Approximate methods have not been considered previously to solve this problem. Therefore, in this master thesis the most efficient methods found in the related literature (PFSP with makespan and total completion time minimization) have been adapted. The calibration and comparison of method has been developed in two groups, the heuristics and metaheuristics. To be calibrate Taillard’s benchmark [ 33 ] has been used. However, Vallad’s benchmark [ 35 ] has been used for the comparison due to its statistical advantages. The heuristics and constructive heuristics has been NEH, NEH M (a modification of NEH), PFH-NEH and LR-NEH.About the calibration, the Case 1 is choosen for all the heuristics. The main reason of the selection is the balance between the improvement of the objective function and the time spends to achieve it. Case 1 is based on set the number of iteration x=n if n≤100 and 1 if it exceeds 100. The great effort in CPU necessary for instances with a large number of jobs is evident. However, a great improvement in a short time is obtained for this small instances.On the other hand, once the heuristics are calibrated is time to compare. The NEH M provides the best results, but it is also the one that spends the highest quantity of computational time. We can conclude that these heuristics provide a good results for our problem, but the implementation as initial sequence to the metaheuristic has been tested. We need to compare if this CPU effort is reflected in an improvement in the final solution. Another conclusion about the comparison of the heuristics selected is the great importance of the first job of the sequence in the objective function. All there are based on repeating a certain algorithm changing the first job, and has been shown the improvement in the objective function. Related to the adaptation of existing metaheuristics for other problems in the literature the next conclusions has be made. First to compare all them, the calibration should be made. The first of this parameter is the 51 52 Chapter 6. Conclusions heuristic implemented to obtain the initial sequence. It is demonstrate that the best heuristic to obtain the initial sequence is the NEH M . The CPUE inverted due to repeated the algorithm changing the first job of the sequence improve the solution. It is another evidence of the impact of the first job in the solution. Then the others parameters are calibrate. About the comparison of the metaheuristic, the best results is provide by the VBIH. Specifically, the best results are provide for small instances, been the IG the best one for big instances. We can conclude that the results reveal a good performance of the method adapted. To end, a future line of research could be to approach the minimization of the TCIT with the minimization of the energy consumption of the machines. Also, based on these results, methods with greater intelligence could be developed based on the objective developed. Appendix A Heuristics A.1 Calibration Table A.1 LR-NEH: ARDI for each case x. Cases n m 1 2 3 4 20 5 0,48 0,48 0,48 0,48 10 0,75 0,75 0,75 0,75 20 0,98 0,98 0,98 0,98 Average 0,74 0,74 0,74 0,74 50 5 0,50 0,50 0,50 0,50 10 0,78 0,78 0,78 0,78 20 0,95 0,95 0,95 0,95 Average 0,74 0,74 0,74 0,74 100 5 0,41 0,41 0,41 0,41 10 0,63 0,63 0,63 0,63 20 0,96 0,96 0,96 0,96 Average 0,67 0,67 0,67 0,67 200 10 0,66 0,22 0,35 0,22 20 0,94 0,54 0,64 0,54 Average 0,80 0,38 0,49 0,38 500 20 0,65 0,65 0,38 0,38 Average 0,65 0,65 0,38 0,38 Average 5 0,46 0,46 0,46 0,46 10 0,70 0,59 0,63 0,59 20 0,90 0,82 0,78 0,76 Average 0,73 0,66 0,65 0,63 53 54 Chapter A. Heuristics Table A.2 NEHM: ARDI for each case x. Cases n m 1 2 3 4 20 5 0,61 0,61 0,61 0,61 10 0,57 0,57 0,57 0,57 20 0,52 0,52 0,52 0,52 Average 0,57 0,57 0,57 0,57 50 5 0,43 0,43 0,43 0,43 10 0,54 0,54 0,54 0,54 20 0,52 0,52 0,52 0,52 Average 0,50 0,50 0,50 0,50 100 5 0,29 0,29 0,29 0,29 10 0,43 0,43 0,43 0,43 20 0,51 0,51 0,51 0,51 Average 0,41 0,41 0,41 0,41 200 10 0,37 0,17 0,24 0,17 20 0,55 0,32 0,37 0,32 Average 0,46 0,24 0,31 0,24 500 20 0,65 0,65 0,45 0,45 Average 0,65 0,65 0,45 0,45 Average 5 0,44 0,44 0,44 0,44 10 0,48 0,43 0,45 0,43 20 0,55 0,50 0,47 0,46 Average 0,50 0,46 0,46 0,45 A.2 Comparison 55 Table A.3 PFH-NEH: ARDI for each case x. Cases n m 1 2 3 4 20 5 0,40 0,40 0,40 0,40 10 0,85 0,85 0,85 0,85 20 0,78 0,78 0,78 0,78 Average 0,67 0,67 0,67 0,67 50 5 0,39 0,39 0,39 0,39 10 0,86 0,86 0,86 0,86 20 0,80 0,80 0,80 0,80 Average 0,68 0,68 0,68 0,68 100 5 0,82 0,82 0,82 0,82 10 0,73 0,73 0,73 0,73 20 0,89 0,89 0,89 0,89 Average 0,81 0,81 0,81 0,81 200 10 1,00 0,52 0,69 0,52 20 0,89 0,51 0,69 0,51 Average 0,95 0,51 0,69 0,51 500 20 0,98 0,98 0,67 0,67 Average 0,98 0,98 0,67 0,67 Average 5 0,54 0,54 0,54 0,54 10 0,86 0,74 0,78 0,74 20 0,87 0,79 0,76 0,73 Average 0,78 0,71 0,71 0,68 A.2 Comparison 56 Chapter A. Heuristics Figure A.1 95% Confidence Intervals for heuristics for different values of n. Figure A.2 95% Confidence Intervals for heuristics for different values of m. A.2 Comparison 57 Table A.4 Heuristics: ARDI for small instances for n and m. n m LR-NEH NEH NEHM PFH-NEH 10 5 0,49 0,52 0,10 0,30 10 0,69 0,78 0,03 0,46 15 0,80 0,60 0,06 0,38 20 0,85 0,58 0,05 0,35 Average 0,71 0,62 0,06 0,37 20 5 0,23 0,91 0,15 0,29 10 0,85 0,76 0,00 0,59 15 0,81 0,49 0,00 0,54 20 0,87 0,56 0,00 0,59 Average 0,69 0,68 0,04 0,50 30 5 0,20 0,89 0,16 0,37 10 0,66 0,88 0,05 0,40 15 0,73 0,90 0,00 0,53 20 0,90 0,59 0,00 0,48 Average 0,63 0,81 0,05 0,44 40 5 0,39 0,79 0,16 0,47 10 0,44 0,92 0,05 0,51 15 0,63 0,91 0,00 0,54 20 0,89 0,69 0,00 0,69 Average 0,59 0,83 0,05 0,55 50 5 0,34 0,65 0,05 0,57 10 0,71 0,77 0,04 0,47 15 0,62 0,92 0,05 0,36 20 0,85 0,71 0,00 0,60 Average 0,63 0,77 0,04 0,50 60 5 0,24 0,96 0,31 0,47 10 0,61 0,84 0,01 0,49 15 0,70 0,82 0,00 0,50 20 0,95 0,58 0,00 0,73 Average 0,63 0,80 0,08 0,55 Average 5 0,32 0,79 0,15 0,41 10 0,66 0,83 0,03 0,49 15 0,72 0,77 0,02 0,48 58 Chapter A. Heuristics Table A.5 Heuristics: ARDI for big instances for n and m. n m LR-NEH NEH NEHM PFH-NEH 100 20 0,87 0,79 0,00 0,66 40 1,00 0,37 0,00 0,43 60 1,00 0,41 0,00 0,42 Average 0,96 0,52 0,00 0,50 200 20 0,57 0,91 0,00 0,67 40 1,00 0,46 0,00 0,45 60 1,00 0,41 0,00 0,32 Average 0,86 0,59 0,00 0,48 300 20 0,50 0,12 0,12 0,90 40 0,99 0,00 0,00 0,51 60 1,00 0,00 0,00 0,26 Average 0,83 0,04 0,04 0,56 400 20 0,23 0,40 0,40 0,88 40 1,00 0,00 0,00 0,60 60 1,00 0,00 0,00 0,28 Average 0,74 0,13 0,13 0,59 500 20 0,27 0,22 0,22 0,93 40 1,00 0,00 0,00 0,52 60 1,00 0,00 0,00 0,37 Average 0,76 0,07 0,07 0,61 600 20 0,08 0,29 0,29 0,96 40 1,00 0,00 0,00 0,54 60 1,00 0,00 0,00 0,26 Average 0,69 0,10 0,10 0,59 700 20 0,33 0,13 0,13 0,98 40 1,00 0,10 0,10 0,34 60 1,00 0,00 0,00 0,33 Average 0,78 0,07 0,07 0,55 800 20 0,24 0,35 0,35 0,97 40 0,83 0,00 0,00 0,54 60 1,00 0,00 0,00 0,31 Average 0,69 0,12 0,12 0,61 Average 20 0,60 0,49 0,11 0,74 40 0,98 0,12 0,01 0,49 60 1,00 0,10 0,00 0,32 Appendix B Metaheuristics B.1 Calibration Table B.1 IG: ARDI for different values of d. d n m 2 3 4 20 5 0,33 0,33 0,33 10 0,47 0,46 0,48 20 0,46 0,44 0,40 Average 0,42 0,41 0,40 50 5 0,30 0,27 0,28 10 0,36 0,37 0,42 20 0,39 0,38 0,40 Average 0,35 0,34 0,37 100 5 0,33 0,33 0,34 10 0,26 0,27 0,30 20 0,33 0,32 0,36 Average 0,30 0,31 0,33 200 10 0,12 0,13 0,16 20 0,20 0,22 0,27 Average 0,16 0,18 0,21 500 20 0,27 0,27 0,27 Average 0,27 0,27 0,27 Average 5 0,32 0,31 0,32 10 0,30 0,31 0,34 20 0,33 0,33 0,34 Average 0,32 0,31 0,33 59 66 Chapter B. Metaheuristics Table B.8 VBIH: ARDI for different values of bmax. bmax n m 3 4 5 6 20 5 0,31 0,26 0,23 0,20 10 0,47 0,42 0,38 0,36 20 0,42 0,38 0,35 0,35 Average 0,40 0,35 0,32 0,30 50 5 0,26 0,23 0,20 0,20 10 0,38 0,32 0,30 0,28 20 0,40 0,37 0,34 0,33 Average 0,35 0,31 0,28 0,27 100 5 0,31 0,28 0,28 0,27 10 0,27 0,24 0,21 0,21 20 0,38 0,32 0,30 0,29 Average 0,32 0,28 0,26 0,26 200 10 0,15 0,12 0,11 0,10 20 0,30 0,26 0,25 0,24 Average 0,22 0,19 0,18 0,17 500 20 0,40 0,39 0,40 0,40 Average 0,40 0,39 0,40 0,40 Average 5 0,29 0,26 0,24 0,22 10 0,32 0,27 0,25 0,24 20 0,38 0,34 0,33 0,32 Average 0,34 0,30 0,28 0,27 B.2 Comparison 67 Table B.9 Heuristics: ARDI for small instances for n and m. n m IG IGALL VBIH 10 5 0,15 0,17 0,07 10 0,34 0,39 0,23 15 0,40 0,38 0,17 20 0,33 0,32 0,19 Average 0,31 0,32 0,17 20 5 0,44 0,36 0,21 10 0,69 0,72 0,46 15 0,57 0,61 0,43 20 0,61 0,63 0,44 Average 0,58 0,58 0,38 30 5 0,37 0,36 0,09 10 0,60 0,71 0,48 15 0,64 0,72 0,49 20 0,62 0,64 0,46 Average 0,56 0,61 0,38 40 5 0,56 0,51 0,30 10 0,58 0,73 0,36 15 0,61 0,71 0,52 20 0,56 0,66 0,42 Average 0,58 0,65 0,40 50 5 0,53 0,49 0,23 10 0,54 0,69 0,33 15 0,58 0,70 0,47 20 0,55 0,67 0,39 Average 0,55 0,64 0,35 60 5 0,48 0,47 0,32 10 0,53 0,64 0,31 15 0,57 0,77 0,50 20 0,51 0,70 0,41 Average 0,52 0,64 0,39 Average 5 0,42 0,39 0,20 10 0,55 0,65 0,36 15 0,56 0,65 0,43 68 Chapter B. Metaheuristics Table B.10 Heuristics: ARDI for big instances for n and m. n m IG IGALL VBIH 100 20 0,41 0,69 0,35 40 0,51 0,61 0,40 60 0,47 0,56 0,49 Average 0,46 0,62 0,41 200 20 0,34 0,58 0,28 40 0,32 0,52 0,41 60 0,30 0,39 0,48 Average 0,32 0,50 0,39 300 20 0,29 0,58 0,40 40 0,29 0,40 0,47 60 0,25 0,35 0,44 Average 0,28 0,44 0,44 400 20 0,30 0,44 0,42 40 0,29 0,40 0,48 60 0,24 0,33 0,41 Average 0,28 0,39 0,44 500 20 0,32 0,44 0,46 40 0,25 0,34 0,42 60 0,26 0,32 0,38 Average 0,28 0,37 0,42 600 20 0,32 0,42 0,45 40 0,28 0,35 0,39 60 0,25 0,32 0,37 Average 0,28 0,36 0,40 700 20 0,27 0,35 0,44 40 0,26 0,35 0,38 60 0,28 0,30 0,36 Average 0,27 0,33 0,39 800 20 0,37 0,46 0,52 40 0,24 0,32 0,36 60 0,26 0,31 0,33 Average 0,29 0,36 0,40 Average 20 0,41 0,54 0,40 40 0,31 0,41 0,42 60 0,29 0,36 0,41 List of Figures 1.1 Machine-oriented and job-oriented Gantt diagrams [16] 3 1.2 Flow layout of flowshop [16] 5 1.3 Flow layout of flowshop [16] 5 1.4 Flow layout of flowshop [16] 5 1.5 Front/Core/Back Idle Times (FIT/CIT/BIT) in a PFSP [5] 7 5.1 95% Confidence Intervals for NEHM 37 5.2 CPU average for NEHM 37 5.3 95% Confidence Intervals for LR-NEH 38 5.4 CPU average for LR-NEH 38 5.5 95% Confidence Intervals for PFH-NEH 39 5.6 CPU average for PFH-NEH 40 5.7 95% Confidence Intervals for Heuristics 40 5.8 95% Confidence Intervals for IG for different Heuristics as the initial sequence 42 5.9 95% Confidence Intervals for IG for different values of T42 5.10 95% Confidence Intervals for IG for different values of d43 5.11 95% Confidence Intervals for IGALL for different Heuristics as the initial sequence 43 5.12 95% Confidence Intervals for IGALL for different values of T 45 5.13 95% Confidence Intervals for IGALL for different values of d45 5.14 95% Confidence Intervals for VBIH for different Heuristics as the initial sequence 46 5.15 95% Confidence Intervals for VBIH for different values of T47 5.16 95% Confidence Intervals for VBIH for different values of bmin 47 5.17 95% Confidence Intervals for VBIH for different values of bmax 48 5.18 95% Confidence Intervals for metaheuristics 48 5.19 95% Confidence Intervals for metaheuristics for different values of n 49 5.20 95% Confidence Intervals for metaheuristics for different values of m 49 A.1 95% Confidence Intervals for heuristics for different values of n 56 69 70 List of Figures A.2 95% Confidence Intervals for heuristics for different values of m 56 List of Tables 2.1 Summarize of the methods applied 11 5.1 Number of instances by size of Taillard instances 33 5.2 Number of instances by size of Vallada’s small instances 34 5.3 Number of instances by size of Vallada’s big instances 34 5.4 Cases of constructive heuristics 35 A.1 LR-NEH: ARDI for each case x 53 A.2 NEHM: ARDI for each case x 54 A.3 PFH-NEH: ARDI for each case x 55 A.4 Heuristics: ARDI for small instances for n and m 57 A.5 Heuristics: ARDI for big instances for n and m 58 B.1 IG: ARDI for different values of d 59 B.2 IG: ARDI for different heuristic as initial sequence 60 B.3 IG: ARDI for different values of T 61 B.4 IGALL: ARDI for different values of d 62 B.5 IGALL: ARDI for different heuristic as initial sequence 63 B.6 IGALL: ARDI for different values of T 64 B.7 VBIH: ARDI for different values of bmin 65 B.8 VBIH: ARDI for different values of bmax 66 B.9 Heuristics: ARDI for small instances for n and m 67 B.10 Heuristics: ARDI for big instances for n and m 68 71 List of Algorithms 1 NEH [27] 19 2 NEH-M [28] 20 3 LR 21 4 LR-NEH 21 5 PF [27] 22 6 PFH-NEH [27] 23 7 Local search 23 8 IG [27] 29 9 IGALL [7] 30 10 VBIH [27] 31 73 Bibliography [1] Arianna Alfieri, Michele Garraffa, Erica Pastore, and Fabio Salassa, Permutation flowshop problems minimizing core waiting time and core idle time, Computers Industrial Engineering 176 (2023), 108983. [2] A. Baskar and M. Anthony Xavior, New idle time-based tie-breaking rules in heuristics for the permutation flowshop scheduling problems, Computers & Operations Research 133 (2021), 105348. [3] Maria Raquel C. Costa, Jorge M.S. Valente, and Jeffrey E. Schaller, Efficient procedures for the weighted squared tardiness permutation flowshop scheduling problem, Flexible Services and Manufacturing Journal 32 (2020), no. 3, 487–522. [4] Alex Paranahyba de Abreu and Helio Yochihiro Fuchigami, An efficiency and robustness analysis of warm-start mathematical models for idle and waiting times optimization in the flow shop, Computers Industrial Engineering 166 (2022), 107976. [5] Sanchez de-los Reyes Paula, Perez-Gonzalez Paz, and M Framinan Jose, Permutation flowshop scheduling problem with total core idle time minimization, IFAC-PapersOnLine 55 (2022), no. 10, 187–191, 10th IFAC Conference on Manufacturing Modelling, Management and Control MIM 2022. [6] B. Dhanasakkaravarthi and A. Krishnamoorthy, A New Priority Rule for Initial Ordering of Jobs in Permutation Flowshop Scheduling Problems, International Journal of Advanced Computer Science and Applications 13 (2022), no. 1, 2022. [7] Jérémie Dubois-Lacoste, Federico Pagnozzi, and Thomas Stützle, An iterated greedy algorithm with optimization of partial solutions for the makespan permutation flowshop problem, Computers and Operations Research 81 (2017), 160–166. 75