# Modeling and Solving the Flow-Shop Scheduling Problem with Sequence-Dependent Setup Times by Firefly Algorithm (Case Study: Automotive Industry)

Authors: Mustafa Mohammadi; Seyed Ahmad Shayannia; Mohamadreza Lotfi; Javad Rezaeian Zaidi
Journal: Discrete Dynamics in Nature and Society
 (2022)

---

## Abstract

Progress in today’s modern industry requires a lot of knowledge, one of which is scheduling. Flow-shop scheduling is one of the most widely used optimization problems. In this research, considering the importance of simultaneously order in different stages of production in the automotive industry, and also in order to make the problem more practical, we have investigated the problem of scheduling the flow-shop, taking into account the lead time and the costs of each order. Due to the fact that in most research studies, the lead time and costs of an order have been ignored because they made it difficult to find the initial solution to the problem. In this research, using the firefly meta-heuristic method, a suitable solution is provided to overcome this problem. Therefore, considered objective function is to minimize the total completion time. Absolute relative error (ARE) has been used to validate the model in a deterministic and meta-heuristic mode. According to the ARE result, the difference in the results between the two algorithms is negligible. Then, the sequence results are determined according to the desired algorithm for 5 tasks considered for automobile parts. The results show that the completion time of job 1 is 1397.85; job 2 is 771.44; job 3 is 608.65; job 4 is 1163.87; and job 5 is 479.45.


---

## Body

## 1. Introduction

Planning is the making of decisions for the future, and production planning means determining the production strategy for allocating production lines to meet orders. One of the most prominent cases in preparing the manufacturing schedule for production lines in determining the accumulated size and sequence of orders and how to allocate resources over time [1]. We always use the term schedule in our everyday conversations. However, we may not always have a proper definition in mind. Although schedules generally seem tangible and simple, creating them is complex without a deep understanding of scheduling. Scheduling problems in the industry have a similar structure. They include a set of activities and resources available to perform those activities. Also, some decisions are known as planning decisions in the industry. The planning process determines the resources needed to produce and the activities required for scheduling. In the scheduling process, we need to determine the type and amount of each resource, and as a result, we can determine the possible time of completion of jobs [2]. Scheduling is allocating resources limited to activities over time to optimize one or more objective functions. Resources include manpower, machinery, materials, and auxiliary equipment. Machinery operations, movements, transfers, loads, etc. are also examples of activities. Activities can have the earliest start time, the latest end time, and the delivery time. The purpose of scheduling is cases such as the minimum completion time for a set of orders, minimum delay, the maximum number of activities or orders completed in a given time, minimum intermediate inventory, and interaction in the use of resources. According to the intended objectives and with regard to the existing constraints such as production capacity, resource capacity, resource inventory, budget constraints, and time constraints, the problem of scheduling or allocating resources to activities over time is done [3, 4].Based on the abovementioned discussion, scheduling is allocating resources over time to perform a set of jobs. This definition has two different meanings. First, scheduling is a kind of decision-making process during which the schedule is set. Second, scheduling is a theoretical topic that encompasses a set of principles, models, methods, and logical outcomes that provide us with in-depth insights into the practice of scheduling. Therefore, considering that, it is assumed that there is a production strategy for ordering in this research. In this strategy, production is done based on the orders received. Unlike the production strategy for the warehouse where the production is done first, and then, the goods are stored in the warehouse to find a suitable customer, no products will be produced without an order from the customer. Many orders are received in the first period, some of which are accepted based on production capacity, and others are rejected. In this case, production needs to be scheduled in such a way as to minimize all tangible costs such as delay costs, adjustment costs, and maintenance costs, which are among the most critical criteria in terms of production scheduling and planning in many industries. In such a situation, a multicriteria scheduling model is usually needed.As mentioned above, in this study, jobs in usual flow-shop problems are replaced by orders. Scheduling several orders where each order contains a certain number of similar jobs and a specific customer with a definite delivery time and a specific delay cost will be the main focus of the research. Maintenance and delay costs will be very important in the problem under study. In such problems, scheduling decisions have two levels. Scheduling of orders is at a higher level so that which order and how and in what order should be processed. The next level is scheduling of jobs within each order in a way that in what order the jobs need to be processed. Here, only the first level is examined, and the order of processing the jobs within each order is not the subject of this research. For this, the main contributions of this article are as follows:(i)
Determined a schedule for sequence orders in the flow-shop problem.(ii)
Proposed an integer linear programming model for flow-shop scheduling problems, assuming sequence-dependent setups.The rest of the article is organized as it is clear. The second section provides the historical background of past studies to identify the research gap. In the third section, the proposed framework and analysis method are introduced. The fourth section provides the research results of solving the proposed model. In the fifth section, managerial insights is presented. Finally, a general conclusion and suggestions for future research are provided in the sixth section.


## 2. Literature Review

