PGP: Evolving Compact Dispatching Rules via Adaptive Feature Selection

TL;DR

In the high-stakes world of Dynamic Job Shop Scheduling (DJSSP), Genetic Programming (GP) is a powerhouse for "evolving" scheduling rules. However, it often suffers from the "curse of dimensionality" and rule bloating. This paper introduces PGP, a framework that uses a ternary attribute vector and online probability learning to prune irrelevant features on-the-fly. The result? Rules that are 21% faster to train, significantly more compact, and superior in performance across dynamic shop scenarios.

1. The Bloat Bottleneck: Why Standard GP Struggles

Designing dispatching rules (e.g., "process the shortest job first") manually is a nightmare for complex factories. Automated design via GP helps, but it has a massive flaw: Feature Overload.

GP tries to combine dozens of attributes (Processing Time, Due Dates, Machine Slack) into a mathematical tree. As you add more features to ensure the AI "understands" the shop, the search space explodes. Previous attempts to solve this used a "binary vector" to turn features on or off, but these vectors were often "blind" to whether a feature was even present in the rule's tree structure. This led to "ghost mutations" where the AI modified settings for features that didn't exist in the rule, wasting precious computational cycles.

2. The Innovation: Ternary Representation & Adaptive Learning

The authors' primary insight is that a feature selection mechanism must be strictly coupled to the tree's anatomy.

A New Individual Representation

Instead of just 0 (off) or 1 (on), the proposed PGP uses a ternary state for each terminal $j$:

• 1 (Active): Present in the tree and used in calculation.
• -1 (Inactive): Present in the tree but its value is neutralized (set to 1).
• 0 (Absent): Not present in the tree at all.

Adaptive Feature Selection (The "How")

The algorithm doesn't just randomly flip switches. It learns from the "elite" rules of the previous generation. It calculates an Activation Probability (AP): $A{P}_j=\frac{extActiveCounts}{extActiveCounts+extInactiveCounts}$

If a feature (like "Due Date") appears in the best-performing rules consistently, its $AP$ rises toward 1.0. In the next generation, new rules are biased toward activating that feature. Conversely, irrelevant features are naturally phased out.

Figure 1: The proposed PGP framework integrating the DES model with adaptive attribute vectors.

3. Experimental Showdown: Does it Work?

The authors tested PGP against Standard GP (SGP) and the previous Hybrid GP (HGP) across 24 scenarios varying in shop utilization (80% to 95% load) and due-date tightness.

Key Findings:

1. Computational Efficiency: PGP achieved a 21.8% reduction in training time. By eliminating "terminal noise," the GP engine converges on high-quality rules much faster.
2. Rule Compactness: Tracking the number of active vs. excluded terminals (as seen in the charts below), PGP effectively "distills" the rules.
3. Generalization: Across 24 testing scenarios, PGP won 19 times against HGP.

Figure 2: Training performance showing (a) lower computational time and (b) faster convergence for the PGP approach.

4. Deep Insight: Frequency Analysis is a Lie

One of the most profound takeaways from the paper is the critique of Frequency Analysis. Usually, researchers assume that if a feature appears often in GP trees, it must be important.

The authors proved this wrong. In their "Modified" frequency analysis, they found that features like DD (Due Date) appeared frequently in the tree structures (Original version) but were deactivated by the attribute vector (Modified version). This suggests many features in GP rules are simply "bloat" or "introns" that don't contribute to performance—PGP is the first to systematically identify and silence them.

5. Conclusion & Future Outlook

The PGP approach marks a significant step toward Interpretable AI in Manufacturing. By forcing the GP to justify the presence of every feature through an adaptive probability mask, we move away from "black-box" trees toward compact, human-readable scheduling logic.

Future Challenges: While PGP excels at Total Weighted Tardiness, the next frontier is applying this adaptive selection to multi-objective problems where features might be "useful" for energy saving but "useless" for speed.

Takeaway for Practitioners: When using GP for optimization, don't just dump all your data into the terminal set. Use a structure-aware selection layer like the ternary vector proposed here to keep your models lean and your training times short.