# Flexible Job Shop Scheduling Problem Using an Improved Ant Colony Optimization

Authors: Lei Wang; Jingcao Cai; Ming Li; Zhihu Liu
Journal: Scientific Programming
 (2017)

---

## Abstract

As an extension of the classical job shop scheduling problem, the flexible job shop scheduling problem (FJSP) plays an important role in real production systems. In FJSP, an operation is allowed to be processed on more than one alternative machine. It has been proven to be a strongly NP-hard problem. Ant colony optimization (ACO) has been proven to be an efficient approach for dealing with FJSP. However, the basic ACO has two main disadvantages including low computational efficiency and local optimum. In order to overcome these two disadvantages, an improved ant colony optimization (IACO) is proposed to optimize the makespan for FJSP. The following aspects are done on our improved ant colony optimization algorithm: select machine rule problems, initialize uniform distributed mechanism for ants, change pheromone’s guiding mechanism, select node method, and update pheromone’s mechanism. An actual production instance and two sets of well-known benchmark instances are tested and comparisons with some other approaches verify the effectiveness of the proposed IACO. The results reveal that our proposed IACO can provide better solution in a reasonable computational time.


---

## Body

## 1. Introduction

Scheduling problem plays a very important role in many industrial systems [1]. Therefore it has attracted considerable researches for recent decades [2–7]. Job shop scheduling problem (JSP) is a branch of production scheduling and combinatorial optimization problems [8]. The flexible job shop scheduling problem (FJSP) is an extension of the job shop scheduling problem (JSP) [9]. Different from JSP, an operation can be processed on more than one candidate machines in FJSP. As a result, two subproblems facing FJSP are machine assignment and operation sequencing. Machine assignment is how to assign a machine for each operation while operation sequencing is how to schedule all operations on machines to optimize the given performance indicators [10]. Thus, FJSP is more complicated than the classical JSP and it has been proven to be a strongly NP-hard in 1993 [11].The FJSP was first studied by Brucker and Schlie who used a polynomial approach to deal with two jobs FJSP [12]. In recent years, a large number of heuristics or metaheuristics have been employed to deal with FJSP, specifically through tabu search (TS) [13], simulated annealing (SA) [14], genetic algorithm (GA) [15, 16], particle swarm optimization (PSO) [17, 18], ant colony optimization (ACO) [19], artificial bee colony (ABC) [20], and hybrid approaches based on different heuristics and metaheuristics.Among these metaheuristics, ACO has been proved to be an efficient approach for dealing with JSPs [21–23]. However, this approach still has some limitations in practice: (1) a lot of computational time will be spent on obtaining the ideal solution. (2) The search usually falls into local optimal solution. Therefore, in order to overcome these limitations, numerous improved ACO algorithms or hybrid ACO algorithms have been developed. A knowledge-based ACO approach for solving flexible job shop scheduling problems is proposed in [19]. An improved ACO was proposed to deal with dynamic hybrid flow shop scheduling in [24]. A modified ACO called two-pheromone ant colony optimization was proposed for solving flexible job shop scheduling problem with due window in [25]. Ant colony optimization combined with tabu search was employed to deal with JSP in [26]. Two-generation Pareto ant colony algorithm was proposed by Zhao et al. for solving multiobjective job shop scheduling problem [27]. A two-stage ant colony optimization was presented to minimize the makespan in [28]. Leung et al. [29] proposed an agent-based ant colony optimization for solving integrated process planning and scheduling problem.Great efforts have been done for solving job shop scheduling problems or flexible job shop scheduling problems by improving ACO algorithms; however, these improved ACO algorithms are almost achieved by changing pheromone update mechanism. Although this can improve the search speed and solution efficiency, excessively strengthening the pheromone feedback of the best path may easily lead to premature convergence. Therefore, in order to solve these problems that exist in the basic ACO or improved ACO algorithms mentioned above, we propose an improved ant colony optimization (IACO) to solve the FJSP in this paper and the results are found to be closer or equal to the global optimum.The remainder of this paper is organized as follows. Section2 describes the model formulation for FJSP. The proposed IACO is introduced in Section 3. Experimental test, comparison, and discussion are reported in Section 4. The conclusions and future work are given in Section 5.


## 2. Description of FJSP

Then×m FJSP can be depicted as follows [30]: there are n jobs and m machines. Each job i comprises ni operations {oi1,oi2,oi3,…,oini}. Each operation oik can be processed by only one machine from the candidate machine set Aik. The assumptions for FJSP are as follows:(1)
Each machine can be used at time zero.(2)
Each job can be processed at time zero.(3)
Each machine can process only one operation at a time.(4)
Once an operation starts on a machine, it cannot be interrupted.(5)
The sequences of operations for all jobs are prespecified.(6)
Neither due dates nor release times are specified.(7)
The transportation times among machines are not considered.(8)
All machines are not always identical.The objective is to minimize the makespan and the mathematical model of the FJSP is shown as follows [31]:(1)minfx=CM=max1≤i≤ncini,(2)s.t.chg-cik-thgj·xhgj≥0∨cik-chg-tikj·xikj≥0,∀i,j,g.h,(3)cini-cik-1≥tikj·xikj,k=2,…,ni,∀i,j,(4)∑xikj∈Aikxikj=1,∀i,j,k,(5)xikj∈0,1,∀i,j,k,(6)cik≥0,∀i,k,where i,h is the job index, i,h=1,2,…,n. j is the machine index, j=1,2,…,m. k,g is the operation index, k,g=1,2,…,ni. n represents total jobs. m represents total machines. ni represents total operations of job i. tikj represents processing time of kth operation of job i on machine j. cik is the completed time of oik. xikj=1, if machine j is selected for oik; otherwise, xikj=0.Equations (2) and (3) are the operation sequence constraint. Equation (4) indicates that each operation can only be processed on one machine from machine set at a time. Equations (5) and (6) are decision variables which are 0-1 binary variable and nonnegative, respectively.