In this section, we introduce studies that have been conducted in the past. Wang and Cheng [5] investigated the permutation flow-shop problem assuming the existence of only two machines and considering the capacity constraint for only the first machine. The setups in their study depended on the sequence. Schaller et al. [6] investigated the scheduling of families’ jobs within each family in the flow-shop environment. In their study, the setup times between families are assumed to depend on sequences. The objective is to minimize the total completion time when jobs within each family are being processed. Ruiz et al. [7] introduced two genetic algorithms for the permutation flow-shop problem and showed that the algorithms introduced by them work better than other algorithms, especially Mercado and Brad [8]. They used the modified NEH method to find the initial solution to the flow-shop problem. The name of the heuristic method is NEHT-RMB, which can be used as an effective method to find a set of appropriate answers to the flow-shop problem. In the genetic algorithms introduced, the answers were used as the pool of answers in the algorithm. Also, Ruiz and Stutzle [9] in their paper introduced two simple local search methods based on an interactive greedy algorithm. Their algorithm is two-stage: the destruction stage, in which some jobs are removed from the initial answer, and the construction stage, in which the deleted jobs are assigned to the initial answer using the NEH heuristic method. They showed that their algorithm works better than the algorithm of Ruiz et al. [7]. The introduced algorithm against a wide range of case studies was compared with a set of algorithms introduced in the literature, which shows the superiority of the introduced algorithm. Of course, the greedy algorithm alone is not very powerful without using local search. Ekşioğlu et al. [10] have provided an article in flow-shop flow problems, and in their article, they have used the modified tabu search method to solve the problem. However, with a general review, their method does not have the simplicity and accuracy of the greedy algorithm. Also, the studied space in the greedy algorithm is more comprehensive than the algorithm developed by them. In their recent article, Allahverdi et al. [11] provide a comprehensive overview of the studies conducted on the problems of flow-shop and permutation flow-shop. In recent studies, Balaji and Porselvi [12] consider the problem of scheduling batches of parts in a multicell flexible manufacturing system with batch setup time. The goal is to find the best sequence of batches and thus minimize the time interval. For this purpose, two mathematical models have been created: the batch availability model and the job availability model. Since the problem is NP-hard, a particle swarm optimization algorithm and a simulated annealing algorithm are proposed to solve the problem. The experimental results show that the simulated annealing method offers a better solution than particle swarm optimization. Celik and Dal [13] have developed a simulated annealing-based meta-heuristic method for cluster-based job scheduling in which sequential and parallel modes of the workflow are implemented in C++ software according to the model in this method. The effectiveness of the proposed approach is shown through 12 well-known criteria from the Brown dataset. In their study, Hashemi et al. [14] proposed a new approach based on particle swarm optimization for cellular problems with alternative routing to minimize intercellular motions. The applied approach offers a very near-optimal solution with only one change in component configuration compared to the best-known solution with the exact method. Finally, the computational results of the applied approach suggest a new adjusted optimization scenario for cellular manufacturing systems with alternative routes. This approach shows that particle swarm optimization with the number of particles as close as possible to the number of parts, inertia weights proportional to the maximum, and a minimum number of alternative routing and learning factors with a normal value of 2 can achieve an optimal value in less time. Brum et al. [15] address the problem of nonpermutation flow-shop scheduling, a more general type of flow-shop problem in which machines can have different sequences of jobs. The goal of this study is to minimize the total completion time. For this purpose, a model for generating meta-heuristic algorithms is proposed, and an automated algorithm configuration is used to obtain efficient methods. Algorithms start by building a high-quality permutation solution, which is then improved in the second stage, creating nonpermutation solutions by changing the order of jobs on some machines. Tamssaouet et al. [16] have proposed a scheduling framework for solving the complex multiobjective job-shop scheduling problem resulting from production. To produce practical and meaningful industrial schedules, this study extends the proposed batch approach by considering periods of unavailability and minimum time delays and simultaneously optimizing various industry-related criteria. To this end, a new criterion for the satisfaction of higher-level decision-making production goals has also been proposed. Abolghasemian et al. [17] presented a delay scheduling based on discrete-event simulation for construction projects. For this purpose, a combined approach of discrete-event simulation and computational modeling was applied; then, we compare the results. Measurements show that the systems fragmented by repeated and short repetitions while referring to early are in optimal performance. Rashidi Komijan et al. [18] presented a new bus routing. For this purpose, a multiobjective mixed-integer model is proposed to handle the associated problem. The minimization of transportation cost as well as traveling time is the main objective. The proposed model is applied in a real case study including 4 schools in Tehran. The results indicate the efficiency of the proposed model in comparison with the existing system. Khanchehzarrin et al. [19] presented a new mixed-integer nonlinear programming model for the time-dependent vehicle routing problem with time windows and intelligent travel times. The aim is to minimize fixed and variable costs, with the assumption that the travel time between any two nodes depends on traffic conditions and is considered to be a function of vehicle departure time. Depending on working hours, the route between any two nodes has a unique traffic parameter. For this purpose, considered each working day to be divided into several equal and large intervals, termed as a time interval of traffic. For this purpose, a Tabu search optimization algorithm is devised for solving large problems. Also, after linearization, a number of random instances are generated and solved by the CPLEX solver of GAMS to assess the effectiveness of our proposed algorithm. The results indicate that the initial travel time is estimated appropriately and updated properly in accordance with the repeating traffic conditions. Rezaei et al. [20] presented a vehicle routing problem in relief supply chain under crisis condition considering blood types. For this purpose, a bi-objective mixed-integer linear programming (MILP) model was developed for relief supply under crisis condition. The mentioned model has two objectives: maximizing the amount of blood collected by bloodmobiles and minimizing the arrival time of the blood receiver buses and a helicopter to a crisis-stricken city after the collected blood is used up. The model is coded by CPLEX software, and the results obtained from solving the model indicate that, without considering a helicopter, the demand is not supplied within the critical period after crisis. Momenitabar et al. [21] for the first time considered the impacts of the backup suppliers and lateral transshipment/resupply simultaneously on designing a sustainable closed-loop supply chain network (SCLSCN) to decrease the shortage that may occur during the transmission of produced goods in the network. In this manner, the fuzzy multiobjective mixed-integer linear programming model is proposed to design an efficient SCLSCN resiliently. Moreover, the concept of circular economy has been studied in this article to reduce environmental effects. This study aims at optimizing total and environmental costs, including energy consumption and pollution emissions, while increasing job opportunities. Pourghader chobar et al. [22] designed a multiobjective hub-spoke network of perishable tourism products. In order to consider the perishable factor of the products, some collection centers are considered for the products, which are perished. Accordingly, the combination of Hub-Spoke network and supply chain is assessed here. Moreover, this combination is to use transportation discounts in the supply chain network. The desired combination is done in such a way that the distributors are considered a set of hubs.


