Sage Journals: Discover world-class research

Abstract

In this article, we present a developed bidirectional convergence ant colony algorithm to solve the integrated job shop scheduling problem with tool flow in flexible manufacturing system. In particular, the optimization problem for a real environment, including system make-span and waiting time for tools, has been approached by means of an effective pheromone trail coding and tailored ant colony operators for improving solution quality. The algorithm provides an effective integration between operation sequence and tool selection. A new principle of state transition probability is proposed with consideration of the waiting time for tools, and an optimization method of tool assignment is put forward. The proposed algorithm employs a machine decomposition method inspired by operations that are processed on fixed machines. The ant just gives the partial solution on one machine each time to construct the global scheduling solution with the previous solution on the other machines. This method performs well using the efficiency of ant colony algorithm for solving job shop scheduling problem. The proposed algorithm is tested by a series of simulation experiments, and interpretations of the results are also presented. Final experimental results indicate that the developed bidirectional convergence ant colony algorithm outperforms some current approaches in job shop scheduling problem with tool flow.

Keywords

Flexible manufacturing system ant colony algorithm job shop scheduling problem tool flow

Introduction

The essence of scheduling in flexible manufacturing system (FMS) is an integrated scheduling problem of job shop scheduling problem (JSSP) with tool flow. In order to decrease job lateness in FMS, sets of different jobs have to be planned with different routings; to increase utilization of machines, sets of jobs have to be performed with optimal sequence.^1,2 The previous research articles on JSSP can be classified with respect to two criteria: job type and machine type. In the case of job type criteria, they can be classified as follows:

Each job starts at the first stage and finished at the last stage;

Each job may visit the same stage several times.

In the case of the machine type criteria, on the other hand, they can be classified as follows:

Those with identical parallel machines;

Those with nonidentical parallel machines.

Especially, nonidentical parallel machines can be found in many real-world situations. For instance, it is common to find up-to-date machines running together with overage machines. However, they may be kept in the production lines because of their high replacement costs, in spite of the fact that overage machines are less efficient. In this case, the modern machines, generally, require a shorter processing time for performing the same operations as the older machines. It is well known that a combinatorial problem such as JSSP presents a nonlinear multi-peak objective function in the multidimensional searching space.³ Thus, undirected searching techniques or branch and bound methods, in the worst case, take an unacceptable computational time to produce a solution close to the optimum. On the other hand, a directed parallel approach to the searching space seems to be very promising.

In recent years, ant colony optimization (ACO) algorithms belonging to the class of constructive meta-heuristic algorithms have been used for solving the combinational optimization problems such as scheduling problems. The ant colony algorithm is a new heuristic bio-mimetic algorithm developed recently, which imitated the foraging behavior of ant colony through the shorter path,⁴ and a directed parallel probabilistic searching technique that can be used to find near-optimal solutions in complex multidimensional searching spaces.⁵ In the last two decades, considerable development has been achieved in the research of JSSP,⁶ especially the ant colony scheduling algorithms were proposed, which took the full advantage of the flexibility of the system and improved the productivity of FMS greatly.^7,8 Ying and Liao⁹ are first to apply ant colony system for the n/m/p/C _max problem, which is used to find a processing order of n different jobs to be processed on m machines in the same sequence with minimizing the make-span. In an ant colony algorithm, an artificial ant probabilistically builds a complete solution by starting with a null one and iteratively adding solution components until a complete solution is built.¹⁰ The ant colony algorithm is also a new evolutionary algorithm, with the characteristic of parallelism, positive feedback, and heuristic search,^11–12 but it has the limitation of stagnation like other evolutionary algorithms.¹³ Several researches have present efficacious approaches to improve the performance of ant colony algorithm. Zhao et al.¹⁴ proposed a mutated ACO algorithm by introducing the mutation mechanism to the ant colony algorithm. This algorithm can enlarge searching range and avoid local minimum by randomly changing one or more elements of the local best solution. Yang and Kamel¹⁵ present a multi-ant colony approach for clustering data that consist of some parallel and independent ant colonies and a queen ant agent.

Researches on improved ant colony algorithm have been made by scholars home and abroad to solve multiple types of JSSP.¹⁶ Recently, ACO approach has become more preferable to solve combinatorial optimization problems. Stützle and Hoos¹⁷ introduce a MAX–MIN ant system, an improved version of basic ant system. T’kindt et al.¹⁸ also proposed an ACO approach to solve two-machine flow shop scheduling problem with the objective of minimizing both the total completion time and the make-span criteria. This heuristic algorithm combines simulated annealing search and a local search algorithm. Ahmadizar¹⁹ has proposed a new ant colony algorithm for make-span minimization in permutation flow shops, with a novel mechanism being employed in initializing the pheromone trail based on an initial sequence and the pheromone trail intensities being limited between lower and upper bounds which change dynamically. Yagmahan and Yenisey²⁰ have proposed a multi-objective ant colony system algorithm, which combines ACO approach and a local search strategy in order to solve JSSP. Additionally, Li et al.,²¹ Marimuthu et al.,²² Chang et al.,²³ and Pasupathy et al.²⁴ present a multi-objective algorithm in which a set of efficient solutions is developed.

