1. INTRODUCTION
Production scheduling focuses on the allocation of limited resources over time to carry out a group of different activities. In the scheduling theory, resources and tasks are often known as machines and jobs, respectively (Ab Yajid, 2020;Thanh et al., 2021;Jalil et al., 2020;Matthews and Mokoena, 2020). Some of the most important objectives of scheduling problems include the efficient use of resources, quick response to demand and accurate compliance of delivery times with the specified delivery date (Qazani et al., 2021;Shamsipur et al., 2012;Tirkolaee et al., 2020). A flexible flow shop scheduling problem is a developed form of general flow shop environments and parallel machines, where C stations are arranged in series instead of m machines, such that m_{1} equal machines are parallel to each other in each station of (L =1, 2,…, c)L . Each task must be performed by one machine (one of the parallel machines) in each station, even though all machines can carry out the process (Barzamini and Ghassemian, 2019;Johar and Alkawaz, 2018;Alhodiry et al., 2021). In other words, each job is performed by one of the parallel machines in station 1, and then by one of the equal parallel machines in station 2 and ultimately by one of the equal machines in the last station. In some machine environments in operating environments, unemployment of a machine between the processing operations of two jobs makes that machine environment or manufacturing industry unfeasible and uneconomical. This is one of the important aspects of industries such as fiberglass manufacturing, casting, production of integrated circuits, steel manufacturing industries, dairy industries, textile industries, paint industries, among others (Dahmardeh et al., 2013;Sholpanbaeva et al., 2021;Nursalim, 2021). This is known as a nonpermutation flowshop scheduling problem (NPFSP), where the unemployment of machines is not allowed from the beginning of the first job to the end of the last job. Therefore, delay in the commence of jobs must occur in a way that the constraints related to the unemployment of each machine (i.e., idle time) are guaranteed to be zero. Two preparation processes are carried in scheduling problems to prepare the machines for jobs. In the first mode, preparation time is sequenceindependent, meaning that preparation time is considered during the processing of the work by the machine. In the second mode, however, machine preparation time depends on the task that has been already processed by the machine (Fofack et al., 2020;Jaapar et al., 2020;Wafa, 2021;Alwreikat and Rjoub, 2020). Observed in most machine environments, the second preparation mode is recognized as sequencedependent preparation time in the literature on scheduling issues. The present study aims to model a flexible flow shop scheduling problem without unemployment by considering sequencedependent preparation times in order to minimize the maximum completion time of works. To date, no research has been conducted to consider such an issue in flow shop problems (Alsunki et al., 2020;Singh et al., 2020;Kormishkina et al., 2021;Ishenin et al., 2021). The remainder of the study is structured, as follows: Section 2 reviews the literature related to the topic under study while Section 3 defines the problem and the model’s premises. Section 4 provides the mathematical modeling of the problem, whereas Section 5 focuses on the validation of the proposed mathematical model by LINGO software, solves the proposed problem using genetics algorithm (GA) and compares its quality and solution time with the mentioned software. Finally, Section 6 concludes and makes suggestions for future studies.
2. LITERATURE REVIEW
Bernik (2021) were the first scholars who evaluated NPFSPs for the first time. In a study, they proposed a polynomial algorithm for a flow shop problem in a certain mode with two machines with the objective function of minimizing the total completion time of works. Ferina et al. (2021) studied an NPFSP with the objective function of minimizing the maximum completion time for the first time and proposed a branchandbound procedure for solving the problem. In a study, Narain and Bagga (2005) focused on njob, 2machine flow shop scheduling problems working under a “noidle” constraint. They developed a branchandbound structure to solve the model and considered the objective function to be the minimization of mean flow shop. In the end, it was proven that the problem with the objective function of the total makespan of works was of NPhard type.
Saadani et al. (2003) treated the scheduling problem of threestage permutation flowshop configuration with noidle machines. The idle characteristic is a very strong constraint, which can seriously affect the value of the makespan criterion. They proposed a heuristic to solve this problem with O(nlogn) complexity. Based on the previous study, Kamburowski (2004) identified a simple network representation of the makespan that provided a better insight into the problem and improved the solution obtained for the noidle flow shop problem. Saadani et al. (2005) investigated a noidle flow shop problem, for which they proposed a mixed integer programming model and then developed a heuristic based on the idea that the problem could be modeled as a traveling salesman problem. In a study, Kalczynski and Kamburowski (2005) focused on the problem of finding a job sequence that minimizes the makespan in mmachine flow shops under the noidle condition. Since the problem was NPhard, they proposed a constructive heuristic for solving the problem that significantly outperformed heuristics known so far. Niu and Gu (2006) developed an improved geneticbased particle swarm optimization for noidle permutation flow shops with fuzzy processing time. Goncharov and Sevastyanov (2009) considered a flow shop problem with noidle constraints and the objective function of minimizing the makespan of jobs. These researchers developed several polynomialtime heuristics for special cases of 3 and 4 machines based on the geometric method. Nagano and Januário (2013) evaluated a noidle flow shop scheduling problem with the objective of minimizing the makespan.
Tasgetiren et al. (2013) presented a variable iterated greedy algorithm (IG) with differential evolution designed to solve the noidle permutation flow shop scheduling problem. The parameters of the algorithm included the destruction size and the probability of applying the IG algorithm to an individual. Pan and Ruiz (2014) studied the mixed noidle extension where only some machines had the noidle constraint. They used an NEHbased heuristic to construct a highquality initial solution. Sun and Gu (2017) proposed a novel hybrid estimation of the distribution algorithm and cuckoo search (CS) algorithm to solve the NIPFSP with the total tardiness criterion minimization. The computational results indicated the proper performance of the hybrid algorithm presented in the foregoing study. Yazdani and Naderi (2016) considered the problem of scheduling noidle hybrid flow shops. They developed a mixedinteger linear programming model to mathematically formulate the problem with the objective function of minimizing the maximum completion time of tasks. In the end, two metaheuristics based on variable neighborhood search and GAs were developed to solve larger instances. The computational results were indicative of the superior performance of GA.
Nagano et al. (2019) addressed the issue of production scheduling in a noidle flow shop environment and proposed a quality constructive heuristic instance following an extensive review of the literature. According to their results, integration of the heuristic method with the IG algorithm led to the higher efficiency of heuristic methods. Goli et al. (2019) developed a mathematical model for scheduling manufacturing systems, where AGV was used for the transportation of parts. Improved GA was applied to solve the scheduling problem in the mentioned condition. The literature review revealed a lack of study on the hypothesis of sequence dependence of preparation times in NIPFSPs with the objective function of minimizing the maximum completion time of jobs, which is addressed in the present research.
3. STATEMENT OF THE PROBLEM AND PREMISES
The NPFSP is developed from a flexible flow shop problem, where the machines are not allowed to be idle from the commence of the first job until finishing the last job. Therefore, delays in the start of jobs must occur in a way that the constraints related to the unemployment of each machine are guaranteed to be zero. The preparation times in the problem assessed are sequencedependent. The evaluated problem is exhibited in the form of $\text{FSS}\left\text{no}\text{idle},\text{SDST}\right{\text{C}}_{\text{max}}$ based on the symbolizing by Graham et al. (1979) which express the NPFSP with sequence dependent preparation times. The objective function is to minimize the maximum makespan of jobs. The following premises are considered for the problem:
The preparation time of machines is sequencedependent. The idle time of the machine is equal to zero (there is no idle interval between the commence of the first job until finishing all tasks). There are parallel and similar machines in each stage (workstation). Notably, simultaneous performance of two operations of a job is not feasible. In other words, each task at each stage (station) should only be processed on one of the parallel and identical machines. There is no interruption i.e., a task remains on the machine until its processing is completed. There is no cancelation during the tasks, meaning that if an operation of a job is being processed, the next operations must also be processed. The transportation time between the machines is trivial, and there is unlimited storage between stations. Each machine is unable to process more than one job at a time. In addition, technical constraints are recognized and inflexible, and there is no stochastic mode, meaning that the processing times, preparation times and the number of jobs have crisp values. There is no downtime and machines are constantly available during the programming period.
4. MATHEMATICAL MODELING OF THE PROBLEM
The indices used for modeling the problem are defined below:
4.1 Indices and Sets