### 2.1. Research Gap

According to previous studies, most of the papers examined in this review have studied sequence-dependent setups. Therefore, studies in which time and cost are sequence-dependent are not considered. The most important gap in this study is to consider similar jobs within each order, in which the time and cost of setup between two jobs from one order are ignored. For this purpose, to fill the research gap, adding such an assumption makes it very difficult to find an initial answer to the problem based on the existing heuristic methods. To overcome such a problem, a specific delivery time and a certain delay cost are assumed for each order (based on the customer’s opinion). Table1 shows previous studies categorized based on solution approach and main goals.Table 1
Categorized literature review.
ReferencesSolution approachGoalAuthorNumberMeta-heuristicExactSimulationComputationalPSOAGIGNSGA-IIHashemi et al[14]∗Minimize intercellular motionBrum et al[15]∗Nonpermutation flow-shopTamssaoret et al[16]∗Flow-shop schedulingAbolghasemian et al[17]∗∗Construction delay schedulingRashidi komijan et al[18]∗Minimizing transportation costKhanchehzarrin et al[19]∗Minimize fix and variable costRezaei et al.[20]∗Minimize amount of blood collectedMomenitabar et al.[21]∗Optimize total and environmental costsPourghader chobar et al.[22]∗Designed a multiobjective hub-spoke network of perishable tourism productsTherefore, the main contributions of this study are as follows:(i)
Determined a schedule for prioritizing orders in the job-shop problem.(ii)
Determining the optimal time for the determined sequences.(iii)
Proposed an integer linear programming model for flow-shop scheduling problems, assuming sequence-dependent setups.(iv)
Using a novel meta-heuristic solution approach to optimize the problem for executing concurrent work on each order using a specific lead time and cost impact factor for each order.


## 2.1. Research Gap

According to previous studies, most of the papers examined in this review have studied sequence-dependent setups. Therefore, studies in which time and cost are sequence-dependent are not considered. The most important gap in this study is to consider similar jobs within each order, in which the time and cost of setup between two jobs from one order are ignored. For this purpose, to fill the research gap, adding such an assumption makes it very difficult to find an initial answer to the problem based on the existing heuristic methods. To overcome such a problem, a specific delivery time and a certain delay cost are assumed for each order (based on the customer’s opinion). Table1 shows previous studies categorized based on solution approach and main goals.Table 1
Categorized literature review.
ReferencesSolution approachGoalAuthorNumberMeta-heuristicExactSimulationComputationalPSOAGIGNSGA-IIHashemi et al[14]∗Minimize intercellular motionBrum et al[15]∗Nonpermutation flow-shopTamssaoret et al[16]∗Flow-shop schedulingAbolghasemian et al[17]∗∗Construction delay schedulingRashidi komijan et al[18]∗Minimizing transportation costKhanchehzarrin et al[19]∗Minimize fix and variable costRezaei et al.[20]∗Minimize amount of blood collectedMomenitabar et al.[21]∗Optimize total and environmental costsPourghader chobar et al.[22]∗Designed a multiobjective hub-spoke network of perishable tourism productsTherefore, the main contributions of this study are as follows:(i)
Determined a schedule for prioritizing orders in the job-shop problem.(ii)
Determining the optimal time for the determined sequences.(iii)
Proposed an integer linear programming model for flow-shop scheduling problems, assuming sequence-dependent setups.(iv)
Using a novel meta-heuristic solution approach to optimize the problem for executing concurrent work on each order using a specific lead time and cost impact factor for each order.


## 3. Proposed Method

This section introduces an integer linear programming model for flow-shop scheduling problems, assuming sequence-dependent setups taken from research sources [23]. For this purpose, details of the proposed mathematical modeling such as symbols, problem statement, and solution approach are stated.


### 3.1. Symbols

#### 3.1.1. Sets

n: Number of jobsm: Number of machinesi: Subscript of job ii=1,…,nj: Subscript of machine jj=1,…,n


#### 3.1.2. Variables

Pij: Processing time, indicating the time required to process job i on machine j.Sikj: Setup time from a job i to job k on machine j (i = 0 refers to the initial setup time of the scheduled job).Cij: Completion time of job i on machine j.Xik: If job i is processed before job k, it is equal to one; otherwise, it is equal to zero.


#### 3.1.3. Objective Function

The objective is to minimize the total completion time or the completion time of the last job on the last machine, which is consideredMinimize makespan=Cnm.


#### 3.1.4. Set of Constraints

Constraint (1) guarantees that all jobs are scheduled and the completion time of job i on machine 1 is at least as large as the processing time of that job on the machine:(1)pi1≥ci1;i=1,…,n.Processing jobi cannot start on machine j unless it is finished on machine j−1. Constraint (2) guarantees that the completion time of job i on machine j must be at least as large as the processing time on machine j, one greater than the completion time on machine j−1:(2)pij+cij−1≥cij,i=1,2,…,n;j=2,3,…,m.Constraints (3) and (4) guarantee that there is only one constraint for each sequence of jobs. This case shows the relationship between precedence and latency between jobs:(3)cij−ckj+Mxik≥skij+pij,(4)cij−ckj+M1−xik≥skij+pij,where k>i≥1 and i=1,2,…,n;k=1,2,…,n;j=1,2,…,m. Also, M is a very large number. Constraints (5) and (6) guarantee that only one job can follow another job in each schedule:(5)∑i=1nxik=1;k=1,2,…,nfori≠k,(6)∑k=1nxik=1;k=1,2,…,nfori≠k.


