Ant Colony Optimization

Introduction

Scheduling is one of the most important aspect in the modern biasness world and most of the firm and company try to find or seek the best way to save there resources and material by finding the proper way to scheduling them .As Scheduling consider important that achieving it makes the firm very successful due to utilizing limited resource to finish projects within stipulated time, budget deliver value to customer, learn and improve and evolve with new practices. there are many way for a company to scheduling its resources and we can divide them to two main type analytical and approximation methods as will the approximation methods can be divided into three sub method Heuristics, Meta heuristics and Permutation Methods in this report we will focus in one of the Meta heuristics method which is ant colony optimization .

Ant colony optimization (ACO) is based on the behavior of real ant colonies, which are able to find the shortest way from their nest to a food source.

Get quality help now

Prof. Finch

Verified writer

Proficient in: Business

4.7 (346)

“ This writer never make an mistake for me always deliver long before due date. Am telling you man this writer is absolutely the best. ”

+84 relevant experts are online

Hire writer

This algorithm or method was developed by Dorigo in the early 1990s. The ant colony optimization process can be explained by representing the optimization problem as a multilayered layer as shown in figure below

Procedure Literature Review

The ACO process can be explained as follows. the colony have a number of ants. The ants begin at the node one (home node) , move through the various layers from the ?rst layer to ?nal layer, and at the end at the destination node in each cycle or iteration.

Each ant can select just one node in each layer .The nodes selected along the path visited by an ant represent a sub optimal solution. Once the path is complete, the ant launches pheromone on the path based on the local updating rule .When all the ants complete their paths, the pheromones on the best path are updated using the global updating rule. In the beginning of the optimization all the edges are initialized with an equal amount of pheromone. The optimization process is terminated if either the previous maximum number of iterations is reached or no better solution is found in the old number of iterations. In total, at the optimum solution, all ants will move along the same path. All of this can be translated mathematical as following,

• When ant K, located at node I, it uses pheromone ?ij to compute the chance of choose j as the next node:

Where ? mean the degree of importance of the pheromones and N(k) I mean the set of nearby nodes of ant k when located at node I.

• Before returning to the home node (backward node), the kth ant deposits ?(k) of pheromone on arcs it has visited. The pheromone value ?ij on the arc (i,j) traversed is updated as follows:

Because of the increase in the pheromone, the probability of this arc being selected by the forthcoming ants will increase.

• When an ant k moves to the next node, the pheromone disappears from all the arcs ij according to the relation:

Where p ? (0,1] is a parameter and A denotes the segments or arcs traveled by ant k in its path from home to destination

• After all the ants return to the home node (nest), the pheromone information is updated according to the relation:

Where ? ? (0,1] is the evaporation rate (also known as the pheromone decay factor) and ?(k) ij is the amount of pheromone deposited on arc ij by the best ant k.

• The pheromone deposited on arc ij by the best ant is taken as:

Where Q is a just a number and Lk is the length of the path traveled by the kth ant

• Equation (5) can be implemented as:

where f worst is the worst value and f best is the best value of the objective function among the paths taken by the N ants, and ? is a parameter used to control the scale of the global updating of the pheromone. Many researcher where keen to develops and improves this method in the field of scheduling of manufacturing we can briefly discuss some of the research paper which are listed below

1. Ant-colony algorithms for permutation ?owshop scheduling to minimize makespan/total ?owtime of jobs Chandrasekharan Rajendran a,*, Hans Ziegler b
2. An ant colony optimization algorithm for scheduling virtual cellular manufacturing systems by P. Peng , X. X. Wang & T. L. Lau
3. Sequencing and scheduling of job and tool in a flexible manufacturing system using ant colony optimization algorithm by P. Udhayakumar & S. Kumanan
4. Scheduling continuous casting of aluminum using a multiple-objective ant colony optimization metaheuristic, Marc Gravel (1), Wilson L. Price (2) & Caroline Gagn? (2)
5. Scheduling of flexible manufacturing systems :an ant colony optimization approach, R Kumar1, M K Tiwari1 and R Shankar2*

Descition

In general the objective of the (ACO) for scheduling in manufacturing and specially in ?ow shops is how to minimizing the make span, and to minimize of total ?ow time of jobs, as will as we can applied (ACO) in scheduling problem for flexible manufacturing systems where the using of two machine and which is considered as hard problem by getting the solution in considerably easier mathematical way and less effort, also (ACO) used in some application in the industry one of them is Scheduling continuous casting of aluminum like in Alcan aluminum foundry ,where it must satisfied the orders of pure metal is available for all pours and that basins and molds are available when required, moreover (ACO) can use in scheduling problems for designing virtual cellular manufacturing systems by minimizing the total materials and components travelling distance, and a lot other filed than we can use (ACO) for scheduling in manufacturing.

Conclusion

Ant colony optimization is one of the meta heuristic method that replicate the behavior of real ant colonies in a mathematical representation to find solution to some problems in real life application , this report focus mainly in problems relating to scheduling in manufacturing as its clear from the report (ACO) the field of use the method is very wide from how shops scheduling to flexible manufacturing systems as also used in some industry like Alcan aluminum foundry ,(ACO) is a great method that can be used in scheduling and its great if more research is applied in this area of research.