TANS: A Tolerance-Aware Neighborhood Search Method for Workflow Scheduling with Uncertainties in Cloud Manufacturing

In this paper, we consider the workflow scheduling problem with soft deadlines and fuzzy time uncertainties in cloud manufacturing environments. Workflow tasks in cloud manufacturing often involve uncertain execution and logistics times due to large-scale and geographically distributed resources, creating significant challenges for efficient and reliable scheduling. To address these challenges, we propose the Tolerance-aware Neighborhood Search (TANS) algorithm, which integrates fuzzy time quantization with heuristic neighborhood search techniques. A comprehensive workflow scheduling architecture is established, and multiple neighborhood structures and heuristic search methods are developed to systematically explore feasible solutions. The effectiveness of TANS is verified by extensive experiments and parameter calibrations based on Analysis of Variance (ANOVA). Experimental results indicate that TANS reduces workflow delays by 39% on average compared to state-of-the-art methods, demonstrating high efficiency in scenarios with different numbers of tasks and resources.