The traditional JSSP does not consider the impact of tool flow, but assumes that the tools are always ready at any time, which is acceptable in simple scheduling in early FMS.^25
–27 Due to improved diversity requirements of production and the limited capacity of the machine tool magazine, the tool flow becomes increasingly important, and the assumption that results in the frequent tool exchange and inefficiency is unsustainable.²⁸ Tool exchange is an important task in actual operation of a FMS, especially in the case of limited tool capacity of the central tool magazine in an FMS and the local tool magazine on a machining center.²⁹ An optimization of tool scheduling model is proposed based on an improved type of genetic algorithm in the constraint of limited tool resources as well as the objective function related with the exchange time of tool.³⁰ Chinese scholar, Shilong et al.,^31,32 introduced a parameter of emergency degree to decide job’s precedence of using tools.

Not much work has been carried out on job shop scheduling with tool flow. Haisheng et al.³³ considered the integrated model of part and tool scheduling and suggested a new method of decision point calculation and a new rule named minimally borrowed. Suresh and Sridharan³⁴ presented a simulation study carried out for analyzing the impact of scheduling rules that control part launching and tool request selection decisions of a FMS operating under tool movement along with part movement policy. Lee et al.³⁵ have addressed a way of finding the best operation sequence that minimizes tool waiting time in real time.

In this article, the scheduling problem of jobs and tool selection probability are considered. And each job may visit the same stage several times and each machine equipped with a tool magazine where each task requires exactly one of the tools during its execution. As in JSSP with tool flow, there are the following two main decisions:

Sequencing the jobs allocated to each machine;

Sequencing the tools allocated to each job.

To increase the practicality of the problem, two objectives, minimizing make-span (for maximizing system throughput) and total waiting time for tools (for maximizing tool utilization), are considered in this article. And a number of scheduling rules are incorporated in the simulation models for the part launching and tool request selection decisions. In this context, a novel ant colony algorithm is proposed to this integrated scheduling problem and represents a further development in the ability to deal with complex manufacturing systems. Particular attention has been dedicated to the following:

The procedure for creating searching route of ants, in order to obtain the terminal condition of each ant;

The procedure for calculating new pheromone concentration, in order to guarantee positive transition probability and increase the possibilities of searching the best routing;

The procedure for deciding priority of choosing tool, in order to increase the utilization of tools.

The rest of this article is organized as follows. In the next section, the problem considered in this article is described with a mathematical model. The solution algorithms are presented in section “Improved bidirectional convergent ant colony algorithm,” and section “Simulation and analysis” reports the simulation results. Finally, section “Summary” summarizes the main results and gives the conclusions.

Mathematical model of optimization for integrated scheduling

Problem description

According to the fixed process of jobs in FMS, the operation processing sequence of each job is changeless, and types of tools needed for each operation are also decided. If the number of matched tools is less with a series of different parts, funds for buying tools would be less but the time for tool exchange would be more and waiting time of tools would be longer, which makes the make-span of all jobs longer. On the contrary, a large number of matched tools did not require much tool exchange and made waiting time of tools shorter, but it increases the processing cost greatly. Therefore, the objective of JSSP with tool flow is to optimize job processing sequence on different machine tools and tools using sequence for different jobs, in order to achieve the shortest make-span of the system. Optimization for JSSP in this article is based on following principles:

Ignore tool wear;

Each tool only occupies one cutter location;

Each machine tool only processes one job simultaneously;

Each operation can only be processed by one machine tool;

Time of processing an operation is determinate and known;

Compared to waiting time of tools and processing operation, time of tool exchange is negligible.

Mathematical model of JSSP with tool flow

Mathematical model

A JSSP of N×M scale with tool constraint can be described as N jobs processed on M machines with determinate process route and each operation with determinate types of tool.

To describe the problem more clearly, an integrated programming model is developed in this article. Suppose there are n ₁ jobs J_i (i = 1, 2, …, n ₁) to be machined and each job has the processing sequence that consists of different processing work v_ij (j = 1, 2, …, n ₂) corresponding with z kinds of tools. Also suppose there are m machine tools in the shop floor. In such a machining system, any one of the machine tools M_j (j = 1, 2, …, m) processes different processing work. The objective of optimization is to minimize the make-span of all jobs and the total waiting time for tools. Note that this model is a modification of the basic JSSP problem of Asadzadeh and Zamanifar.³⁶ More specifically, the main modification is the collection of operations for each ant to search and the waiting time for tools. The model is presented using the following notation:

i indices for different jobs, i = 1, 2, …, n ₁

j indices for different operations, j = 1, 2, …, n ₂

k indices for different machining center, k = 1, 2, …, m

λ indices for different tools, λ = 1, 2, …, z

v_ij operation j of job i

U_k set of operations to be performed on machining tool k

Q scheme number of tool deployment

M_k capacity of tool magazine on machine tool k

$t_{ijk}^{s}$ start time of v_ij performed on machine tool

