An integrated ant colony optimization algorithm to solve job allocating and tool scheduling problem

Abstract

In this article, max–min ant colony optimization algorithm is proposed to determine how to allocate jobs and schedule tools with the objective of minimizing the makespan of processing plans in flexible manufacturing system. To expand the application range of max–min ant colony optimization algorithm, tool movement policy is selected as the running mode of flexible manufacturing system, which assumes that tools are shared among work centers and each operation is allowed to be machined by different kinds of tools. In the process of converting this scheduling problem into traveling salesman problem, disjunctive graph is modified to possess more than one path between each neighbor node. Besides providing practical methods of initializing pheromone, selecting node and calculating pheromone increment, max–min ant colony optimization algorithm employs the pheromone updating rule in max–min ant system to limit pheromone amount in a range, of which the upper and lower boundaries are updated after each iteration by formulations involving the current optimal makespan, the average number of optional tools and parameters. Finally, different sizes of processing plans are randomly generated, through which max–min ant colony optimization algorithm is proved effectively to tackle early stagnation and local convergence and thus obtains better solution than ant colony optimization algorithm and bidirectional convergence ant colony optimization algorithm.

Introduction

Flexible manufacturing system (FMS) is an integrated production system that consists of multifunctional numerically controlled machines connected to an automated handling system. ¹

As batch size is gradually decreasing, the demands to meet specific customer requirements call for considerable flexibility in manufacturing field. FMS has emerged as a highly competitive manufacturing strategy to satisfy these requirements, which is capable of machining a wider range of product types, from small- to medium-sized batches, and also has higher production efficiency than traditional assembly lines which are designed for high-volume and low-variety manufacture.

To improve the efficiency in FMS, various decisions should be made. One of these decisions is job allocating and tool scheduling, which focuses on how to arrange jobs and tools to each available work center to finish processing plans as quickly as possible.

Related work

Two policies are proposed to describe the running mode of FMS. These two policies are job movement policy and tool movement policy.

Job movement policy assumes that jobs move among work centers, while tools remain on initial work centers during the machining process. However, the ability of versatile machines is often constrained by the availability of tools since the capacity of tool magazines cannot be extended beyond their design limit. In this running mode, the common approaches of coping with the demands of diverse products are increasing the capacity of tool magazines and allocating as many tools as possible to tool magazines, which require very high tool inventories.

Tool movement policy assumes that each job remains on the initial work center until all operations are completed, whereas tools are transferred among work centers by tool delivery devices, such as motor-driven vehicles, automated guided vehicles (AGVs) and overhead gantry robots. ² The developments of technologies in transport devices and shop floor information system have achieved the tool sharing. EIMaraghy ³ described the basic modules of automated tool management in FMS, including tool transfer, tool control system and tool storage. Hammer ⁴ designed an AGV to deliver a set of eight tools among tool magazines or between tool magazines and the central tool magazine. Besides, AGV can also be used to load and unload jobs in this research. Kumar et al. ⁵ dealt with unforeseen situations in the shop floor by assuming that AGVs can deliver any job to any machine in the shortest possible time and regarding the routing, loading and unloading of AGVs as certainties in the FMS scenario. The tool movement policy has remarkable advantages over the job movement policy ⁶ since the tool sharing makes it possible to require a smaller number of tools and there is no need to reset jobs, which also contributes to improving cutting precision. ⁷

Some researches that were based on tool movement policy have been carried out in recent years. In order to minimize the total tool waiting time, Lee et al. ⁸ focused on an integrated model that considered operation sequence and tool selection simultaneously. Suresh Kumar and Sridharan ⁹ built a simulation-based model to solve tool sharing problem in single-stage FMS and identified the best possible scheduling combinations for part launching and tool request selection. Udhaya Kumar and Kumanan ¹⁰ and Prabaharan et al. ¹¹ generated active schedule and the optimal sequence of jobs and tools to shorten the makespan for FMS.

However, they both assumed that the kinds of tools for each operation were pre-specified, which limited the diversity of processing plans and may not satisfy the actual demands of FMS. Zeballos ¹² made a progress which allowed each kind of tools to own several copies, but processing time among copies was uniform.

In this research, there are several optional tools for each operation and each tool may consume different processing time.

