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

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

Effective process scheduling is very important to the modern manufacturing production. This research addresses a classical scheduling problem — the job shop scheduling problem from the standpoint of both static and dynamic environment. In this study, the job shop scheduling problem (JSSP) is investigated in three aspects: (1) static JSSP that operates under a static scheduling environment with known information about the jobs and machines without unexpected events; (2) semi-dynamic JSSP which is developed based on static JSSP but violating the non-operation disruption assumption due to the presence of uncertainties occurring in the dynamic scheduling process; (3) dynamic online JSSP that operates under a dynamic operating environment in which jobs continuously arrive that are accompanied by unpredictable disruptions, such as machine failures. In the thesis, these three types of JSSP are solved by artificial immune systems (AIS) based algorithms. For static JSSP, a hybrid algorithm is proposed based on clonal selection theory and immune network theory of AIS, and particle swarm optimization (PSO). The clonal selection theory establishes the framework of the hybrid algorithm, while the immune network theory is applied to increase the diversity of antibody set which represents the solution candidates. The proposed framework involves the processes of selection, cloning, hypermutation, memory, and receptor editing. The PSO is designed to optimize the hypermutation process of the antibodies to accelerate the search procedure. This hybrid algorithm is tested with benchmark problems of different sizes and is compared with other methods. The results demonstrate the efficiency of the proposed algorithm, the effectiveness of PSO, and the contribution of long-lasting memory which is one of the key features of AIS. The semi-dynamic JSSP is handled by the rescheduling process. An extended deterministic dendritic cell algorithm (dDCA) is proposed to control the rescheduling process under considerations of the stability and efficiency of the scheduling system. The main role of the extended dDCA is to quantify the negative effect generated from the unexpected disturbances and to determine the best time to trigger the rescheduling process. This algorithm is tested on static benchmark problems with the existence of different kinds of disruptions. The experimental results demonstrate its capability of timely triggering the rescheduling process. The dynamic online JSSP is modeled as a multi-objective optimization problem. In this case, the immune network theory of AIS is hybridized with priority dispatching rules (PDRs) to establish the idiotypic network model for dispatching rules. This idiotypic network model drives the dispatching rule selection process under a dynamic scheduling environment. Based on the job shop situations represented by the antigens, the dispatching rules that perform best under specific conditions are selected as the antibodies of the idiotypic network model. Finally, the thesis proposes a generic framework of JSSP that combines the three different aspects studied in this research with corresponding scheduling strategies. The scheduling framework for a job shop system consists of four collaborating modules and is designed to solve various scheduling situations efficiently under a dynamic operating environment. / published_or_final_version / Industrial and Manufacturing Systems Engineering / Doctoral / Doctor of Philosophy

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

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

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

For the successful deployment of task-achieving multi-robot systems (MRS), the interactions must be coordinated among the robots within the MRS and between the robots and the task environment. There have been a number of impressive experimentally demonstrated coordinated MRS. However it is still of a premature stage for real world applications. This dissertation presents an MRS control scheme using Artificial Immune Systems (AIS). This methodology is firmly grounded in the biological sciences and provides robust performance for the intertwined entities involved in any task-achieving MRS. Based on its formal foundation, it provides a platform to characterize interesting relationships and dependencies among MRS task requirements, individual robot control, capabilities, and the resulting task performance. The work presented in this dissertation is a first of its kind wherein the principles of AIS have been used to model and organize the group behavior of the MRS. This has been presented in the form of a novel algorithm. In addition to the above, generic environments for computer simulation and real experiment have been realized to demonstrate the working of an MRS. These could potentially be used as a test bed to implement other algorithms onto the MRS. The experiment in this research is a bomb disposal task which involves a team of three heterogeneous robots with different sensors and actuators. And the algorithm has been tested practically through computer simulations.

CAPES / Esta tese propõe um novo algoritmo baseado em Sistemas Imunológicos Artificiais (SIA) para classificação hierárquica e multi-label, onde os classificadores gerados são representados na forma de regras SE-ENTÃO. A classificação hierárquica e multi-label é considerada desafiadora uma vez que um exemplo está associado a uma ou mais classes organizadas hierarquicamente, sendo que esta organização estrutural de classes deve ser considerada na construção dos classificadores. A técnica proposta aborda a construção de classificadores hierárquicos locais (onde cada classificador processa apenas exemplos de classes em uma região local da hierarquia) e globais (onde um único classificador processa exemplos de todas as classes ao mesmo tempo). A área de aplicação utilizada para validação desta tese foi a predição de função biológica de proteínas usando termos da ontologia gênica como classes a serem preditas pelo SIA. O desempenho do algoritmo é avaliado experimentalmente para 10 bases de proteínas. Os critérios de avaliação do algoritmo nos experimentos computacionais são a precisão preditiva (taxa de acerto e área da curva precision-recall) e a simplicidade do conhecimento descoberto (medida pelo número de regras e número total de condições nas regras descobertas). Os experimentos computacionais permitem identificar parâmetros e procedimentos que influenciam no desempenho da técnica proposta. Os testes comparativos com outras abordagens mostram que sobre alguns conjuntos de experimentos a abordagem proposta se mostrou superior, enquanto em outros conjuntos não foi possível superar a técnica da literatura usada para comparação. / This thesis proposes a new approach based on Artificial Immune System (AIS) for hierarchical multi-label classification, where the classifiers produced by the system are represented in the form of IF-THEN classification rules. Hierarchical multi-label classification is a challenging problem, because an example is associated with one or more classes organized into a hierarchy and the class hierarchy must be considered in the construction of the classifiers. The proposed method addresses the construction of local hierarchical classifiers (where each classifier processes only examples of classes in a local region of the hierarchy) and global hierarchical classifiers (where a single classifier processes examples of all classes at the same time). The application domain used to validate the proposed methods was the prediction of the biological function of proteins, using terms of the Gene Ontology as classes to be predicted by the AIS. The performance of the algorithm was evaluated in computational experiments with 10 datasets of proteins. The evaluation criteria in these experiments were the predictive accuracy (accuracy rate and the area under the precision-recall curve) and the simplicity of the discovered knowledge (measured by the number of rules and total number of conditions in the discovered rules). The computational experiments allowed the identification of parameter settings and procedures that significantly influence the performance of the proposed method. The experiments comparing the proposed method with other methods have shown that in some datasets the proposed method outperformed other methods, whilst in other datasets it was not possible to outperform other methods proposed in the literature.

