Solving Integrated Process Planning and Scheduling Problems with Metaheuristics

This dissertation, "Solving Integrated Process Planning and Scheduling Problems With Metaheuristics" by Luping, Zhang, 张路平, was obtained from The University of Hong Kong (Pokfulam, Hong Kong) and is being sold pursuant to Creative Commons: Attribution 3.0 Hong Kong License. The content of this dissertation has not been altered in any way. We have altered the formatting in order to facilitate the ease of printing and reading of the dissertation. All rights not granted by the above license are retained by the author. Abstract: Process planning and scheduling are two important manufacturing planning functions which are closely related to each other. Usually, process planning and scheduling have to be performed sequentially, whereby the process plans are the input for scheduling. Many investigations have shown that the separate conduction of the two functions is much likely to ruin the effectiveness and feasibility of the process plans and schedules, and it is also difficult to cater for the occurrence of uncertainties in the dynamic manufacturing environment. The purpose of integrated process planning and scheduling (IPPS) is to perform the two functions concurrently. IPPS is a typical combinatorial optimization problem which belongs to the category of NP-hard problems. Research on IPPS has intensified in recent years. Researchers have reported various IPPS systems and solution approaches which are able to generate good solutions for specific IPPS problems. However, there is in general an absence of theoretical models for the IPPS problem representation, and research on the theoretical aspects of the IPPS is limited. The objective of this research is to establish a metaheuristic-based solution approach for the IPPS problem in flexible jobshop type of manufacturing systems. To begin with, a graph-based modeling approach for formulating the IPPS problem domain is proposed. This approach defines a way to use a category of AND/OR graphs to construct IPPS models. The graph-based IPPS model can be formulated using mathematical programming tools including polynomial mixed integer programming (PMIP) and mixed integer linear programming (MILP). The analytical mathematical programming approaches can be used to solve simple IPPS instances but they are not capable for large-scale IPPS problems. This research proposes a new IPPS modelling approach to incorporate metaheuristics in the solution strategy. Actually, the solution strategy comprises the metaheuristics and a mapping function. The metaheuristic is responsible for generating the operation sequences; a mapping function is then used to assign the operations to appropriate time slots on a schedule. General studies of applying constructive and improvement metaheuristics to solve the IPPS problem are conducted in this research. The ant colony optimization (ACO) is applied as a representative constructive metaheuristic, and a nonstandard genetic algorithm approach object-coding genetic algorithm (OCGA) is implemented as an improvement metaheuristic. The OCGA contains dedicated genetic operations to support the object-based genetic representation, and three particular mechanisms for population evolution. The metaheuristic-based solution approaches are implemented in a multi-agent system (MAS) platform. The hybrid MAS and metaheuristics based IPPS solution methodology is able to carry out dynamic rescheduling to cope with occurrence of uncertainties in practical manufacturing environments. Experiments have been carried out to test the IPPS solution approach proposed in this thesis. It is shown that both metaheuristics, ACO and OCGA, are having good performance in terms of solution quality and computational efficiency. In particular, due to the special genetic operations and population evolutionary mechanisms, the OCGA shows great advantages in experiments on benchmark problems. Finally, it is shown that the hybrid approach of MSA and metaheuristics is