n : number of jobs

j, i : index of jobs $\text{j,}\hspace{0.17em}\text{i}=\left\{1,2,\hspace{0.17em}\dots ,\hspace{0.17em}\text{n}\right\}$

m : number of stages (stations)

k : index of stages (stations) $\text{k}=\left\{1,2,\hspace{0.17em}\dots ,\hspace{0.17em}\text{m}\right\}$

m_{k} : number of machines at the k stage

l : index of the machine at the k stage k l={1, 2,…, m_{k}}

h : index of the sequence of jobs on each machine k h ={1, 2,…, h_{k}}
4.2 Model Parameters

p_{ik} : processing duration of the ith job at the k stage

SUP_{ijk} : preparation time of the jth job if the jth job is immediately processed after the ith job in the k stage. Given the similarity of machines at each stage, this parameter is independent of the machine index.

M : a big positive number
4.3 Decision Variables

C_{max} : maximum completion time of jobs

X_{ijklh} : a binary variable; 1, if the jth job is placed in the h position in the l machine immediately after the ith job in the k stage and the jth and ith jobs are placed in the h and h1 positions, respectively; otherwise, 0.

R_{iklh} : a binary variable; 1, if the ith job is placed in the h position of the l machine at the k stage; otherwise, 0.

S_{ik} : the start time of processing the ith job at the k stage