#### 3.1.5. Model Assumption

The main model assumption is as follows:(i)
There is a certain number of jobs that can be assigned to a station.(ii)
Each operation is performed on its own machine.(iii)
The processing time of each job is determined.(iv)
The prerequisites for each work have been determined. Therefore, a task is executable when its prerequisite is completely completed.


### 3.2. Problem Statement

Azintaneh Factory, which is studied in this research, was established in 1994 and operated in manufacturing light- and heavy-vehicle brake system components. This factory has received special attention by employing specialized and experienced employees required by a part of the country’s automotive industry in the company’s management, along with increasing manufacturing capacity and product quality. This company succeeded and became one of the important suppliers of Iran-Khodro, Saipa, and Renault Pars Khodro. It also operates under the license of Lockheed A.P. of the United Kingdom and Bosch of Germany. This factory produces five types of booster products as follows.(1)
8-inch ABS booster (Bardo) for use in Peykan Pickup.(2)
9-inch ABS booster—for use in Peugeot 405.(3)
RANA booster—for use in Rana.(4)
10-inch ABS booster—for use in Samand.(5)
10-inch booster (LX)—for use in Samand LX.We have five jobs, four types of machines, and 58 activities. We have measured the time of each of these activities, which we examine below. The stages of each of these products are shown in Tables2–6 .Table 2
8-inch ABS booster line.
Name of 8-inch ABS booster line stationTime (minute : seconds)First station27 : 27Second station22 : 28Third station10 : 06Fourth station11 : 05Fifth station38 : 29Sixth station34 : 17Seventh station19 : 94Eighth station25 : 66Ninth station36 : 09Tenth station36 : 04Eleventh station23 : 75Twelfth station18 : 63Thirteenth station32 : 63Fourteenth station29 : 01Fifteenth station30 : 78Sixteenth station42 : 23Seventeenth station17 : 71Table 3
9-Inch ABS booster line.
Name of 9-inch ABS booster line stationTime (minute : seconds)First station20 : 55Second station14 : 17Third station21 : 91Fourth station41 : 20Fifth station78 : 48Sixth station18 : 19Seventh station3 : 31Eighth station39 : 68Ninth station14 : 14Tenth station12 : 14Table 4
10-inch ABS booster line.
Name of 10-inch ABS booster line stationTime (minute : seconds)First station31 : 64Second station26 : 31Third station39 : 37Fourth station35 : 11Fifth station25 : 19Sixth station20 : 96Seventh station27 : 01Eighth station35 : 94Ninth station45 : 84Table 5
RANA booster line.
Name of RANA booster line stationTime (minute : seconds)First station39 : 69Second station25 : 17Third station28 : 64Fourth station23 : 99Fifth station15 : 45Sixth station32 : 35Seventh station11 : 99Eighth station21 : 04Ninth station22 : 22Tenth station24 : 39Eleventh station39 : 69Twelfth station13 : 32Thirteenth station14 : 06Table 6
LX booster line.
Name of LX booster line stationTime (minute : seconds)First station25 : 12Second station23 : 74Third station18 : 64Fourth station15 : 99Fifth station26 : 71Sixth station18 : 76Seventh station17 : 86Eighth station21 : 51Ninth station30 : 12


### 3.3. Solution Approach: A Firefly Optimization Algorithm

The firefly algorithm is one of the most powerful asset optimization algorithms, which is highly regarded for its convergence to the global optimal solution. The firefly algorithm, like other meta-heuristic algorithms, includes stages. This algorithm consists of seven stages: first, selecting the parameters; second, the initial random solution (Rand of sizek) and writing the main loop of the algorithm, which is different according to the type of algorithms; third, moving around the firefly towards brighter fireflies; fourth, merging; fifth, choosing the best; sixth, if the stopping condition was set, stop the algorithm; otherwise, return to the second stage and re-run the stages, and finally the output of the algorithm.


#### 3.3.1. Setting Required Parameters

To determine and adjust the parameters of the firefly algorithm, we first design a number of scenarios using a design of experiment. In order to design experiments in the firefly algorithm, the Taguchi method has been used. To use this method, first, 3 different levels (low-level code 1, medium-level code 2, and high-level code 3) are defined for their parameters. And then, the predefined tests in this algorithm are executed for all possible combinations. The recommended values for the parameters of this algorithm are according to Table7.Table 7
Parameters and levels for the firefly algorithm.
ParametersValueLevel 1Level 2Level 3Gamma0.0250.050.1Beta0.050.10.2Alpha0.20.30.5Alpha_damp0.250.750.99Then, with Taguchi’s L9 design, we create different experiments and implement the firefly algorithm for each one. The execution results are presented in Table8. In Table 8, all possible states are shown for different levels considered for the firefly algorithm factors. For example, in the first experiment, all the factors have been included in the experiment for their lowest level. In the second experiment, the gamma factor with the lowest level value and other factors with their respective average level value are present. In the same way, other possible states are completed based on the permutation rule in statistics. By running each design and calculating the value of the firefly algorithm, the desired response level is estimated using this algorithm.Table 8
Results of design of experiment response.
RunAlgorithm parametersFirefly outputGammaBetaAlphaAlpha_damp111110.534212220.612313330.537421230.491522310.576623120.637731320.599832130.973933210.642By calculating the signal-to-noise ratio for each of the parameters and evaluating the calculated values, we determine the best level for each of the parameters. The lower the value of the signal-to-noise ratio for each parameter level, the more that parameter level is selected. Table9 shows the calculated signal-to-noise ratio.Table 9
S/N results.
ParametersS/NLevel 1Level 2Level 3Gamma4.95.10.2Beta5.20.34.3Alpha0.34.84.9Alpha-damp4.343.7Therefore, the best value of each parameter according to the S/N results is selected as follows:Gamma = 0.1: light absorption coefficient,Beta0 = 0.1: Absorption coefficient base value,Alpha = 0.2: mutation coefficient,Alpha_damp = 0.99: Alpha decreases by one percent in each iteration. We want it to converge towards a good solution.