## 3. Improved Ant Colony Optimization for FJSP

### 3.1. Principles of Ant Colony Optimization

As social insects, ants live in colonies and their behavior is governed by the goal of colony survival rather than being focused on the survival of individuals. The main idea of the ACO is inspired by the behavior of real ants searching for food. The real ants can communicate with each other about food sources through pheromone. When the real ants move along, they release pheromone on the path they have passed. Other ants are attracted to follow them by observing the pheromone trail. Therefore, the path is enhanced and thus attracts more ants [32, 33]. Compared with some other heuristics, the ACO is characterized by distributed computation and positive feedback [34].If the operations are looked at as ants, it can be seen easily that there exist lots of similarities between an ant colony’s foraging process and FJSP. Operations must search for proper machine to process them. Like ants, they want to search for the shortest path. Ants’ nest and food source are similar with start and end dummy operation, respectively. If we look at an operation as an ant’s path for foraging food, then the relation of any two operations can be looked at as an alternative path, and different processing time of all the operations on the machine just like different length of paths.The disjunctive graph of an FJSP example can be described in Figure1. There are three jobs and each job has three operations. J1-1, J1-2, and J1-3 represent three operations of job 1. J2-1, J2-2, and J2-3 represent three operations of job 2. J3-1, J3-2, and J3-3 represent three operations of job 3. Each job must comply with the process sequence constraints. According to the constraints of process sequence and machine occupancy, ants travel total nine operations of the three jobs and search for the operation order on each machine and then gain the optimal or near-optimal solution for the flexible job shop scheduling problem. Therefore it is feasible to use ACO to solve the flexible job shop scheduling problems.Figure 1
Ants’ moving disjunctive graph.The key steps of the basic ACO are the calculations of transition probability, visibility, and pheromone amount. The nodes or goal point are chosen by ants according to pheromone amount and visibility [35]. At timet, the probability for ant k choosing the path from point i to j is calculated as follows:(7)pijkt=τijαtηijβt∑s∈allowedkτisαtηisβt,ifj∈allowedk0otherwise,where the allowedk is selectable machines group that ant k can choose and α and β are the pheromone and expectation factor, respectively. ηij(t) is heuristic factor and it is computed as ηij(t)=1/f(x). The more pheromone value on the path is and the higher visibility is and the bigger probability for choosing this path is.As time goes on, the pheromone of the path evaporates gradually. An ant will modify the pheromone value on the passed edges by applying the local updating rule, as follows:(8)τijt=1-ρ·τijt+ρτ0,where ρ is the evaporation coefficient of pheromone and 0<ρ<1. τ0 is the initial value of pheromone on each path.Once all ants have arrived at their destination, the value of pheromone on the edge is modified again by applying the global updating rule, as follows:(9)τijt=1-ρ·τijt+ρΔτijkt,where Δτijk(t) is the quantity of pheromone on the path (i,j) laid by ant k, and it can be defined as follows:(10)Δτijkt=Qfxkifantktravelthrougharci,j0otherwise.In (10), Q is a constant and it denotes the strength of pheromone; f(x)k is evaluation value of the kth ant after finishing the search task.As mentioned above, the basic ACO still has some weaknesses in practice. For example, the search usually gets trapped in local optimal solution. Meanwhile it needs a lot of computational time to obtain the ideal solution. Therefore, we propose an improved ant colony optimization to solve the FJSP in this paper.


### 3.2. Improved Aspects on Ant Colony Optimization Algorithm

