TL;DR
This paper explores using Artificial Immune Systems (AIS) to tackle the dynamic challenge of job shop rescheduling in manufacturing environments. The authors propose an AIS model that aims to generate robust schedules that can adapt to unexpected changes, outperforming traditional genetic algorithm approaches in certain scenarios.
What Problem Does This Paper Address?
Manufacturing environments are inherently dynamic. Unexpected events like new job arrivals, machine breakdowns, or changes in job priorities can disrupt pre-existing production schedules. This necessitates efficient rescheduling systems that can quickly adapt to these changes while maintaining schedule quality and robustness. Robustness, in this context, means that a schedule's performance doesn't degrade significantly when minor changes occur in the input data. Traditional scheduling methods can struggle with this dynamic nature, often requiring significant time to generate new schedules or failing to produce resilient ones. This paper investigates how AIS, inspired by the biological immune system's ability to learn and adapt to pathogens, can offer a more effective solution for rescheduling in these unpredictable environments.
Methods
The core of this research lies in applying an Artificial Immune System (AIS) model to job shop rescheduling. The AIS model conceptualizes:
- Antigens: Representing "the sequence of jobs on a particular machine given a particular scenario."
- Antibodies: Representing "a short sequence of jobs that is common to more than one schedule."
The process involves:
- Generating Antigen and Antibody Universes: Both are generated using a genetic algorithm. Antibodies are represented as sequences of integers with a length less than the antigens.
- Matching Antigens and Antibodies: Antibodies are aligned with antigens to calculate a "match score." A perfect match receives a score of five, and a "wild card" match (using an asterisk) receives one. The total match score across all antigens contributes to an antibody's fitness.
- Evolving Antibodies: Antibodies with higher match scores are prioritized and used as building blocks.
- Recombining Antibodies into Schedules: Antibodies are recombined using mechanisms like simple recombination, somatic recombination, and single job addition to form complete schedules.
- Evaluating Immune System Fitness: The average fitness of the antigens is calculated to assess the diversity and robustness of the immune system.
The authors also mention exploring variations in the number of components within gene libraries and the number of libraries used to generate antibodies, drawing inspiration from previous work by Hightower et al. and Hart et al.
Datasets
The paper states that the antigen universes will be generated based on a benchmark problem by Morton & Pentico [9], which is the same benchmark problem used by Hart et al. and Fang in their previous work. No new datasets were introduced.
Key Insights and Ideas
- AIS for Dynamic Environments: The paper highlights the potential of AIS to provide robust solutions for rescheduling in dynamic manufacturing environments, where unexpected changes are common.
- Robustness as a Key Goal: The research emphasizes the importance of generating schedules that are not only good but also resilient to minor variations in input data, a critical factor in unpredictable settings.
- Trade-off in Antigen Range: While increasing the number of antigens can lead to better schedules, it can negatively impact the immune system's performance (fitness). This suggests a delicate balance is needed.
- Antibody Diversity is Crucial: Increasing the number of antibodies, even by a small percentage, can significantly improve the AIS's performance, underscoring the importance of a diverse antibody population.
- Gene Libraries as Building Blocks: The concept of using gene libraries to create diverse antibody components offers a promising avenue for improving the AIS's adaptability.
Key Results
The paper references previous work by Hart et al. [5] which showed that their AIS model produced schedules that were as good as, and more robust than, those generated by a genetic algorithm (Fang [3]). However, they also noted that increasing the number of antigens negatively impacted the immune system's performance. This research aims to improve upon these results by rescheduling the same problem using the same method, with a focus on maintaining robustness. The authors plan to investigate the impact of increasing the number of components within gene libraries and the number of libraries on the AIS's performance, particularly as the number of antigens increases.
Limitations and Future Work
- Performance Degradation with Antigen Range: A key limitation identified from prior work is that while AIS can produce good schedules as the range of antigens increases, it affects the system's overall fitness. This suggests the immune system may not be diverse enough to cope with a wide range of antigens.
- Future Work: The authors plan to investigate the impact of increasing the number of components within gene libraries and the number of libraries on the AIS's performance. They will also compare their results with previous studies to validate their improvements. The ultimate goal is to enhance the robustness of schedules generated by AIS in changing manufacturing environments.
Summary updated