Integrating Social Choice Theory into Task Scheduling: The Borda Scheduling Heuristic

Abstract Efficient task scheduling is essential in parallel and distributed systems, particularly in heterogeneous computing environments such as cloud computing. Traditional list-based heuristics, for example, HEFT, PEFT, and IPPTS prioritize tasks based on predefined criteria, each providing better results in specific scenarios but constantly performing suboptimally in others. This paper introduces the Borda Scheduling Heuristic (BSH), a novel approach that considers the Borda Count from social choice theory to aggregate task rankings generated by multiple scheduling heuristics. By combining the strengths of individual heuristics, BSH creates a unified and adaptive scheduling strategy. Experimental results on synthetic and real-world workflows demonstrate that BSH consistently outperforms standalone heuristics, particularly for large-scale and complex workflows. These findings highlight the potential of integrating social choice theory into scheduling algorithms to address computational challenges in modern distributed systems.