3rd joint congress on fuzzy and intelligent systems , 2009-07-15

Title : ( Comparison of MOGA with Greedy Algirithms in Soft Real- time Task Scheduling on Heterogeneous Processors with Communication Delay )

Authors: N. Sedaghat , H. Tabatabaee-yazdi , Mohammad Reza Akbarzadeh Totonchi ,

Citation: BibTeX | EndNote

Abstract

Scheduling of real-dme tasks on a multiprocessor system is an NP-hard problem. This paper aims to propose an algorithm based, on multi-objective GA (MOGA) for scheduling of static soft real-time tasks on a heterogeneous multi-processor system v/hen the real-world constraints- including the precedence relationship between tasks, different arrival time for each task as well as communication delays between the processors are all considered. The objectives of the proposed scheduling algorithm are maximizing system utilization and minimizing total tardiness. Since these objectives are conflicting, the proposed method applies adaptive v/eight approach (AWA) where some useful information from the current population is utilized to readjust the weights for obtaining a search pressure toward a positive ideal point. In this paper, we also propose two greedy algorithms in which each algorithm aims to optimize a single objective either idle time or communication delay. The performance of the proposed MOGA is compared with the performance of the greedy algorithms on two types of DAGs, sparse and non-sparse. The results demonstrate the. high efficiency of the proposed. MOGA in solving real-world task scheduling problems.

Keywords

, Task Scheduling, Heterogeneous Multiprocessor System, Directed Acyclic Task Graph (DAG), MOGA, Greedy Algorithms
برای دانلود از شناسه و رمز عبور پرتال پویا استفاده کنید.

@inproceedings{paperid:1016188,
author = {N. Sedaghat and H. Tabatabaee-yazdi and Akbarzadeh Totonchi, Mohammad Reza},
title = {Comparison of MOGA with Greedy Algirithms in Soft Real- time Task Scheduling on Heterogeneous Processors with Communication Delay},
booktitle = {3rd joint congress on fuzzy and intelligent systems},
year = {2009},
location = {یزد, IRAN},
keywords = {Task Scheduling; Heterogeneous Multiprocessor System; Directed Acyclic Task Graph (DAG); MOGA; Greedy Algorithms},
}

[Download]

%0 Conference Proceedings
%T Comparison of MOGA with Greedy Algirithms in Soft Real- time Task Scheduling on Heterogeneous Processors with Communication Delay
%A N. Sedaghat
%A H. Tabatabaee-yazdi
%A Akbarzadeh Totonchi, Mohammad Reza
%J 3rd joint congress on fuzzy and intelligent systems
%D 2009

[Download]