Flexible Job Shop Scheduling Problem with Fuzzy Times and Due-Windows: Minimizing Weighted Tardiness and Earliness Using Genetic Algorithms

Citation: Campo, E.A.; Cano, J.A.; Gómez-Montoya, R.; Rodríguez-Velásquez, E.; Cortés, P. Flexible Job Shop Scheduling Problem with Fuzzy Times and Due-Windows: Minimizing Weighted Tardiness and Earliness Using Genetic Algorithms. Algorithms 2022, 15, 334. https://doi.org/10.3390/ a15100334 Academic Editor: Frank Werner Received: 28 July 2022 Accepted: 16 September 2022 Published: 20 September 2022 Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations. Copyright: © 2022 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https:// creativecommons.org/licenses/by/ 4.0/). algorithms Article Flexible Job Shop Scheduling Problem with Fuzzy Times and Due-Windows: Minimizing Weighted Tardiness and Earliness Using Genetic Algorithms Emiro Antonio Campo 1, Jose Alejandro Cano 1,* , Rodrigo Gómez-Montoya 2, Elkin Rodríguez-Velásquez 3 and Pablo Cortés4 1Faculty of Economic and Administrative Sciences, Universidad de Medellin, Medellin 050026, Colombia 2Faculty of Administration, Politécnico Colombiano Jaime Isaza Cadavid, Medellin 050022, Colombia 3Facultad de Minas, Universidad Nacional de Colombia, Medellin 050034, Colombia 4Escuela Técnica Superior de Ingeniería, Universidad de Sevilla, Camino de los Descubrimientos s/n, 41092 Sevilla, Spain *Correspondence: [email protected] Abstract: The current requirements of many manufacturing companies, such as the fashion, textile, and clothing industries, involve the production of multiple products with different processing routes and products with short life cycles, which prevents obtaining deterministic setup and processing times. Likewise, several industries present restrictions when changing from one reference to another in the production system, incurring variable and sequence-dependent setup times. Therefore, this article aims to solve the flexible job shop scheduling problem (FJSSP) considering due windows, sequence-dependent setup times, and uncertainty in processing and setup times. A genetic algorithm is proposed to solve the FJSSP by integrating fuzzy logic to minimize the weighted penalties for tardiness/earliness. The proposed algorithm is implemented in a real-world case study of a fabric finishing production system, and it is compared with four heuristics adapted to the FJSSP such as earliest due date, critical reason, shortest processing time, and Monte Carlo simulation. Results show that the performance of the proposed algorithm provides efficient and satisfactory solutions concerning the objective function and computing time since it overperforms (more than 30%) the heuristics used as benchmarks. Keywords: genetic algorithm; flexible job shop; production scheduling; uncertainty; fuzzy logic; time windows; earliness/tardiness; sequence-dependent setup times 1. Introduction The assignment and sequencing of jobs to production resources represent a complex process in most manufacturing companies, even more in flexible job shop systems where the production scheduling problem has been proved to be a nondeterministic polynomial time-hard problem (NP-hard problem) [ 1 , 2 ], and for which optimal solution algorithms cannot provide solutions in reasonable computational times, especially for large and complex production plants. When considering the FJSSP, the concept of a set of machines in series is replaced by a set of work centers, where each work center contains a set of parallel machines that can have different processing times. In the FJSSP, each job follows a production route and can be processed on any machine that makes up a work center [ 3 ]. Moreover, the FJSSP requires a detailed discussion of the scheduling of orders importance from the point of due dates [ 4 ], implying the consideration of objective functions related to tardiness and earliness [ 5 , 6 ]. However, many FJSSP models proposed in the literature assume conditions far from reality, ignoring the recirculation of jobs in work centers or machines and considering certainty in all the parameters used to perform the production schedule. Algorithms 2022,15, 334. https://doi.org/10.3390/a15100334 https://www.mdpi.com/journal/algorithms Algorithms 2022,15, 334 2 of 19 In addition, the studies considering parameter uncertainty do not include variables such as setup times dependent on the operation sequence. In most scheduling models, processing time and due dates represent uncertain variables [ 7 – 11 ], and some studies use fuzzy logic theory to create a hybrid genetic algorithm to minimize makespan [ 12 ]. Furthermore, production scheduling problems optimizing earliness and tardiness have increased in relevance in recent years due to the growing interest in just-in-time production [ 13 ]. In realistic production scheduling problems, jobs finish as close as possible to due dates or within time-windows, due dates (due windows) since the early completion of jobs generates additional production and storage costs and inventory obsolescence; while late completion causes lost sales [ 5 , 14 ]. Therefore, optimal scheduling minimizing earliness and tardiness penalties can improve the economic effects of firms. On the other hand, the complexity of the FJSSP requires the use of techniques that provide solutions in reasonable computational times to NP-hard problems. These solutions come from artificial intelligence techniques, which have been active in planning and scheduling for four decades [ 15 ]. Therefore, many heuristics and metaheuristics such as genetic algorithms, honey bee optimization, artificial bee colony, ant colony optimization, particle swarm optimization, simulated annealing, and hybrid approaches have been proposed to solve the FJSSP [ 16 ]. Chaudhry and Khan [ 17 ] performed a review of techniques addressing the FJSSP, highlighting ant colony optimization (ACO), artificial bee colony (ABC), artificial immune system (AIS), evolutionary algorithms, greedy randomized adaptive search procedure (GRASP), Integer/Linear programming, neighborhood search (NS), particle swarm optimization (PSO), simulated annealing (SA), tabu search (TS), mathematical programming, deterministic heuristics, hybrid techniques, and miscellaneous techniques. Evolutionary algorithms represent the most used techniques in the literature to solve the FJSSP and cover a wide variety of techniques including Biogeography-based optimization (BBO), Differential evolution (DE), Evolution strategy (ES), Gene expression programming (GEP), Genetic Algorithms (GA), Genetic programming (GP), Harmony Search (HS), Learning classifier system (LCS), Memetic Algorithms (MA), and Estimation of distribution algorithm (EDA). These techniques are effective for minimizing the maximum completion time of the jobs, better known as makespan [ 18 ], and they can also assume other objectives, such as reducing delivery times, minimizing tardiness, minimizing earliness, minimizing resource costs, minimizing flow time, and minimizing the number of tardy jobs [15,17]. Within artificial intelligence techniques, genetic algorithms are usually efficient for the optimization of complex systems, represent a good solver for combinatorial problems, provide a wide range of solutions [ 19 ], and have been used to solve many problems related to the FJSSP [ 20 ], becoming a powerful and successful technique for solving of NP- Hard problems due to the logic of evolutionary principles [ 21 , 22 ]. The genetic algorithm as an evolutionary algorithm has advantages as it is relatively easy to understand and apply and presents fault tolerance [ 23 ]. However, although it has been proven that this metaheuristic efficiently solves complex optimization problems, the parameter values must prevent premature convergences and promote the finding of global solutions instead of local solutions [24,25]. Liu, Yang, Xing, and Lu [ 26 ] presented a study considering a flexible job shop system, fuzzy parameters, and time windows, introduced a multi-objective programming problem with fuzzy time windows, and solved the problem through a multi-group genetic algorithm. Similarly, Zhang, Collart-Dutilleul, and Mesghouni [ 27 ] developed a model that incorporates time windows, capacity, and space constraints and uses mixed integer programming to limit cyclic activities. Shi, Zhang, and Li [ 26 ] use a rolling window rescheduling strategy and dynamic scheduling for the FJSSP with fuzzy delivery time, considering a trapezoidal delivery window to minimize energy consumption, maximum makespan, and consumer dissatisfaction, and solving this problem with an immune genetic algorithm. Other studies have added restrictions to the FJSSP models to adapt to realistic problems and seek to fulfill several objectives considering multi-objective uncertainty environ- Algorithms 2022,15, 334 3 of 19 ments [ 25 , 28 ]. In this sense, Jamrus et al. [ 29 ] propose a model where the processing time can be exact or fuzzy depending on the availability of job data, and the FJSSP is solved using a hybrid algorithm between a genetic algorithm and the particle swarm optimization algorithm. In most of these models, the fuzzy variables receive triangular membership functions due to the ease of their construction. Based on the abovementioned, this article aims to address the FJSSP considering due-window and fuzzy setup times with triangular membership functions to minimize the weighted penalties for tardiness/earliness through a genetic algorithm. The present study contributes in multiple ways: Firstly, it develops a methodology to calculate the possibility of tardiness and earliness of a job, comparing the due-date time window with the fuzzy set of the completion time and using this result to calculate the penalty of tardiness and earliness in the objective function. Secondly, the study adapts GA and deterministic methods (heuristics and rules) for the specific assumptions of the proposed FJSSP model. Thirdly, it presents a novel solution representation for each chromosome of the GA in two ways, one to calculate the total penalty (objective function) and another for the mutation and crossover operators to minimize the chance of infectable chromosomes, reducing the use of repairing operators and the algorithm computing time. Fourthly, the proposed algorithm solves a real-world case study in the textile sector, demonstrating the algorithm’s applicability to industries with complex production systems. 2. FJSSP Description Scheduling of job shop production is defined by four main research problems represented by Job Shop Scheduling Problem (JSSP), Flexible Job Shop Scheduling Problem (FJSSP), Dynamic Job Shop Scheduling Problem (DJSSP), and Flow Shop Scheduling Problem (FSSP) [ 19 ]. The classical JSSP represents one of the most difficult workshop problems, it assumes that there is no flexibility in the resources (including machines and tools) for each operation of every job. The FJSSP is an extension of the classical job shop scheduling problem allowing an operation to be processed by any machine from a given set [ 1 ]. The FJSSP consists of assigning and sequencing njobs in mwork center, each work center can have a different number of machines or resources, and each machine may process more than one type of operation [ 30 ]. In the FJSSP, each job is formed by a sequence of consecutive operations, each operation requires one machine, and each operation has to be performed to complete the job. This problem covers two difficulties namely the machine assignment problem (how to assign the operations on the machines) and the operation sequencing problem (how to sequence the operations on the machines) [ 31 ]. The general objective of the FJSSP is to improve the organization’s productivity while reducing production consumption by switching over the selectable machine and taking full advantage of the underutilized capacity, adjusting the processing workload on machines [ 32 ]. The performance measures, restrictions, and characteristics the model must comply with must be established to define the FJSSP model. The model proposed in this study is based on the following assumptions: • All machines are available at the beginning of the scheduling horizon and can process only one job simultaneously. • No job can start an operation until the previously assigned has finished or until a machine is available to perform that operation. Therefore, only one job operation can be executed at a time. • Processing times are represented by fuzzy numbers and modeled by triangular membership functions. • Once an operation of a job has started on a machine, it will not be interrupted until it finishes the total number of units of said job. •Staff is available to perform each operation. • Machine breakdown or downtime due to maintenance or repairs in the planning horizon are not considered. •Setup times depend on the job sequence Algorithms 2022,15, 334 4 of 19 • Setup times are represented by fuzzy numbers and modeled by triangular membership functions. • Recirculation is allowed since a machine can perform several processes (not at the same time), so a job can be processed several times on the same machine. • A time window defines the expected completion time for each job (interval to determine whether a job is completed on time). •Machines in the same work center may have different processing times. The mathematical model of the FJSSP is based on the study by Ortiz et al. [ 33 ] and Demir and I¸sleyen [ 34 ], where the objective functions minimize the number of late jobs and the Makes-pan, respectively. However, in these studies, the delivery dates are not represented with time intervals but with exact dates, and they do not consider the time of preparation depending on the sequence, for which we present adjustments to the mathematical model. The indices, sets, data, variables, and mathematical model formulation to optimize the FJSSP are as follows: Indices jJob index hJob index iOperation index kMachine index lIndex of the positions in the sequencing Parameters: nTotal number of jobs mTotal number of machines Akij Binary parameter to indicate whether operation iof the job jis performed on machine k Pkij Processing time of operation iof the job jon machine k Skjh Setup time in machine kif job jstarts after completing job h MVery large number djA Lower limit of the due window of job j djB Upper limit of the due window of the job j wjWeighting for job j wTWeighting for tardiness wEWeighting for earliness Variables: Xijkl Binary variable to indicate whether operation iof job jon machine kis sequenced in position l Vijk Binary variable to assign operation jof job ion machine k TMkl Start time of machine kat position l PSij Total process time (includes setup time) of operation iof job j TIij Start time of operation iof job j CjCompletion time of job j TjTardiness of job j EjEarliness of job j Model: Min Z =∑Wi(TiWT+EiWE)(1) Cj≥TIij +PSij ∀i,j(2) Tj≥Cj−djB ∀j(3) Ej≥djA −Cj∀j(4) ∑k[(Pkij +Skjh)×Vijk] = PSij ∀i,j,h(5) TIij +PSij ≤TIi+1j∀j∀i=1, . . . , I−1 (6) TMkl +PSij ×Xijkl ≤TMkl+1∀i,j,k∀l=1, . . . , L−1 (7) TMkl ≤TIij 1−Xijkl×M∀i,j,k,l(8) Algorithms 2022,15, 334 5 of 19 TMkl ≤TMkl1−Xijkl×M∀i,j,k,l(9) Vijk ≤Akij ∀i,j,k(10) ∑i∑jXijkl =1∀k,l(11) ∑kVijk =1∀i,j(12) ∑lXijkl =Vijk∀i,j,k(13) TIij,PSij ≥0∀i,j(14) TMkl ≥0∀k,l(15) Tj,Ej≥0∀j(16) Xijkl ∈{0, 1}∀i,j,k,l(17) Vijk ∈{0, 1}∀i,j,k(18) Equation (1) minimizes the total weighted penalty of the jobs given by lateness and promptness, where the earliness of a job is defined as the maximum between zero and the difference between the lower limit of the due window and the completion time of said job Ej=Max0 , djA −Cj , and the tardiness of a job is defined as the maximum between zero and the difference between the completion time and the upper limit of the due window of said job Tj=Max0 , Cj−djB  . Although the proposed model deals with two performance measures, these are represented in a single objective function (total penalty) that relates them through weights, which allows lateness and promptness to be assessed differently according to the decision-maker preferences. Constraint (2) calculates the completion time of the operations of each job. Constraints (3) and (4) define respectively the tardiness and earliness of each job based on the limits of the due dates. Constraint (5) ensures that the total processing time of each job includes the machine processing time and the setup time. Constraint (6) guarantees the compliance of precedence of operations. Constraint (7) ensures that machines can perform one operation at a time. Constraints (8) and (9) guarantee that any operation starts when the assigned machine is available, and the previous operation is completed. Constraint (10) establishes the relationship between the assigned machines and the operations assigned to those machines. Constraint (11) guarantees that each operation of each job is assigned to a position on a machine. Constraints (12) and (13) ensure that each operation is processed on the assigned machine and position. Constraints (14)–(18) define the variable domains. 3. Genetic Algorithm and Fuzzy Logic for the FJSSP No efficient algorithm provides an optimal solution in short computing times to a combinatorial optimization problem such as the FJSSP, so it is necessary to use alternatives to complex and analytical methods [ 10 , 17 ]. These models provide optimal solutions in reasonable computational times only for small instances, which is infeasible for realistic problems, so metaheuristics are suggested to find feasible solutions in reasonable computing times [ 24 ]. Adaptive algorithms for production scheduling in fuzzy environments have delivered good results and have provided excellent solutions; therefore, genetic algorithms have become one of the most used metaheuristics to generate efficient and high-quality job sequences in flexible job shop systems [ 20 , 21 , 29 , 35 ]. Thus, this study proposes a genetic algorithm with fuzzy logic that follows the ones described in Figure 1and detailed below. Algorithms 2022,15, 334 6 of 19 Algorithms2022,15,xFORPEERREVIEW6of20  Constraints(12)and(13)ensurethateachoperationisprocessedontheassignedmachine andposition.Constraints(14)–(18)definethevariabledomains. 3.GeneticAlgorithmandFuzzyLogicfortheFJSSP Noefficientalgorithmprovidesanoptimalsolutioninshortcomputingtimestoa combinatorialoptimizationproblemsuchastheFJSSP,soitisnecessarytousealternativestocomplexandanalyticalmethods[10,17].Thesemodelsprovideoptimalsolutions inreasonablecomputationaltimesonlyforsmallinstances,whichisinfeasibleforrealistic problems,sometaheuristicsaresuggestedtofindfeasiblesolutionsinreasonablecomputingtimes[24].Adaptivealgorithmsforproductionschedulinginfuzzyenvironments havedeliveredgoodresultsandhaveprovidedexcellentsolutions;therefore,geneticalgorithmshavebecomeoneofthemostusedmetaheuristicstogenerateefficientandhighqualityjobsequencesinflexiblejobshopsystems[20,21,29,35].Thus,thisstudyproposes ageneticalgorithmwithfuzzylogicthatfollowstheonesdescribedinFigure1anddetailedbelow.  Figure1.Flowchartforthegeneticalgorithm. Step1.Entertheweightofeachjobj(𝑊),theduewindowofeachjob󰇛𝑑,𝑑󰇜, processingroutes,availablemachines,processingtimes,sequence‐dependentsetuptimes, weightoftardiness(𝑤)andearliness(𝑤).Enterthegeneticalgorithmparameterssuch asPopulation(PB),Iterations(N),Elitismrate(ET),Crossoverrate(PC),Mutationrate (MR). Step2.Generatetheinitialpopulationrandomly(numberofchromosomes)basedon theparameterPB,thencalculatethenumberofoperationsrequiredtocompleteallthe scheduledjobs.Inthisstep,PBchromosomesarerandomlygeneratedandarecalledalpha chromosomes.Eachalphachromosomerepresentsasolutiontotheproposedscheduling problem;eachgenehasaninputtoassignajobrandomlyandestablishthesequenceto performtheoperations,andanotherinputtostorearandomnumberbetween0and1to assignthemachinethatperformstherespectiveoperation.Arepresentationofanalpha chromosomeisshownbelowinFigure2. Modelinputinformation Generateinitialpopulationrandomly Foreachalphachromosome,calculate itsrespectivebetachromosome Assessthefitnessofeachbeta chromosome Selectthebestbetachromosomesusing theelitismoperator Applycrossoverandmutation operators Usetherepairmechanismforalpha chromosomes Iterations=Maximum iterations Start End Selectbestbetachromosomeand generateresultsreport Yes No Figure 1. Flowchart for the genetic algorithm. Step 1. Enter the weight of each job j( Wj ), the due window of each job djA,djB , processing routes, available machines, processing times, sequence-dependent setup times, weight of tardiness ( wT ) and earliness ( wE ). Enter the genetic algorithm parameters such as Population (PB), Iterations (N), Elitism rate (ET), Crossover rate (PC), Mutation rate (MR). Step 2. Generate the initial population randomly (number of chromosomes) based on the parameter PB, then calculate the number of operations required to complete all the scheduled jobs. In this step, PB chromosomes are randomly generated and are called alpha chromosomes. Each alpha chromosome represents a solution to the proposed scheduling problem; each gene has an input to assign a job randomly and establish the sequence to perform the operations, and another input to store a random number between 0 and 1 to assign the machine that performs the respective operation. A representation of an alpha chromosome is shown below in Figure 2. Algorithms2022,15,xFORPEERREVIEW7of20   Figure2.Illustrationofanalphachromosome. Step3.Sincethealphachromosomeisusedtoperformthecrossoverandmutation operators,thebetachromosomefacilitatestheevaluationoftheobjectivefunction(fitness value).Thischromosomerepresentationenhancesoffspringfeasibility,onlyrequiringthe repairofchromosomesbythenumberofoperationsperjob.Thebetachromosomesresult fromthealphachromosomesbyassigningininput2ofeachgenethemachinethatperformstheoperationforthejobassignedininput1.Themachineassignmentshownin Figure3comparesthevaluestoredininput2ofthealphachromosomewiththeprobabilityassignedtoeachmachineenabledtoperformtheoperationindicatedininput1.All machinesenabledtoperformanoperationreceivethesameselectionprobability.Asan example,Figure4indicatesthesequencingofjobscorrespondingtothebetachromosome fromFigure3,wherejob3isshowntobeassignedthreeoperations,thefirstoperationis assignedtomachine2(j3‐O1),thesecondoperationisassignedtomachine4(j3‐O2),and thethirdoperationisassignedtomachine7(j3‐O3).  Figure3.Illustrationofanalphachromosome.  Figure4.Sequencingofjobsfromthebetachromosome. Step4.Thefuzzycompletiontime𝐶 ofeachjobjmustbecalculatedtoassessthe fitnessofeachbetachromosome.AsshowninEquation(19),thecompletiontimefora selectedgeneiscalculatedasthestarttimeoftheoperation(maximumbetweentheavailabletimeofmachinei𝑇𝑀 andthecumulativecompletiontimeofjobjuptotheevaluatedgene𝐶 )plusthesetuptimeinmachinei𝑆 andtheprocessingtimeofoperation oofjobjinmachinei𝑃 .Theavailabletimeofmachineiwillbeupdatedwiththecompletiontimeofjobjthathasbeenprocessedinthismachine(𝑇𝑀  𝐶 ).Intheproposed methodology,thefuzzysetsusedhavetriangularmembershipfunctionssuchthat𝐶  𝐶,𝐶𝐶.Theelementsthatmakeupthetriangularfuzzynumberareshownin Figure5,andthesecanbecalculatedfollowingEquations(20)–(22). 𝐶 max󰇛𝐶   ,𝑇𝑀  󰇜𝑃   𝑆   (19) 𝐶 max 󰇛𝐶 ,𝑇𝑀󰇜 𝑃    𝐴   (20) Gene1Gene2Gene3Gene4Gene5Gene6Gene7Gene8Gene9Gene10 Gene11 Gene12 Gene13 Gene14 Gene15 Gene16 Gene17 Input131354422122351154 Input20.660.930.310.800.730.750.910.560.210.990.960.380.440.410.800.060.10 Gene1Gene2Gene3Gene4Gene5Gene6Gene7Gene8Gene9Gene10 Gene11 Gene12 Gene13 Gene14 Gene15 Gene16 Gene17 Input131354422122351154 Input2M 2 M 3 M 4 M 8 M 7 M 2 M 3 M 5 M 4 M 8 M 2 M 7 M 1 M 6 M 2 M 4 M 4 Machine M 1 j 5 ‐O 2 M 2 j 3 ‐O 1 j 4 ‐O 2 j 2 ‐O 4 j 1 ‐O 4 M 3 j 1 ‐O 1 j 2 ‐O 1 M 4 j 3 ‐O 2 j 1 ‐O 2 j 5 ‐O 3 j 4 ‐O 3 M 5 j 2 ‐O 2 M 6 j 1 ‐O 3 M 7 j 4 ‐O 1 j 3 ‐O 3 M 8 j 5 ‐O 1 j 2 ‐O 3 Sequence Figure 2. Illustration of an alpha chromosome. Step 3. Since the alpha chromosome is used to perform the crossover and mutation operators, the beta chromosome facilitates the evaluation of the objective function (fitness value). This chromosome representation enhances offspring feasibility, only requiring the repair of chromosomes by the number of operations per job. The beta chromosomes result from the alpha chromosomes by assigning in input 2 of each gene the machine that performs the operation for the job assigned in input 1. The machine assignment shown in Figure 3compares the value stored in input 2 of the alpha chromosome with the probability assigned to each machine enabled to perform the operation indicated in input 1. All machines enabled to perform an operation receive the same selection probability. As an example, Figure 4indicates the sequencing of jobs corresponding to the beta chromosome from Figure 3, where job 3 is shown to be assigned three operations, the first operation is assigned to machine 2 (j 3 -O 1 ), the second operation is assigned to machine 4 (j 3 -O 2 ), and the third operation is assigned to machine 7 (j3-O3). Algorithms 2022,15, 334 7 of 19 Algorithms2022,15,xFORPEERREVIEW7of20   Figure2.Illustrationofanalphachromosome. Step3.Sincethealphachromosomeisusedtoperformthecrossoverandmutation operators,thebetachromosomefacilitatestheevaluationoftheobjectivefunction(fitness value).Thischromosomerepresentationenhancesoffspringfeasibility,onlyrequiringthe repairofchromosomesbythenumberofoperationsperjob.Thebetachromosomesresult fromthealphachromosomesbyassigningininput2ofeachgenethemachinethatperformstheoperationforthejobassignedininput1.Themachineassignmentshownin Figure3comparesthevaluestoredininput2ofthealphachromosomewiththeprobabilityassignedtoeachmachineenabledtoperformtheoperationindicatedininput1.All machinesenabledtoperformanoperationreceivethesameselectionprobability.Asan example,Figure4indicatesthesequencingofjobscorrespondingtothebetachromosome fromFigure3,wherejob3isshowntobeassignedthreeoperations,thefirstoperationis assignedtomachine2(j3‐O1),thesecondoperationisassignedtomachine4(j3‐O2),and thethirdoperationisassignedtomachine7(j3‐O3).  Figure3.Illustrationofanalphachromosome.  Figure4.Sequencingofjobsfromthebetachromosome. Step4.Thefuzzycompletiontime𝐶 ofeachjobjmustbecalculatedtoassessthe fitnessofeachbetachromosome.AsshowninEquation(19),thecompletiontimefora selectedgeneiscalculatedasthestarttimeoftheoperation(maximumbetweentheavailabletimeofmachinei𝑇𝑀 andthecumulativecompletiontimeofjobjuptotheevaluatedgene𝐶 )plusthesetuptimeinmachinei𝑆 andtheprocessingtimeofoperation oofjobjinmachinei𝑃 .Theavailabletimeofmachineiwillbeupdatedwiththecompletiontimeofjobjthathasbeenprocessedinthismachine(𝑇𝑀  𝐶 ).Intheproposed methodology,thefuzzysetsusedhavetriangularmembershipfunctionssuchthat𝐶  𝐶,𝐶𝐶.Theelementsthatmakeupthetriangularfuzzynumberareshownin Figure5,andthesecanbecalculatedfollowingEquations(20)–(22). 𝐶 max󰇛𝐶   ,𝑇𝑀  󰇜𝑃   𝑆   (19) 𝐶 max 󰇛𝐶 ,𝑇𝑀󰇜 𝑃    𝐴   (20) Gene1Gene2Gene3Gene4Gene5Gene6Gene7Gene8Gene9Gene10 Gene11 Gene12 Gene13 Gene14 Gene15 Gene16 Gene17 Input131354422122351154 Input20.660.930.310.800.730.750.910.560.210.990.960.380.440.410.800.060.10 Gene1Gene2Gene3Gene4Gene5Gene6Gene7Gene8Gene9Gene10 Gene11 Gene12 Gene13 Gene14 Gene15 Gene16 Gene17 Input131354422122351154 Input2M 2 M 3 M 4 M 8 M 7 M 2 M 3 M 5 M 4 M 8 M 2 M 7 M 1 M 6 M 2 M 4 M 4 Machine M 1 j 5 ‐O 2 M 2 j 3 ‐O 1 j 4 ‐O 2 j 2 ‐O 4 j 1 ‐O 4 M 3 j 1 ‐O 1 j 2 ‐O 1 M 4 j 3 ‐O 2 j 1 ‐O 2 j 5 ‐O 3 j 4 ‐O 3 M 5 j 2 ‐O 2 M 6 j 1 ‐O 3 M 7 j 4 ‐O 1 j 3 ‐O 3 M 8 j 5 ‐O 1 j 2 ‐O 3 Sequence Figure 3. Illustration of a beta chromosome. Algorithms2022,15,xFORPEERREVIEW7of20   Figure2.Illustrationofanalphachromosome. Step3.Sincethealphachromosomeisusedtoperformthecrossoverandmutation operators,thebetachromosomefacilitatestheevaluationoftheobjectivefunction(fitness value).Thischromosomerepresentationenhancesoffspringfeasibility,onlyrequiringthe repairofchromosomesbythenumberofoperationsperjob.Thebetachromosomesresult fromthealphachromosomesbyassigningininput2ofeachgenethemachinethatperformstheoperationforthejobassignedininput1.Themachineassignmentshownin Figure3comparesthevaluestoredininput2ofthealphachromosomewiththeprobabilityassignedtoeachmachineenabledtoperformtheoperationindicatedininput1.All machinesenabledtoperformanoperationreceivethesameselectionprobability.Asan example,Figure4indicatesthesequencingofjobscorrespondingtothebetachromosome fromFigure3,wherejob3isshowntobeassignedthreeoperations,thefirstoperationis assignedtomachine2(j3‐O1),thesecondoperationisassignedtomachine4(j3‐O2),and thethirdoperationisassignedtomachine7(j3‐O3).  Figure3.Illustrationofanalphachromosome.  Figure4.Sequencingofjobsfromthebetachromosome. Step4.Thefuzzycompletiontime𝐶 ofeachjobjmustbecalculatedtoassessthe fitnessofeachbetachromosome.AsshowninEquation(19),thecompletiontimefora selectedgeneiscalculatedasthestarttimeoftheoperation(maximumbetweentheavailabletimeofmachinei𝑇𝑀 andthecumulativecompletiontimeofjobjuptotheevaluatedgene𝐶 )plusthesetuptimeinmachinei𝑆 andtheprocessingtimeofoperation oofjobjinmachinei𝑃 .Theavailabletimeofmachineiwillbeupdatedwiththecompletiontimeofjobjthathasbeenprocessedinthismachine(𝑇𝑀  𝐶 ).Intheproposed methodology,thefuzzysetsusedhavetriangularmembershipfunctionssuchthat𝐶  𝐶,𝐶𝐶.Theelementsthatmakeupthetriangularfuzzynumberareshownin Figure5,andthesecanbecalculatedfollowingEquations(20)–(22). 𝐶 max󰇛𝐶   ,𝑇𝑀  󰇜𝑃   𝑆   (19) 𝐶 max 󰇛𝐶 ,𝑇𝑀󰇜 𝑃    𝐴   (20) Gene1Gene2Gene3Gene4Gene5Gene6Gene7Gene8Gene9Gene10 Gene11 Gene12 Gene13 Gene14 Gene15 Gene16 Gene17 Input131354422122351154 Input20.660.930.310.800.730.750.910.560.210.990.960.380.440.410.800.060.10 Gene1Gene2Gene3Gene4Gene5Gene6Gene7Gene8Gene9Gene10 Gene11 Gene12 Gene13 Gene14 Gene15 Gene16 Gene17 Input131354422122351154 Input2M 2 M 3 M 4 M 8 M 7 M 2 M 3 M 5 M 4 M 8 M 2 M 7 M 1 M 6 M 2 M 4 M 4 Machine M 1 j 5 ‐O 2 M 2 j 3 ‐O 1 j 4 ‐O 2 j 2 ‐O 4 j 1 ‐O 4 M 3 j 1 ‐O 1 j 2 ‐O 1 M 4 j 3 ‐O 2 j 1 ‐O 2 j 5 ‐O 3 j 4 ‐O 3 M 5 j 2 ‐O 2 M 6 j 1 ‐O 3 M 7 j 4 ‐O 1 j 3 ‐O 3 M 8 j 5 ‐O 1 j 2 ‐O 3 Sequence Figure 4. Sequencing of jobs from the beta chromosome. Step 4. The fuzzy completion time e Cj of each job jmust be calculated to assess the fitness of each beta chromosome. As shown in Equation (19), the completion time for a selected gene is calculated as the start time of the operation (maximum between the available time of machine i g TMi and the cumulative completion time of job jup to the evaluated gene f Cj ) plus the setup time in machine i f Silj and the processing time of operation oof job jin machine if Pjio. The available time of machine iwill be updated with the completion time of job jthat has been processed in this machine ( g TMi=e Cj ). In the proposed methodology, the fuzzy sets used have triangular membership functions such that e Cj=Cin f j,Cmod jCsup j . The elements that make up the triangular fuzzy number are shown in Figure 5, and these can be calculated following Equations (20)–(22). e Cj=max(f Cj,g TMi) + f Pjio +f Silj (19) Cin f j=max (Cin f j,TMin f i) + Pin f jio +Ain f ilj (20) Cmod j=max (Cmod j,TMmod i) + Pmod jio +Amod ilj (21) Csup j=max (Csup j,TMsup i) + Psup jio +Asup ilj (22) Algorithms2022,15,xFORPEERREVIEW8of20  𝐶 max 󰇛𝐶 ,𝑇𝑀󰇜 𝑃    𝐴  (21) 𝐶 max 󰇛𝐶 ,𝑇𝑀󰇜 𝑃   𝐴   (22)  Figure5.Triangularmembershipfunctionforthecompletiontimeofjobj. Likewise,itisnecessarytocalculatethefuzzytardinessandearlinessofeachjobto obtainthefitnessofeachchromosome.Itrequirescomparing𝐶  withthelimitsofthedue window(𝑑 , 𝑑).Thefuzzytardiness(𝑇 )isdeterminedbyintercepting𝐶  withthetardinessinterval(𝐼𝑇)thatstartsat𝑑andisnotboundedbyanuppervalue󰇛 𝑑 ,∞󰇜. Thefuzzyearlinessofeachjobj(𝐸 )isdeterminedbytheinterceptof𝐶  withtheearliness interval(𝐼𝐸)thatstartsatzeroandendsat𝑑󰇛0 ,𝑑󰇜.Figure6illustratesthedifferent casesinwhichfuzzydelayandfuzzypromptnesscanbeconfigured.Figure6ashowsthe firstcasewherethereisthepossibilityofcompletingjobjearly(earliness)orlate(tardiness),butthereisalsothepossibilityofcompletingjobjwithintheduewindow(ontime andwithoutpenalties).Figure6bshowsthesecondcasewherejobjcannotbedelivered early(earliness)orlate(tardiness),assuminga100%possibilitythatjobjwillbecompletedwithintheduewindowdespiteconsideringuncertainty.Figure6cshowsthethird casewherejobjcannotbecompletedlate(tardiness),butthereisapossibilitythatjobj willbedeliveredearly(earliness);however,when𝐶 𝑑,thereisa100%possibility thatjobjwillbecompletedearly.Figure6dshowsthefourthcasewherejobjcannotbe deliveredearly(earliness),butthereisapossibilitythatjobjwillbecompletedlate(tardiness);however,when𝐶 𝑑,thereisa100%possibilitythatjobjwillbecompleted late.  Figure6.Casesoffuzzytardinessandfuzzyearlinessforeachjobj(a)tardinessorearliness;(b)no tardinessorearliness;(c)earliness;(d)tardiness. Possibility 1 0Time (a) (b) (c) (d) 1 0 1 0 1 0 1 0 Possibility Time Possibility Time Possibility Time Possibility Time Figure 5. Triangular membership function for the completion time of job j. Likewise, it is necessary to calculate the fuzzy tardiness and earliness of each job to obtain the fitness of each chromosome. It requires comparing e Cj with the limits of the due window ( djA , djB ). The fuzzy tardiness ( e Tj ) is determined by intercepting e Cj with the tardiness interval ( ITj ) that starts at djB and is not bounded by an upper value djB ,+∞ . The fuzzy earliness of each job j( e Ej ) is determined by the intercept of e Cj with the earliness Algorithms 2022,15, 334 8 of 19 interval ( IEj ) that starts at zero and ends at djA 0 , djA . Figure 6illustrates the different cases in which fuzzy delay and fuzzy promptness can be configured. Figure 6a shows the first case where there is the possibility of completing job jearly (earliness) or late (tardiness), but there is also the possibility of completing job jwithin the due window (on time and without penalties). Figure 6b shows the second case where job jcannot be delivered early (earliness) or late (tardiness), assuming a 100% possibility that job jwill be completed within the due window despite considering uncertainty. Figure 6c shows the third case where job jcannot be completed late (tardiness), but there is a possibility that job jwill be delivered early (earliness); however, when Csup j≤djA , there is a 100% possibility that job jwill be completed early. Figure 6d shows the fourth case where job j cannot be delivered early (earliness), but there is a possibility that job jwill be completed late (tardiness); however, when Cin f j≥djB , there is a 100% possibility that job jwill be completed late. Algorithms2022,15,xFORPEERREVIEW8of20  𝐶 max 󰇛𝐶 ,𝑇𝑀󰇜 𝑃    𝐴  (21) 𝐶 max 󰇛𝐶 ,𝑇𝑀󰇜 𝑃   𝐴   (22)  Figure5.Triangularmembershipfunctionforthecompletiontimeofjobj. Likewise,itisnecessarytocalculatethefuzzytardinessandearlinessofeachjobto obtainthefitnessofeachchromosome.Itrequirescomparing𝐶  withthelimitsofthedue window(𝑑 , 𝑑).Thefuzzytardiness(𝑇 )isdeterminedbyintercepting𝐶  withthetardinessinterval(𝐼𝑇)thatstartsat𝑑andisnotboundedbyanuppervalue󰇛 𝑑 ,∞󰇜. Thefuzzyearlinessofeachjobj(𝐸 )isdeterminedbytheinterceptof𝐶  withtheearliness interval(𝐼𝐸)thatstartsatzeroandendsat𝑑󰇛0 ,𝑑󰇜.Figure6illustratesthedifferent casesinwhichfuzzydelayandfuzzypromptnesscanbeconfigured.Figure6ashowsthe firstcasewherethereisthepossibilityofcompletingjobjearly(earliness)orlate(tardiness),butthereisalsothepossibilityofcompletingjobjwithintheduewindow(ontime andwithoutpenalties).Figure6bshowsthesecondcasewherejobjcannotbedelivered early(earliness)orlate(tardiness),assuminga100%possibilitythatjobjwillbecompletedwithintheduewindowdespiteconsideringuncertainty.Figure6cshowsthethird casewherejobjcannotbecompletedlate(tardiness),butthereisapossibilitythatjobj willbedeliveredearly(earliness);however,when𝐶 𝑑,thereisa100%possibility thatjobjwillbecompletedearly.Figure6dshowsthefourthcasewherejobjcannotbe deliveredearly(earliness),butthereisapossibilitythatjobjwillbecompletedlate(tardiness);however,when𝐶 𝑑,thereisa100%possibilitythatjobjwillbecompleted late.  Figure6.Casesoffuzzytardinessandfuzzyearlinessforeachjobj(a)tardinessorearliness;(b)no tardinessorearliness;(c)earliness;(d)tardiness. Possibility 1 0Time (a) (b) (c) (d) 1 0 1 0 1 0 1 0 Possibility Time Possibility Time Possibility Time Possibility Time Figure 6. Cases of fuzzy tardiness and fuzzy earliness for each job j( a ) tardiness or earliness; (b) no tardiness or earliness; (c) earliness; (d) tardiness. Consequently, in some cases, it cannot be assured with certainty that a job jwill be completed with earliness or tardiness, and in some cases, this possibility can be very high or low. Thus, when calculating the total weighted penalty of a job j, the possibility of occurrence of an advance PE j or a delay PT j will be considered. For this, Equation (23) describes the membership function µCj(x) of the fuzzy completion time e Cj , Equations (24)–(26) show the centroid method to defuzzify the fuzzy earliness, and Equations (27)–(29) show the centroid method to defuzzify the fuzzy tardiness and obtain a real number where E∗ j and T∗ j represent the defuzzification value of earliness and tardiness of job j, xµEj(x) and xµTj(x) represent the membership function of the fuzzy earliness and tardiness. µCj(x) =                    0six ≤Cin f j x−Cin f j cmod j−Cin f j siCin f j<x≤Cmod j Csup j−x csup j−Cmod j siCmod j<x<Csup j 0six ≥Csup j (23) E∗ j=R. SE xµEj(x)dx R. SE µEj(x)=R. SE xµCj(x)dx R. SE µCj(x)(24) Algorithms 2022,15, 334 9 of 19 PE j=R. SE µEj(x)dx R. SµCj(x)=R. SE µCj(x)dx R. SxµCj(x)(25) Ej=djA −E∗ j×PE j(26) T∗ j=R. ST xµTj(x)dx R. ST µTj(x)=R. ST xµCj(x)dx R. ST µCj(x)(27) PT j=R. ST µTj(x)dx R. SµCj(x)=R. ST µCj(x)dx R. SxµCj(x)(28) Tj=T∗ j−djB×PT j(29) Once the earliness and tardiness of job j(Ejand Tj) are obtained, Equation (30) calculates the total weighted penalty of the beta chromosome ror fitness value, considering the weight of earliness (WE), the weight of lateness (WT), and the weighting of job j(Wj). Zr=∑n 1WjTjWT+EjWE(30) Step 5. After evaluating the beta chromosomes, they are ordered from lowest to highest according to their fitness value (total weighted penalty), and the best chromosomes are selected to form part of the next generation using the elitism rate (ET ×PB). Step 6. The crossover operator completes the next generation by randomly selecting two alpha chromosomes from the current population (parents), then determining with the crossover probability (PC) whether the crossover operation is performed on the parents; or two offspring are generated identically to the parents. In the case of applying the crossover to the selected parents, a single crossing point is randomly chosen to divide each parent into two crossing sections, which are exchanged to form two offspring, as shown in Figure 7. Algorithms2022,15,xFORPEERREVIEW10of20   Figure7.Crossoveroperatorbasedonsinglecrossingpoint. Themutationoperatorisappliedaftercreatingtheoffspringalphas,generatinga randomnumberforeachoffspring.Ifthisrandomnumberislessthantheprobabilityof mutationMR,themutationoperationisperformedusingtheswappingmutationmethod (exchangemutation),wheretworandomlychosengenesareexchangedthroughaSWAP movement[36,37](seeFigure8).  Figure8.MutationoperatorbasedonSWAPmovements. Step7.Afterapplyingthecrossoverormutationoperator,infeasibleoffspringmay begeneratedbecauseoneormorejobsdonothaveassignedthenumberofoperations theyrequire,soajobjappearsmoreorfewertimesintheoffspringthanthenumberof operationsitmustperform.AsshowninFigure9,therepairmechanismrandomlyexchangesoneoftheremainingoperationsforamissingone. Gene1Gene2Gene3Gene4Gene5Gene6Gene7Gene8Gene9Gene10 Gene11 Gene12 Gene13 Gene14 Gene15 Gene16 Gene17 Input1313544221 2 2 3 5 1 1 5 4 Input2 0.66 0.93 0.31 0.80 0.73 0.75 0.91 0.56 0.21 0.99 0.96 0.38 0.44 0.41 0.80 0.06 0.10 Gene1Gene2Gene3Gene4Gene5Gene6Gene7Gene8Gene9Gene10 Gene11 Gene12 Gene13 Gene14 Gene15 Gene16 Gene17 Input1154332243 5 1 1 4 1 2 5 2 Input2 0.18 0.24 0.90 0.83 0.83 0.34 0.21 0.94 0.44 0.47 0.36 0.24 0.23 0.67 0.51 0.39 0.43 Gene1Gene2Gene3Gene4Gene5Gene6Gene7Gene8Gene9Gene10 Gene11 Gene12 Gene13 Gene14 Gene15 Gene16 Gene17 Input1313544223 5 1 1 4 1 2 5 2 Input2 0.66 0.93 0.31 0.80 0.73 0.75 0.91 0.56 0.44 0.47 0.36 0.24 0.23 0.67 0.51 0.39 0.43 Gene1Gene2Gene3Gene4Gene5Gene6Gene7Gene8Gene9Gene10 Gene11 Gene12 Gene13 Gene14 Gene15 Gene16 Gene17 Input1154332241 2 2 3 5 1 1 5 4 Input2 0.18 0.24 0.90 0.83 0.83 0.34 0.21 0.94 0.21 0.99 0.96 0.38 0.44 0.41 0.80 0.06 0.10 Parent1 Parent2 SectionA SectionASectionB SectionB Offspring1 SectionA‐Parent1SectionB‐Parent2 Offspring2 SectionA‐Parent2SectionB‐Parent1 Gene1Gene2Gene3Gene4Gene5Gene6Gene7Gene8Gene9Gene10 Gene11 Gene12 Gene13 Gene14 Gene15 Gene16 Gene17 Input1154332241 2 2 3 5 1154 Input2 0.180.240.900.830.83 0.34 0.21 0.94 0.21 0.99 0.96 0.38 0.44 0.41 0.80 0.06 0.10 Gene1Gene2Gene3Gene4Gene5Gene6Gene7Gene8Gene9Gene10 Gene11 Gene12 Gene13 Gene14 Gene15 Gene16 Gene17 Input1154312241 2 2 3 5 3154 Input2 0.180.240.900.830.41 0.34 0.21 0.94 0.21 0.99 0.96 0.38 0.44 0.83 0.80 0.06 0.10 Offspring2Mutated Offspring2 SWAP movement Figure 7. Crossover operator based on single crossing point. Algorithms 2022,15, 334 16 of 19 Algorithms2022,15,xFORPEERREVIEW17of20  heuristic.Regardingtheaveragepossibilityoftardyjobs,GAprovidesaveragesavingsof 95.8%comparedtothebenchmarksconsidering20jobsandaveragesavingsof76.2%considering30jobs.Thus,itisconfirmedthattheproposedGA,inadditiontoprovidingsatisfactorysolutionsintheweightedtardinessandearlinesspenalty,alsoprovidessatisfactorysolutionsregardingthepossibilityandnumberoftardyjobs.  (a)(b) Figure13.Objectivefunctionvs.iterationsinthegeneticalgorithmconsidering(a)20jobsand(b) 30jobs. Table5.NumberoftardyjobsfortheGAcomparedtothebenchmarks. Algorithm NumberofTardyJobsBased onPossibilities%Savings j=20j=30j=20j=30 Geneticalgorithm15‐‐ HeuristicEDD51580.0%66.7% HeuristicSPT61783.3%70.6% HeuristicCR41275.0%58.3% MonteCarloSimulation51480.0%64.3% Table6.AveragepossibilityoftardyjobsfortheGAcomparedtothebenchmarks. Algorithm AveragePossibilityofTardy Jobs%Savings j=20j=30j=20j=30 Geneticalgorithm0.50%10.72%‐ ‐ HeuristicEDD12.05%47.06%95.9%77.2% HeuristicSPT13.96%52.16%96.4%79.4% HeuristicCR9.55%39.05%94.8%72.5% MonteCarloSimulation12.79%44.14%96.1%75.7% Regardingcomputingtime,thegeneticalgorithmrequiresanaverageof10.5minto findthebestsolutionwhenconsidering20jobsand2000iterations,whileitrequires17.6 mintofindthebestsolutionwhenconsidering30jobsand2000iterations.Whencomparingthecomputingtimefor20jobsagainst30jobs(50%increaseinthenumberofjobs), thecomputingtimeincreasesonaverageby68.3%,showingthecombinatorialcomplexity andNP‐hardnatureoftheFJSSPwithsequence‐dependentsetuptimes.Inthissense,itis relevantthatdecision‐makersconsiderthetrade‐offbetweenthesolutionqualityandthe computingtimeofthegeneticalgorithmtoobtainsatisfactorysolutionsinreasonable timesforproductionsystems.  350 400 450 500 550 600 650 700 750 10 80 150 220 290 360 430 500 570 640 710 780 850 920 990 1060 1130 1200 1270 1340 1410 1480 1550 1620 1690 1760 1830 1900 1970 FitnessValue Iterations 900 1000 1100 1200 1300 1400 1500 1600 1 70 140 210 280 350 420 490 560 630 700 770 840 910 980 1050 1120 1190 1260 1330 1400 1470 1540 1610 1680 1750 1820 1890 1960 FitnessValue Iterations Figure 13. Objective function vs. iterations in the genetic algorithm considering ( a ) 20 jobs and ( b ) 30 jobs. In addition to the analysis of the objective function of this study, Tables 5and 6present other performance indicators such as the number of tardy jobs (based on possibilities), and the average possibility of tardy jobs, where it is considered that a job jhas tardiness possibility when Csup j>djB . Based on the results, the solution obtained with the GA provides only one job that can be late with a 0.50% chance when considering 20 jobs, while five jobs can be late with a 10.72% chance when considering 30 jobs. Likewise, the GA provides average savings of 79.6% in the number of late jobs compared to the benchmarks considering 20 jobs and maximum savings of 83.3% compared to the SPT heuristic. Similarly, GA provides average savings of 65.0% in the number of tardy jobs compared to the benchmarks considering 30 jobs and maximum savings of 70.6% compared to the SPT heuristic. Regarding the average possibility of tardy jobs, GA provides average savings of 95.8% compared to the benchmarks considering 20 jobs and average savings of 76.2% considering 30 jobs. Thus, it is confirmed that the proposed GA, in addition to providing satisfactory solutions in the weighted tardiness and earliness penalty, also provides satisfactory solutions regarding the possibility and number of tardy jobs. Table 5. Number of tardy jobs for the GA compared to the benchmarks. Algorithm Number of Tardy Jobs Based on Possibilities % Savings j= 20 j= 30 j= 20 j= 30 Genetic algorithm 1 5 - - Heuristic EDD 5 15 80.0% 66.7% Heuristic SPT 6 17 83.3% 70.6% Heuristic CR 4 12 75.0% 58.3% Monte Carlo Simulation 5 14 80.0% 64.3% Table 6. Average possibility of tardy jobs for the GA compared to the benchmarks. Algorithm Average Possibility of Tardy Jobs % Savings j= 20 j= 30 j= 20 j= 30 Genetic algorithm 0.50% 10.72% - - Heuristic EDD 12.05% 47.06% 95.9% 77.2% Heuristic SPT 13.96% 52.16% 96.4% 79.4% Heuristic CR 9.55% 39.05% 94.8% 72.5% Monte Carlo Simulation 12.79% 44.14% 96.1% 75.7% Regarding computing time, the genetic algorithm requires an average of 10.5 min to find the best solution when considering 20 jobs and 2000 iterations, while it requires 17.6 min to find the best solution when considering 30 jobs and 2000 iterations. When comparing the computing time for 20 jobs against 30 jobs (50% increase in the number Algorithms 2022,15, 334 17 of 19 of jobs), the computing time increases on average by 68.3%, showing the combinatorial complexity and NP-hard nature of the FJSSP with sequence-dependent setup times. In this sense, it is relevant that decision-makers consider the trade-off between the solution quality and the computing time of the genetic algorithm to obtain satisfactory solutions in reasonable times for production systems. 6. Conclusions This study addresses for the first time FJSSP in fuzzy environments considering parameters and constraints of real production systems such as sequence-dependent setup times, due windows, recirculation, and consideration of earliness and tardiness in objective functions. Due to the complexity of the FJSSP, it is necessary to use artificial intelligence techniques such as genetic algorithms, which provide satisfactory solutions in reasonable computation times. One of the main contributions of this article is the proposal of a genetic algorithm and four heuristics since they represent one of the first approaches to tackle the FJSSP considering the realistic conditions presented in this study and applied to a fabric finishing production system. When comparing the results of the proposed genetic algorithm with different heuristics, it was possible to verify that, in all cases, the proposed methodology exceeded the performance of the heuristics by more than 30%, which shows the effectiveness of the proposed algorithm. Additionally, the GA provides satisfactory solutions regarding the possibility and number of tardy jobs. Moreover, the computing time of the genetic algorithm is viable for operating environments; therefore, it can be used daily in flexible job shop systems once the production orders are available. These results showed that the proposed genetic algorithm provides the best solutions for the FJSSP, outperforming heuristics widely used in production systems. Consequently, this study reduces the penalties related to earliness and tardiness and flexible job shop systems, increasing customer service and storage costs, inventory obsolescence, and lost sales. Despite the contributions of the study, it still has some flaws. In the future, datasets such as BRdata [ 44 ], Kacem data [ 45 ], BCdata [ 46 ], and HUdata [ 47 ] can be used to test the efficiency and effectiveness of the proposed GA, and compare its performance with other metaheuristics such as ACO, ABC, AIS, NS, SA, TS, PSO, hybrid metaheuristics, and other evolutionary algorithms. Likewise, future studies could include orthogonal experiments for parameter tuning for both the genetic algorithm and the metaheuristics used as benchmarks. Future works could consider changes in work speed, limitations in transportation and storage within the production system, machine downtime, and stockout probabilities. Moreover, the proposed algorithm could be complemented with a local search algorithm to improve the fitness of the chromosomes and reduce the number of iterations necessary to find a satisfactory solution. Author Contributions: Conceptualization, E.A.C. and E.R.-V.; methodology, E.A.C., E.R.-V. and J.A.C.; software, E.A.C.; validation, E.R.-V., J.A.C. and R.G.-M.; formal analysis, E.A.C. and J.A.C.; investigation, E.A.C.; resources, R.G.-M.; data curation, E.A.C.; writing—original draft preparation, E.A.C. and J.A.C.; writing—review and editing, J.A.C. and E.A.C.; visualization, J.A.C. and E.A.C.; supervision, E.R.-V. and P.C.; project administration, E.A.C.; funding acquisition, R.G.-M. All authors have read and agreed to the published version of the manuscript. Funding: This research received no external funding. Data Availability Statement: The data will be accessible upon request. Conflicts of Interest: The authors declare no conflict of interest. References 1. Li, X.; Gao, L. An effective hybrid genetic algorithm and tabu search for fl exible job shop scheduling problem. Intern. J. Prod. Econ. 2016,174, 93–110. [CrossRef] 2. Zhang, G.; Lu, X.; Liu, X.; Zhang, L.; Wei, S.; Zhang, W. An effective two-stage algorithm based on convolutional neural network for the bi-objective flexible job shop scheduling problem with machine breakdown. Expert Syst. Appl. 2022 ,203, 117460. [CrossRef] Algorithms 2022,15, 334 18 of 19 3. Li, H.; Wang, X.; Peng, J. A hybrid differential evolution algorithm for flexible job shop scheduling with outsourcing operations and job priority constraints. Expert Syst. Appl. 2022,201, 117182. [CrossRef] 4. Ojstersek, R.; Tang, M.; Buchmeister, B. Due date optimization in multi-objective scheduling of flexible job shop production. Adv. Prod. Eng. Manag. 2020,15, 481–492. [CrossRef] 5. Liu, W.; Wang, X.; Wang, X.; Zhao, P. Due-window assignment scheduling with past-sequence-dependent setup times. Math. Biosci. Eng. 2022,19, 3110–3126. [CrossRef] [PubMed] 6. Jiang, T.; Deng, G. Optimizing the Low-Carbon Flexible Job Shop Scheduling Problem Considering Energy Consumption. IEEE Access 2018,6, 46346–46355. [CrossRef] 7. Lei, D. Pareto archive particle swarm optimization for multiobjective fuzzy job shop scheduling problems. Int. J. Adv. Manuf. Technol. 2008,37, 157–165. [CrossRef] 8. Hu, Y.; Yin, M.; Li, X. A novel objective function for job-shop scheduling problem with fuzzy processing time and fuzzy due date using differential evolution algorithm. Int. J. Adv. Manuf. Technol. 2011,56, 1125–1138. [CrossRef] 9. Ahmadizar, F.; Zarei, A. Minimizing makespan in a group shop with fuzzy release dates and processing times. Int. J. Adv. Manuf. Technol. 2013,66, 2063–2074. [CrossRef] 10. Behnamian, J. Survey on fuzzy shop scheduling. Fuzzy Optim. Decis. Mak. 2016,15, 331–366. [CrossRef] 11. Ahmadizar, F.; Rabanimotlagh, A.; Arkat, J. Stochastic group shop scheduling with fuzzy due dates. J. Intell. Fuzzy Syst. 2017 , 33, 2075–2084. [CrossRef] 12. Kacem, I.; Hammadi, S.; Borne, P. Pareto-optimality Approach Based on Uniform Design and Fuzzy Evolutionary Algorithms for Flexible Job-shop Scheduling Problems (FJSPs). In Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, Yasmine Hammamet, Tunisia, 6–9 October 2002; pp. 304–310. 13. Dhamala, T.N.; Thapa, G.B.; Yu, H.-N. An Efficient Frontier for Sum Deviation JIT Sequencing Problem in Mixed-model Systems via Apportionment. Int. J. Autom. Comput. 2012,9, 87–97. [CrossRef] 14. Cano, J.A.; Correa-Espinal, A.A.; Gómez-Montoya, R.A. Mathematical programming modeling for joint order batching, sequencing and picker routing problems in manual order picking systems. J. King Saud Univ.-Eng. Sci. 2020,32, 219–228. [CrossRef] 15. Çali¸s, B.; Bulkan, S. A research survey: Review of AI solution strategies of job shop scheduling problem. J. Intell. Manuf. 2015 , 26, 961–973. [CrossRef] 16. Soto, C.; Dorronsoro, B.; Fraire, H.; Cruz-Reyes, L.; Gomez-Santillan, C.; Rangel, N. Solving the multi-objective flexible job shop scheduling problem with a novel parallel branch and bound algorithm. Swarm Evol. Comput. 2020,53, 100632. [CrossRef] 17. Chaudhry, I.A.; Khan, A.A. A research survey: Review of flexible job shop scheduling techniques. Int. Trans. Oper. Res. 2016 , 23, 551–591. [CrossRef] 18. Hajibabaei, M.; Behnamian, J. Flexible job-shop scheduling problem with unrelated parallel machines and resources-dependent processing times: A tabu search algorithm. Int. J. Manag. Sci. Eng. Manag. 2021,16, 242–253. [CrossRef] 19. Ojstersek, R.; Brezocnik, M.; Buchmeister, B. Multi-objective optimization of production scheduling with evolutionary computation: A review. Int. J. Ind. Eng. Comput. 2020,11, 359–376. [CrossRef] 20. Amjad, M.K.; Butt, S.I.; Kousar, R.; Ahmad, R.; Agha, M.H.; Faping, Z.; Anjum, N.; Asgher, U. Recent Research Trends in Genetic Algorithm Based Flexible Job Shop Scheduling Problems. Math. Probl. Eng. 2018,2018, 9270802. [CrossRef] 21. Pezzella, F.; Morganti, G.; Ciaschetti, G. A genetic algorithm for the Flexible Job-shop Scheduling Problem. Comput. Oper. Res. 2008,35, 3202–3212. [CrossRef] 22. Zhang, G.; Gao, L.; Shi, Y. An effective genetic algorithm for the flexible job-shop scheduling problem. Expert Syst. Appl. 2011 , 38, 3563–3573. [CrossRef] 23. Sonmez, R.; Bettemir, Ö.H. A hybrid genetic algorithm for the discrete time-cost trade-off problem. Expert Syst. Appl. 2012 , 39, 11428–11434. [CrossRef] 24. Gogna, A.; Tayal, A. Metaheuristics: Review and application. J. Exp. Theor. Artif. Intell. 2013,25, 503–526. [CrossRef] 25. Wang, C.; Tian, N.; Ji, Z.; Wang, Y. Multi-objective fuzzy flexible job shop scheduling using memetic algorithm. J. Stat. Comput. Simul. 2017,87, 2828–2846. [CrossRef] 26. Shi, D.L.; Zhang, B.B.; Li, Y. A multi-objective flexible job-shop scheduling model based on fuzzy theory and immune genetic algorithm. Int. J. Simul. Model. 2020,19, 123–133. [CrossRef] 27. Zhang, H.; Collart-Dutilleul, S.; Mesghouni, K. Cyclic Scheduling of Flexible Job-shop with Time Window Constraints and Resource Capacity Constraints. IFAC-PapersOnLine 2015,48, 816–821. [CrossRef] 28. Jafarzadeh, H.; Moradinasab, N.; Gerami, A. Solving no-wait two-stage flexible flow shop scheduling problem with unrelated parallel machines and rework time by the adjusted discrete multi objective invasive weed optimization and fuzzy dominance approach. J. Ind. Eng. Manag. 2017,10, 887–918. [CrossRef] 29. Jamrus, T.; Chien, C.F.; Gen, M.; Sethanan, K. Hybrid Particle Swarm Optimization Combined With Genetic Operators for Flexible Job-Shop Scheduling Under Uncertain Processing Time for Semiconductor Manufacturing. IEEE Trans. Semicond. Manuf. 2018 , 31, 32–41. [CrossRef] 30. Chen, J.C.; Wu, C.C.; Chen, C.W.; Chen, K.H. Flexible job shop scheduling with parallel machines using Genetic Algorithm and Grouping Genetic Algorithm. Expert Syst. Appl. 2012,39, 10016–10021. [CrossRef] 31. Nouiri, M.; Bekrar, A.; Jemai, A.; Niar, S. An effective and distributed particle swarm optimization algorithm for flexible job-shop scheduling problem. J. Intell. Manuf. 2018,29, 603–615. [CrossRef] Algorithms 2022,15, 334 19 of 19 32. Wei, Z.; Liao, W.; Zhang, L. Hybrid energy-efficient scheduling measures for flexible job-shop problem with variable machining speeds. Expert Syst. Appl. 2022,197, 116785. [CrossRef] 33. Ortiz, M.; Neira, D.; Jiménez, G.; Hernández, H. Solving flexible job-shop scheduling problem with transfer batches, setup times and multiple resources in apparel industry. Lect. Notes Comput. Sci. 2016,9713, 47–58. [CrossRef] 34. Demir, Y.; I¸sleyen, S.K. Evaluation of mathematical models for flexible job-shop scheduling problems. Appl. Math. Model. 2013 , 37, 977–988. [CrossRef] 35. Wang, W.; Li, X.; Zhang, Y. An improved multi-objective genetic algorithm for fuzzy flexible job-shop scheduling problem. Int. J. Comput. Appl. Technol. 2013,47, 280–288. [CrossRef] 36. Cano, J.A.; Correa-Espinal, A.A.; Gómez-Montoya, R.A.; Cortés, P. Genetic Algorithms for the Picker Routing Problem in Multi-block Warehouses. In Lecture Notes in Business Information Processing; Abramowicz, W., Corchuelo, R., Eds.; Springer: Cham, Switzerland, 2019; Volume 353, pp. 313–322. ISBN 9783030204846. 37. Cano, J.A.; Cortés, P.; Muñuzuri, J.; Correa-Espinal, A. Solving the picker routing problem in multi-block high-level storage systems using metaheuristics. Flex. Serv. Manuf. J. 2022. [CrossRef] 38. Coello, C.A. Introducción a la Computación Evolutiva (Notas de Curso); CINVESTAV-IPN: Mexico City, Mexico, 2022; pp. 1–296. Available online: https://delta.cs.cinvestav.mx/~{}ccoello/compevol/apuntes.pdf (accessed on 27 July 2022). 39. Teekeng, W.; Thammano, A. Modified Genetic Algorithm for Flexible Job-Shop Scheduling Problems. Procedia Comput. Sci. 2012 , 12, 122–128. [CrossRef] 40. Ruiz, S. Metodología multiobjetivo basada en un comportamiento evolutivo para programar sistemas de producción flexible job shop. In Aplicaciones en la Industria Metalmecánica; Universidad Nacional de Colombia: Bogotá, Colombia, 2015. 41. Salazar, E.; Figueroa, B. Tardiness minimization for the flexible flowshop with setup using constructive heuristics and a genetic algorithm. Ingeniare 2012,20, 89–98. [CrossRef] 42. González, Á. Diseño de una metodología de programación de producción para la reducción de costos en un flow shop híbrido flexible mediante el uso de algoritmos genéticos. In Aplicación a la Industria Textil; Universidad Nacional de Colombia: Bogotá, Colombia, 2013. 43. Companys, R.; D’Armas, M. Operation scheduling with setup times by local optimization algorithms. Universidad, Cienc. y Tecnol. 2005,9, 155–162. 44. Brandimarte, P. Routing and scheduling in a flexible job shop by taboo search. Ann. Oper. Res. 1993,41, 157–183. [CrossRef] 45. Kacem, I.; Hammadi, S.; Borne, P. Pareto-optimality approach for flexible job-shop scheduling problems: Hybridization of evolutionary algorithms and fuzzy logic. Math. Comput. Simul. 2002,60, 245–276. [CrossRef] 46. Barnes, J.W.; Chambers, J.B. Flexible job shop scheduling by tabu search. In Graduate Program in Operations and Industrial Engineering, The University of Texas at Austin, Technical Report Series, ORP96-09; The University of Texas at Austin: Austin, TX, USA, 1996. 47. Hurink, J.; Jurisch, B.; Thole, M. Tabu search for the job-shop scheduling problem with multi-purpose machines. OR Spectr. 1994 , 15, 205–215. [CrossRef]