## 3.1. Symbols

### 3.1.1. Sets

n: Number of jobsm: Number of machinesi: Subscript of job ii=1,…,nj: Subscript of machine jj=1,…,n


### 3.1.2. Variables

Pij: Processing time, indicating the time required to process job i on machine j.Sikj: Setup time from a job i to job k on machine j (i = 0 refers to the initial setup time of the scheduled job).Cij: Completion time of job i on machine j.Xik: If job i is processed before job k, it is equal to one; otherwise, it is equal to zero.


### 3.1.3. Objective Function

The objective is to minimize the total completion time or the completion time of the last job on the last machine, which is consideredMinimize makespan=Cnm.


### 3.1.4. Set of Constraints

Constraint (1) guarantees that all jobs are scheduled and the completion time of job i on machine 1 is at least as large as the processing time of that job on the machine:(1)pi1≥ci1;i=1,…,n.Processing jobi cannot start on machine j unless it is finished on machine j−1. Constraint (2) guarantees that the completion time of job i on machine j must be at least as large as the processing time on machine j, one greater than the completion time on machine j−1:(2)pij+cij−1≥cij,i=1,2,…,n;j=2,3,…,m.Constraints (3) and (4) guarantee that there is only one constraint for each sequence of jobs. This case shows the relationship between precedence and latency between jobs:(3)cij−ckj+Mxik≥skij+pij,(4)cij−ckj+M1−xik≥skij+pij,where k>i≥1 and i=1,2,…,n;k=1,2,…,n;j=1,2,…,m. Also, M is a very large number. Constraints (5) and (6) guarantee that only one job can follow another job in each schedule:(5)∑i=1nxik=1;k=1,2,…,nfori≠k,(6)∑k=1nxik=1;k=1,2,…,nfori≠k.


### 3.1.5. Model Assumption

The main model assumption is as follows:(i)
There is a certain number of jobs that can be assigned to a station.(ii)
Each operation is performed on its own machine.(iii)
The processing time of each job is determined.(iv)
The prerequisites for each work have been determined. Therefore, a task is executable when its prerequisite is completely completed.


## 3.1.1. Sets

n: Number of jobsm: Number of machinesi: Subscript of job ii=1,…,nj: Subscript of machine jj=1,…,n


## 3.1.2. Variables

Pij: Processing time, indicating the time required to process job i on machine j.Sikj: Setup time from a job i to job k on machine j (i = 0 refers to the initial setup time of the scheduled job).Cij: Completion time of job i on machine j.Xik: If job i is processed before job k, it is equal to one; otherwise, it is equal to zero.


## 3.1.3. Objective Function

The objective is to minimize the total completion time or the completion time of the last job on the last machine, which is consideredMinimize makespan=Cnm.


## 3.1.4. Set of Constraints

Constraint (1) guarantees that all jobs are scheduled and the completion time of job i on machine 1 is at least as large as the processing time of that job on the machine:(1)pi1≥ci1;i=1,…,n.Processing jobi cannot start on machine j unless it is finished on machine j−1. Constraint (2) guarantees that the completion time of job i on machine j must be at least as large as the processing time on machine j, one greater than the completion time on machine j−1:(2)pij+cij−1≥cij,i=1,2,…,n;j=2,3,…,m.Constraints (3) and (4) guarantee that there is only one constraint for each sequence of jobs. This case shows the relationship between precedence and latency between jobs:(3)cij−ckj+Mxik≥skij+pij,(4)cij−ckj+M1−xik≥skij+pij,where k>i≥1 and i=1,2,…,n;k=1,2,…,n;j=1,2,…,m. Also, M is a very large number. Constraints (5) and (6) guarantee that only one job can follow another job in each schedule:(5)∑i=1nxik=1;k=1,2,…,nfori≠k,(6)∑k=1nxik=1;k=1,2,…,nfori≠k.


## 3.1.5. Model Assumption

The main model assumption is as follows:(i)
There is a certain number of jobs that can be assigned to a station.(ii)
Each operation is performed on its own machine.(iii)
The processing time of each job is determined.(iv)
The prerequisites for each work have been determined. Therefore, a task is executable when its prerequisite is completely completed.


## 3.2. Problem Statement