The following improvements are done for machine selection: the machine which has the shortest processing time for finishing thejth operation of job i is selected by using 60% probability; the machine which has the shortest time for processing thejth operation of job i is selected by using 30% probability; the machine is randomly selected by using 10% probability, and the random selection can be achieved by using roulette selection method. The range for selecting machine can be expanded by using these three kinds of selection method. Take Figure 2, for instance, T1<T2<T3; therefore M1 is selected with a 60% probability, M2 is selected with a 30% probability, and one machine among M1, M2, and M3 is randomly selected with a 10% probability.Figure 2
Gantt chart for machine selection.The main steps of the basic ACO are the initialization position of ants, the calculation of transition probability, visibility, and pheromone value, as mentioned in Section3.1.When some other control parameters remain unchangeable, the initial position of the ants has a greater influence on the ACO. The ants should be distributed uniformly on the set which contains the first operations of all jobs, and the probability for searching for the global ideal solution will become much greater. If a large number of ants search for food from the same starting point, the solution diversity may be lost. Therefore, an initialization mechanism is used to distribute uniformly the ants’ initial positions.In the initial search stage, some paths are passed by ants, and some other paths are not passed. If an ant searches for path according to the pheromone’s guiding mechanism, it is easy to reduce the probability for selecting the path that has not been passed yet, and therefore the chance for ants to find the global ideal solution will be reduced. So when the pheromone exceeds a certain value, the ants are allowed to find the optimal path according to pheromone’s guiding mechanism, as follows:(11)τijt≥1.1∗τ0,where τ0 is the initial value of pheromone on each path and τij(t) is pheromone value between node i and j (path i→j) at time t.In order to expand the search scope of the ants and improve the search space of the basic ACO, initializing pheromone needs to be done when the pheromone value on a path is more than 90% of the total pheromone value on all paths (shown in (12)) because the ACO has fallen into local optimum in this case.(12)τijt≥0.9∗τSumt,where τSum(t) is the total pheromone value on all paths.However, the next available path selected by employing the transition probability does not always obtain the optimal direction for the basic ACO, and the pheromone deviated from the ideal solution has the potential to be enhanced, which will easily lead to the local optimal solution.After the transition probability for each candidate is obtained, if the roulette selection method is adopted, not only the path with a large transition probability is likely to be selected, but also the path with a small transition probability has the opportunity to be selected; thereby the search space and solution quality can be expanded and improved, respectively.Therefore, a new node selection method, combining prior knowledge, probability search, and random search, is proposed in this paper. When the search is trapped in local optimal solution, the solution space can be further searched by adjusting the pheromone and increasing the random selection probabilities.(13)p=p1=argmaxj∈allowedkτijtα·ηijtβ·ξijt0≤q≤q0p2=pijkt=τijαtηijβtξijt∑s∈allowedkτisαtηisβtξijt,j∈allowedk0otherwiseq0<q≤q1p3=randomsearchq1<q≤1,where q is a random value and 0≤q<1; q0 is the degree of prior knowledge; q1 is the lower bound level of random search; ξij(t) represents the appearing number of arc(i,j) during previous iterations for searching good solution.The more the arc (i,j) appears, the more the role is played for searching good solution by using positive feedback.A good balance relation between “using the past information to speed up the convergence” and “exploring new paths” can be established by combining these three selection methods. By this way, the search space can be enlarged and the global good solution can be obtained with a larger probability.In addition, a concept of the invalid search number is defined, which means the difference between the current number of iterationsN1 and the recent number of iterations N2 for improving the solution, as shown in (14). When the number of the invalid search exceeds a specified value N0, the algorithm is considered as a local optimum, as shown in (15).(14)N=N1-N2,(15)N≥N0.Meanwhile, the maximum or minimum pheromone trails may lead to premature convergence for searching solution. Therefore, the maximal pheromone trailτmax and the minimal pheromone trail τmin are given in our IACO in order to make all pheromone trails τij(t) satisfy τmin≤τij(t)≤τmax. This idea is inspired by the Max–Min ant system [36].When the number of the invalid searches exceeds a specified valueN0, the pheromone on the path is forcedly destroyed in order to avoid falling into the local optimum. In this paper, the value is reduced to sixty percent of the original pheromone τij(t), as follows:(16)τijt+n=60%∗τijtifN≥N0Eq.9otherwise.


### 3.3. Steps of the IACO

The specific implementation steps of the proposed IACO for solving FJSP are shown as follows.Step 1.
Initialize parametersα, β, ρ, Q, q0, q1, and τ0 and tabu list.Step 2.
Initialize the ants’ initial positions by using uniform distribution mechanism.Step 3.
Select machine by using our proposed machine selection strategy.Step 4.
Establish three sets: one setS1 contains operations that have been already visited by ants. One set S2 contains operations for next candidates. Another set S3 contains operations that are waiting to be added to the candidate set. And add the first operation of each job to the set of next candidate operation waiting to be selected.Step 5.
Judge whether the pheromoneτij(t) on the path is greater or equal to 1.1∗τ0 or not. If not, then select next operation in a random manner. If so, then select the next path according to (13). After the transition probability for each candidate is obtained, the roulette selection method is adopted to select the next path or node.Step 6.
Add the just selected operation to setS1 and remove the just selected operation from set S1. Meanwhile, add the next operation to set S2 and remove the next operation from set S3.Step 7.
Judge whether there are subsequent operations or not. If there are subsequent operations, then go to Step5. Otherwise go to Step 8.Step 8.
Calculate the good solution of this iteration and save.Step 9.
Find the best ant and update its global pheromone.Step 10.
Calculate the pheromone value on each path and limit the pheromone value on each path within the range of two valuesτmax and τmin. Meanwhile, judge whether τij(t) is not less than 0.9∗τSum(t). If so, initialize the pheromone value of that path.Step 11.
Judge whetherN is more than N0 or not. If it is satisfied, then forcedly destroy the pheromone value of that path according to (16).Step 12.
End the algorithm either when the optimal or near-optimal solution is found or when a maximal iteration is satisfied and then output the global optimal or near-optimal solution. Otherwise go to Step2.The framework of our IACO is shown in Figure3.Figure 3
The flowchart of the proposed IACO.


## 3.1. Principles of Ant Colony Optimization

