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 able to support real-time rescheduling in dynamic manufacturing systems. / published_or_final_version / Industrial and Manufacturing Systems Engineering / Doctoral / Doctor of Philosophy

published_or_final_version / Industrial and Manufacturing Systems Engineering / Doctoral / Doctor of Philosophy

published_or_final_version / Industrial and Manufacturing Systems Engineering / Master / Master of Philosophy

Thesis (MEng)--University of Stellenbosch, 2002. / ENGLISH ABSTRACT: Artificial intelligence has provided several techniques with applications in manufacturing. Knowledge based systems, neural networks, case based reasoning, genetic algorithms and fuzzy logic have been successfully employed in manufacturing. This thesis will provide the reader with an introduction and an understanding of each of these techniques (Chapter 2 & 3). The intelligent manufacturing process can be a complex one and can be decomposed into several components: intelligent design, intelligent process planning, intelligent quality management, intelligent maintenance and diagnosis, intelligent scheduling and intelligent control. This thesis will focus on how each of the artificial intelligence techniques can be applied to each of the manufacturing process fields. Chapter 5 Chapter 6 Chapter 7 Knowledge based systems Neural networks Fuzzy logic Case based reasoning Genetic algorithms Chapter 8 Chapter 9 Chapter 10 Manufacturing intelligence can be approached from two main directions: theoretical research and practical application. Most of the concepts, methods and techniques discussed in this thesis are approached from a theoretical research point of view. This thesis is also aimed at providing the reader with a broader picture of manufacturing intelligence and how to apply the intelligent techniques, in theory. Specific attention will be given to intelligent scheduling as an application (Chapter 11). The application will demonstrate how case based reasoning can be applied in intelligent scheduling within a small manufacturing plant. / AFRIKAANSE OPSOMMING: Kunsmatige intelligensie bied 'n verskeidenheid tegnieke en toepassings in die vervaardigingsomgewing. Kennis baseerde sisteme, neurale netwerke, gevalle basseerde redenasie, generiese algoritmes en wasige logika word suksesvol in die vervaardigingsopset toegepas. Dié tesis gee die leser 'n inleiding en basiese oorsig van metodes om elk van die tegnieke te gebruik (hoofstuk 2 & 3). Die intelligente vervaardigingproses is 'n komplekse proses en kan afgebreek word in verskeie komponente: intelligente ontwerp, intelligente prosesbeplanning, intelligente gehaltebestuur, intelligente onderhoud en diagnose, intelligente kontrole en intelligente skedulering. Hierdie tesis sal fokus op hoe elk van die kunsmatige intelligente tegnieke op elk van die vervaardigingprosesvelde toegepas kan word. Hoofstuk 5 Hoofstuk 6 Hoofstuk 7 Kennis gebaseerde sisteme Wasige logika Neurale netwerke Gevalle baseerde redenasie Generiese algoritmes Hoofstuk 8 Hoofstuk 9 Hoofstuk 10 Vervaardigingsintelligensie kan vanuit twee oogpunte benader word, naamlik 'n teoretiese ondersoek en 'n praktiese aanslag. Die meeste van hierdie konsepte, metodes en tegnieke word in hierdie tesis vanuit 'n teoretiese oogpunt benader. Die tesis is daarop gerig om die leser 'n wyer perspektief te gee van intelligente vervaardiging en hoe om die intelligente tegnieke, in teorie, toe te pas. Spesifieke aandag sal gegee word aan intelligente skedulering as 'n toepassing (Hookstuk 11). Die toepassing sal demonstreer hoe gevalle baseerde redenasie toegepas kan word in intelligente skedulering.