Azintaneh Factory, which is studied in this research, was established in 1994 and operated in manufacturing light- and heavy-vehicle brake system components. This factory has received special attention by employing specialized and experienced employees required by a part of the country’s automotive industry in the company’s management, along with increasing manufacturing capacity and product quality. This company succeeded and became one of the important suppliers of Iran-Khodro, Saipa, and Renault Pars Khodro. It also operates under the license of Lockheed A.P. of the United Kingdom and Bosch of Germany. This factory produces five types of booster products as follows.(1)
8-inch ABS booster (Bardo) for use in Peykan Pickup.(2)
9-inch ABS booster—for use in Peugeot 405.(3)
RANA booster—for use in Rana.(4)
10-inch ABS booster—for use in Samand.(5)
10-inch booster (LX)—for use in Samand LX.We have five jobs, four types of machines, and 58 activities. We have measured the time of each of these activities, which we examine below. The stages of each of these products are shown in Tables2–6 .Table 2
8-inch ABS booster line.
Name of 8-inch ABS booster line stationTime (minute : seconds)First station27 : 27Second station22 : 28Third station10 : 06Fourth station11 : 05Fifth station38 : 29Sixth station34 : 17Seventh station19 : 94Eighth station25 : 66Ninth station36 : 09Tenth station36 : 04Eleventh station23 : 75Twelfth station18 : 63Thirteenth station32 : 63Fourteenth station29 : 01Fifteenth station30 : 78Sixteenth station42 : 23Seventeenth station17 : 71Table 3
9-Inch ABS booster line.
Name of 9-inch ABS booster line stationTime (minute : seconds)First station20 : 55Second station14 : 17Third station21 : 91Fourth station41 : 20Fifth station78 : 48Sixth station18 : 19Seventh station3 : 31Eighth station39 : 68Ninth station14 : 14Tenth station12 : 14Table 4
10-inch ABS booster line.
Name of 10-inch ABS booster line stationTime (minute : seconds)First station31 : 64Second station26 : 31Third station39 : 37Fourth station35 : 11Fifth station25 : 19Sixth station20 : 96Seventh station27 : 01Eighth station35 : 94Ninth station45 : 84Table 5
RANA booster line.
Name of RANA booster line stationTime (minute : seconds)First station39 : 69Second station25 : 17Third station28 : 64Fourth station23 : 99Fifth station15 : 45Sixth station32 : 35Seventh station11 : 99Eighth station21 : 04Ninth station22 : 22Tenth station24 : 39Eleventh station39 : 69Twelfth station13 : 32Thirteenth station14 : 06Table 6
LX booster line.
Name of LX booster line stationTime (minute : seconds)First station25 : 12Second station23 : 74Third station18 : 64Fourth station15 : 99Fifth station26 : 71Sixth station18 : 76Seventh station17 : 86Eighth station21 : 51Ninth station30 : 12


## 3.3. Solution Approach: A Firefly Optimization Algorithm

The firefly algorithm is one of the most powerful asset optimization algorithms, which is highly regarded for its convergence to the global optimal solution. The firefly algorithm, like other meta-heuristic algorithms, includes stages. This algorithm consists of seven stages: first, selecting the parameters; second, the initial random solution (Rand of sizek) and writing the main loop of the algorithm, which is different according to the type of algorithms; third, moving around the firefly towards brighter fireflies; fourth, merging; fifth, choosing the best; sixth, if the stopping condition was set, stop the algorithm; otherwise, return to the second stage and re-run the stages, and finally the output of the algorithm.


### 3.3.1. Setting Required Parameters

To determine and adjust the parameters of the firefly algorithm, we first design a number of scenarios using a design of experiment. In order to design experiments in the firefly algorithm, the Taguchi method has been used. To use this method, first, 3 different levels (low-level code 1, medium-level code 2, and high-level code 3) are defined for their parameters. And then, the predefined tests in this algorithm are executed for all possible combinations. The recommended values for the parameters of this algorithm are according to Table7.Table 7
Parameters and levels for the firefly algorithm.
ParametersValueLevel 1Level 2Level 3Gamma0.0250.050.1Beta0.050.10.2Alpha0.20.30.5Alpha_damp0.250.750.99Then, with Taguchi’s L9 design, we create different experiments and implement the firefly algorithm for each one. The execution results are presented in Table8. In Table 8, all possible states are shown for different levels considered for the firefly algorithm factors. For example, in the first experiment, all the factors have been included in the experiment for their lowest level. In the second experiment, the gamma factor with the lowest level value and other factors with their respective average level value are present. In the same way, other possible states are completed based on the permutation rule in statistics. By running each design and calculating the value of the firefly algorithm, the desired response level is estimated using this algorithm.Table 8
Results of design of experiment response.
RunAlgorithm parametersFirefly outputGammaBetaAlphaAlpha_damp111110.534212220.612313330.537421230.491522310.576623120.637731320.599832130.973933210.642By calculating the signal-to-noise ratio for each of the parameters and evaluating the calculated values, we determine the best level for each of the parameters. The lower the value of the signal-to-noise ratio for each parameter level, the more that parameter level is selected. Table9 shows the calculated signal-to-noise ratio.Table 9
S/N results.
ParametersS/NLevel 1Level 2Level 3Gamma4.95.10.2Beta5.20.34.3Alpha0.34.84.9Alpha-damp4.343.7Therefore, the best value of each parameter according to the S/N results is selected as follows:Gamma = 0.1: light absorption coefficient,Beta0 = 0.1: Absorption coefficient base value,Alpha = 0.2: mutation coefficient,Alpha_damp = 0.99: Alpha decreases by one percent in each iteration. We want it to converge towards a good solution.


## 3.3.1. Setting Required Parameters

