Integrated construction scheme and critical path search for scheduling with reentrant and skippable operations in real-world hybrid flowshop

This paper investigates a complex scheduling problem originating from real-world pharmaceutical workshops, characterised by the coexistence of reentrant and skippable operations, which we define as the hybrid flowshop scheduling problem with reentrant and skippable operations (HFSP_RAS). The core challenge lies in effectively handling cross-stage operational dependencies, along with strict machine cleaning and transfer time constraints. To accurately capture these complex industrial constraints and to provide highly effective exact benchmarks, two mathematical models are developed: a Mixed-Integer Linear Programming (MILP) model and a Constraint Programming (CP) model. Considering the demand for real-time computational efficiency in modern manufacturing, we further develop a heuristic approach that integrates a Construction Scheme (CS) and Critical Path Search (CPS), named CS-CPS. Specifically, the CS adopts a dual-job encoding and a two-phase active decoding mechanism to generate high-quality initial schedules. The CPS further improves the solutions by introducing a critical-path-based search and a neighbourhood pruning strategy. This paper compares the CS-CPS with the MILP and CP models, constructive heuristics, and metaheuristics. The results demonstrate that the proposed CS-CPS, while bridging the computational gap of exact solvers, consistently outperforms the compared algorithms in terms of solution quality and stability. Finally, validation based on real-world production data further confirms its superiority.