Improved Hungarian algorithm–based task scheduling optimization strategy for remote sensing big data processing

Abstract

With the development of remote sensing technology and computing science, remote sensing data present typical big data characteristics. The rapid development of remote sensing big data has brought a large number of data processing tasks, which bring huge challenges to computing. Distributed computing is the primary means to process remote sensing big data, and task scheduling plays a key role in this process. This study analyzes the characteristics of batch processing of remote sensing big data. This paper uses the Hungarian algorithm as a basis for proposing a novel strategy for task assignment optimization of remote sensing big data batch workflow, called optimal sequence dynamic assignment algorithm, which is applicable to heterogeneously distributed computing environments. This strategy has two core contents: the improved Hungarian algorithm model and the multi-level optimal assignment task queue mechanism. Moreover, the strategy solves the dependency, mismatch, and computational resource idleness problems in the optimal scheduling of remote sensing batch processing tasks. The proposed strategy likewise effectively improves data processing efficiency without increasing computer hardware resources and without optimizing the computational algorithm. We experimented with the aerosol optical depth retrieval algorithm workflow using this strategy. Compared with the processing before optimization, the makespan of the proposed method was shortened by at least 20%. Compared with popular scheduling algorithm, the proposed method has evident competitiveness in acceleration effect and large-scale task scheduling.

Keywords

• Workflow
• Hungarian algorithm
• optimal assignment
• remote sensing big data
• large-scale task