An enhanced ant colony optimization approach for integrating process planning and scheduling based on multi-agent system

Abstract

Process planning and scheduling are two important manufacturing planning functions which are traditionally performed separately and sequentially. Usually, the process plan has to be prepared first before scheduling can be performed. However, due to the complexity of manufacturing systems and the uncertainties and dynamical changes encountered in practical production, process plans and schedules may easily become inefficient or even infeasible. The concept of integrated process planning and scheduling (IPPS) has been proposed to improve the efficiency, effectiveness as well as flexibility of the respective process plan and schedule. By combining both functions together, the process plan for producing a part could be dynamically arranged in accordance with the availability of manufacturing resources and current status of the system, and its operations’ schedule could be determined concurrently. Therefore, IPPS could provide an essential solution to the dynamic process planning and scheduling problem in the practical manufacturing environment. Nevertheless, process planning and scheduling are both complex functions that depend on many factors and flexibilities in the manufacturing system, IPPS is therefore a highly complex NP-hard problem.

Ant colony optimization (ACO) is a widely applied meta-heuristics, which has been proved capable of generating feasible solutions for IPPS problem in previous research. However, due to the nature of the ACO algorithm, the performance is not that favourable compared with other heuristics. This thesis presents an enhanced ACO approach for IPPS. The weaknesses and limitations of standard ACO algorithm are identified and corresponding modifications are proposed to deal with the drawbacks and improve the performance of the algorithm. The mechanism is implemented on a specifically designed multi-agent system (MAS) framework in which ants are assigned as software agents to generate solutions. First of all, the manufacturing processes of the parts are graphically formulated as a disjunctive AND/OR graph. In applying the ACO algorithm, ants are deployed to find a path on the disjunctive graph. Such an ant route indicates a corresponding solution with associated operations scheduled by the sequence of ant visit.

The ACO in this thesis is enhanced with the novel node selection heuristic and pheromone update strategy. With the node selection heuristic, pheromone is deposited on the nodes as well as edges on the ant path. This is contrast to the conventional ACO algorithm that pheromone is only deposited on edges. In addition, a more reasonable strategy based on “earliest completion time” of operations are used to determine the heuristic desirability of ants, instead of the “greedy” strategy used in standard ACO, which is based on the “shortest processing time”.

The approach is evaluated by a comprehensive set of problems with a full set of flexibilities, while multiple performance measurements are considered, including makespan, mean flow time, average machine utilization and CPU time, among which makespan is the major criterion. The results are compared with other approaches and encouraging improvements on solution quality could be observed.