SB_{klh} : the start time of processing a job that is placed in the h position of the l machine at the k stage.
4.4 Mathematical Model
4.4.1 Objective Function
4.4.2 Constraints
4.5 Model Description
In this model, Equation 1 is the objective function of the problem, which minimizes the maximum completion time of jobs. Constraints 2 and 3 guarantee that the operations of each job at each station are placed in a position of the sequence of jobs on the machine. Constraints 4 means that the X_{ijklh} the variable is equal to one if the jth job is placed in the sequence of jobs on the l machine at the k stage following the ith job and if the jth and ith jobs are placed in h and h1 positions, respectively. Otherwise, it will be zero (in other words, the variable of X_{ijklh} will be equal to one when the variables of R_{jklh} and R_{jkl,h1} are both equal to one). In addition, the mentioned constraints make the model nonlinear, and linearization of the model is addressed in the next stage. Constraints 5 tune the start time of processing each job on each workstation. In other words, a job will not be processed in a station until its processing is completed in the previous station. Constraints 6 and 7 are defined for tuning the start time of processing each job in each station and the start time of jobs on the machines. Constraints 8 is defined for tuning the start time of jobs on each machine of stations. These constraints are added to the model to determine the start time of jobs on the machine and indicate that the processing of the jth job cannot be initiated until the processing of the previous job is not finished and the preparation time of the jth task, which depends on the previous ith job, is not passed. In addition, the equal sign guarantees the noidle hypothesis (machine unemployment occurs when the start time of the current job is larger than the finish time of the previous job plus the preparation time. However, using equality in the constraints will prevent idle time. Meanwhile, the sequencedependent preparation times between the jobs existing in the sequence will be calculated and applied). Constraints 9 calculate the objective function, which is minimizing the completion time of jobs. Finally, constraints 1014 determine the nature of the decision variables of the model.
5. Solution method
5.1 Model linearization
Constraints make the model nonlinear due to the existence of a multiplication sign between the decision variables. Therefore, Constraints 4 are replaced by constraints 15 and 16 to develop a linear model (Meng and Pan, 2021).
In the next section, the mathematical model is solved by LINGO software at small scales, followed by presenting GA to solve the problems and compare the solution time and quality of LINGO software to the GA which is described as follows.
5.2 Proposed Genetic Algorithm
From the 1960s onward, there has been an extensive development of modeling living creatures' behaviors to increase the robustness of the existing algorithms or create new algorithms for optimal problemsolving. In short, algorithms developed based on this type of thinking are recognized as evolutionary algorithms, one of the most popular of which is the GA. This natureinspired algorithm is widely applied in various problems. The GA is an evolved search method based on natural selection and genetics, which uses a structured but random approach to exploit genetic data in pursuit of new search routes. GA is applied in a wide range of scientific fields. The algorithm is developed and used in the present study to optimize the proposed mathematical model.
Since the problem presented in the research encompasses two sections of: A) allocating jobs to machines at each stage, and B) determining the sequence of jobs allocated to each machine at each stage, the solution of the problem is displayed in the form of a matrix with K rows and N columns (K is the number of stages and N is the number of jobs). Each tow shows the sequence of jobs at each stage. The matrix has a value in the range of zeroone. First, the numbers in each row are divided by the number of parallel machines available. For instance, if there are two parallel machines in the first stage, numbers in the range of 00.5 will be allocated to the first machine and numbers in the range of 0.51 will be assigned to the second machine. Similarly, if there are three parallel machines, numbers in the ranges of 00.333, 0.3330.666, 0 and 1, and 0.6661 will be allocated to the firstthird machines, respectively. The same process is carried out for a higher number of machines. Afterwards, the jobs assigned to each machine are arranged from small to large. This, in fact, shows the sequence of jobs on each machine. For instance, assume that N=5, K=2, and M=[23], meaning that there are two machines in the first stage and three machines in the second stage. The example solution strand of the problem is shown in Table 1.
The order of jobs in the first stage is, as follows:
134
52
In the second stage, the order of jobs is, as follows:
41
2
35
The fit function considered for each chromosome of each generation is equal to the value of the objective function or Cmax, and the initial population is generated by producing a uniform random number between 0 and 1. Some of the most common parent selection methods are the Roulette wheel, the random method, the ranking method, and the competitive selection method. In this article, the parent selection process is completely random for the crossover due to the nature of GA, which is based on a random search. There are several methods for the crossover operator in chromosomes that use the numbers zero and one and integers. In this regard, some of the conventional methods are listed below:
Onepoint crossover, twopoint crossover, multipoint crossover, uniform crossover, threeparent crossover, PPX crossover, and sorted crossover. Other crossover techniques are used in chromosomes in which real numbers are used for coding. In this regard, one of these methods is the intermediate propagation method, in which the value of the child variable is a linear combination of parent variables (Equation 17).
where X2 and X1 are parent variables, X’2 and X1 are child variables and λ2, λ1 are linear coefficients.
Crossover operations are often implemented on a percentage of the population. A coefficient of 0.8 or 80% is considered for the problem under study. In this article, the crossover is carried out in intermediate propagation or linear combination form. First, a parameter named Landa is randomly generated in the range of [0.2 1.2]. Afterwards, the linear combination of two parents is calculated and introduced as children. It is notable that if the cell’s value is higher than one, it will be changed to one, and if it is less than zero, it will be changed to zero. In the problem of the present study, 20% of chromosomes are changed by the mutation operator. This value is obtained due to choosing an 80% coefficient for the crossover operator. To carry out the mutation process, we select 20% of the cells on each chromosome (response strand) and change their value randomly. If 20% of the number of cells is not an integer, it will be rounded to the nearest multiple of five. The mechanism of survival selection is such that children produced better than the parents are passed on to the next generation as elite without any change. Afterwards, 80% of the remaining population is generated by the crossover operator and 20% is used by the mutation operator for the next generation. In this article, the initial population is created randomly, and the algorithm is terminated after reaching a certain number generation.
6. NUMERICAL RESULTS
In this section, a numerical instance is presented and solved by the LINGO software. In addition, validation of the model is carried out following drawing its Gantt chart. Consider a problem with five jobs and three stages (stations), where there are three identical and parallel machines in the first station, one machine in the second station and two similar and parallel machines in the third station. Assume that the processing time of jobs on the machines of each station is the form of Table2. The numbers related to the processing times of each job in each stage (pik) are randomly generated in the range [1070] of uniform distribution. Afterwards, the generated numbers are rounded to the nearest multiple of five (given the fact that the machines of each station are identical and parallel, the processing time of each job at the stations is independent of the number of machines. Therefore, the processing times of each job are presented at each stage).
Given the threedimensional nature of the parameter of sequencedependent preparation times at each stage (SUP_{ijk}), the values cannot be shown in a twodimensional table (the matrix related to this parameter is in threedimensional form). Therefore, data is presented in the form of the following example. The numbers related to the preparation times are generated randomly in the range of 520 of uniform distribution and then the created numbers are rounded to the nearest multiple of five:
According to Equation 19, the preparation time, which depends on the sequence of the job of j=2, will be equal to 10 units of time if the job is placed in the sequence of jobs at the stage of k=3 after the job of j=1. The value of the objective function is estimated at 295 following coding and solving the model in LINGO software. The solution is obtained in 1601 seconds by a computer with features of CPU DualCore 1.6 GHz and 2GB RAM (Table 3 presents a summary of primary results).
Table 4 exhibits the Gantt chart of the example solved by the LINGO software (red colors are related to the sequencedependent preparation times).
As observed in Table 4, the start time of each job is delayed in a way that the noidle hypothesis is established. In addition, the preparation times are considered to be sequencedependent.
6.1 Evaluation of the Proposed Mathematical Model
One of the important indicators for evaluating mathematical programming models is estimating the computational time of the model to solve a problem in specialized mathematical programming software. Therefore, the numbers for each problem are listed in the related tables generating a number of problems and solving them by LINGO software. Afterwards, the validation of the models is carried out by comparing the results. The values of this parameter are randomly selected from a discrete uniform distribution range of 570. Another important parameter is the sequencedependent preparation time, the value of which is selected randomly from a discrete uniform distribution range of 1224. To evaluate the numerical examples, the problems are generated in three classes, as follows:
First class: classic flow shop (only one machine exists in each stage).
Second class: hybrid flow shop with an equal number of machines at each stage.
Third class: hybrid flow shop with a different number of machines at each stage. All examples are obtained by a computer with 2GB of RAM and an Intel DualCore 1.6 GHz CPU, and the maximum solution time is reported to be 7200 seconds. Tables 57 present the results of the LINGO solution report related to the first to thirdclass problems to find the optimal solution. The optimality gap column is the percentage difference of the upper and lower bound of the objective function in examples where the software fails to achieve an optimal solution in 7200 seconds.
According to the figure, the higher the number of stages, the longer the solution time for an equal number of jobs. For instance, the solution time of five jobs at two stages is equal to 70 seconds, which is much less than the solution time of five jobs at four stages, where no optimal solution is obtained in 7200 seconds.
6.2 Evaluation and Comparison of Problem Solution Results by LINGO and GA Solution Method
Table 8 shows the results related to the comparison of results of solving a number of examples by the LINGO software and the proposed GA.
Table 8 has 11 columns, firstthree of which show the number of problem rows, the number of stages (stations) and the number of machines per stage from left to right, respectively. In addition, the fourth column shows the number of jobs per problem, and the fiftheighth columns show the objective function solution, the lower bound, optimality gap and solution time by LINGO, respectively. Moreover, the ninth and tenth columns are related to the solution and solution time of GA. The last column shows the percentage of difference in the solution of LINGO and GA. The negative values shown in the last column show that the solution obtained by LINGO at intervals of 7200 and 14400 seconds is worse than the solutions obtained by GA. The symbol of (*) next to the solutions of the fifth column shows that the LINGO software does not yield an optimal solution in 7200 seconds. In addition, the column of optimality gap shows the percentage of difference in the optimal solution obtained in the intervals of 7200 0r 14400 seconds, and the lower bound is estimated by LINGO software. The figure of the column of LINGO solutions and GA solutions is drawn in Figure 1.
In Figure 1, in 15 out of 36 solved problems, GA yields solutions in the intervals of 7200 and 14400 seconds, which are better or equal to LINGO. However, LINGO yields better results in 21 cases, which is due to comparing the results within the range of issues resolved with LINGO. This number will change in favor of the GA if the number of problems in larger sizes, in which solution time by lingo increases dramatically, is also taken into account. In problems of rows 6 and 11, LINGO fails to reach an optimal solution even within the interval of 14400 seconds. The solution is obtained with a 17% and 45% optimality gap. However, GA yields better results with 3.1% and 1.4% and at five and six seconds, respectively, which shows the extremely good speed of GA. A comparison of mean computational times for problems 1 6 is shown in Figure 2, which demonstrates the superiority of the GA in this regard.
The mean computational time of GA for the problems is equal to 4.6 seconds. Meanwhile, the mean computational time of solving the mathematical model by the LINGO software is equal to 2976 seconds, which shows a considerable difference with the GA’s computational time. According to the results, as the number of stages and jobs increases, the computational time increases, and this increase is exponential in Lingo. The mean percentage of deviation of the solutions of the GA and Lingo in 36 solved problems with the inclusion of positive and negative values is equal to 2.1% and in the case of worse deviation (positive) is equal to 5.2% and in equal or better (negative) deviation values is equal to 4.7%.
7. CONCLUSION AND RECOMMENDATIONS
In this study, we developed a linear mixedinteger mathematical model following describing an NPFSP with identical and parallel machines in stations with the objective function of minimizing the maximum completion time of jobs. The validation of the model was carried out by coding the mathematical model in the LINGO software. Given the fact that the problem was NPhard, we presented a heuristic GA approach, which was coded in MATLAB software. The computational results of solving 36 problems generated with random numbers by the LINGO and GA in 7200 and 14400 seconds are compared in terms of solution quality and computational time. In the end, the computational results demonstrated the relatively suitable performance of GA, such that the mean percentage of GA solutions to the mathematical model was equal to 2.1% and the mean time of reaching a solution was 4.6 seconds for GA against the average time of yielding a solution by LINGO, which was reported to be 2976 seconds.
For future studies, it is recommended that:
Presenting efficient heuristic and metaheuristic approaches and efficient hybrid methods for the problem, adding new observable premises in the operational environments such as buffer’s limit for each station, considering the constraints of maintenance and preventive repairs for the existing machines, considering uncertainty for the problem, considering batch processing machines such as heat furnaces that have the ability to process or simultaneously heat several parts, considering the noidle assumption for a certain number of machines in each stage and assuming unemployment permit for other machines, considering other objective functions such as minimizing the total time of delays for delivery of works, considering the existence of parallel and nonparallel machines in each stage in terms of processing speed, and considering a nowait premise for jobs along with noidle for machines that will increase the complexity of the problem are recommended for future studies.