Abstract
Artificial immune systems (AIS) offer a promising framework for generating schedules in dynamic manufacturing environments. While AIS-based schedules have demonstrated superior robustness compared to those developed via traditional genetic algorithms (GA), increasing the range of environmental variables (antigens) often leads to a degradation in individual schedule fitness. This research investigates methods to improve system performance by refining the rescheduling process, specifically through the expansion of genetic libraries, while maintaining the inherent robustness of the generated schedules.
Introduction
In industrial manufacturing, the Job Shop Scheduling (JSS) problem involves the allocation of shared resources to perform a collection of tasks over time. In a static environment, optimization is straightforward; however, real-world factories are characterized by stochastic disruptions such as machine failures, fluctuating job arrival times, and shifting priorities. Traditional optimization methods, particularly standard Genetic Algorithms (GAs), tend to produce "brittle" schedules—solutions that are mathematically optimal for a specific snapshot of time but fail catastrophically when conditions change.
This paper explores the application of Artificial Immune Systems (AIS) to address these challenges. By mimicking the adaptive capabilities of biological immune systems, the researchers aim to develop "quality robust" schedules that remain effective despite environmental volatility.
The AIS Framework for Scheduling
The proposed model utilizes an AIS metaphor where scheduling scenarios are treated as antigens (the "threats" or problems) and partial schedules are treated as antibodies (the "solutions").
Antibody Representation and Evolution
Antibodies are represented as sequences of integers corresponding to specific jobs. To evolve these solutions, the researchers utilize the GENESIS package, a standard Genetic Algorithm framework. The evolution process focuses on identifying "building blocks" of schedules that perform well across a variety of scenarios.
Gene Libraries and Diversity
A critical component of this AIS is the use of gene libraries—structured collections of genetic material used to construct antibodies. In previous models, a standard set of five libraries was used. However, a known "Diversity Paradox" exists: as the system is exposed to more antigens to increase its robustness, the specific fitness of the antibodies often decreases. The system becomes a "jack of all trades, master of none."
To counteract this, this research proposes increasing the number of gene libraries from five to ten. Mathematically, this expansion allows for a significantly larger variety of antibody combinations ($c^l$), theoretically providing the system with the "memory" needed to handle complex environments without sacrificing the precision of the schedules.
Methodology
The system operates through a cycle of matching, scoring, and recombination:
- Matching & Scoring: Antibodies are aligned against antigens. A direct match between a job in an antibody and a requirement in an antigen scores 5 points. To allow for flexibility, "wildcards" (placeholders) are used, scoring 1 point.
- Somatic Recombination: Once the most effective antibodies are identified, they undergo recombination and single-job addition to form a complete, functional schedule.
- Rescheduling: Unlike traditional methods that restart the optimization from scratch when a disruption occurs, the AIS approach focuses on adapting the existing "immune memory" to the new scenario, significantly reducing computational overhead.
Evaluation and Benchmarks
The effectiveness of the AIS approach is measured using the Morton & Pentico (1993) benchmark, a standard in the heuristic scheduling community. The research compares the AIS performance against:
- Traditional GAs (Fang): To measure the gain in robustness.
- Previous AIS Models (Hart et al.): To measure the improvement gained by expanding the gene libraries.
Preliminary findings from the foundational literature indicate that even a marginal increase in the antibody population (as low as 0.001%) can yield measurable improvements in environmental adaptation.
Discussion and Future Directions
The core hypothesis of this investigation is that library scaling is the key to overcoming the fitness trade-offs inherent in diverse scheduling environments. By providing a more robust genetic vocabulary, the AIS can maintain high performance across a wider range of antigens.
As this research is ongoing, future work will focus on:
- Empirical Validation: Conducting full-scale experiments to compare the 5-library and 10-library models.
- Efficiency in Rescheduling: Quantifying the time saved by reusing genetic building blocks versus total schedule recalculation.
- Wildcard Optimization: Fine-tuning the balance between wildcard flexibility and schedule specificity to ensure that "robust" does not become "vague."
Conclusion
Artificial Immune Systems represent a significant shift in scheduling philosophy, prioritizing adaptability and robustness over brittle optimality. By expanding the genetic diversity of the system through increased library complexity, it is possible to create manufacturing schedules that are not only efficient but also resilient to the inevitable disruptions of the real world.
Summary updated