Thesis (MScEng (Process Engineering))--University of Stellenbosch, 2006. / The natural immune system is an exceptional pattern recognition system based on memory and learning that is capable of detecting both known and unknown pathogens. Artificial immune systems (AIS) employ some of the functionalities of the natural immune system in detecting change in dynamic process systems. The emerging field of artificial immune systems has enormous potential in the application of fault detection systems in process engineering. This thesis aims to firstly familiarise the reader with the various current methods in the field of fault detection and identification. Secondly, the notion of artificial immune systems is to be introduced and explained. Finally, this thesis aims to investigate the performance of AIS on data gathered from simulated case studies both with and without noise. Three different methods of generating detectors are used to monitor various different processes for anomalous events. These are: (1) Random Generation of detectors, (2) Convex Hulls, (3) The Hypercube Vertex Approach. It is found that random generation provides a reasonable rate of detection, while convex hulls fail to achieve the required objectives. The hypercube vertex method achieved the highest detection rate and lowest false alarm rate in all case studies. The hypercube vertex method originates from this project and is the recommended method for use with all real valued systems, with a small number of variables at least. It is found that, in some cases AIS are capable of perfect classification, where 100% of anomalous events are identified and no false alarms are generated. Noise has, expectedly so, some effect on the detection capability on all case studies. The computational cost of the various methods is compared, which concluded that the hypercube vertex method had a higher cost than other methods researched. This increased computational cost is however not exceeding reasonable confines therefore the hypercube vertex method nonetheless remains the chosen method. The thesis concludes with considering AIS’s performance in the comparative criteria for diagnostic methods. It is found that AIS compare well to current methods and that some of their limitations are indeed solved and their abilities surpassed in certain cases. Recommendations are made to future study in the field of AIS. Further the use of the Hypercube Vertex method is highly recommended in real valued scenarios such as Process Engineering.

CAPES / Este trabalho tem como objetivo principal a proposição de um sistema híbrido baseado em Computação Natural que seja capaz de solucionar, de forma eficiente, diferentes instâncias do problema de Despacho Econômico de Energia Elétrica com efeito de ponto de válvula. Para isso está sendo proposta uma abordagem baseada em um Algoritmo Cultural, o qual tem como espaço populacional um Algoritmo Imunológico Artificial. No espaço de crenças são utilizados quatro tipos de conhecimentos: situacional, normativo, topográfico e histórico. Nos protocolos de comunicação, a função de aceitação e dinâmica e a função de influência e baseada em um Sistema de Inferência Fuzzy, o qual define o possível percentual de aplicação de cada um dos conhecimentos. Para avaliar o paradigma proposto são utilizadas três instâncias do problema do Despacho Econômico de Energia Elétrica. Os resultados mostram que a introdução de um Sistema de Inferência Fuzzy, auxiliando a decisão do tipo de conhecimento a ser aplicado, pode trazer benefícios nos resultados. Na comparação com os resultados reportados na literatura, observa-se que a abordagem, apesar de não ter seus parâmetros otimizados para cada caso, e competitiva com os algoritmos do estado-da-arte. / The main objective of this work is the proposal of a hybrid system based on Natural Computing approaches, which is capable of efficiently solving different instances of the Economic Load Dispatch problem of electrical energy with valve-point effect. For this purpose it is developed a new approach based on Cultural Algorithm, which has as its population space an Artificial Immune System. In the belief space, we use four knowledge types: situational, normative, topographical and historical. In the communication protocols, the acceptance function is dynamic and the principal influence function is based on a Fuzzy Inference System which defines the probable percentage of application of each knowledge type. Three instances of the Economic Load Dispatch with Non-smooth Cost Functions problem are used to evaluate the proposed paradigm. The results show that the introduction of fuzzy systems to support the decision of which type of knowledge must be applied can bring benefits to the obtained results. Although its parameters were not optimized for each case of study, the proposed algorithm performed likewise the state-of-the-art algorithms.