t_ijk processing time of v_ij performed on machining tool k (note that there is one-to-one correspondence between an operation and a machining tool)

X_ijk decision variable which equals 1 if operation v_ij is allocated to machining tool k and equals 0 otherwise

N_ijλ decision variable which equals 1 if operation v_ij should be performed with tool λ and equals 0 otherwise

Y_ijkλ decision variable which equals 1 if operation v_ij do not need to wait for tool λ when to be performed on machining tool k; in other words, operation v_ij precedes to use tool λ than other operations and equals 0 otherwise

$t_{ij λ}^{w} (Q)$ waiting time for tool λ of operation v_ij under scheme Q

$T_{k}^{p}$ time of incessant processing operations on machine tool k

$T_{k}^{w}$ total waiting time for tools under tool configuration scheme Q on machining tool k

Now, the integrated scheduling mathematical model is given as

\begin{matrix} Minimize max {T_{k}^{p} + T_{k}^{w}} \\ Minimize max {T_{k}^{w}} \\ k = 1, 2, \dots, m \end{matrix}

Subject to

T_{K}^{P} = max {(t_{ijk}^{s} + t_{ijk}) X_{ijk}} for all i, j

(1)

T_{k}^{w} = \sum_{i = 1}^{n_{1}} \sum_{j = 1}^{n_{2}} \sum_{λ = 1}^{z} X_{ijk} \cdot (1 - Y_{k λ}) \cdot N_{ij λ} \cdot t_{ij λ}^{w} (Q)

(2)

\sum_{k = 1}^{m} X_{ijk} = 1 for all i, j (v_{ij} \in U_{k})

(3)

\begin{matrix} t_{ij k_{1}}^{s} \geq t_{i (j - 1) k_{2}}^{s} + t_{i (j - 1) k_{2}} \\ for all i, j and k_{1}, k_{2} \in (1, 2, \dots, m) \end{matrix}

(4)

(t_{i_{1} j_{1} k}^{s}, t_{i_{1} j_{1} k}^{s} + t_{i_{1} j_{1} k}) \cap (t_{i_{2} j_{2} k}^{s}, t_{i_{2} j_{2} k}^{s} + t_{i_{2} j_{2} k}) = ϕ, i_{1}, i_{2} \in {1, 2, \dots, n_{1}} and j_{1}, j_{2} \in {1, 2, \dots, n_{2}} and for all v_{ij} \in U_{k}

(5)

X_{ijk} \in {0, 1} for all i, j, k

(6)

N_{ij λ} \in {0, 1} for all i, j, λ

(7)

Y_{ijk λ} \in {0, 1} for all i, j, k λ

(8)

The two objective functions denote to minimize make-span and total waiting time for tools. The incessant processing time of each machining center and total waiting time for tools on machining center can be specified by constraints (1) and (2), respectively. Constraint (3) ensures that only one job can be processed on a machine at any time. Finally, the other constraints (4), (5), and (6) represent the conditions of decision variables.

The problem (even with only one of the two objective functions) is nondeterministic polynomial time (NP) hard since it has been proved that job shop with tool flow make-span scheduling problem is NP hard.²³ Therefore, after transforming the integrated mathematical model into disjunctive graph, ant colony algorithm is suggested.

Model of disjunctive graph for JSSP with tool flow

The disjunctive graph is widely used as an instance description in ant colony algorithm to solve JSSP scheduling problem. When the disjunction graph is used to describe JSSP, a oriented graph is defined as $G = (V, C \cup D)$ , where V is a set of operations consisting of all procedures and two dummy nodes which are start node “0” and terminal node “*” with no processing time and no tools, C is a set of all conjunctive arcs corresponding to procedure route of a job and D is a set of all disjunctive arcs connecting operations processed on the same machine tool.

Figure 1 shows a disjunctive graph of a 3 × 3 JSSP where straight solid lines are conjunctive arcs and straight dotted lines are disjunctive arcs. And the weights of conjunctive arcs are the processing time of corresponding start operations.

Figure 1.

A model of disjunction graph of a 3×3 JSSP.

The classic model of disjunction graph for JSSP only showed the constraints of the process route of a job, but the constraint of limited tools is not demonstrated. Therefore, another kind of directed arcs representing mutually exclusive characteristic of tools is added to the classic model of disjunction graph, called tool mutually exclusive arcs. The tool exclusive arcs connect different procedures which have mutually exclusive requirement for the same tool synchronously. The set of all tool mutually exclusive arcs is denoted as R and then the disjunctive graph of JSSP considering the mutually exclusive characteristic of tools is denoted as an oriented graph, $G = (V, C \cup D \cup R)$ .

Figure 2 shows a disjunction graph of a 3 × 3 JSSP with tool flow where unidirectional straight solid lines are conjunctive arcs, bidirectional straight dotted lines are disjunctive arcs, and bidirectional solid curves are tool exclusive arcs. The weights of conjunctive arcs are the sum of processing time of corresponding operations and the waiting time of tools.

Figure 2.

A model of disjunctive graph of a 3×3 JSSP with tool flow.

