A Graph-based Ant Colony Optimization Approach for Integrated Process Planning and Scheduling

This paper considers an ant colony optimization algorithm based on AND/OR graph for integrated process planning and scheduling (IPPS). Generally, the process planning and scheduling are studied separately. Due to the complexity of manufacturing system, IPPS combining both process planning and scheduling can depict the real situation of a manufacturing system. The IPPS is represented on AND/OR graph consisting of nodes, and undirected and directed arcs. The nodes denote operations of jobs, and undirected/directed arcs denote possible visiting path among the nodes. Ant colony goes through the necessary nodes on the graph from the starting node to the end node to obtain the optimal solution with the objective of minimizing makespan. In order to avoid local convergence and low convergence, some improved strategy is incorporated in the standard ant colony optimization algorithm. Extensive computational experiments are carried out to study the influence of various parameters on the system performance.

The AND/OR graph consists of two parts including three operations respectively. The blue directed arcs and green undirected arcs represent possible paths from one node to another. Ant colony visits all nodes along the arcs. The heuristic desirability of nodes and pheromone amount on the arcs will guide the ant to search the optimal path from the start node to the end node, which represents the schedule with minimum Cmax.Figure optionsDownload as PowerPoint slideGantt chart reflects the result of process planning and scheduling. This chart is the result of problem 3, which is constructed with 6 parts and 15 machines and is one of 24 test-bed problems provided by Kim et al. The result has shown that the minimum Cmax is 345.Figure optionsDownload as PowerPoint slide