Min-heap-based scheduling algorithm: an approximation algorithm for homogeneous and heterogeneous distributed systems. Issue 1 (2nd January 2016)

• Record Type: Journal Article
• Authors: Gabriel, Paulo H.R.; Albertini, Marcelo K.; Castelo, Antonio; de Mello, Rodrigo F.
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 31:Issue 1(2016)
• Page Start: 64
• Page End: 84
• Publication Date: 2016-01-02
• Subjects: process scheduling -- distributed systems -- approximation algorithms -- system-oriented scheduling; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2015.1009067
• Languages: English
• ISSNs: 1744-5760

Abstract

Abstract : One of the most important issues in the design of distributed systems is process scheduling, which maps applications to resources in an attempt to reduce the application execution time or maximise resource utilisation. The complexity involved in finding good scheduling solutions has motivated the design of several heuristics and approximation algorithms. Although heuristics aim at finding good solutions within acceptable time constraints, they do not guarantee solution quality. On the other hand, approximation-based algorithms provide optimal solution bounds, but they are usually designed to address simple scenarios. In an attempt to combine the best of both algorithmic approaches, this paper proposes the min-heap-based scheduling algorithm (MHSA), which finds solutions for homogeneous and heterogeneous distributed environments within acceptable time constraints and optimal solution bounds. MHSA considers applications that can be bag-of-tasks or which communicate among each other. Such solutions minimise the application execution time and maximise resource utilisation; therefore, MHSA is a system-oriented scheduling algorithm. Results confirm that MHSA provides better solutions than schedulers such as Random, Round-Robin, Workload-Queue and List-Scheduling. In addition, MHSA provides an -approximation ratio for reaching optimal solution bounds.