Evolving heuristic rules for dynamic flexible job shop scheduling problem with grey processing time

Abstract

This study addresses the grey dynamic flexible job shop scheduling problem (GDFJSP), in which jobs with uncertain grey-number processing times arrive stochastically and must be dispatched in real time. It aims to develop a genetic programming algorithm that evolves interpretable heuristic dispatching rules while handling stochastic arrivals and iterative grey-time updating efficiently. A memory-guided adaptive feature genetic programming (MGAFGP) algorithm is proposed with a dual-tree encoding for routing and sequencing decisions. The algorithm combines parallel simulation for concurrent fitness evaluation, an elite-memory-guided strategy with separate feature probability vectors for routing and sequencing trees, and a generation-dependent parent selection function. Its performance is evaluated across multiple scenarios defined by different objectives, utilization levels, and due-date tightness conditions. MGAFGP reaches high-quality rules substantially faster than standard GP under the tested scenarios, showing corrected significant advantages during early evolution and reaching GP's full-budget mean performance with a substantially smaller iteration budget. No corrected full-budget comparison favours standard GP. The evolved rules outperform classical heuristic combinations after independent test re-evaluation, while feature-use patterns, symbolic expressions, and tree-complexity statistics show that the resulting dispatching logic remains inspectable. The approach provides a computationally tractable way to discover interpretable dispatching rules for dynamic manufacturing environments with uncertain processing times and limited historical data. By reaching strong rules earlier, MGAFGP can reduce the simulation budget needed for rule evolution, support managerial inspection of scheduling logic and reduce reliance on expert-designed heuristics. The study integrates generalized grey-number processing times into the DFJSP and develops a GP algorithm with separate feature probability adaptation for routing and sequencing. The elite-guided strategy with generation-dependent parent selection provides a mechanism for accelerating convergence in simulation-based GP under grey processing-time uncertainty.