Multi-objective integrated process planning and scheduling : a hybrid MAS/ACO approach

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 encountered in practical production, the sequentially prepared process plans and schedules may sometimes become inefficient or even infeasible. Integrated process planning and scheduling (IPPS) is a relatively new concept in manufacturing domain, which aims at improving the feasibility and optimality of the respective process plan and schedule, by combining both functions together. Scheduling itself is an NP-hard problem. With the complexity and flexibility involved by the incorporation of process planning function, IPPS is an even more difficult problem which is almost impossible to be solved by traditional optimisation methods.

In this thesis, a graphical formulation based on disjunctive AND/OR graphs, as well as a mixed integer programming model are presented for representing IPPS problems. Inspired by the negotiation-based multi-agent system (MAS) and ant colony optimisation (ACO) approaches, a novel hybrid MAS/ACO (HMA) approach is developed for solving IPPS problems. The approach is implemented on an MAS with a number of solution generator agents, each controlling a series of jobs agents and machine agents, negotiating with each other to realise the step-by-step assignment of operations, and finally yielding a feasible solution to the problem. In order to improve the performance, the pheromone accumulation, and evaporation mechanism in ACO are introduced into the negotiation process; the probabilistic and iterative features of ACO are also inherited to make the approach non-deterministic, and hence capable of progressively improving the solution quality as a meta-heuristic.

For multi-objective optimisation, correlations between different measures of scheduling problems have been experimentally and statistically studied; makespan and total tardiness are then chosen as the objectives to be simultaneously optimised. Furthermore, other extensions of IPPS including the incorporation of sequence dependent setup times, assembly operations, as well as dynamic rescheduling under disruptions, have also been studied and given solutions with the HMA approach. Experiments have been carried out to select an appropriate parameter set, and to evaluate and illustrate the applicability and effectiveness of the approach. The experimental results show that the HMA approach is a competitive and reliable method for solving IPPS problems.