A hybrid genetic algorithm for the Dual-Resource Constrained Job Shop Scheduling Problem with Mobile Robots

This paper investigates the Dual-Resource Constrained Job Shop Scheduling Problem with Mobile Robots (DRCJSPMR), where machine processing, worker allocation, and robot transportation are tightly coupled. The strong interdependence among these resources makes the problem significantly more challenging than classical job shop scheduling. To address this problem, we first formulate a mixed-integer linear programming (MILP) model, and then develop a topology-driven solution framework that exploits the directed acyclic graph (DAG) structure of scheduling constraints. The problem is reformulated as the search for feasible topological sequences combined with resource assignment decisions, enabling an efficient decoding procedure that generates schedules with earliest feasible start times under precedence constraints. Based on this representation, a hybrid genetic algorithm (HGA) is designed to effectively explore the structured search space, incorporating problem-specific operators and a transport–processing combination strategy to further reduce the search space and improve computational efficiency. Computational experiments on 32 benchmark JSPMR instances and 80 large-scale instances demonstrate that the proposed approach achieves high solution quality and efficiency. Compared with existing methods, the proposed acceleration strategy reduces computational time by approximately 26% and improves the objective value by about 5%, while exhibiting a significantly faster convergence rate.