Improved genetic algorithms and list scheduling techniques for independent task scheduling in distributed systems
Ημερομηνία
2007Λέξη-κλειδί
Επιτομή
Given a set of tasks with certain characteristics, e.g., data size, estimated execution time and a set of processing nodes with their own parameters, the goal of task scheduling is to allocate tasks at nodes so that the total makespan is minimized. The problem has been studied under various assumptions concerning task and node parameters with the resulting problem statements usually being NP-complete. List scheduling (LS) heuristics such as MaxMin and MinMin together with genetic algorithms (GAs) were applied in the past to find solutions. In this paper we investigate new heuristics for both the LS and the GA paradigm with the specific aim of improving the performance of the standard algorithms when task computations involve large data transfers. Experimental results under various environment assumptions illustrate the merits of the new algorithms. © 2007 IEEE.
Collections
Related items
Showing items related by title, author, creator and subject.
-
Online Algorithms for the Interval Scheduling Problem in the Cloud: Affinity Pair Threshold Based Approaches
Oikonomou P., Tziritas N., Loukopoulos T., Theodoropoulos G., Hanai M., Khan S.U. (2022)In the interval scheduling problem, jobs have known start and end times (referred to as job intervals) and must be assigned to processing nodes for their whole duration. Although the problem originally stems from the ... -
Control and optimization meet the smart power grid: Scheduling of power demands for optimal energy management
Koutsopoulos, I.; Tassiulas, L. (2012)The smart power grid harnesses information and communication technologies to enhance reliability and enforce sensible use of energy through effective management of demand load. We envision a scenario with real-time ... -
Bin Packing Heuristics for the Multiple Workflow Scheduling Problem
Pappas N., Oikonomou P., Tziritas N., Kolomvatsos K., Loukopoulos T. (2021)In the multiple workflow scheduling problem a set of workflows has to be scheduled concurrently onto system's available resources. Workflows exhibit different characteristics e.g., topological structure, size and ...