To determine and adjust the parameters of the firefly algorithm, we first design a number of scenarios using a design of experiment. In order to design experiments in the firefly algorithm, the Taguchi method has been used. To use this method, first, 3 different levels (low-level code 1, medium-level code 2, and high-level code 3) are defined for their parameters. And then, the predefined tests in this algorithm are executed for all possible combinations. The recommended values for the parameters of this algorithm are according to Table7.Table 7
Parameters and levels for the firefly algorithm.
ParametersValueLevel 1Level 2Level 3Gamma0.0250.050.1Beta0.050.10.2Alpha0.20.30.5Alpha_damp0.250.750.99Then, with Taguchi’s L9 design, we create different experiments and implement the firefly algorithm for each one. The execution results are presented in Table8. In Table 8, all possible states are shown for different levels considered for the firefly algorithm factors. For example, in the first experiment, all the factors have been included in the experiment for their lowest level. In the second experiment, the gamma factor with the lowest level value and other factors with their respective average level value are present. In the same way, other possible states are completed based on the permutation rule in statistics. By running each design and calculating the value of the firefly algorithm, the desired response level is estimated using this algorithm.Table 8
Results of design of experiment response.
RunAlgorithm parametersFirefly outputGammaBetaAlphaAlpha_damp111110.534212220.612313330.537421230.491522310.576623120.637731320.599832130.973933210.642By calculating the signal-to-noise ratio for each of the parameters and evaluating the calculated values, we determine the best level for each of the parameters. The lower the value of the signal-to-noise ratio for each parameter level, the more that parameter level is selected. Table9 shows the calculated signal-to-noise ratio.Table 9
S/N results.
ParametersS/NLevel 1Level 2Level 3Gamma4.95.10.2Beta5.20.34.3Alpha0.34.84.9Alpha-damp4.343.7Therefore, the best value of each parameter according to the S/N results is selected as follows:Gamma = 0.1: light absorption coefficient,Beta0 = 0.1: Absorption coefficient base value,Alpha = 0.2: mutation coefficient,Alpha_damp = 0.99: Alpha decreases by one percent in each iteration. We want it to converge towards a good solution.


## 4. Computational Results

The developed model has been implemented in a personal system with CPU Intel Core i5 and RAM 4 GB specifications. To solve exact model GAMS 24.1.2 software and firefly meta-heuristic model MATLAB are used. For this, first, the problem data includes the times of each activity on the machines; we have five types of jobs and a total of 58 activities, and each activity has prerequisites. According to Table10, the prerequisites of each activity are specified. Then, after entering the data, we explain the parameters as follows. After running the model based on the items set above, it calculates the value of the objective function, which is the maximum value of time for the machines, in such a way as to minimize the machine that performs its job the latest. For this purpose, the function z=maxmach.t calculates the maximum time of machines taking into account Max it=10.Table 10
Prerequisites for each activity.
Station1234567891011121314151617Job 1———3—5678——11——14—16Job 2—1———56——9———————Job 3———345—78————————Job 4—12—45—789——12————Job 5—123——678————————According to the results, the completion time of the busiest machine is 275.83 seconds. After the evolutionary process that has been done, it reaches 271.27 seconds the second time, which is 4.56 seconds better than the previous one, and thus improves. Table11 shows the other computational results of the objective function of the problem based on the implementation of the firefly algorithm.Table 11
Results of objective functions in the ten iterations.
Iteration 1: Best fit = 275.83Iteration 2: Best fit = 271.27Iteration 3: Best fit = 266.83Iteration 4: Best fit = 261.79Iteration 5: Best fit = 259.83Iteration 6: Best fit = 259.83Iteration 7: Best fit = 259.83Iteration 8: Best fit = 254.83Iteration 9: Best fit = 254.83Iteration 10: Best fit = 254.83Then, by plotting the objective function according to Figure1, it is clear that the decreasing trend from the first to the tenth iteration is evident. Therefore, the objective function has a downward trend.Figure 1
The trend of changes in the value of the objective function in each iteration.In Tables12–16, the priority of the execution of each activity is shown according to their operations. In addition, the implementation of each operation using each machine is specified. Also, the duration of the execution of each activity in the optimal sequence mode has also been calculated. In Table 12, the sequence of job 1 activities is shown. The sequence of job 1 activities is 1; 2; 5; 6; 7; 11; 12; 13; 14; 15; 9; 10; 16; 17; 4; 3; 8. Based on the optimal sequence, the completion time of Job 1 is equal to 1397.85 minutes.Table 12
Sequence of job 1 operations.
JobOperationMachineStart timeFinal timeDuration111091.2791.2712291.27186.5595.281550129.29129.29166146.15190.3244.17177190.32280.2689.9411111036.7539.751121239.3278.9539.631131378.95148.5869.6311414148.58199.5951.0111515199.59260.3760.781990133.9133.911010305.35360.3955.0411616260.37347.657.2311717347.6451.31103.71144213.79248.29226.5133186.55261.6175.06188311.1346.7635.66Table 13
Sequence of job 2 operations.
JobOperationMachineStart timeFinal timeDuration2880115.68115.68244057.257.22923115.68174.8259.1421010174.82254.9680.142722019.3119.31211160.03186.5826.552219186.58297.05110.472320297.05415.96118.91252157.2213.65156.45266333.6361.1927.59Table 14
Sequence of job 3 operations.
JobOperationMachineStart timeFinal timeDuration35260104.19104.19366104.19146.1541.96311122.39160.0337.643224160.03272.24112.2133250101.75101.75344248.29287.439.113727146.15271.1612.01388271.16311.139.943928311.1430.94119.84Table 15
Sequence of job 4 operations.
JobOperationMachineStart timeFinal timeDuration41212039.3239.324133539.32153.92193.244229094.1794.17433094.17144.8150.6449330108.22108.2241010254.96305.3550.3941134305.35432.04126.69444144.81183.838.994531183.8287.25103.45466287.25333.646.354732090.9990.99488346.76387.841.04411186.58240.2753.69Table 16
Sequence of job 4 operations.
JobOperationMachineStart timeFinal timeDuration5538038.7138.7156638.71100.4761.7651191.27122.3931.125236052.7452.74533752.74118.3865.64544183.8213.7929.995739100.47196.3395.86588196.33224.8428.515940224.84299.9675.12In Table13, the sequence of job 2 activities is shown. The sequence of job 2 activities is 8; 4; 9; 10; 7; 1; 2; 3; 5 and 6. Based on the optimal sequence, the completion time of Job 2 is equal to 771.44 minutes.In Table14, the sequence of job 3 activities is shown. The sequence of job 3 activities is 5; 6; 1; 2; 3; 4; 7; 8; and 9. Based on the optimal sequence, the completion time of Job 3 is equal to 608.65 minutes.In Table15, the sequence of job 4 activities is shown. The sequence of job 4 activities is 12; 13; 2; 3; 9; 10; 11; 4; 5; 6; 7; 8 and 1. Based on the optimal sequence, the completion time of Job 4 is equal to 1163.87 minutes.In Table16, the sequence of job 5 activities is shown. The sequence of job 5 activities is 5; 6; 1; 2; 3; 4; 7; 8; and 9. Based on the optimal sequence, the completion time of Job 5 is equal to 479.45 minutes.