As social insects, ants live in colonies and their behavior is governed by the goal of colony survival rather than being focused on the survival of individuals. The main idea of the ACO is inspired by the behavior of real ants searching for food. The real ants can communicate with each other about food sources through pheromone. When the real ants move along, they release pheromone on the path they have passed. Other ants are attracted to follow them by observing the pheromone trail. Therefore, the path is enhanced and thus attracts more ants [32, 33]. Compared with some other heuristics, the ACO is characterized by distributed computation and positive feedback [34].If the operations are looked at as ants, it can be seen easily that there exist lots of similarities between an ant colony’s foraging process and FJSP. Operations must search for proper machine to process them. Like ants, they want to search for the shortest path. Ants’ nest and food source are similar with start and end dummy operation, respectively. If we look at an operation as an ant’s path for foraging food, then the relation of any two operations can be looked at as an alternative path, and different processing time of all the operations on the machine just like different length of paths.The disjunctive graph of an FJSP example can be described in Figure1. There are three jobs and each job has three operations. J1-1, J1-2, and J1-3 represent three operations of job 1. J2-1, J2-2, and J2-3 represent three operations of job 2. J3-1, J3-2, and J3-3 represent three operations of job 3. Each job must comply with the process sequence constraints. According to the constraints of process sequence and machine occupancy, ants travel total nine operations of the three jobs and search for the operation order on each machine and then gain the optimal or near-optimal solution for the flexible job shop scheduling problem. Therefore it is feasible to use ACO to solve the flexible job shop scheduling problems.Figure 1
Ants’ moving disjunctive graph.The key steps of the basic ACO are the calculations of transition probability, visibility, and pheromone amount. The nodes or goal point are chosen by ants according to pheromone amount and visibility [35]. At timet, the probability for ant k choosing the path from point i to j is calculated as follows:(7)pijkt=τijαtηijβt∑s∈allowedkτisαtηisβt,ifj∈allowedk0otherwise,where the allowedk is selectable machines group that ant k can choose and α and β are the pheromone and expectation factor, respectively. ηij(t) is heuristic factor and it is computed as ηij(t)=1/f(x). The more pheromone value on the path is and the higher visibility is and the bigger probability for choosing this path is.As time goes on, the pheromone of the path evaporates gradually. An ant will modify the pheromone value on the passed edges by applying the local updating rule, as follows:(8)τijt=1-ρ·τijt+ρτ0,where ρ is the evaporation coefficient of pheromone and 0<ρ<1. τ0 is the initial value of pheromone on each path.Once all ants have arrived at their destination, the value of pheromone on the edge is modified again by applying the global updating rule, as follows:(9)τijt=1-ρ·τijt+ρΔτijkt,where Δτijk(t) is the quantity of pheromone on the path (i,j) laid by ant k, and it can be defined as follows:(10)Δτijkt=Qfxkifantktravelthrougharci,j0otherwise.In (10), Q is a constant and it denotes the strength of pheromone; f(x)k is evaluation value of the kth ant after finishing the search task.As mentioned above, the basic ACO still has some weaknesses in practice. For example, the search usually gets trapped in local optimal solution. Meanwhile it needs a lot of computational time to obtain the ideal solution. Therefore, we propose an improved ant colony optimization to solve the FJSP in this paper.


## 3.2. Improved Aspects on Ant Colony Optimization Algorithm

The following improvements are done for machine selection: the machine which has the shortest processing time for finishing thejth operation of job i is selected by using 60% probability; the machine which has the shortest time for processing thejth operation of job i is selected by using 30% probability; the machine is randomly selected by using 10% probability, and the random selection can be achieved by using roulette selection method. The range for selecting machine can be expanded by using these three kinds of selection method. Take Figure 2, for instance, T1<T2<T3; therefore M1 is selected with a 60% probability, M2 is selected with a 30% probability, and one machine among M1, M2, and M3 is randomly selected with a 10% probability.Figure 2
Gantt chart for machine selection.The main steps of the basic ACO are the initialization position of ants, the calculation of transition probability, visibility, and pheromone value, as mentioned in Section3.1.When some other control parameters remain unchangeable, the initial position of the ants has a greater influence on the ACO. The ants should be distributed uniformly on the set which contains the first operations of all jobs, and the probability for searching for the global ideal solution will become much greater. If a large number of ants search for food from the same starting point, the solution diversity may be lost. Therefore, an initialization mechanism is used to distribute uniformly the ants’ initial positions.In the initial search stage, some paths are passed by ants, and some other paths are not passed. If an ant searches for path according to the pheromone’s guiding mechanism, it is easy to reduce the probability for selecting the path that has not been passed yet, and therefore the chance for ants to find the global ideal solution will be reduced. So when the pheromone exceeds a certain value, the ants are allowed to find the optimal path according to pheromone’s guiding mechanism, as follows:(11)τijt≥1.1∗τ0,where τ0 is the initial value of pheromone on each path and τij(t) is pheromone value between node i and j (path i→j) at time t.In order to expand the search scope of the ants and improve the search space of the basic ACO, initializing pheromone needs to be done when the pheromone value on a path is more than 90% of the total pheromone value on all paths (shown in (12)) because the ACO has fallen into local optimum in this case.(12)τijt≥0.9∗τSumt,where τSum(t) is the total pheromone value on all paths.However, the next available path selected by employing the transition probability does not always obtain the optimal direction for the basic ACO, and the pheromone deviated from the ideal solution has the potential to be enhanced, which will easily lead to the local optimal solution.After the transition probability for each candidate is obtained, if the roulette selection method is adopted, not only the path with a large transition probability is likely to be selected, but also the path with a small transition probability has the opportunity to be selected; thereby the search space and solution quality can be expanded and improved, respectively.Therefore, a new node selection method, combining prior knowledge, probability search, and random search, is proposed in this paper. When the search is trapped in local optimal solution, the solution space can be further searched by adjusting the pheromone and increasing the random selection probabilities.(13)p=p1=argmaxj∈allowedkτijtα·ηijtβ·ξijt0≤q≤q0p2=pijkt=τijαtηijβtξijt∑s∈allowedkτisαtηisβtξijt,j∈allowedk0otherwiseq0<q≤q1p3=randomsearchq1<q≤1,where q is a random value and 0≤q<1; q0 is the degree of prior knowledge; q1 is the lower bound level of random search; ξij(t) represents the appearing number of arc(i,j) during previous iterations for searching good solution.The more the arc (i,j) appears, the more the role is played for searching good solution by using positive feedback.A good balance relation between “using the past information to speed up the convergence” and “exploring new paths” can be established by combining these three selection methods. By this way, the search space can be enlarged and the global good solution can be obtained with a larger probability.In addition, a concept of the invalid search number is defined, which means the difference between the current number of iterationsN1 and the recent number of iterations N2 for improving the solution, as shown in (14). When the number of the invalid search exceeds a specified value N0, the algorithm is considered as a local optimum, as shown in (15).(14)N=N1-N2,(15)N≥N0.Meanwhile, the maximum or minimum pheromone trails may lead to premature convergence for searching solution. Therefore, the maximal pheromone trailτmax and the minimal pheromone trail τmin are given in our IACO in order to make all pheromone trails τij(t) satisfy τmin≤τij(t)≤τmax. This idea is inspired by the Max–Min ant system [36].When the number of the invalid searches exceeds a specified valueN0, the pheromone on the path is forcedly destroyed in order to avoid falling into the local optimum. In this paper, the value is reduced to sixty percent of the original pheromone τij(t), as follows:(16)τijt+n=60%∗τijtifN≥N0Eq.9otherwise.