A scheduling sequence constructed after an ant travels through all the nodes. Performing sequence of each machine is obtained at the same time, and the direction of the disjunctive arcs can be sure.

Improved bidirectional convergent ant colony algorithm

Step 1. Optimization for procedure sequence

In light of the disadvantages of ant colony algorithm such as large calculation and low efficiency in the iterative prophase, all operations are classified into different collections based on their processing machine tools. The disjunctive graph in Figure 2 is classified into three collections defined as $G_{1}, G_{2}, G_{3}$ . First, a feasible global solution based on process route must be obtained, which is defined as initial solution. Then ant colony search on subgraph $G_{j}$ consisting of each operation collection for partial operation sequence on machine tools, which makes the global solution be optimized. Finally, each optimized partial operation sequence of machine tools is all added to the completed disjunctive graph. Figure 3 is a subgraph of procedure collections referring to the different processing machine tools in Figure 2.

Figure 3.

Separate graphs of procedure collections on different machines in Figure 2.

In order to obtain a feasible and more optimal solution, appropriate start for each subgraph should be appointed when solving procedure sequences in subgraphs within each iteration. Then operations with smaller operation indices in each collection would be more probable to be chosen as their starts. Therefore, starts of each subgraph are any operations whose operation index is smaller than threshold values W defined as

W = min j + z (max j - min j)

(9)

where min j and max j denote minimum operation index and maximum operation index in each subgraph, respectively.

Step 2. Optimization for tool assignment

Optimization for procedure sequence is to determine more optimal processing sequence for machines. The method of operations classified by machines applied in ant colony algorithm solves the problem of priority for different procedures to process on the same machine tool. But the problem of precedence of using tools for procedures on different machine tools at the same time still exists. Therefore, the precedence sequence of using tools needs to be decided, when jobs on different machine tools have requirement for the same tools synchronically.

This problem has an indeterminate factor, that is, the procedures requiring the same tool at a moment are not always the same while the processing sequence is changed. In view of this, it should be formulated as a rule to solve the conflict for using tools in each iteration.

If all procedures requiring the same tool W at moment t synchronically are denoted as a procedure collection $(r_{1}, r_{2}, \dots, r_{l})$ , where ${r_{1}, r_{2}, \dots, r_{l}} \subseteq {1, 2, \dots, n_{2}}$ , the probability of using tool W preferentially by the procedure $r_{c} (c \in (1, 2, \dots, l))$ is computed according to the formula

γ = \frac{\frac{1}{r_{c}}}{\sum_{c = 1}^{l} \frac{1}{r_{c}}}

(10)

which means that operations with smaller operation index can use the tools more preferentially. In this way, not only the rules for priority of using tools are instituted but also the algorithm will not be limited into partial optimal solution, based on the precondition that procedure sequence is optimized.

Step 3. Integrated design of the improved bidirectional convergence ant colony algorithm

According to the solving requirement of this problem and the characteristic of basic ant colony algorithm, the following improvements are proposed:

As the integrated problem of JSSP with tool flow is not an ergodic problem, terminal condition of each ant is not traveling all operations but the operations which are machined on the same machine tool.

There are not enough tools because of limited funds. Therefore, the time for an ant to reach the successor operation consists of time of processing and waiting for tools.

The information of each operation in Figure 2 is formulated as operation = (t^w, t^s, t^e, Tm, Next), where t^w is the time of waiting for tools, t^s and t^e are starting time and ending time of the operation for processing, Tm is the required tool collection, and Next is the information of successor operation including the list of accessible operation and the information of reaching these operations.

Considering constraints of procedures and tools synthetically, the improved algorithm is based on the following principles:

After reaching an operation on the same machine, ants cannot turn to its nondirect successor operation, for example, operations v ₂₁ and v ₃₂ are both to be processed on machine k, and after machine k processed operation v ₂₁, ants of machine k cannot turn to v ₃₂ unless operation v ₃₁ has been processed.

Ants cannot travel from the former operation to the successor operation until the first required tool of the successor operation is ready.

Ants cannot turn to the successor operation until all the process steps of the former operation are finished.

The paths in the graph represent the interval time “make-span” computed by evaluation function.

The meaning of the procedure sequence is appended to the paths when make-span is calculated.

The algorithm formula is presented using the notation in section “Mathematical model of optimization for integrated scheduling” and the following notation:

α the power factor of information heuristic expression

β the power factor of expectation heuristic expression

$τ_{xy}$ information heuristic expression

$η_{xy}$ expectation heuristic expression

$Δ τ_{xy}$ the increment of pheromone

ρ the volatilization coefficient of pheromone

$tab u_{e}$ the tabu list of operations that ant e has gone through

$N - tab u_{e}$ the operations that ant e can reach in next transformation

In each iteration, as shown in Figure 3, each ant must reach all operations from the start to the end in corresponding subgraph. In equation (11), the larger the value of α, the more important the affection of pheromone for ants to decide which path to choose, which also means less iteration times. And β decides the affection of heuristic message, which leads to the better paths subject to sequence of operations and limited tools. Then, the transition probability of ant traveling from an operation to another is based on equation (11)

