Investigations On Evolutionary Computation For Scheduling Problems In Uncertain Manufacturing Environments

Scheduling under uncertainty has become one active and popular research area from the viewpoints of both academia and industry. To improve the adaptability of current Evolutionary Computation methods toward uncertain scheduling problems, a generic Evolutionary Computation framework together with its various algorithms has been investigated thoroughly and systematically, in which case-based reasoning (CBR) and fitness landscape have served as the most important components to adapt to new environments by reuse of previous knowledge. Firstly, based on DNA inexact matching ideas, a 2-level similarity is defined to reflect the routing characteristics of Job-shop scheduling problems. CBR mechanisms and the classical genetic algorithms/immune algorithms (GAs/IAs) are then fused to form certain genetic learning methods. These methods have shown their effectiveness when tested in deterministic or dynamic Job-shop scheduling environments.Secondly, a new fitness-distance analyzing (FDA) method has been proposed to measure the similarity between two fitness landscapes. Then, the autocorrelation function of the random walk series on certain fitness landscape, {r(s)}, are found to be able to characterize the landscape to some extent. With the help of {r(s)}, the fitness landscapes of typical scheduling problems are analyzed in an innovative way.Further, the scheduling cases are redefined where each case corresponds to the pair of fitness landscapes and their optima. One new evolutionary and learning framework, CFL-EC, is then proposed to solve uncertain dynamic problems. The fitness landscapes of fuzzy scheduling problems are also tested and analyzed with the result that there existed certain correlation between fuzzy problems and their crisp samples. This result immediately leads to a new evolutionary algorithm, namely FCFL-EC, which uses the sample instances to predict fuzzy landscapes.Finally, a Genetic Programming system is proposed to learn effective predictive scheduling heuristics subject stochastic machine failures. When applied to various typical scheduling problems and real dyeing&weaving processing instances, the above evolutionary computation framework and algorithms can adapt to the new environment generally. Hence, our innovative research work opens a new window for further investigation on scheduling problems under uncertainty.