A robust min–max algorithm for bi-objective USV task assignment using interval time costs under wind-wave-current uncertainty

The practical deployment of unmanned surface vehicle (USV) formations is hindered by environmental uncertainties – especially combined wind, wave, and current effects – that make accurate mission-time prediction infeasible, necessitating robust rather than deterministic task assignment. Existing studies, however, focus mainly on deterministic time costs or dynamic online reallocation, overlooking initial task-allocation optimization under uncertainty. To address this gap, we propose a robust min-max framework for bi-objective task assignment. First, a fast perfect-matching detection (FPMD) algorithm is developed for bipartite graphs. On this basis, an exact fast min–max (FMM) algorithm rapidly identifies schemes minimizing the maximum time cost. Wind-wave-current effects are modeled using an interval travel–time matrix, and the bi-objective FMM (BOFMM) algorithm computes best- and worst-case assignment schemes, balancing expected task time and its variability. Simulations show that the proposed method outperforms benchmarks and provides superior, guaranteed performance in uncertain marine environments.