Contention Awareness In Task Scheduling Using Tabu Search

A task scheduling problem is to arrange the tasks of an application on computing resources so as to achieve minimum schedule length. Many effective scheduling algorithms have been proposed, but most of them assumes that network is fully connected and contention free. In order to make this problem mo...

Full description

Saved in:
Bibliographic Details
Main Authors: Shanmugapriya, R., Padmavathi, S., Shalinie, S.M.
Format: Conference Proceeding
Language:English
Subjects:
Computer science
Delay
Dynamic scheduling
Educational institutions
Environmentally friendly manufacturing techniques
link contention
Migration Scheduling Algorithm (MSA) with tabu search
optimal schedule
Optimal scheduling
Parallel programming
Processor scheduling
Scheduling algorithm
Task scheduling
Time measurement
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A task scheduling problem is to arrange the tasks of an application on computing resources so as to achieve minimum schedule length. Many effective scheduling algorithms have been proposed, but most of them assumes that network is fully connected and contention free. In order to make this problem more practical, the link contention constraints are considered. In this paper we proposed an effective and efficient scheduling algorithm called Migration scheduling algorithm (MSA) based on Tabu search extended from list scheduling algorithm. The edges among the tasks are also scheduled by treating communication links between the processors as resources. To present the effectiveness of the proposed algorithm, we compared it with the Dynamic level scheduling algorithm (DLS) and List scheduling without contention. The proposed algorithm has admissible time complexity and suitable for regular as well as irregular task graph structures. Experimental results show that algorithm with tabu search produce optimal schedules in reasonable time.
DOI:10.1109/IADCC.2009.4809020