p_{kj} = {\begin{matrix} \frac{{[τ_{xy} (t)]}^{α} \cdot {[η_{xy}]}^{β}}{\sum_{j \in {N - tab u_{e}}} {[τ_{xy} (t)]}^{α} \cdot {[η_{xy}]}^{β}} & j \in {N - tab u_{k}} \\ 0 & otherwise \end{matrix}

(11)

$η_{xy}$ is the expectation heuristic expression of relative arc (x, y), where x and y are the start node and ending node of the arc, and in the disjunctive graph, it can be calculated by equation (12)

η_{xy} = \frac{1}{(1 + \frac{t_{y}^{w}}{t_{y}^{s} - t_{y}^{e}} + y)}

(12)

where y is the index number of operation, $t_{y}^{w}$ is the time of procedure y waiting for tools, and $t_{y}^{s}$ and $t_{y}^{e}$ are the starting and ending time of processing operation y. In equation (12), the smaller the value of $t_{y}^{w} / (t_{y}^{s} - t_{y}^{e})$ or y, the larger the value of $η_{xy}$ . In this way, when choosing successor operation, ants tend to choose the operations with smaller operation index and shorter waiting time for tools. Simultaneously, time of tool exchange can be decreased in this way.

$τ_{xy} (t)$ is the pheromone concentration of arc (x, y) at moment t in the disjunctive graph. The more the pheromone concentration, the higher the probability of ants choosing the path. Each ant updates the weight of pheromone concentration of the path, according to the quality of performance index obtained in each iteration. Then, new pheromone concentration is based on equation (13)

τ_{xy} (t + 1) = (1 - ρ) τ_{xy} (t) + Δ τ_{xy}

(13)

The number of ants on machine k in iteration n is equal to the number of procedures to be processed on the machine. And then, the obtained procedure sequence of machine tool k in iteration n is $S_{k}^{n}$ , combining the previous procedure sequence of other machines, $S_{1}^{n - 1}, S_{2}^{n - 1}, \dots, S_{k - 1}^{n - 1}, S_{k + 1}^{n - 1}, \dots, S_{m}^{n - 1}$ , to constitute the global scheduling sequence $S_{1}^{n - 1}, S_{2}^{n - 1}, \dots, S_{k - 1}^{n - 1}, S_{k}^{n}, S_{k + 1}^{n - 1}, \dots, S_{m}^{n - 1}$ , which is the weight of new obtained critical key path $S_{max k}^{n}$ .

In this way, for each machine tool, the initial procedure sequence of machine tool $1, 2, 3, \dots, m$ is $P_{1}, P_{2}, P_{3}, \dots, P_{m}$ , respectively. The time of machine tool k to perform all procedures that should be processed on this machine is

T_{k} = \sum_{v_{ij} \in P_{k}} (t_{ij} + Δ t_{ij}), k \in (1, 2, \dots, m)

(14)

where $t_{ij}$ and $Δ t_{ij}$ denote processing time and waiting time for tools on machine k, respectively, finishing the procedure $v_{ij}$ in procedure sequence $P_{k}$ . And $t_{ij}$ is already known and $Δ t_{ij}$ can be obtained by the procedure processing sequence and the scheme of tool assignment. Then, the weight of critical key path is defined as equation (15)

S_{max k}^{n} = max_{1 \leq k \leq m} (T_{k})

(15)

Therefore, the penalty factor in equation (13) is equation (16)

Δ τ_{xy} = {\begin{matrix} \frac{1}{S_{max k}^{n}}, & S_{max k}^{n} < S_{max}^{n - 1} \\ - \frac{1}{S_{max k}^{n}}, & S_{max k}^{n} \geq S_{max}^{n - 1} \end{matrix}

(16)

where $S_{max k}^{n}$ is the weight of the new critical key path and ρ is the evaporation factor. And $1 - ρ$ is the proportion of remaining pheromone based on the previous weight of pheromone after updating per unit time. In order to prevent the situation with $τ_{xy} (t) < 0$ , the weight of $τ_{xy} (t)$ is set same as in literature,¹⁷ which would not be elaborated here. After the repeated iteration and constant optimization of the weight of critical path, the optimal solution will be obtained. The working of the algorithm can best be understood by the following steps, which are shown in Figure 4.

Step 1. Choose the operations first to be processed on the machine tools, which are the starts of ants on each machine tool, based on the selection standard.

Step 2. Assign tools for each operation based on the selection standard of using tools when there are not less than two operations demanding the same tool synchronically.

Step 3. If the required tool is available, then go to step 4, otherwise compute the waiting time for the required tool and then go to step 4 until the tool is ready.

Step 4. Choose next operation for each ant based on the transition probability.

Step 5. If the required tool is available, then go to step 6, otherwise compute the waiting time for the required tool and then go to step 6 until the tool is ready.

Step 6. If all the operations on each machine tool are processed, then go to step 7, otherwise go to step 4.

Step 7. Compute the key path $S_{max k}^{n}$ and update the pheromone concentration $τ_{xy} (t)$ of each path.

Step 8. If the number of iteration is equal to the maximum number of iteration or the optimal results are the same in the last 10 iterations, then go to step 9, otherwise go to step 1.

Figure 4.

Flowchart of the ant colony algorithm.

In summary, the pseudo-code of the ant algorithm in this article is presented as follows

Input a problem instance

Initialization

Set termination criteria

Set algorithm parameters α, β, ρ, λ, τ ₀

Get the number of tool as D, if $z_{i} (t_{ij}^{s}, t_{ij}^{e}) = 1$ , tool z is occupied by ant i between t ₁ and t ₂

Get disjunctive child graph G ₁, G ₂, …, G_m (the procedure set of each machine)

Set number of ants N_k on G_k = number of total procedures on machine tool k

While terminating criteria is not met do

Output the optimal results

For k = 1 to m do

Get G_k

Set tabu list tabu = Φ

Set unvisited list U = G_k− tabu

End for

For each G_k

randomly choose the initial operation which the operation number is smaller than or

equal to W in equation (9)

randomly assign the tools to the initial operation according to equation (10)

For ant i = 1 to N_k do

Set $t_{ij}^{s}$ = time of ant i arrives at operation j, $t_{ij}^{e}$ = time of ant i leave operation j

While U_i≠Φ do

Choose the next operation j from U_i according to equation (11)

randomly assign the tools to ants according to equation (10)

Set $z_{i} (t_{ij}^{s}, t_{ij}^{e}) = 1$ , after time $t_{ij}^{e}$ , tool z is available

Add operation j into tabu_i

Delete operation j in U_i

End while

Compute the make-span S _max k and the total waiting time for tools

End for

Update pheromone of all paths according to equation (13)

End for

End while

Output the global optimal solution

Simulation and analysis

The performance of the proposed algorithm in optimizing JSSP with tool flow is evaluated using appropriate quality measures. Therefore, an example is used to validate the effectivity of the application of bidirectional convergence ant colony algorithm for JSSP with tool flow, and the results are reported in this section. First, to see how the different schemes of tool assignment influence the performance of the algorithm in this article, we work out three schemes and the performances are mentioned in Table 2. Then, comparisons between the proposed algorithm and algorithm in Siemiatkowski and Przybylski²⁷ are implemented based on 10 times simulation results of the example. To determine which method is much more effective, the performance of methods mentioned in Table 4 was compared with four pertinent objectives.

The mechanical system consists of four machining center, two automated guided vehicles, and a tool manipulator. The numbers of machines are m1, m2, m3, and m4, and the parameters of the example are shown in Table 1.

Table 1.

The process data of the system.

Number of job	Number of procedure	Number of machine tool	Number of work step (type of tool/using time)
			1	2
1	1	1	1/19	2/30
	2	3	3/20	2/18
	3	4	4/35	5/31
2	1	2	6/32	2/35
	2	3	3/25	5/25
	3	1	4/40	1/20
3	1	4	4/22	5/31
	2	1	1/29	3/33
	3	2	2/35	6/40
4	1	1	2/27	3/25
	2	2	4/24	1/20
	3	3	2/35	1/22
5	1	2	1/28	6/30
	2	3	2/20	5/27
	3	4	4/32	3/24

The example has five jobs to process and requires six types of tool. As Table 1 shows, types 1 and 2 of tools are used most frequently, called key tool which has the maximum times of exchanges, and types 3, 4, 5, and 6 of tools are used relatively less. Therefore, the following three schemes of tool assignment are proposed.

Scheme 1. Each type is configured one tool.

Scheme 2. Types 1 and 2 are both configured two tools and the others are configured one.

Scheme 3. Each type is configured enough tools to ensure that every procedure needs no time of waiting for tools.

Table 2 shows the best optimized global solution of the make-span and the average utilization of machining centers under different schemes of tool assignment. As shown in Figure 2, the make-span is 331 min, and the average utilization of machining centers is much lower when the tool resource for manufacturing a batch of jobs is short. After increasing the number of key tools under the requirement of practical process, the best optimized solution of make-span is only 259 min significant with 22% of decline, and the availability of each machine center is boosted remarkably and becomes more balanced. However, it is known that the make-span and the availability of each machine center in the tool configuration schemes 2 and 3 are almost identical. Therefore, in practical machining process, an effective algorithm can not only improve the efficiency of machines but also obviously decrease the amount of tools, which effectively reduce costs. The numerical results of this algorithm applied to different schemes of tool assignment are summarized in Table 3. For different schemes, the results concerning best and poorest make-spans, mean and standard deviation of error gap are all reported.

Table 2.

The average utilization of machine tools under different schemes of tool assignment.

Scheme number of tool assignment	Utilization of machine tools (%)				Total waiting time for tools (min)	Make-span of system (min)
Scheme number of tool assignment	m1	m2	m3	m4	Total waiting time for tools (min)	Make-span of system (min)
1	86.10	91.04	67.37	74.15	85	331
2	86.10	96.14	80.31	79.19	12	259
3	86.10	96.14	80.31	82.16	0	259

Table 3.

The performance index of make-span under different schemes of tool assignment.

Scheme number of tool assignment	Optimal solution	Best solution	Poorest solution	Mean	Standard deviation of error gap
1	308	331	386	357	17.35
2	249	259	293	275	9.97
3	249	259	285	271	7.99

The goal of this article is to propose a new ant colony algorithm to solve JSSP with tool flow more effectively. To assess the performance of this algorithm, it is compared with other algorithm³⁷ of JSSP with tool flow. The algorithm in literature³⁷ developed a new method of decision point calculation of choosing parts and a new rule named tools minimally borrowed. The comparison between the new ACO algorithm and algorithm in literature³⁷ is given in Table 2 under scheme 2 of tool assignment, where for the problem, best and poorest solutions, mean, error rate, and computation time are reported in detail. To make a fair comparison, the two algorithms are both simulated on the same computer. The experiments are run using MATLAB 2011a on a 2.9-GHz Intel i5 personal computer (PC).

The parameters of new ant colony algorithm are $ρ = 0.7$ , $α = 1.0$ , $β = 1.5$ , $λ = 0.4$ , and $τ_{0} = 10$ , and the definitions of parameters are according to literature.³⁸ As shown in Table 4, the solution of improved algorithm is much more optimal. In addition, the improved algorithm avoids the trouble of falling into local minimum solution to some extent. Figure 5 shows the procedure sequence corresponding to the optimal solution under scheme 2 of tool assignment, in which O_ijs represents work step s of process j of job i in Table 1.

Table 4.

The comparison of the performance of different algorithms under scheme 2.

Algorithm	Best solution	Poorest solution	Mean	Error rate	CPU time (s)
Improved	259	311	279	7.72%	1.23
Literature²⁷	294	365	334	13.61%	1.57

CPU: central processing unit.

Figure 5.

The procedure sequence corresponding to the optimal solution under scheme 2.

Summary

Actually, optimization for production scheduling problem in FMS is integrated optimization for JSSP with tool flow. This article considers the optimization for assignment of tool flow based on optimal scheduling for part flow. A designed bidirectional convergence ant colony algorithm is proposed to solve the problem of optimization for job shop scheduling with tool flow. Therefore, a mathematical model of JSSP with tool flow is established, and a designed bidirectional convergence ant colony algorithm is used to get optimal solution for the model. The results in simulation analysis show that the designed algorithm not only shortens the make-span of the system but also reduces processing cost by decreasing the number of tooling setup. Compared to original class of ant colony algorithm for integrated scheduling problem of JSSP with tool flow, the designed algorithm is much more effective.

Footnotes

Declaration of conflicting interests

The authors declare that they have no conflicts of interest.

Funding

The National Outstanding Youth Science Foundation (Grant No. 50925518), National Science and Technology Major Project (Grant No. 2012ZX04011-031), National Science and Technology Support Plan Subsidization Project (Grant No. 2012BAF12B09), and the Youth Science Foundation of National Natural Science Foundation (Grant No. 51005260) support this research project.

References

Hutchison

Leong

Synder

. Scheduling approach for random job shop flexible manufacturing systems. Int J Prod Res 1991; 29: 1053–1067.

Ovacik

Uszoy

. Decomposition methods for complex factory scheduling problem. Norwell, MA: Kluwer Academic Publishers, 1997.

Drobouchevitch

Strusevich

. Heuristics for the two-stage job shop scheduling problem with a bottleneck machine. Eur J Oper Res 2000; 123: 229–240.

Duan

. Ant colony algorithms: theory and applications. 1st ed. Beijing, China: Science Press, 2005.

Huang

R-H

Yang

C-L

. Ant colony system for job shop scheduling with time windows. Int J Adv Manuf Tech 2008; 39: 151–157.

Xiuli

. Research on flexible job shop dynamic scheduling problem. J Syst Simul 2008; 20: 3828–3832.

Merkle

Middendorf

Schmeck

. Ant colony optimization for resource-constrained project scheduling. IEEE T Evolut Comput 2002; 6: 333–346.

Liang

Peihang

Wuru

. Application of an improved genetic algorithm for tool scheduling in FMS. Ind Control Comput 2009; 22: 75–78.

Ying

K-C

Liao

C-J

. An ant colony system for permutation flow-shop sequencing. Comput Oper Res 2004; 31: 791–801.

10.

Heinonen

Pettersson

. Hybrid ant colony optimization and visibility studies applied to a job-shop scheduling problem. Appl Math Comput 2007; 187: 989–998.

11.

Eswaramurthy

Tamilarasi

. Hybridizing tabu search with ant colony optimization for solving job shop scheduling problems. Int J Adv Manuf Tech 2009; 40: 1004–1015.

12.

Montgomery

Fayad

Petrovic

. Solution representation for job shop scheduling problems in ant colony optimisation. Int J Adv Manuf Tech 2006; 4150: 484–491.

13.

Rossi

Dini

. Flexible job-shop scheduling with routing flexibility and separable setup times using ant colony optimisation method. Robot Cim-Int Manuf 2007; 23: 503–516.

14.

Zhao

. Ant colony optimization algorithm with mutation mechanism and its applications. Expert Syst Appl 2010; 37: 4805–4810.

15.

Yang

Kamel

. An aggregated clustering approach using multi-ant colonies algorithms. Pattern Recogn 2006; 39: 1278–1289.

16.

Shibei

Yugeng

. A machine decomposition method for job shop scheduling problem based on ant colony algorithm. Comput Simul 2008; 25: 187–190.

17.

Stützle

Hoos

. MAX–MIN ant system. Future Gener Comp Sy 2000; 16: 889–914.

18.

T’kindt

Monmarche

Tercinet

. An ant colony optimization algorithm to solve a 2-machine bicriteria flowshop scheduling problem. Eur J Oper Res 2002; 142: 250–257.

19.

Ahmadizar

. A new ant colony algorithm for makespan minimization in permutation flow shops. Comput Ind Eng 2012; 63: 355–361.

20.

Yagmahan

Yenisey

. A multi-objective ant colony system algorithm for flow shop scheduling problem. Expert Syst Appl 2010; 37: 1361–1368.

21.

Baki

Aneja

. Flow shop scheduling to minimize the total completion time with a permanently present operator: models and ant colony optimization meta-heuristic. Comput Oper Res 2011; 38: 152–164.

22.

Marimuthu

Ponnambalam

Jawahar

. Threshold accepting and ant-colony optimization algorithms for scheduling m-machine flow shops with lot streaming. J Mater Process Tech 2009; 209: 1026–1041.

23.

Chang

Hsieh

Lin

. The development of gradual-priority weighting approach for the multi-objective flowshop scheduling problem. Int J Prod Econ 2002; 79(3): 171–183.

24.

Pasupathy

Rajendran

Suresh

. A multi-objective genetic algorithm for scheduling in flow shop to minimize the makespan and total flow time of jobs. Int J Adv Manuf Tech 2006; 27: 804–815.

25.

Antonio

HongNian

Kelleher

. Hybrid heuristic search for the scheduling of flexible manufacturing systems using petri-nets. IEEE T Robotic Autom 2002; 18: 240–244.

26.

Haolin

. Algorithm of FMS production scheduling based on genetic algorithm. Chin J Mech Eng 2000; 20: 3828–3832.

27.

Siemiatkowski

Przybylski

. Simulation studies of process flow with in-line part inspection in machining cells. J Mater Process Tech 2006; 171: 27–34.

28.

Echer

Gupta

JND

. Scheduling tasks on a flexible manufacturing machine to minimize tool change delays. Eur J Oper Res 2005; 164: 627–638.

29.

Cheung

EHM

Chuah

. Increase the efficiency of an FMS by improving the tool scheduling strategies. J Mater Process Tech 1996; 61: 213–218.

30.

Hong-Fang

. An ant colony algorithm for job shop scheduling problem. In: Proceedings of the 5th world congress on intelligent control and automation, Hangzhou, China, 15–19 June 2004, vol. 4, pp.2899–2903.

31.

Shilong

Zhongjun

Lide

. On-line tool management system for flexible manufacturing system. High Technol Lett 1995; 5: 31–35.

32.

Shilong

Lide

Dan

. Online tool management system in FMS. Manuf Technol Mach Tool 1993; 4: 25–29.

33.

Haisheng

Gang

Dan

. Research of dynamic scheduling in job-shop with tool-flow. Manuf Technol Mach Tool 2008; 3: 21–27.

34.

Suresh

Sridharan

. Simulation modeling and analysis of part and tool-flow control decision in a flexible manufacturing system. Robot Cim-Int Manuf 2009; 25: 829–838.

35.

Lee

Kim

Choi

. Operation sequence and tool selection in flexible manufacturing systems under dynamic tool allocation. Comput Ind Eng 2003; 45: 61–73.

36.

Asadzadeh

Zamanifar

. An agent-based parallel approach for the job shop scheduling problem with genetic algorithms. Math Comput Model 2010; 52: 1957–1965.

37.

Wen

Shilong

. Research on ant colony algorithm for multi-agent based workshop dynamic scheduling. Modul Mach Tool Autom Manuf Tech 2004; 6: 23–26.

38.

Shichang

Jie

Jun

. The optimal selection on the parameters of the ant colony algorithm. B Sci Technol 2003; 19: 381–386.

An ant colony algorithm for job shop scheduling problem with tool flow

Abstract

Keywords

Introduction

Mathematical model of optimization for integrated scheduling

Problem description

Mathematical model of JSSP with tool flow

Mathematical model

Model of disjunctive graph for JSSP with tool flow

Improved bidirectional convergent ant colony algorithm

Step 1. Optimization for procedure sequence

Step 2. Optimization for tool assignment

Step 3. Integrated design of the improved bidirectional convergence ant colony algorithm

Simulation and analysis

Summary

Footnotes

Declaration of conflicting interests

Funding

References