## 3.3. Steps of the IACO

The specific implementation steps of the proposed IACO for solving FJSP are shown as follows.Step 1.
Initialize parametersα, β, ρ, Q, q0, q1, and τ0 and tabu list.Step 2.
Initialize the ants’ initial positions by using uniform distribution mechanism.Step 3.
Select machine by using our proposed machine selection strategy.Step 4.
Establish three sets: one setS1 contains operations that have been already visited by ants. One set S2 contains operations for next candidates. Another set S3 contains operations that are waiting to be added to the candidate set. And add the first operation of each job to the set of next candidate operation waiting to be selected.Step 5.
Judge whether the pheromoneτij(t) on the path is greater or equal to 1.1∗τ0 or not. If not, then select next operation in a random manner. If so, then select the next path according to (13). After the transition probability for each candidate is obtained, the roulette selection method is adopted to select the next path or node.Step 6.
Add the just selected operation to setS1 and remove the just selected operation from set S1. Meanwhile, add the next operation to set S2 and remove the next operation from set S3.Step 7.
Judge whether there are subsequent operations or not. If there are subsequent operations, then go to Step5. Otherwise go to Step 8.Step 8.
Calculate the good solution of this iteration and save.Step 9.
Find the best ant and update its global pheromone.Step 10.
Calculate the pheromone value on each path and limit the pheromone value on each path within the range of two valuesτmax and τmin. Meanwhile, judge whether τij(t) is not less than 0.9∗τSum(t). If so, initialize the pheromone value of that path.Step 11.
Judge whetherN is more than N0 or not. If it is satisfied, then forcedly destroy the pheromone value of that path according to (16).Step 12.
End the algorithm either when the optimal or near-optimal solution is found or when a maximal iteration is satisfied and then output the global optimal or near-optimal solution. Otherwise go to Step2.The framework of our IACO is shown in Figure3.Figure 3
The flowchart of the proposed IACO.


## 4. Experimental Results

To test the performance of the proposed IACO, two groups of simulation experiments are executed. One group of experiments comes from an actual production instance, and the other group of experiments comes from benchmark problems.


### 4.1. Test on the Actual Production Instance

Table1 shows the process information from an actual production instance. The value in Table 1 represents processing time on each machine and “—” means the operation cannot be processed on that machine.Table 1
Process information.
Job Operation Machine M 1 M 2 M 3 M 4 M 5 M 6 M 7 M 8 M 9 M 10 J 1 o 1 - 1 2 — 4 — 10 3 — 8 — 5 o 1 - 2 5 7 — 8 — 9 — — — 11 o 1 - 3 — 6 5 — 10 9 — — 4 — o 1 - 4 — — — 7 — 5 — 8 — —  J 2 o 2 - 1 10 — 4 — 10 — — 8 — — o 2 - 2 9 — 8 — — 7 — 6 — — o 2 - 3 — 6 — 5 — 8 7 — — 4  J 3 o 3 - 1 — — 9 — 6 — 4 — — 5 o 3 - 2 — — 6 — 8 — — 7 — — o 3 - 3 — 9 — — — 5 — 6 4 — o 3 - 4 — — 4 — 3 6 — — — —  J 4 o 4 - 1 — 8 — 5 — — 2 4 — — o 4 - 2 — — 6 — — — 8 — 5 — o 4 - 3 5 — — 8 — — 4 — — 9 o 4 - 4 — 3 — — 11 6 — 8 — 10 o 4 - 5 — — 2 — 5 8 — — 8 —  J 5 o 5 - 1 6 — — 4 — 3 — — 8 — o 5 - 2 3 — — 7 — 6 — 10 — 8/9 o 5 - 3 — — 9 — — — 4 — — 11 o 5 - 4 — 7 — — 6 — — 7 — 9  J 6 o 6 - 1 — — — — 10 8 — 5 — — o 6 - 2 — — — 3 — — 2 7 — 3 o 6 - 3 — 3 — — 10 — — — 6 — o 6 - 4 10 — — 6 — 10 — — 9 8 o 6 - 5 — — 7 — 8 9 — 10 — —  J 7 o 7 - 1 9 — 5 — 7 9 — — — 8 o 7 - 2 2 — 6 — 8 — 3 7 — — o 7 - 3 — — — 5 6 2 — 9 3 — o 7 - 4 9 — 15 5 3 — — 6 — 5  J 8 o 8 - 1 — 3 — 6 — 8 5 — — — o 8 - 2 4 — 6 3 — — — 8 10 — o 8 - 3 — 5 8 — — 6 — — 5 — o 8 - 4 2 — 6 — — — 6 — 3 8 o 8 - 5 3 — — 5 — 3 — 5 9 8The parameters and their values, which are used for running our IACO, are shown as follows: number of antsm=39, weight of pheromone trail α=1, weight of heuristic information β=2, pheromone evaporation parameter ρ=0.1, the initial value of pheromone value τ0=0.1, constant for pheromone updating Q=120, premature constant N0=20, τmax=10, τmin=0.01, the value of prior knowledge q0=0.3, the lower bound value of random search q1=0.8, and number of iterations G=100.The Gantt charts obtained by our IACO, the basic ACO, and Max–Min Ant System (MMAS) are shown in Figures4, 5, and 6. In addition, Figure 7 depicts the convergence curves of the best makespan by using our IACO, the basic ACO, and MMAS. To such an instance, from Figure 7, it can be seen that our IACO obtains the ideal makespan (25) with 8 iterations. The basic ACO only obtains the ideal makespan (28) and it needs 28 iterations. Though the MMAS can obtain the ideal makespan (25), however, it needs as many as 61 iterations. Therefore, our proposed IACO is very efficient for solving FJSP.Figure 4
Gantt chart for the actual production instance obtained by IACO.Figure 5
Gantt chart for the actual production instance obtained by the basic ACO.Figure 6
Gantt chart for the actual production instance obtained by MMAS.Figure 7
Convergence processes of different algorithms.In order to prove the solving solution quality and solving efficiency of our IACO, Table2 shows the experimental results of the proposed IACO in comparison to the basic ACO and MMAS by 10 independent experiments. The best solution, the average solution, the worst solution, and the average computing time of our proposed IACO are the best among the compared methods. The results demonstrate that the proposed IACO is effective and efficient in solving FJSP.Table 2
Comparison of the algorithm performances for the actual production instance.
Algorithm The best solution The worst solution The average solution The average computing time (s) The basic ACO 28 36 32.4 9.327 MMAS 25 28 26.8 6.458 IACO 25 26 25.2 5.825