The job allocating and tool scheduling problem is one of the strongly nondeterministic polynomial-time hard (NP-hard) combinatorial optimization problems which are difficult to find optimal solutions. In practical researches, genetic algorithm (GA) is able to find acceptable solutions in a large scale. Rossi and Dini ¹³ presented GA for generalized job shop problem. Choudhary et al. ¹⁴ then proposed a new version of GA to solve job-type selection and operation allocation on machines by chromosome differentiation. Wang and Brumn ¹⁵ embedded a simple heuristic rule to GA to avoid the production of unfeasible solutions. Qudeiri ¹⁶ introduced GAs combined with production simulator system to find the appropriate order of a set of operations for jobs that need to be operated on available machine tools in FMSs. However, the search abilities of GA are limited, which may consume a lot of time and probably fall into local convergence. In addition, the performances of GA are greatly affected by initial population, coding method and genetic operators.

In recent years, ant colony optimization (ACO) algorithm is receiving more and more attention in solving NP-hard problems, which is not only a new heuristic bio-mimetic algorithm that imitates the foraging behavior of ant colony through the shorter path but also a directed parallel probabilistic searching technique that can be used to find near-optimal solutions in complex searching spaces. ¹⁷ Ying and Liao ¹⁸ applied ACO algorithm to the n/m/p $C_{max}$ problem to find optimal operation sequences of n different jobs on m machines. Kumar et al. ¹⁹ dealt with the stagnation problem of ACO algorithm by certain modifications which were appropriate for scheduling problem. Lu et al. ²⁰ designed an ACO algorithm to guide the ants searching the routes along uniformly scattered directions.

However, in terms of solving NP-hard problems, ACO algorithm may not be comparable to its improved versions, such as bidirectional convergence ant colony optimization (BCACO) algorithm and max–min ant system. According to the pheromone updating rule of BCACO algorithm, the pheromone amount is reduced once the performance of the finished route is worse than the average level. Wang et al. ²¹ designed BCACO algorithm with a different evaporating method to promote efficiency and usability of original ACO. Dridi ²² proposed a hybrid BCACO algorithm which included a solution construction developed for more complicated problems with a Pareto-guided local search engine. Rui ²³ presented a developed BCACO algorithm to solve the integrated job shop scheduling problem in FMS with consideration of the waiting time for tools. By reinforcing the influence of previously generated solutions, BCACO algorithm is able to increase search speed and save calculating time, but modifying the pheromone updating rule in this way may lead ants trapped in repeated routes early. Max–min ant system is put forward by Stützlea and Hoos, ²⁴ which prescribed limits to pheromone increment after each iteration and has been proved dramatically to avoid early stagnation and local convergence.

In this research, max–min ant colony optimization (MMACO) algorithm is designed to solve the local convergence in scheduling problem, which is an integrated algorithm that combines the basic procedures of ACO algorithm with pheromone updating rules in max–min ant system.

The details of this research are presented in following sections. Section “Problem description” gives definitions of the mathematical model. In section “Proposed methodologies,” ACO, MMACO and BCACO algorithms are formulated to solve scheduling problem. Besides, steps of MMACO algorithm are illustrated by flowchart. The simulation results obtained by ACO, BCACO and MMACO algorithms are presented and discussed in section “Performance comparison and analysis.” Section “Conclusion” summarizes the consequences of different algorithms and gives explanations to the assumptions.

Problem description

The processing plans

The processing plans in this research are made up of some jobs, each of which is supposed to have the same number of operations. The operation sequence is fixed, so an operation is not permitted to be machined until its former operations are finished.

When work centers are sufficient, all jobs can be allocated to work centers synchronously and only tool scheduling is involved. However, in most cases, work centers are limited, which means some jobs have to wait for machining. Due to the fact that different solutions of job scheduling will lead to different tool scheduling, the job scheduling should be determined in the first place. In this research, the possible solutions of job allocating are enumerable. When allocating m jobs on c work centers, the number of possible solutions is $C_m^c{A}_{m-c}^c\dots A_{m-(m/c-1)*c}^c{A}_c^{m\%c}$ , where $m/c$ is the integer of the calculation and $m\%c$ is the remainder.

The running mode of FMS

