A novel state transition method for metaheuristic-based scheduling in heterogeneous computing systems

Young Choon Lee*, Albert Y. Zomaya

*Corresponding author for this work

Research output: Contribution to journalArticle

51 Citations (Scopus)

Abstract

Much of the recent literature shows a prevalance in the use of metaheuristics in solving a variety of problems in parallel and distributed computing. This is especially ture for problems that have a combinatorial nature, such as scheduling and load balancing. Despite numerous efforts, task scheduling remains one of the most challenging problems in heterogeneous computing environments. In this paper, we propose a new state transitionscheme, called the Duplication-based State Transition (DST) method specially designed for metaheuristics that can be used for the task scheduling problem in heterogeneous computing environments. State transition in metaheuristics is a key component that takes charge of generating variants of a given state. The DST method produces a new state by first overlapping randomly generated states with the current state and then the resultant state is refined by removing ineffectual tasks. The proposed method is incorporated into three different metaheuristics, GA, SA ans AIS. They are experimentally evaluated and are also compared with existing algorithms. The experimental results confirm DST's promising impact on the performance of metaheuristics.

Original languageEnglish
Pages (from-to)1215-1223
Number of pages9
JournalIEEE Transactions on Parallel and Distributed Systems
Volume19
Issue number9
DOIs
Publication statusPublished - 2008
Externally publishedYes

Fingerprint Dive into the research topics of 'A novel state transition method for metaheuristic-based scheduling in heterogeneous computing systems'. Together they form a unique fingerprint.

Cite this