Artificial Immune Systems Applied to Job Shop Scheduling
An attempt has been made to draw on immunological metaphors to build an Artificial Immune System (AIS) that can be applied to the area of Job Shop Scheduling. The distinctive feature of the AIS is its ability to provide robust solutions. Based on the research undertaken in this thesis to evaluate the existing AIS principles, models and applications, an algorithm applicable to Job Shop Scheduling was built. This algorithm was based on the theories of the Positive Selection Algorithm and the Clonal Selection Principle. A Visual Basic (VB) program was created to test the viability of this algorithm on Job Shop problems. The test comprised of evaluating 10 Job Shop problems with the new AIS model against a Genetic Algorithm (GA) model using the dimensions of optimality and robustness. Extensive testing revealed that the AIS model was slightly less competitive than the GA model in the optimality test but beat the GA in robustness. Another key finding was that the robustness of the model increased as the best solutions produced by the model were closer to the known optimal. Finally, a few areas for future research were identified to improve the optimality of the algorithm, such as, adding the aspect of memory and continuing to keep tabs on the advancements in the field of AIS.
School Location:USA - Ohio
Source Type:Master's Thesis
Keywords:artificial immune systems job shop scheduling
Date of Publication:01/01/2008