Integrating Petri net heuristics within MILP for optimizing energy-efficient scheduling of flexible manufacturing systems

Abstract

Flexible Manufacturing Systems (FMSs) increasingly need to reconcile flexibility, high productivity and energy efficiency. This paper addresses the energy-efficient scheduling of routing-flexible FMSs with multiple job instances, shared machines and route-level Work-in-Process (WIP) constraints, where makespan and production energy consumption are jointly optimized. A Petri Net–Mixed-Integer Linear Programming (PN–MILP) hybrid framework is proposed, in which a Timed and Energy-aware Transition Petri Net (TETPN) models the discrete-event scheduling logic of the FMS, including routing alternatives, operation precedence, machine sharing and route-level WIP limits. Based on the TETPN representation and simulation, feasible timed schedules are generated by a Hybrid Filtered Beam Search Algorithm (HFBSA) and its Randomized Beam-Retention extension (RBR-HFBSA). These schedules are then translated into feasible warm starts for a time-indexed MILP formulation, which enforces the same scheduling constraints in optimization form and refines the final solution through exact search. The resulting PN–MILP hybrid schemes, HFBSA+MILP and RBR-HFBSA+MILP, therefore, connect PN-based feasible-schedule generation with MILP-based exact optimization. Computational experiments on a 60-scenario benchmark show that PN-based warm starts substantially improve the robustness of the exact solution process relative to solving the MILP model without any PN-derived warm start, particularly in large-scale and unbalanced production settings, by increasing the probability of attaining a feasible incumbent within the imposed time limit. The proposed framework thus enables more reliable and effective exact optimization for complex routing-flexible FMS scheduling problems.