### 4.2. Test on Kacem Benchmark Instances

FJSP was classified into two categories by Kacem et al. [37]: (1) Partial FJSP (P-FJSP) which means that each operation can be processed by a subset of machines and (2) Total FJSP (T-FJSP) which means that each operation can be processed by all machines.Firstly, one 8 × 8 P-FJSP and one 10 × 10 T-FJSP from benchmark instances are applied to evaluate the performance of our proposed IACO.The Gantt chart and the convergence curve for 8 × 8 benchmark P-FJSP obtained by our IACO are shown in Figures8 and 9, respectively. The Gantt chart and the convergence curve for 10 × 10 benchmark T-FJSP obtained by our IACO are shown in Figures 10 and 11, respectively. To such an instance, from Figure 8–11, it can be seen that our IACO can easily obtain the best makespan with very few iterations.Figure 8
Gantt chart for 8 × 8 P-FJSP.Figure 9
Convergence process for 8 × 8 P-FJSP.Figure 10
Gantt chart for 10 × 10 T-FJSP.Figure 11
Convergence process for 10 × 10 T-FJSP.In addition, we compare the performances of our proposed IACO with several methods including AL + CGA [37], PSO + TS [17], PVNS [38], KBACO [19], and TSPCB [13]. Table 3 shows the best results of all these several methods, where C∗ is the best value found so far.Table 3
Results of the five Kacem benchmark instances.
Problem n × m C ∗ AL +CGA [37] PSO +TS [17] PVNS[38] KBACO[19] TSPCB[13] IACO Best RT Case1 4 × 5 11 16 — — 11 11 11 0.51 Case2 8 × 8 14 15 15 14 14 14 14 3.53 Case3 10 × 7 11 15 — — 11 11 11 3.26 Case4 10 × 10 7 7 7 7 7 7 7 4.45 Case5 15 × 10 11 23 12 12 11 11 11 4.86From Table3, it can be concluded that the proposed IACO is not worse than other algorithms, even better than several improved algorithms. Meanwhile, the proposed IACO can almost obtain the best values for the five benchmark problems for every independent test. In addition, the running time (RT) of the proposed IACO is very short; for instance, it can find the best solution for the 10 × 10 T-FJSP in the second iteration within 5 s.Table4 illustrates the comparison of the best value and the average value between IACO and those from literatures (BEDA [39]; PBABC [40]; EA [41]; and EQEA [9]) on the Kacem benchmark instances [37]. For each instance, all algorithms are run for 10 times independently. From Table 4, it can be seen easily that the best value can be obtained by these algorithms with a 100% success rate. Therefore, our IACO is very effective and robust.Table 4
Comparison result of the best value and the average value.
Problem n × m C ∗ BEDA [39] PBABC [40] Chiang and Lin [41] EQEA [9] IACO Best AVG Best AVG Best AVG Best AVG Best AVG Case1 4 × 5 11 11 11 11 11 11 11 11 11 11 11 Case2 8 × 8 14 14 14 14 14 14 14 14 14 14 14 Case3 10 × 7 11 11 11 11 11 11 11 11 11 11 11 Case4 10 × 10 7 7 7 7 7 7 7 7 7 7 7 Case5 15 × 10 11 11 11 11 11 11 11 11 11 11 11


### 4.3. Test on the BRdata Instances

