Modeling and multi-objective evolutionary solution for coupled spatio-temporal crowdsourced processing task scheduling
TL;DR
A hybrid evolutionary algorithm (NS-RIME) that integrates the Frost-Inspired Mechanism for Exploration (RIME) with the Non-dominated Sorting Genetic Algorithm II (NSGA-II) and embeds RIME’s soft-frost search and hard-frost penetration strategies to enhance global exploration and local exploitation.
Abstract
In crowdsourced manufacturing (CSM), product processing tasks are decomposed and allocated to geographically distributed resources with discrete availability, forming a spatio-temporal task scheduling problem that integrates both processing and logistics. This problem encompasses multiple constraints, including operation precedence, resource capacities, and time windows, while optimizing conflicting objectives such as minimizing service completion time and total service cost. Here, we formulate a spatio-temporal CSM and logistics service task scheduling model to capture these complexities. To efficiently solve this multi-objective combinatorial problem, we propose a hybrid evolutionary algorithm (NS-RIME) that integrates the Frost-Inspired Mechanism for Exploration (RIME) with the Non-dominated Sorting Genetic Algorithm II (NSGA-II). The algorithm employs a dual-layer hybrid encoding with proactive decoding to ensure feasible schedules, embeds RIME’s soft-frost search and hard-frost penetration strategies to enhance global exploration and local exploitation, and incorporates a variable neighborhood search to improve elite solution quality. Comparative experiments on 15 instances of varying scale demonstrate that NS-RIME consistently outperforms NSGA-II, SPEA2, MOACO, and MOPSO in both Inverted Generational Distance and Hypervolume, confirming its superiority in solution accuracy and Pareto front diversity.