Learning from Random Solutions: Data-Mining-Guided Heuristic Search for Permutation Flow Shop Scheduling

The permutation flow shop scheduling problem (PFSP) is a fundamental scheduling problem for which heuristic methods are widely used because of the rapidly growing solution space. This study investigates whether solution populations generated entirely from random permutations contain structural information that can improve heuristic search. For 140 Taillard and VFR instances, five independent random pools were generated per problem, and pairwise-precedence (P) and relative-position-region (R) information was extracted from Elite and Poor groups using Elite-only and Contrast mining. The mined information was integrated into five NEH-based constructive and reinsertion heuristics while preserving makespan as the primary decision criterion. Mean-of-Five improvements averaged 0.418% for Elite-only and 0.409% for Contrast, with larger gains when the information was used to guide reinsertion search (0.738% and 0.722%) than when restricted to Cmax tie-breaking (0.205% and 0.200%). Ablation and five-pool analyses showed complementary P/R contributions and high structural repeatability. QIG and Q-NEH achieved better absolute solution quality under equal-budget comparison, while offline mining required 0.28–230.18 s. Overall, the results show that random-pool mining can provide interpretable, reproducible, and useful guidance for heuristic search, with exploratory evidence that the same structural information can also benefit stronger methods such as QIG and Q-NEH when introduced through suitably matched interfaces.