Next we do tests on the ten BRdata instances [11]. Table 5 shows the comparison results by using our proposed IACO and LEGA of Ho et al. [42], GA of Pezzella et al. [43], PVNS [38], KBACO [19], and TSPCB [13].Table 5
Results of the ten Kacem benchmark instances.
LEGA [42] GA [43] PVNS [38] KBACO [19] TSPCB [13] IACO Mk01 40 40 40 39 40 40 Mk02 29 26 26 29 26 26 Mk03 — 204 204 204 204 204 Mk04 67 60 60 65 62 60 Mk05 176 173 173 173 172 173 Mk06 67 63 60 67 65 60 Mk07 147 139 141 144 140 140 Mk08 523 523 523 523 523 523 Mk09 320 311 307 311 310 307 Mk10 229 212 208 229 214 208As for the best makespans, from Table5, it can be seen that with the best results obtained our IACO is equal or smaller than that of other algorithms for dealing with almost all ten BRdata instances. Our IACO outperforms GA [40] in three out of the ten BRdata instances, outperforms KBACO [19] in six out of the ten BRdata instances, outperforms LEGA [39] in seven out of the ten BRdata instances, outperforms TSPCB [13] in four out of the ten BRdata instances, and is almost as good as PVNS [38] for the ten BRdata instances. Therefore, it is concluded that our IACO has more powerful optimizing ability in dealing with flexible job shop scheduling problem.


## 4.1. Test on the Actual Production Instance

Table1 shows the process information from an actual production instance. The value in Table 1 represents processing time on each machine and “—” means the operation cannot be processed on that machine.Table 1
Process information.
Job Operation Machine M 1 M 2 M 3 M 4 M 5 M 6 M 7 M 8 M 9 M 10 J 1 o 1 - 1 2 — 4 — 10 3 — 8 — 5 o 1 - 2 5 7 — 8 — 9 — — — 11 o 1 - 3 — 6 5 — 10 9 — — 4 — o 1 - 4 — — — 7 — 5 — 8 — —  J 2 o 2 - 1 10 — 4 — 10 — — 8 — — o 2 - 2 9 — 8 — — 7 — 6 — — o 2 - 3 — 6 — 5 — 8 7 — — 4  J 3 o 3 - 1 — — 9 — 6 — 4 — — 5 o 3 - 2 — — 6 — 8 — — 7 — — o 3 - 3 — 9 — — — 5 — 6 4 — o 3 - 4 — — 4 — 3 6 — — — —  J 4 o 4 - 1 — 8 — 5 — — 2 4 — — o 4 - 2 — — 6 — — — 8 — 5 — o 4 - 3 5 — — 8 — — 4 — — 9 o 4 - 4 — 3 — — 11 6 — 8 — 10 o 4 - 5 — — 2 — 5 8 — — 8 —  J 5 o 5 - 1 6 — — 4 — 3 — — 8 — o 5 - 2 3 — — 7 — 6 — 10 — 8/9 o 5 - 3 — — 9 — — — 4 — — 11 o 5 - 4 — 7 — — 6 — — 7 — 9  J 6 o 6 - 1 — — — — 10 8 — 5 — — o 6 - 2 — — — 3 — — 2 7 — 3 o 6 - 3 — 3 — — 10 — — — 6 — o 6 - 4 10 — — 6 — 10 — — 9 8 o 6 - 5 — — 7 — 8 9 — 10 — —  J 7 o 7 - 1 9 — 5 — 7 9 — — — 8 o 7 - 2 2 — 6 — 8 — 3 7 — — o 7 - 3 — — — 5 6 2 — 9 3 — o 7 - 4 9 — 15 5 3 — — 6 — 5  J 8 o 8 - 1 — 3 — 6 — 8 5 — — — o 8 - 2 4 — 6 3 — — — 8 10 — o 8 - 3 — 5 8 — — 6 — — 5 — o 8 - 4 2 — 6 — — — 6 — 3 8 o 8 - 5 3 — — 5 — 3 — 5 9 8The parameters and their values, which are used for running our IACO, are shown as follows: number of antsm=39, weight of pheromone trail α=1, weight of heuristic information β=2, pheromone evaporation parameter ρ=0.1, the initial value of pheromone value τ0=0.1, constant for pheromone updating Q=120, premature constant N0=20, τmax=10, τmin=0.01, the value of prior knowledge q0=0.3, the lower bound value of random search q1=0.8, and number of iterations G=100.The Gantt charts obtained by our IACO, the basic ACO, and Max–Min Ant System (MMAS) are shown in Figures4, 5, and 6. In addition, Figure 7 depicts the convergence curves of the best makespan by using our IACO, the basic ACO, and MMAS. To such an instance, from Figure 7, it can be seen that our IACO obtains the ideal makespan (25) with 8 iterations. The basic ACO only obtains the ideal makespan (28) and it needs 28 iterations. Though the MMAS can obtain the ideal makespan (25), however, it needs as many as 61 iterations. Therefore, our proposed IACO is very efficient for solving FJSP.Figure 4
Gantt chart for the actual production instance obtained by IACO.Figure 5
Gantt chart for the actual production instance obtained by the basic ACO.Figure 6
Gantt chart for the actual production instance obtained by MMAS.Figure 7
Convergence processes of different algorithms.In order to prove the solving solution quality and solving efficiency of our IACO, Table2 shows the experimental results of the proposed IACO in comparison to the basic ACO and MMAS by 10 independent experiments. The best solution, the average solution, the worst solution, and the average computing time of our proposed IACO are the best among the compared methods. The results demonstrate that the proposed IACO is effective and efficient in solving FJSP.Table 2
Comparison of the algorithm performances for the actual production instance.
Algorithm The best solution The worst solution The average solution The average computing time (s) The basic ACO 28 36 32.4 9.327 MMAS 25 28 26.8 6.458 IACO 25 26 25.2 5.825