The proposed job allocating and tool scheduling problem is implemented under the FMS that consists of a center tool magazine (CTM), work centers $(\mathrm{WC}\#1,\dots ,\mathrm{WC}\#X)$ , two AGVs, job storage room (JSR) and central control system. The layout of the FMS is illustrated in Figure 1. Some assumptions and descriptions about the hardware are made as follows:

1. Each work center is capable of fixing any tool and machining any job.

2. Two AGVs are used to convey tools and jobs to work centers. Each AGV is fitted with a manipulator arm which is designed to load and unload tools or jobs. The route of AGVs and action of manipulator arms are decided by the central control system that monitors the location and condition of all tools and jobs.

3. Once an operation is completed, the tool is delivered to CTM or other required work centers immediately, which means the delivery time is negligible.

Figure 1.

The layout of FMS.

Definitions

The following notations are used for the description of the scheduling problem and ACO algorithm:

• x sequence number of work centers, $x=1,\dots ,X$

• m sequence number of jobs, $m=1,\dots ,M$

• n sequence number of operations, $n=1,\dots ,N$

• w sequence number of tools, $w=1,2,\dots ,W$

• A number of ants in simulation experiments

• a sequence number of ants, $a=1,2,\dots ,A$

• $t(m,n,w)$  processing time of operation $O_{\mathrm{mn}}$ machined by tool no. w

• PT three-order matrix to store processing time $\mathrm{PT}=|t(m,n,w)|$ ( $m=1,M;n=1,\dots ,N;w=1,\dots ,W$ )

• $N(i,j)$  node $(i,j)$ in disjunctive graph, $i=1,\dots ,M*N$ , $j=1,\dots ,W$

• ${\mathrm{tabu}}_f^a$  matrix to record nodes having been visited by ant no. a in iteration no. f ${\mathrm{tabu}}_f^a=\left|\begin{array}{c}\hfill i^1\cdots i^s\cdots i^{M*N}\hfill \\ \multicolumn{1}{c}{j^1\cdots j^s\cdots j^{M*N}}\end{array}\right|$ $(s=1,\dots ,M*N)$

• $O{S}^m$  time when job no. m starts to be processed

• $O{C}^m$  time when job no. m is completed

• OT matrix used to record stare time and end time of jobs $\mathrm{OT}=\left|\begin{array}{c}\hfill o{s}^1\cdots o{s}^m\cdots o{s}^M\hfill \\ \multicolumn{1}{c}{o{c}^1\cdots o{c}^m\cdots o{c}^M}\end{array}\right|$

• $t{s}^w$  time when tool no. w starts to be occupied

• $t{c}^w$  time when tool no. w is released

• TT matrix used to store occupation status of tools $\mathrm{TT}=\left|\begin{array}{c}\hfill t{s}^1\cdots t{s}^w\cdots t{s}^W\hfill \\ \multicolumn{1}{c}{t{c}^1\cdots t{c}^w\cdots t{c}^W}\end{array}\right|$

• $L_f^a$  makespan of the solution obtained by ant no. a in iteration no. f

• F terminal number of iterations in simulation experiments

• f sequence number of iteration, $f=1,\dots ,F$

Objectives

In this research, makespan is selected as the unique parameter to compare the performance of FMS. After all operations are completed, the latest end time is the makespan. It should be noted that the nodes $N(i,j)$ in ${\mathrm{tabu}}_f^a$ indicate not only the processing sequences of operations but also the selected tools. $\mathrm{OT}(1,m)$ and $\mathrm{OT}(2,m)$ represent the start and end time of current operation of job no. m, respectively. $\mathrm{TT}(1,j^s)$ and $\mathrm{TT}(2,j^s)$ represent the start and end occupation time of tool no. $j^s$ , respectively. The steps to get makespan are shown as follows:

Step 1: Set s = 1 and go to Step 2;

Step 2: Set $i^s={\mathrm{tabu}}_f^a(1,s)$ , $j^s={\mathrm{tabu}}_f^a(2,s)$ ,

$m=i^s/N+1$ , $n=i^s\%N+1$ , $w=j^s$ ;

/*Obtain the operation and tool represented by node no. s*/

Go to Step 3;

Step 3: If $\mathrm{OT}(2,m)\in [\mathrm{TT}(1,j^s),\mathrm{TT}(2,j^s)]$ , go to Step 4;

Else, go to Step 5;

Step 4: Set $\mathrm{OT}(1,m)=\mathrm{TT}(2,j^s)$ , $\mathrm{OT}(2,m)=\mathrm{OT}(1,m)+\mathrm{PT}(m,n,w)$ ;

/*The required tool is occupied, so the job has to wait until the tool is released. The start

time of job no. m equals to the end occupation time of the selected tool.*/

Go to Step 6;

Step 5: Set $\mathrm{OT}(1,m)=\mathrm{OT}(2,m)$ , $\mathrm{OT}(2,m)=\mathrm{OT}(1,m)+\mathrm{PT}(m,n,w)$ ;

/* The tool is free, so the job no. m can be processed immediately. The first $\mathrm{OT}(2,m)$

represents the end time of former operation of job no. m and the second one represents

that of current operation.*/

Go to Step 6;

Step 6: Set $\mathrm{TT}(1,j^s)=\mathrm{OT}(1,m)$ , $\mathrm{TT}(2,j^s)=\mathrm{OT}(2,m)$ ;

/*Once a tool is arranged to an operation, it turns to be occupied until the operation is

completed. The start and end occupation time of tool no. $j^s$ equal to those of the operation

that have been updated by steps above. */

s++;

Go to Step 7;

Step 7: If $s<=M*N$ , go to Step 2;

Else, output $L_f^a=\mathrm{Max}(\mathrm{OT}(2,m))$ and end the program.

Proposed methodologies

The transition to traveling salesman problem

Colorni et al. ²⁵ put forward a graph-based method to solve job shop scheduling problems in FMS. The disjunctive graph is modified to convert the job allocating and tool scheduling problem into traveling salesman problem (TSP), represented by equation (1)

$$\mathrm{DG}=(N,P)$$

(1)

where N is the set of nodes which represent all operations and available tools for each operation, plus the dummy start and end nodes coded by the symbols * and #, respectively. If the operation $O_{M*N}$ is machined by tool no. w, it will be represented by node $N(i,j)$ where $t=(m-1)*N+n-1$ and $j=w$ . P is the set of paths between every pair of operations, and operations must be processed in the direction of arrows. Figure 2 shows an example of 3*6 job allocating and tool scheduling problem, where node $N(7,3)$ and node $N(7,4)$ mean that the operation $O_{32}$ is machined by tool no. 3 and tool no. 4, respectively. Two jobs are allocated to each work center since the number of jobs is twice as large as that of work centers.

Figure 2.

The disjunctive graph of 3*6 example problem.

Considering constraints of procedures and optional tools synthetically, the movement of ants obeys the following principles:

1. Ants cannot move to a node until its all former operations are finished.

2. If a node has been selected, the other nodes belonging to the same operation are turned to be forbidden.

The basic procedures of ACO algorithm

It is well known that real ants leave substance (pheromone) in the nest-food path. The pheromone has a function to attract other ants to move along it. Ants construct candidate solutions by starting with an empty collection and then adding nodes into the collection until a complete solution is generated. ²⁶ When finishing the construction, each ant gives feedback to the just constructed route by depositing pheromone. ²⁷ The less time the ants take, the more the pheromone will be left. Meanwhile, the pheromone slowly evaporates to prevent ants falling into local optimal solution in early period.

Initialization of heuristic desirability

The heuristic desirability $\eta (u,v)$ is a fixed value that reflects attractiveness between paths, which depends on the processing time of operations, given in equation (2)

$$\eta (u,v)=\frac{C}{t(m,n,w)}$$

(2)

where C is a positive constant.

Initialization of pheromone amount

The pheromone amount ${\tau }_f(u,v)$ describes how previous solutions affect the current selection. In the beginning of the algorithm, $\tau (u,v)$ is assigned the same value in every path by equation (3)

$${\tau }_1(u,v)={\tau }_0$$

(3)

The method of node selection

Ants are more likely to choose the path with higher pheromone amount or the heuristic desirability. The transition probability of moving from node u to node v in iteration no. f is given in equation (4)

$$P_f(u,v)=\frac{{({\tau }_f(u,v))}^{\alpha }{({\eta }_f(u,v))}^{\beta }}{\sum {({\tau }_f(u,v))}^{\alpha }{({\eta }_f(u,v))}^{\beta }}$$

(4)

where $\alpha$ and $\beta$ indicate the relative importance of pheromone amount and heuristic desirability, respectively, which plays a key role to obtain the global optimal solution since employing large value of $\alpha$ will decrease the opportunities to try new routes and promoting the value of $\beta$ to a high level will decrease the calculating speed of algorithms. In this research, $\alpha$ and $\beta$ are set by trial and error for simplicity.

When ants arrive at a node, they use roulette wheel to choose the path. Every feasible path has its own transition probability in the roulette wheel, and after spinning the roulette wheel, a path is chosen.

Pheromone updating rule of ACO algorithm

In ACO algorithm, there are two methods of updating pheromone amount, global updating rule and local updating rule.

In global updating rule, pheromone amount on a path is dynamically updated only after an ant has finished the route. The pheromone increment $\Delta {\tau }_f^a(u,v)$ is deposited by ant no. a in iteration f and inversely proportional to $L_f^a$ . The global updating rule is shown in equations (5) and (6)

$${\tau }_{f+1}(u,v)=(1-\rho )*{\tau }_f(u,v)+\Delta {\tau }_f^a(u,v)$$

(5)

$$\Delta {\tau }_f^a(u,v)=\frac{Q}{L_f^a}$$

(6)

where Q is a positive value associated with the number of operations and constant C.

In local updating rule, ants leave a certain amount of pheromone immediately as long as they go through a path. The local updating rule is closer to the real world, but leaving pheromone neglecting the differences among candidate solutions greatly increases the number of iterations, which is less efficient than global updating rule. In this research, only global updating rule is chosen to update pheromone amount.

Pheromone updating rule of MMACO algorithm

Adopting global updating rule probably generates large increment differences among ants, which makes pheromone amount significantly high in some paths. According to the node selection method in this research, ants tend to choose paths with higher pheromone amount, so the pheromone gaps among paths will be aggravated during later iterations. Once trapped in this situation, ants construct the same solution over and over again and the exploration will fall into stagnation.

To overcome the drawbacks of global updating rule, one of the most efficient methods is to narrow the pheromone gaps. Since the heuristic desirability is typically problem-dependent and static throughout the algorithm, limiting the pheromone amount on all paths in a certain range is adopted to achieve this goal. After obtaining ${\tau }_{f+1}$ by equations (5) and (6), MMACO algorithm imposes explicit limits ${\tau }_f^{min}$ and ${\tau }_f^{max}$ on the pheromone amount, given in equation (7). The detailed methods to update the range of pheromone amount are elaborated in the next section

$${\tau }_{f+1}(u,v)=\{\begin{array}{c}\hfill {\tau }_f^{min}{\tau }_{f+1}(u,v)⩽{\tau }_f^{min}\hfill \\ \multicolumn{1}{c}{{\tau }_f^{max}{\tau }_{f+1}(u,v)⩾{\tau }_f^{max}}\\ \multicolumn{1}{c}{{\tau }_{f+1}(u,v)\mathrm{else}}\end{array}$$

(7)

The update of pheromone limits

A modified approach to determine the upper and lower boundaries of pheromone amount is introduced in this section. We say MMACO algorithm is globally convergent if at each choice node, one of the alternative paths has maximum pheromone amount ${\tau }_f^{max}$ , while other paths have the same minimum pheromone amount ${\tau }_f^{min}$ . If the condition of global convergence is satisfied, the candidate solution will be constructed by always choosing paths with maximum pheromone amount and will typically correspond to the optimal solution. The MMACO in this research is assumed to be globally convergent.

The maximum possible pheromone increment in any iteration is $Q/L^{\mathrm{best}}$ where $L^{\mathrm{best}}$ is makespan of the ideal optimal solution. The largest pheromone amount among paths after iteration no. f can be determined according to equations (5) and (6), given in equation (8). Since $0<\rho <1$ , ${\tau }_f^{max}$ will converge to $(1/(1-\rho ))·(Q/L^{\mathrm{best}})$ . ${\tau }_f^{max}$ is set to $(1/(1-\rho ))·(Q/L_f^{{}^{\mathrm{best}}})$ in equation (9) where $L_f^{\mathrm{best}}$ which indicates the makespan of the optimal solution until iteration no. f is regarded as the approximate value of $L^{\mathrm{best}}$

$${\tau }_f^{max}=\sum _{i=1}^f\left({\rho }^{f-i}\frac{Q}{L^{\mathrm{best}}}\right)+{\rho }^f{\tau }_0$$

(8)

$${\tau }_f^{max}=\frac{1}{1-\rho }.\frac{Q}{L_f^{\mathrm{best}}}$$

(9)

During the process of iterations, pheromone is greatly accumulated, so it has more influence on node selection than heuristic desirability. Neglecting the influence of heuristic desirability, the transition probability $P_{\mathrm{cvg}}$ under the condition of global convergence is totally decided by lower and upper pheromone boundaries, given in equation (10). ${\tau }_f^{min}$ can be obtained by equation (11)

$$P_{\mathrm{cvg}}=\frac{{\tau }_f^{max}}{{\tau }_f^{max}+(\mathrm{avg}-1){\tau }_f^{min}}$$

(10)

$${\tau }_f^{min}=\frac{(1-P_{\mathrm{cvg}})}{(\mathrm{avg}-1)P_{\mathrm{cvg}}}{\tau }_f^{max}$$

(11)

where avg is the average number of available paths at each node, and $P_{\mathrm{cvg}}$ is a positive constant, larger than $1/(\mathrm{avg}-1)$ . According to the constrains among operations, there are M available paths to each node except the last one, so avg can be determined by equation (12)

$$\mathrm{avg}=\frac{M^2*(N-1)+\sum _{i=1}^{M-1}i}{M*N}$$

(12)

The initialization of pheromone limits

To initialize the range of pheromone amount, it is necessary to find an appropriate method to generate initial feasible solutions. Udhaya Kumar and Kumanan ¹⁰ developed an enumerative procedure to generate all feasible schedules for general scheduling problem. It is a numerical version by drawing Gantt chart. Whenever two or more jobs require the same tool at one time, the selection is made arbitrarily, and by enumerating all possible choices which occur at different stages one by one, the entire set of active feasible schedules can be obtained, including the optimal one. This algorithm is very simple and fast to be implemented, which is proper to initialize the range of pheromone amount.

Pheromone updating rule of BCACO algorithm

The pheromone updating rule of BCACO algorithm which is applicable to this built model is shown in equation (13)

$$\Delta {\tau }_f^a(u,v)=\{\begin{array}{c}\hfill \frac{Q}{L_f^a}{L}_f^a>L_{f-1}^{\mathrm{Mean}}\hfill \\ \multicolumn{1}{c}{-\frac{Q}{L_f^a}{L}_f^a<L_{f-1}^{\mathrm{Mean}}}\end{array}$$

(13)

where $L_{f-1}^{\mathrm{Mean}}$ is the mean makespan in last iteration, proposed to decide whether the candidate solution is good or not.

Steps to obtain optimal solution of MMACO algorithm

The methods of optimizing solutions of job allocating and tool scheduling through MMACO algorithm are given and illustrated by flowchart in Figure 3.

Figure 3.

Flowchart of MMACO algorithm.

• Step 1: Input information of the scheduling problem and basic parameters of MMACO algorithm, including $M,N,W,C,t(m,n,w),\alpha ,\beta ,\rho ,F,P_{\mathrm{cvg}}$ .

• Step 2: Initialize pheromone amount and heuristic desirability.

• Step 3: Generates a new solution of job allocating according to section “The processing plans.”

• Step 4: Obtain a feasible sequence to initialize the range of pheromone amount by the enumerative procedure mentioned in section “The initialization of pheromone limits.”

• Step 5: Empty matrix ${\mathrm{tabu}}_f^a$ to begin a new iteration.

• Step 6: Select one from feasible paths by means of roulette wheel selection and record the end node of the selected path in matrix ${\mathrm{tabu}}_f^a$ . An operation is not feasible until its former operations are completed because of the priority constraints among operations.

• Step 7: If all operations are finished, go to Step 8. Otherwise, return to Step 6.

• Step 8: Calculate makespan $L_f^a$ according to the methods in section “Objectives.”

• Step 9: If the number of completed iterations is equal to the terminal number F, go to Step 11. Otherwise, go to Step 10.

• Step 10: Update the pheromone amount and its boundaries, and return to Step 5.

The pheromone amount between the first node $N(i^1,j^1)$ and start node * is updated by equation (14)

$$\tau (*,(i^1,j^1))=\tau (*,(i^1,j^1))+\frac{Q}{L_f^a}$$

(14)

The pheromone amount between neighbor nodes, denoted as $N(i^s,j^s)$ and $N(i^{s\prime },j^{s\prime })$ , is updated according to equation (15). If a new optimal solution is acquired in the current iteration, update the lower and upper pheromone boundaries by equations (9) and (11). What is more, the pheromone amount must be limited in the range determined by equation (7)

$$\tau ((i^s,j^{s\prime }),(i^s,j^{s\prime }))=\tau ((i^s,j^{s\prime }),(i^s,j^{s\prime }))+\frac{Q}{L_f^a}$$

(15)

• Step 11: If all possible job allocating plans are included, go to Step 12. Otherwise, generate a new job allocating plan and go to Step 3.

• Step 12: Output the solution of job allocating and tool scheduling that has the minimum makespan as final consequence.

Performance comparison and analysis

In this section, the results of MMACO algorithm are compared with those obtained by ACO and BCACO algorithm.

Due to the fact that in the open literature there are few simulation models that provide each operation various tools, the data employed in the computation are originally generated. The available tools and their corresponding processing time are presented in Table 1 as the data pool, from which 11 test problems are constructed and each problem has 3–10 jobs and three to five operations, as shown in Table 2.

Table 1.

The basic information of 16 jobs.

Job no.	Operation no.	Alternative tool no.	Processing time	Job no.	Operation no.	Alternative tool no.	Processing time
1 9	1	1	6	5 13	1	2 5	5 7
	2	5	7		2	3	6
	3	6 7	6 8		3	5 6	5 9
	4	8	5		4	6 7	7 4
	5	10 11 12	8 10 7		5	8 10 12	8 6 5
2 10	1	1 2	7 5	6 14	1	2 3	6 7
	2	4 5	5 7		2	3 7	4 5
	3	7 8	10 9		3	4 5 7	6 8 4
	4	9	7		4	9 10	8 9
	5	10	6		5	11	5
3 11	1	5 2 3	8 9 8	7 15	1	1 3	6 5
	2	7	6		2	5 2	7 8
	3	4 6	7 8		3	4 6	8 9
	4	8 9 10	4 4 6		4	8 9	4 6
	5	10	4		5	9 12	7 5
4 12	1	2 3	6 8	8 16	1	1 2 5	4 5 7
	2	4 6	5 7		2	4 7	7 8
	3	4 6 7	5 8 6		3	6 8	5 6
	4	8	8		4	7 9	6 8
	5	11	6		5	11 12	8 6

Table 2.

Details of test problems.

Problem no.	X	M	Job no.	N
1	3	3	2 3 4	3
2	3	3	1 6 8	4
3	4	4	1 3 4 6	4
4	4	4	2 3 5 6	5
5	5	5	1 2 3 4 5	5
6	5	5	1 2 4 6 7	5
7	5	5	1 3 5 7 8	5
8	5	5	2 4 5 7 8	5
9	4	8	1 2 3 4 5 6 11 14	4
10	5	10	1 2 4 5 6 7 8 10 12 15	5
11	5	10	1 2 3 4 5 7 8 9 11 13	5

X: number of available work centers; M: number of jobs in corresponding problem; N: number of operations in each job.

The simulation process is implemented by MATLAB 2011a on a 3.60-GHz Intel i5 personal computer. It would be the case that only one set of parameters used throughout the process is more favorable for verification. The parameters are given as follows: $\alpha =0.15$ , $\beta =0.20$ , $F=100$ , $A=10$ , $\rho =0.80$ , ${\tau }_0=0.7$ , $C=1$ , $Q=N/3$ and $P_{\mathrm{cvg}}=0.8$ .

The detailed solution of test problem no. 11 is described in Table 3 and illustrated by Gantt chart in Figure 4. The columns “Job no.” and “Tool no.,” respectively, show how jobs and tools are allocated to each work center. The makespan obtained by ACO, BCACO and MMACO algorithm is 81, 79 and 76, respectively, among which MMACO possesses the best one. Besides, tool utilization variance, represented by the standard deviation of tool processing time, is introduced to indicate the tool utilization status. A solution with lower tool utilization variance means more balanced tool utilization, which contributes to reducing tool modification time and cost. According to the consequence of tool scheduling in Table 3, tool utilization variance of ACO, BCACO and MMACO algorithm is 2.09, 1.80 and 1.54, respectively, which indicates that the tool utilization status can be improved by MMACO algorithm.

Table 3.

The detailed solution of problem no. 11.

Work center no.	ACO		BCACO		MMACO
	Job no.	Tool no.	Job no.	Tool no.	Job no.	Tool no.
1	1	1 5 6 8 12	1	1 5 6 8 11	1	1 5 6 8 12
	8	5 4 8 9 11	13	2 3 6 7 12	8	1 4 8 7 12
2	2	2 4 8 9 10	2	2 4 8 9 10	2	2 4 8 9 10
	9	1 5 7 8 12	7	3 2 4 8 9	9	1 5 7 8 11
3	3	3 7 4 9 10	3	2 7 4 9 10	3	3 7 4 9 10
	7	1 2 4 9 9	9	1 5 6 8 10	11	5 7 6 10 10
4	4	2 4 7 8 11	4	3 4 7 8 11	4	2 4 7 8 11
	13	2 3 5 7 10	8	2 4 8 9 11	13	2 3 6 7 10
5	5	5 3 6 7 12	5	5 3 6 7 12	5	5 3 6 7 12
	11	3 7 4 8 10	11	5 7 4 10 10	7	3 2 4 9 9

ACO: ant colony optimization; BCACO; bidirectional convergence ant colony optimization; MMACO: max–min ant colony optimization.

Figure 4.

The Gantt chart of problem no. 11.

To verify the effectiveness of the proposed algorithm, 20 trials of simulation experiment are carried out for each test problem. The average results of objective value (makespan) and reference value (processing time) are presented in Table 4. It can be seen from Table 4 that for problems whose job number is fewer than four, there are no makespan differences among MMACO, BCACO and ACO algorithms. It can be explained that there are rare tool conflicts among jobs. So just arranging tools with minimum machining time can approach the optimal solution. However, for more complicated problems, if adopting the same strategy, some operations will wait for longer time due to the high frequency of tool conflicts.

Table 4.

The average result of test problems.

Problem no.	Makespan			Processing time
	ACO	BCACO	MMACO	ACO	BCACO	MMACO
1	21.23	21.79	21.01	60.17	60.48	60.73
2	19.46	19.34	19.80	53.47	53.29	53.11
3	31.87	34.27	30.64	108.96	104.71	102.30
4	41.24	42.68	39.52	121.09	122.06	122.74
5	43.76	45.87	39.79	159.26	156.16	153.83
6	45.91	44.61	42.48	157.79	158.88	159.48
7	42.82	40.52	39.13	162.55	158.14	160.37
8	44.56	42.59	41.68	158.42	162.60	157.17
9	57.77	57.83	55.19	205.81	212.26	198.34
10	80.06	77.70	74.85	320.74	315.87	316.27
11	81.35	79.59	74.36	318.29	317.62	313.91

ACO: ant colony optimization; BCACO; bidirectional convergence ant colony optimization; MMACO: max–min ant colony optimization.

Figures 5 and 6, respectively, show the makespan and processing time differences in Table 4 among ACO, BCACO and MMACO algorithms. It can be observed from Figure 5 that MMACO algorithm performs better than ACO and BCACO algorithms except the first two, and the performance of BCACO algorithm exceeds ACO algorithm from test problem no. 6. This makes it evident that MMACO algorithm is an excellent method to solve NP-hard problems in FMS. Compared to ACO algorithm, BCACO algorithm is preferable to solve large-sized processing plan. The feature that the trend of makespan is not coincident with that of processing time demonstrates that pheromone trail has the function to make ants select paths from a global perspective.

Figure 5.

The comparison graph of makespan.

Figure 6.

The comparison graph of processing time.

Such a superior performance of MMACO algorithm can be explained by the differential pheromone updating rule which not only considers the effect of better solutions obtained during the process of iterations but also provides ants more opportunities to try new routes. Figure 7 presents the comparison of mean makespan obtained by all ants in each iteration. Figure 8 presents the comparison of the optimal makespan obtained by the current iteration. The proposed reason can be strongly verified by the feature in Figures 7 and 8 that when iteration reaches the distinct number, the mean and optimal makespan obtained by BCACO algorithm tends to be fixed, while those obtained by MMACO algorithm are still being updated.

Figure 7.

The convergence graph of the mean makespan.

Figure 8.

The convergence graph of the optimal makespan.

Conclusion

MMACO algorithm is developed as an extended version of ACO algorithm. By imposing limits to the pheromone amount, MMACO algorithm reduces the differences between different paths, thus avoiding ants trapped in repeated route. To improve the performance of the algorithm, more effective tuning of the parameters is necessary.

In addition to describing a processing plan more conveniently, assuming that all jobs have the same number of operations will generate more tool conflicts which are essential to compare the performance of involved algorithms.