Stagnation Avoidance
It represents the situation while all ants construct the similar solution and thus the probability of searching newer path as zero. This kind of situation occurs mainly because of inappropriate tuning of the control parameter ρ or trail persistence. The stagnation may happen whereas its low quantity restricts the information flow, if the quantity ρ is extremely high. By generating a random number 'μ', this undesirable condition can be overcome, that is to be compared along with the intensity of pheromone trail τ_{ij}. For low amount of pheromone trail the possibility of occurrence of the event μ > τ_{ij} will be on upper side hence the newer path can be explored. Algorithm will stick on the particular edge, if pheromone trail is extremely high. Hence, the system is prevented from stagnating at a specific point. The modifications discussed on top that have been incorporated in the common ACO algorithm and the flowchart of the similar is represents in following figure.
Definition
Specified a set of part types P = {P_{1}, P_{2} ... P_{P}} associated along with the set of alternative
P process plans P_{i } = {Pi_{1} , Pi_{2} ... Pi^{Pi}} , processing times
P_{r} Ti^{j} = {Pr Ti_{1} , Pr Ti_{2} ... Pr_{i} ^{Pri}} and number of steps S_{i} = {Si_{1} , Si_{2} ... Si^{Pi} }
Here, i ∈ 1, 2 . . .  P ) such that the processing is to be carried over the resources as machines, tools, fixtures whose availability is being indicated by the corresponding ones in the binary incidence matrix I, the problem is to choose a plan as a node in graphical representation p ∈ Pi for the processing of all parts type i or i^{th} cluster of nodes such that the total processing cost is minimized subject to the constraint such only one node is to be chosen from all clusters.
For the above definition, the cost function or C is described as the weighted sum of overall cost associated along with the processing time or C_{P}, number of steps comprised or C_{S} and the hamming distance or C_{H} signifying the dissimilarity between the process plans that is the problem is:
Minimize
C = A × (C_{p} + C_{s} ) + B × C_{H} ....................Eq(6)
Such as:
Here, A and B are the constants; Ω^{i}_{j} is binary decision variable which considered as the value 1 if the plan j is chosen for processing of part i; C_{P} is the cost per unit time; C_{S} indicate the cost per step; and D (i, j)(k, l) is the hamming distance among plan j or of part i and plan l or of part k that shows the dissimilarity count of the two plans computed by using incidence matrix I.
I is a binary matrix.
And λ = total number of machines, tools and fixtures = M + T + F along with each 1 as per to the requirement of particular alternative for a plan.
Table no.3: Problem Characteristics for demonstration
Parameter

Value

Parameter

Value

P

{P1, P2, P3, P4, P5}

S1

{6, 8}

P1

2
{P11, P1 }

S2

{5, 4}

P2

2
{P21, P2 }

S3

{3, 4, 7}

P3

1 2 3
{P3 , P3 , P3 }

S4

{4, 8, 5}

P4

1 2 3
{P4 , P4 , P4 }

S5

{6, 8}

P5

2
{P51, P5 }

A

1

PrT1

{17, 21}

B

1

PrT2

{12, 11}

cP

1 $/unit time

PrT3

{8, 9, 18}

cS

1 $/step

PrT4

{13, 17, 8}

wm

3

PrT5

{12, 20}

wf

2



wt

1

1 =



Part 1

Part 2

Part 3

Part 4

Part 5


m1

1



1



1


1





m2


1


1

1



1



1

1

1

m3

1


1





1


1




f1








1

1

1

1

1


f2

1

1

1









1

1

f3



1


1







1


f4




1




1





1

f5








1



1

1


t1

1

1


1

1




1





t2


1




1



1


1



t3

1


1

1







1



t4




1

1

1



1


1



t5

1

1






1

1





t6








1




1


t7



1







1

1

1

1



















Hamming distance or C_{H} is explained as weighted sum of number of resources unlike in two plans i or part j and k or part l; so mathematically:
Here, w_{m}, w_{f} and w_{t} are weight factors corresponding to the tools, fixtures and the machine as; Δ^{m}_{k} and Δ^{t}_{k}, Δ^{f}_{k} are the binary decision variables that consider as the value 1 while the k∈ tool, fixture or machine and corresponding values in incidence matrix are not similar. In the underlying problem, five parts have been considered with a total of twelve plans. Other parameter values concerned to the problem definition are given in Table no.3
Initialize the pheromone trails for each edge by an amount ε.
Initialize the visibility of each plan node l (part k) from a plan node j (part i), J_{i,j} as given below as:
Initialize some parameters as like n, α and β, iter.maximum
Input the process plans and compute the relevant data concerned to problem such is hamming distance matrix D_{H} for problem type 1 and D_{S}, SI and μ for problem type 2.
Set iter.current = 0.
Begin
Begin for each ant
Randomly place the ant on a node
Enter the selected node in Tabu1
Update Tabu2
Begin
Generate a random number u (0 ≤ u ≤ 1)
Create Tabu2 (excluding the nodes from the cluster of selected part types)
If u ≤ u0
Compute the probability for each probable node
Generate a random number s (0 ≤ s ≤ 1)
If s ≤ ξ^{k}_{i,j} (that is probability of j^{th} process plane of i^{th} part for ant k)
Choose the node with highest probability
Update Tabu1
Else
Else
Select the next node randomly and Update Tabu1
End
End
Select the next node randomly and Update Tabu1
Update best ant Update best global ant Update pheromone matrix like:
If (iter.corrent < iter.maximum) then continue begin
Else End
Output best global ant
Programme no.2: Application of Ant Colony Optimization to PPS Problem