## 4.2. Test on Kacem Benchmark Instances

FJSP was classified into two categories by Kacem et al. [37]: (1) Partial FJSP (P-FJSP) which means that each operation can be processed by a subset of machines and (2) Total FJSP (T-FJSP) which means that each operation can be processed by all machines.Firstly, one 8 × 8 P-FJSP and one 10 × 10 T-FJSP from benchmark instances are applied to evaluate the performance of our proposed IACO.The Gantt chart and the convergence curve for 8 × 8 benchmark P-FJSP obtained by our IACO are shown in Figures8 and 9, respectively. The Gantt chart and the convergence curve for 10 × 10 benchmark T-FJSP obtained by our IACO are shown in Figures 10 and 11, respectively. To such an instance, from Figure 8–11, it can be seen that our IACO can easily obtain the best makespan with very few iterations.Figure 8
Gantt chart for 8 × 8 P-FJSP.Figure 9
Convergence process for 8 × 8 P-FJSP.Figure 10
Gantt chart for 10 × 10 T-FJSP.Figure 11
Convergence process for 10 × 10 T-FJSP.In addition, we compare the performances of our proposed IACO with several methods including AL + CGA [37], PSO + TS [17], PVNS [38], KBACO [19], and TSPCB [13]. Table 3 shows the best results of all these several methods, where C∗ is the best value found so far.Table 3
Results of the five Kacem benchmark instances.
Problem n × m C ∗ AL +CGA [37] PSO +TS [17] PVNS[38] KBACO[19] TSPCB[13] IACO Best RT Case1 4 × 5 11 16 — — 11 11 11 0.51 Case2 8 × 8 14 15 15 14 14 14 14 3.53 Case3 10 × 7 11 15 — — 11 11 11 3.26 Case4 10 × 10 7 7 7 7 7 7 7 4.45 Case5 15 × 10 11 23 12 12 11 11 11 4.86From Table3, it can be concluded that the proposed IACO is not worse than other algorithms, even better than several improved algorithms. Meanwhile, the proposed IACO can almost obtain the best values for the five benchmark problems for every independent test. In addition, the running time (RT) of the proposed IACO is very short; for instance, it can find the best solution for the 10 × 10 T-FJSP in the second iteration within 5 s.Table4 illustrates the comparison of the best value and the average value between IACO and those from literatures (BEDA [39]; PBABC [40]; EA [41]; and EQEA [9]) on the Kacem benchmark instances [37]. For each instance, all algorithms are run for 10 times independently. From Table 4, it can be seen easily that the best value can be obtained by these algorithms with a 100% success rate. Therefore, our IACO is very effective and robust.Table 4
Comparison result of the best value and the average value.
Problem n × m C ∗ BEDA [39] PBABC [40] Chiang and Lin [41] EQEA [9] IACO Best AVG Best AVG Best AVG Best AVG Best AVG Case1 4 × 5 11 11 11 11 11 11 11 11 11 11 11 Case2 8 × 8 14 14 14 14 14 14 14 14 14 14 14 Case3 10 × 7 11 11 11 11 11 11 11 11 11 11 11 Case4 10 × 10 7 7 7 7 7 7 7 7 7 7 7 Case5 15 × 10 11 11 11 11 11 11 11 11 11 11 11


## 4.3. Test on the BRdata Instances

Next we do tests on the ten BRdata instances [11]. Table 5 shows the comparison results by using our proposed IACO and LEGA of Ho et al. [42], GA of Pezzella et al. [43], PVNS [38], KBACO [19], and TSPCB [13].Table 5
Results of the ten Kacem benchmark instances.
LEGA [42] GA [43] PVNS [38] KBACO [19] TSPCB [13] IACO Mk01 40 40 40 39 40 40 Mk02 29 26 26 29 26 26 Mk03 — 204 204 204 204 204 Mk04 67 60 60 65 62 60 Mk05 176 173 173 173 172 173 Mk06 67 63 60 67 65 60 Mk07 147 139 141 144 140 140 Mk08 523 523 523 523 523 523 Mk09 320 311 307 311 310 307 Mk10 229 212 208 229 214 208As for the best makespans, from Table5, it can be seen that with the best results obtained our IACO is equal or smaller than that of other algorithms for dealing with almost all ten BRdata instances. Our IACO outperforms GA [40] in three out of the ten BRdata instances, outperforms KBACO [19] in six out of the ten BRdata instances, outperforms LEGA [39] in seven out of the ten BRdata instances, outperforms TSPCB [13] in four out of the ten BRdata instances, and is almost as good as PVNS [38] for the ten BRdata instances. Therefore, it is concluded that our IACO has more powerful optimizing ability in dealing with flexible job shop scheduling problem.


## 5. Conclusions

In this paper, an efficient IACO is proposed for FJSP in order to minimize makespan. Experimental results on an actual production instance and two sets of well-known benchmark FJSP Instances indicate that our proposed IACO is competitive to other algorithms. The results demonstrate that the proposed IACO is effective and efficient in dealing with FJSP.Our future work still needs to be done from the following aspects: (1) multiobjective flexible job shop scheduling problem especially related to the fuzzy due date and energy consumption need to be considered. (2) Dynamic scheduling for FJSP is another research direction, because in real manufacturing systems, unpredictable events, such as machine breakdown and new job arrivals and so on, often happen.



---

*Source: 9016303-2017-01-26.xml*