Adaptive, distributed decision support using genetic learning: Application to a production scheduling environment

Scheduling is a crucial activity in a manufacturing system. With traditional approaches, applications of optimization techniques to a mathematical formulation of the problem have proven to be intractable even for many idealized situations; thus, a variety of Artificial Intelligence (AI) approaches have been proposed for effective production scheduling. These techniques too, however, have felt the limitations imposed by the lack of adequate means to acquire the requisite knowledge.; This knowledge acquisition bottleneck is further aggravated by the complexity of the production scheduling environment and the lack of reliable human experts from whom to glean the required knowledge--hence, the need for the development of machine learning schemes to aid in production scheduling.; Genetic algorithms (GAs) provide a stochastic search strategy based on principles of biological evolution and are noted to be specially suited for application to complex, poorly understood search spaces. A framework for utilizing genetic algorithm based learning in typical decentralized factory-floor decision making environments is presented. A high level knowledge representation scheme for modelling the production environment is developed, with facilities for genetic learning within this scheme. Experimental results from job shop simulations considering initial stages of a semiconductor manufacturing line demonstrate the feasibility of the designed approach and provide insights for future enhancements.; A second part of this research focusses on the theoretical analysis of genetic algorithms. Most theoretical studies on GAs consider binary encodings of the search space, and the fundamental principle of minimal alphabets suggests the optimality of binary over higher cardinality representations for genetic processing. A growing number of successful applications using higher level representations, however, present a potential conflict between theory and practice.; This research undertakes a generalization of a recent model of binary GAs, providing a detailed characterization of their search behavior, to higher cardinality alphabets. Walsh functions have been widely used in studying binary GAs, and a generalization of the Walsh matrix terms to consider higher cardinality representations is obtained. This, and other identities derived in the analysis, provide useful results for further studies of nonbinary GAs.