Jul 2026· Grey Systems Theory and Application· pp. 1-25· 0 citations· 44 references
TL;DR
A memory-guided adaptive feature genetic programming algorithm that evolves interpretable heuristic dispatching rules while handling stochastic arrivals and iterative grey-time updating efficiently and can reduce the simulation budget needed for rule evolution, support managerial inspection of scheduling logic and reduce reliance on expert-designed heuristics.
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.
The unrelated parallel machines scheduling problem is an important and challenging problem with significant industrial relevance. This paper addresses a specific variant involving precedence constraints between jobs and the requirement of additional resources for job execution. The problem is NP-hard, and practical solution approaches are therefore predominantly heuristic. In dynamic scheduling environments, dispatching rules (DRs) represent one of the most effective and widely used heuristic approaches. A DR consists of a schedule generation scheme (SGS) and a priority function (PF). The manual design of high-quality DRs is difficult and time-consuming, making the problem well suited for hyper-heuristic and evolutionary approaches. In this work, genetic programming (GP) is employed to automatically evolve the PF component of DRs. Additionally, several problem-specific SGSs are proposed and evaluated. The evolved DRs are compared against adapted state-of-the-art DRs from the literature. The results show that the proposed GP-based approach enables the automated generation of high-quality DRs, outperforming manually designed heuristics for the considered problem.
Josipa Sabljo, Mateja Đumić, M. Đurasević· Annual Conference on Genetic...· 0 citations
The Job Shop Scheduling Problem (JSP) is a core decision-making issue for improving production efficiency in discrete manufacturing industries. Traditional genetic algorithms (GAs) used to solve JSP suffer from bottlenecks such as a high number of invalid solutions and difficulty in balancing solution accuracy and convergence speed. To address large-scale JSP under dynamic machine fault disturbances, this study proposes an improved genetic algorithm integrating hybrid encoding and customized operators. Specifically, a hybrid encoding strategy combining job sequences and machine sequences is adopted to naturally satisfy the process and equipment constraints of JSP. The evolutionary process is optimized using tournament selection, Position-based Order Crossover (POX), and mutation within the valid domain, while a fault identification and machine switching mechanism is integrated to adapt to dynamic disturbance scenarios. Experimental results show that the improved algorithm achieves an optimal Makespan value of 190 in dynamic disturbance scenarios and exhibits strong robustness, providing an efficient and feasible solution for job shop scheduling in complex production environments.
Jianguo Du, Chengkun Li, Zijie Tang· ITM Web of Conferences· 0 citations
The hybrid flow shop scheduling problem (HFSP) with unrelated parallel machines (UPMs), sequence-dependent setup times (SDSTs), and inter-stage transportation times has recently emerged as a prominent research topic. To address this scheduling problem with the objective of minimizing the maximum completion time (makespan), this paper first formulates a mixed-integer linear programming (MILP) model based on the machine-position modeling idea. Exact solution analyses on small-scale instances reveal that the strong coupling effect of these triple constraints concentrates the computational bottleneck on the time-consuming proof of optimality, thereby underscoring the strongly NP-hard nature of the investigated HFSP-SDST-T problem. To efficiently solve large-scale instances, a novel adaptive co-evolutionary memetic algorithm (ACMA) is proposed. ACMA adopts a dual-population co-evolutionary framework, where a customized genetic algorithm (GA) is designed for global exploration and a Lévy flight-enhanced particle swarm optimization (PSO) improves local search capability. To dynamically balance exploration and exploitation, a Dynamic Role Allocation (DRA) mechanism is developed to adaptively reassign individuals between the two populations according to their evolutionary states. Moreover, a progressive two-stage memetic enhancement strategy is proposed to overcome premature convergence by sequentially activating deep variable neighborhood search (VNS) and a catastrophe-based diversification strategy, enabling adaptive responses to different stagnation levels. Extensive experiments, including ablation studies, comparisons with benchmark algorithms, and computational complexity analysis, are conducted on small- and large-scale instances. The results show that ACMA consistently obtains the exact optimal solutions obtained from the MILP model for small-scale instances and achieves competitive performance on large-scale complex instances. Furthermore, Wilcoxon signed-rank tests confirm the statistical significance of the performance differences, supporting the reliability of the experimental results.
The job sequencing and tool switching problem with non-identical parallel machines (SSP-NPM) is a challenging combinatorial optimization problem that arises in flexible manufacturing systems. It jointly involves job assignment, sequencing, and tool management decisions under limited magazine capacities to minimize the makespan. In this paper, we first propose an improved position-based MILP (IPM). This model builds upon the one presented by [1], offering a more compact representation of completion times and is strengthened by static improvement mechanisms inspired by [2]. We then develop a genetic algorithm (GA) using an explicit permutation-assignment encoding and a tool-switch evaluator. Computational experiments were conducted on benchmark instances from the literature. Results show that the IPM solves 58.43% of instances to optimality, outperforming existing formulations, while on medium-size large-scale instances, the proposed GA converges about 50% faster than existing metaheuristic approaches.
Khaled Khayati, K. Salem, Benoit Lardeux et al.· International Conference on...· 0 citations
This paper addresses the Job-Shop Scheduling Problem in dynamic semiconductor manufacturing environments by proposing a decentralized, bottom-up Artificial Bee Colony (ABC) scheduling algorithm. Machines and lots are modeled as autonomous agents whose local interactions give rise to system-level scheduling behavior. Alongside classical scheduling objectives, the proposed approach focuses on regulating production dynamics by maintaining sufficient diversity in machine queues, formalized through entropy-based measures. Bottlenecks are treated not only as a consequence of static capacity constraints relative to work in progress, but also as emergent effects of short-term demand concentration, where multiple lots converge toward the same resources within limited time horizons. To manage these effects, a fitness formulation is introduced that promotes balanced queue states through local decision-making. Scheduling foresight is incorporated via a Look-Ahead Window, while uncertainty in distant future routing is accounted for using a decay factor, jointly enabling adaptive prioritization under bounded computational effort. Simulation-based evaluation across fabrication scenarios of increasing scale shows that the method achieves modest improvements in Flow Factor and Tardiness, while inducing an expected trade-off in Makespan under higher load conditions. More importantly, analysis of queue-level dynamics reveals more regular behavior in the evaluated scenarios, with reduced fluctuations in queue lengths, batch waiting, and minimum queue entropy over time. These results indicate that the proposed ABC-based approach can improve observed predictability at the queue level, offering a complementary perspective to performance-driven scheduling in highly dynamic environments.
The Flexible Job Shop Scheduling Problem with Worker constraints (FJSSP-W) is a challenging optimization problem that simultaneously coordinates machine assignment, worker allocation, and operation sequencing. This paper proposes a Late Acceptance Hill Climbing (LAHC) metaheuristic to address the FJSSP-W. LAHC uses a single-state trajectory with a history-based acceptance criterion, enabling straightforward parameter tuning and interpretation. Our implementation explores a neighborhood structure comprising machine and worker reassignments, as well as job-sequence permutations, while using a secondary objective of workload balance to break ties in makespan values. Experimental results on the competition's benchmark demonstrate that the proposed LAHC approach is a promising algorithm to address the problem.
Eduard Iorga, Ben Ertugrul, Alexandros Tzanetos· Proceedings of the Genetic a...· 0 citations