Investigating a Hybrid Metaheuristic For Job Shop Rescheduling

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

TL;DR

This paper explores a hybrid Artificial Immune System (AIS) approach to tackle job shop rescheduling by evolving "antibodies"—robust partial schedules—that can act as building blocks for new solutions when production is disrupted. By hybridizing the AIS with local search metaheuristics like Simulated Annealing and the Great Deluge algorithm, the researchers achieved a fitness improvement of over 28% for these scheduling components.

What Problem Does This Paper Address?

In manufacturing, a "perfect" schedule rarely survives first contact with reality. Job shop scheduling—the task of assigning $n$ jobs to $m$ machines—is notoriously difficult, and unexpected changes like early or late job arrivals can throw an entire factory into chaos.

Traditional methods often involve rescheduling from scratch, which is computationally expensive and disruptive. The authors of this paper propose a more flexible approach: instead of finding one rigid schedule, they aim to generate a library of robust "building blocks" (partial schedules). These blocks can be quickly swapped in to patch a schedule when disturbances occur, maintaining production flow with minimal interruption.

Methods

The researchers utilize an Artificial Immune System (AIS) framework, drawing an analogy between biological immunity and manufacturing robustness:

  • Antigens: These represent the "threats" or scenarios—specifically, ten complete schedules based on different job arrival dates.
  • Antibodies: These are the "solutions"—partial schedules (sequences of 5 jobs) that the system tries to match to the antigens.

The study is divided into two phases:

  1. Phase I (Evolution): A Genetic Algorithm (GA) evolves a population of antibodies. These antibodies are constructed using a modular design from "gene libraries" (see Figure 1). The system evaluates how well an antibody matches an antigen by aligning them gene-by-gene to calculate a matching score (see Figure 2).
  2. Phase II (Hybridization): The best antibodies from Phase I are refined using two local search metaheuristics: Simulated Annealing (SA) and the Great Deluge (GD) algorithm. These algorithms tweak the partial schedules to see if their fitness (how well they match the target scenarios) can be further improved.

![Fig.

  1. Constructing an antibody from gene libraries](/figures/art_39d51a38a8564511bbb2ebf74df2d512)

![Fig.

  1. The process of matching an antibody with an antigen by aligning the antibody at every possible alignment position](/figures/art_b7c8aed768d14c59bbc9f13ee5ebab5d)

Datasets

The study uses a benchmark job shop problem known as jb11 (from Morton and Pentico), consisting of 15 jobs and 5 machines.

  • Antigen Universe: Ten test scenarios were created by mutating job arrival dates.
  • Baseline: The results are compared against a seminal AIS scheduling paper by Hart and Ross [17].

Key Insights and Ideas

  • Fitness vs. Coverage: A fascinating takeaway is the trade-off between how "good" a partial schedule is (fitness) and how many different scenarios it can handle (coverage). While the hybrid search (Phase II) significantly boosted the fitness of individual antibodies, it didn't necessarily improve their coverage. In some cases, the hybrid models produced antibodies that were too specific to one scenario, making them less useful as general-purpose building blocks.
  • Diversity Matters: The authors tested three types of antibody populations (Type A, B, and C) to see how duplication affects the system. They found that exposing antibodies to more antigens generally increases their fitness and recognition capabilities.
  • Efficiency: The entire process is remarkably fast. Generating the initial population takes less than a minute, and the hybrid refinement phase adds only another minute or less, making it a viable approach for real-time rescheduling.

Key Results

The researchers successfully improved upon the baseline established by Hart and Ross.

  • Fitness Gains: When hybridizing the AIS with either Simulated Annealing or the Great Deluge algorithm, the fitness of the antibody populations increased by more than 28% compared to using the AIS alone (for a single antigen sample).
  • Coverage Trends: The modified AIS model showed a consistent trend where the number of unmatched antigens decreased as the antibody sample size increased, outperforming the baseline trends shown in Table 1.
Table 1. Average number of antigens (out of a possible 10) not matched by any antibody as generated by Hart and Ross [17]

Limitations and Future Work

The primary limitation is the scale of the problem; the researchers used a relatively small benchmark (15 jobs, 5 machines) to prove the concept. While the results are promising, the authors acknowledge that larger, more complex job shop environments need to be tested.

Future work aims to apply these findings to hyper-heuristics, where the evolved antibodies would represent sequences of low-level heuristics rather than just job sequences. This could lead to even more flexible and intelligent rescheduling systems.

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
@misc{abdullah2008investigating,
  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}},
  year = {2008},
  eprint = {0803.1728},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/0803.1728},
}
Figure