Modern production systems require sophisticated scheduling approaches that simultaneously address machine-task allocation and production planning while accounting for real-world uncertainties. Flexible manufacturing scheduling plays a pivotal role in optimizing production efficiency through shortest processing time sequencing and deadlock prevention. Recognizing the critical impact of uncertainty in manufacturing systems, this study adopts a probabilistic vague set approach, specifically utilizing trapezoidal fuzzy numbers to model process variability through distance-based vague sets. To solve this complex scheduling problem, we develop a hybrid optimization methodology combining an enhanced branch and bound algorithm with genetic algorithm components, validated through robust ranking techniques. The proposed framework is implemented and tested through practical case studies that demonstrate its functionality and analyze the sensitivity of the vague modeling approach. This integrated solution provides decision-makers with powerful tools to quantify operational uncertainties, maintain scheduling flexibility, and effectively respond to dynamic production demands, while the modified hybrid algorithm’s performance is systematically verified through both theoretical analysis and practical validation. The results offer manufacturers a mathematically rigorous yet practical approach to optimize scheduling in uncertain environments.