### 4.1. Validation

In order to evaluate the effectiveness of the algorithm, 7 numerical samples with different aspects are considered. Then, according to the response of the CPLEX exact method and the firefly algorithm, absolute relative error (ARE) is calculated that recommended Abolghasemian et al. [24]. ARE is calculated as shown in Equation (7) based on the comparison of genetic output and branches and borders. Table 17 compares the results obtained from the branch and bound algorithm.(7)Cplex output−firefly outputGfirefly output.Table 17
Comparing the obtained results from branch and bound algorithm.
Thenumberof problemMachinesOperationsResponseAREFireflytime(seconds)CPLEXtime(second)13622031940.04248112302500.0831034364500.03422134344420.015414105311000.04664189921000.097285404941000.01The ARE results shown in Table 17 are calculated to be less than 0.1 for each sample therefore, the error difference between the results of the two algorithms is negligible.


## 4.1. Validation

In order to evaluate the effectiveness of the algorithm, 7 numerical samples with different aspects are considered. Then, according to the response of the CPLEX exact method and the firefly algorithm, absolute relative error (ARE) is calculated that recommended Abolghasemian et al. [24]. ARE is calculated as shown in Equation (7) based on the comparison of genetic output and branches and borders. Table 17 compares the results obtained from the branch and bound algorithm.(7)Cplex output−firefly outputGfirefly output.Table 17
Comparing the obtained results from branch and bound algorithm.
Thenumberof problemMachinesOperationsResponseAREFireflytime(seconds)CPLEXtime(second)13622031940.04248112302500.0831034364500.03422134344420.015414105311000.04664189921000.097285404941000.01The ARE results shown in Table 17 are calculated to be less than 0.1 for each sample therefore, the error difference between the results of the two algorithms is negligible.


## 5. Managerial Insight

The issue of scheduling operations with dependent start-up times in an-work model and n-machine (n/n) has always been of interest to researchers. This issue, despite the developed methods, the complexity of the problems, and the time-consuming nature of their solution, continues to be of interest to researchers and especially executives. In this article, based on the application of research theorems in operations and the properties of the solution space of mathematical planning models, the integer of a new algorithm can be developed that can easily present the n/n operation sequence if it has dependent start-up times. Quick access to answers and problem-solving is one of the salient features of this method, while all previous methods have very long solution times.Therefore, in this research, by overcoming the difficulty of the problem after considering the assumption of simultaneous execution of operation in each order, taking into account the lead time and the cost of each order, we were able to provide a prioritization of the execution of operations in the production of various parts in the automotive industry. Therefore, the most important managerial applications of the present research are(i)
Determining the optimal sequence of parts based on their completion time.(ii)
Calculating the execution time of each operation in each part and also the total time of making the final part.


## 6. Conclusion and Future Work

This article develops the flow-shop problem from its classic mode to the flow-shop problem with setup and sequence-dependent times. The objective function considered in this research is to minimize the completion time of the last job. Usually, in scheduling problems, the processing time of each job operation is assumed to be given and fixed. However, this point is not emphasized in the relevant literature. Therefore, studies in which time and cost are sequence-dependent are not considered. For this purpose, in the present study, similar jobs are within each order in which the time and cost of setup between two jobs from one order are ignored. Therefore, considered objective function is to minimize the total completion time or the completion time of the last job on the last machine. Also, the main contribution of this paper is determining a schedule for prioritizing orders in the flow-shop problem. For this purpose, an integer linear programming model for flow-shop scheduling problems is proposed, assuming sequence-dependent setups. Therefore, using a novel meta-heuristic as solution approach optimized the problem. For this purpose, using the firefly algorithm, the optimal order for each production unit that you want to do is determined. The algorithm considers the initial 100 vectors and generates 100 new vectors and, after merging all the answers, selects the best solution from the 100 solutions obtained. By sorting the answers based on quality, which is due to the completion time of the last machine, each one that has less time is placed at the beginning of the sequence. Therefore, the algorithm gives the vector of the optimal solution that the vector of the solution in our problem is the order of operations. Finally, the sequence results are determined according to the desired algorithm for 5 tasks considered for automobile parts. The results show that the completion time of job 1 is 1397.85; job 2 is 771.44; job 3 is 608.65; job 4 is 1163.87, and job 5 is 479.45. In order to show the validity of the obtained results, absolute relative error (ARE) has been used. For this purpose, the results between the mathematical model and meta-heuristic have been compared with each other, and a slight difference between the results has been observed, which can be ignored. For further research, it is suggested that the results be implemented with other optimization algorithms such as genetics and simulated annealing, which is also mentioned in the literature. The computational results are compared with the results of this research. The complexity of the problem in case of increasing the dimensions of the answer space is the most important limitation of this research. In contrast, the most important advantage of using the high-end response method is problem-solving. Given that there are indefinite parameters in the real world, it is recommended to provide a model based on indefinite parameters for model development.



---

*Source: 8962052-2022-08-24.xml*