Investigating a Hybrid Metaheuristic for Job Shop Rescheduling

Salwani Abdullah, Uwe Aickelin, Edmund K. Burke, Aniza Mohamed Din, Rong QuACAL 2007 · DOI · OpenReview

TL;DR

This paper explores a hybrid approach to job shop rescheduling by combining artificial immune systems (AIS) with local search algorithms like simulated annealing and the great deluge algorithm. The goal is to generate robust partial schedules that can quickly adapt to unexpected disruptions in manufacturing environments, improving upon existing AIS methods.

What Problem Does This Paper Address?

Manufacturing environments are dynamic, and unexpected events like job arrivals can disrupt production schedules. Efficiently rescheduling to minimize delays and maintain flow is crucial. Traditional job shop scheduling problems are well-studied, but adapting to these real-time changes, known as rescheduling, presents a significant challenge. This paper focuses on developing methods to quickly generate diverse and effective partial schedules that can serve as replacements for disrupted segments of an existing schedule, thereby enabling rapid adaptation to unforeseen circumstances.

Methods

The paper proposes a two-phase approach:

  • Phase I: Artificial Immune System (AIS) for Antibody Generation: This phase uses an AIS model inspired by the human immune system to generate "antibodies," which are partial schedules. These antibodies are evolved using a genetic algorithm. The core idea is to create building blocks of schedules that can be used to construct backup solutions when disturbances occur. The process involves creating an "antigen universe" (a collection of complete schedules), gene libraries, and then evolving antibody populations based on their fitness (how well they match antigens).
  • Phase II: Hybridization with Local Search: In this phase, the best antibodies generated in Phase I are used as initial solutions for local search algorithms: Simulated Annealing (SA) and the Great Deluge (GD) algorithm. The aim is to further improve the fitness of these partial schedules. Two operators are used for generating new antibodies: changing one job or swapping two jobs.

Datasets

The research utilizes a benchmark problem by Morton and Pentico [22] for job shop scheduling. Specifically, it uses 15 jobs assigned to five machines. Ten test scenarios were created by mutating job arrival dates. The schedules generated from these scenarios form the "antigen universe" for the study.

Key Insights and Ideas

  • AIS as a Generator of Diverse Partial Schedules: The study demonstrates that AIS can effectively generate a diverse set of partial schedules (antibodies) that can be used as building blocks for rescheduling.
  • Hybridization Improves Fitness, Not Necessarily Coverage: While combining AIS with SA and GD improved the "fitness" of the generated antibodies (meaning they better matched the target scenarios), it did not necessarily improve the overall "coverage" of the antigen universe compared to the AIS alone. This suggests that the hybrid methods might produce more specific antibodies that are highly optimized for certain scenarios but might not be as broadly applicable.
  • Trade-off between Specificity and Coverage: The results hint at a potential trade-off. More specific antibodies (potentially generated by hybrid methods) might be better for certain situations, but a broader set of more general antibodies (potentially from AIS alone) might offer better overall coverage for a wider range of potential disruptions.
  • Efficiency of Hybrid Methods: The hybrid approaches (AIS+SA and AIS+GD) were found to be computationally efficient, with final solution generation times being very short.

Key Results

  • The hybrid search algorithms (AIS+SA and AIS+GD) showed an improvement in the fitness of antibodies, increasing by over 28% compared to the AIS alone in certain scenarios.
  • However, the coverage of the antigen universe (measured by the average number of unmatched antigens) did not consistently improve with the hybrid methods, and in some cases, it decreased.
  • The study generated three types of antibody populations (with varying degrees of duplication) to assess their impact on coverage, finding that the type of population did not drastically alter the outcomes.

Limitations and Future Work

  • Limited Scope of Hybridization: The paper notes that the hybrid algorithms did not significantly improve coverage compared to the AIS alone, except for specific combinations of antigens and matching thresholds.
  • Specificity vs. Coverage Trade-off: The authors suggest that the hybrid models might produce more specific antibodies, which could lead to better fitness for certain scenarios but potentially less overall coverage.
  • Future Work: The authors plan to use these results as a platform for future work on "hyper heuristics," where antibodies might represent sequences of low-level heuristics. They also mention the possibility of using a larger problem size in future research.

Summary updated

Abstract

Previous research has shown that artificial immune systems can be used to produce robust schedules in a manufacturing environment. The main goal is to develop building blocks (antibodies) of partial schedules that can be used to construct backup solutions (antigens) when disturbances occur during production. The building blocks are created based upon underpinning ideas from artificial immune systems and evolved using a genetic algorithm (Phase I). Each partial schedule (antibody) is assigned a fitness value and the best partial schedules are selected to be converted into complete schedules (antigens). We further investigate whether simulated annealing and the great deluge algorithm can improve the results when hybridised with our artificial immune system (Phase II). We use ten fixed solutions as our target and measure how well we cover these specific scenarios.
BibTeX
@inproceedings{abdullah2007investigating,
  author = {Salwani Abdullah and Uwe Aickelin and Edmund K. Burke and Aniza Mohamed Din and Rong Qu},
  title = {{Investigating a Hybrid Metaheuristic for Job Shop Rescheduling}},
  booktitle = {ACAL},
  year = {2007},
  doi = {10.2139/ssrn.2831302},
}
Figure