DAG Scheduling on Cluster of Workstations Using Hybrid Particle Swarm Optimization

Task Scheduling is one of the core steps to effectively exploit the capabilities of resources in cluster computing environment. Scheduling of applications modeled by Directed Acyclic Graph (DAG) is a key issue in this type of environment. The task scheduling problem has been shown to be a NP Complet...

Full description

Saved in:
Bibliographic Details
Main Authors: Padmavathi, S., Suguna, M., Shalinie, S.M.
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
DAG Scheduling
Optimal scheduling
Particle swarm optimization
Processor scheduling
Program processors
Schedules
Scheduling
Tabu Search
Task Scheduling
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page 389
container_issue
container_start_page 384
container_title
container_volume
creator Padmavathi, S.
Suguna, M.
Shalinie, S.M.
description Task Scheduling is one of the core steps to effectively exploit the capabilities of resources in cluster computing environment. Scheduling of applications modeled by Directed Acyclic Graph (DAG) is a key issue in this type of environment. The task scheduling problem has been shown to be a NP Complete in general as well as in several restricted cases. This paper presents a List Scheduling algorithm using Particle Swarm Optimization (PSO) based on the concept of Tabu Search (TS). This approach combines the excellence of both PSO and TS. This is different from the existing methods since the procedure adaptively incorporates information about Tabu lists into PSO algorithm. The proposed algorithm outperforms other algorithms in the aspects of performance and scalability. The experimental results manifest that the proposed hybrid method is effective and efficient in finding near optimal schedule length.
doi_str_mv 10.1109/ICETET.2008.245
format conference_proceeding
fullrecord <record><control><sourceid>ieee_CHZPO</sourceid><recordid>TN_cdi_ieee_primary_4579929</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>4579929</ieee_id><sourcerecordid>4579929</sourcerecordid><originalsourceid>FETCH-LOGICAL-i90t-c7f73a4637cbbc678264d1d13592d055666f1acac87dfb0896cdccd5dad1bc193</originalsourceid><addsrcrecordid>eNo9j8tKAzEARaNYsK1du3CTH5gx70yWZewLChU74rJkkoxG51GSKVK_3lbF1b2Lw-FeAG4xSjFG6n6Vz4pZkRKEspQwfgFGSArFKRGSX4IhwVwmiGX86r9LOQCjM6-IwJRdg0mM7wghojDlGRuCp4fpAm7Nm7OH2revsGthXh9i7wLsKvjShY_Y6953bYTP8Qwsj2XwFj7q0HtTO7j91KGBm33vG__1Q96AQaXr6CZ_OQbFfFbky2S9Wazy6TrxCvWJkZWkmgkqTVkaITMimMX2NEsRizgXQlRYG20yaavydEAYa4zlVltcGqzoGNz9ar1zbrcPvtHhuGNcKkUU_QYgjFQ4</addsrcrecordid><sourcetype>Publisher</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype></control><display><type>conference_proceeding</type><title>DAG Scheduling on Cluster of Workstations Using Hybrid Particle Swarm Optimization</title><source>IEEE Xplore All Conference Series</source><creator>Padmavathi, S. ; Suguna, M. ; Shalinie, S.M.</creator><creatorcontrib>Padmavathi, S. ; Suguna, M. ; Shalinie, S.M.</creatorcontrib><description>Task Scheduling is one of the core steps to effectively exploit the capabilities of resources in cluster computing environment. Scheduling of applications modeled by Directed Acyclic Graph (DAG) is a key issue in this type of environment. The task scheduling problem has been shown to be a NP Complete in general as well as in several restricted cases. This paper presents a List Scheduling algorithm using Particle Swarm Optimization (PSO) based on the concept of Tabu Search (TS). This approach combines the excellence of both PSO and TS. This is different from the existing methods since the procedure adaptively incorporates information about Tabu lists into PSO algorithm. The proposed algorithm outperforms other algorithms in the aspects of performance and scalability. The experimental results manifest that the proposed hybrid method is effective and efficient in finding near optimal schedule length.</description><identifier>ISSN: 2157-0477</identifier><identifier>EISSN: 2157-0485</identifier><identifier>EISBN: 0769532675</identifier><identifier>EISBN: 9780769532677</identifier><identifier>DOI: 10.1109/ICETET.2008.245</identifier><identifier>LCCN: 2008926134</identifier><language>eng</language><publisher>IEEE</publisher><subject>Algorithm design and analysis ; DAG Scheduling ; Optimal scheduling ; Particle swarm optimization ; Processor scheduling ; Program processors ; Schedules ; Scheduling ; Tabu Search ; Task Scheduling</subject><ispartof>2008 First International Conference on Emerging Trends in Engineering and Technology, 2008, p.384-389</ispartof><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/4579929$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>309,310,780,784,789,790,23930,23931,25140,27925,54555,54932</link.rule.ids><linktorsrc>$$Uhttps://ieeexplore.ieee.org/document/4579929$$EView_record_in_IEEE$$FView_record_in_$$GIEEE</linktorsrc></links><search><creatorcontrib>Padmavathi, S.</creatorcontrib><creatorcontrib>Suguna, M.</creatorcontrib><creatorcontrib>Shalinie, S.M.</creatorcontrib><title>DAG Scheduling on Cluster of Workstations Using Hybrid Particle Swarm Optimization</title><title>2008 First International Conference on Emerging Trends in Engineering and Technology</title><addtitle>ICETET</addtitle><description>Task Scheduling is one of the core steps to effectively exploit the capabilities of resources in cluster computing environment. Scheduling of applications modeled by Directed Acyclic Graph (DAG) is a key issue in this type of environment. The task scheduling problem has been shown to be a NP Complete in general as well as in several restricted cases. This paper presents a List Scheduling algorithm using Particle Swarm Optimization (PSO) based on the concept of Tabu Search (TS). This approach combines the excellence of both PSO and TS. This is different from the existing methods since the procedure adaptively incorporates information about Tabu lists into PSO algorithm. The proposed algorithm outperforms other algorithms in the aspects of performance and scalability. The experimental results manifest that the proposed hybrid method is effective and efficient in finding near optimal schedule length.</description><subject>Algorithm design and analysis</subject><subject>DAG Scheduling</subject><subject>Optimal scheduling</subject><subject>Particle swarm optimization</subject><subject>Processor scheduling</subject><subject>Program processors</subject><subject>Schedules</subject><subject>Scheduling</subject><subject>Tabu Search</subject><subject>Task Scheduling</subject><issn>2157-0477</issn><issn>2157-0485</issn><isbn>0769532675</isbn><isbn>9780769532677</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>2008</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNo9j8tKAzEARaNYsK1du3CTH5gx70yWZewLChU74rJkkoxG51GSKVK_3lbF1b2Lw-FeAG4xSjFG6n6Vz4pZkRKEspQwfgFGSArFKRGSX4IhwVwmiGX86r9LOQCjM6-IwJRdg0mM7wghojDlGRuCp4fpAm7Nm7OH2revsGthXh9i7wLsKvjShY_Y6953bYTP8Qwsj2XwFj7q0HtTO7j91KGBm33vG__1Q96AQaXr6CZ_OQbFfFbky2S9Wazy6TrxCvWJkZWkmgkqTVkaITMimMX2NEsRizgXQlRYG20yaavydEAYa4zlVltcGqzoGNz9ar1zbrcPvtHhuGNcKkUU_QYgjFQ4</recordid><startdate>200807</startdate><enddate>200807</enddate><creator>Padmavathi, S.</creator><creator>Suguna, M.</creator><creator>Shalinie, S.M.</creator><general>IEEE</general><scope>6IE</scope><scope>6IL</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIL</scope></search><sort><creationdate>200807</creationdate><title>DAG Scheduling on Cluster of Workstations Using Hybrid Particle Swarm Optimization</title><author>Padmavathi, S. ; Suguna, M. ; Shalinie, S.M.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-i90t-c7f73a4637cbbc678264d1d13592d055666f1acac87dfb0896cdccd5dad1bc193</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>2008</creationdate><topic>Algorithm design and analysis</topic><topic>DAG Scheduling</topic><topic>Optimal scheduling</topic><topic>Particle swarm optimization</topic><topic>Processor scheduling</topic><topic>Program processors</topic><topic>Schedules</topic><topic>Scheduling</topic><topic>Tabu Search</topic><topic>Task Scheduling</topic><toplevel>online_resources</toplevel><creatorcontrib>Padmavathi, S.</creatorcontrib><creatorcontrib>Suguna, M.</creatorcontrib><creatorcontrib>Shalinie, S.M.</creatorcontrib><collection>IEEE Electronic Library (IEL) Conference Proceedings</collection><collection>IEEE Proceedings Order Plan All Online (POP All Online) 1998-present by volume</collection><collection>IEEE Xplore All Conference Proceedings</collection><collection>IEEE/IET Electronic Library (IEL)</collection><collection>IEEE Proceedings Order Plans (POP All) 1998-Present</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext_linktorsrc</fulltext></delivery><addata><au>Padmavathi, S.</au><au>Suguna, M.</au><au>Shalinie, S.M.</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>DAG Scheduling on Cluster of Workstations Using Hybrid Particle Swarm Optimization</atitle><btitle>2008 First International Conference on Emerging Trends in Engineering and Technology</btitle><stitle>ICETET</stitle><date>2008-07</date><risdate>2008</risdate><spage>384</spage><epage>389</epage><pages>384-389</pages><issn>2157-0477</issn><eissn>2157-0485</eissn><eisbn>0769532675</eisbn><eisbn>9780769532677</eisbn><abstract>Task Scheduling is one of the core steps to effectively exploit the capabilities of resources in cluster computing environment. Scheduling of applications modeled by Directed Acyclic Graph (DAG) is a key issue in this type of environment. The task scheduling problem has been shown to be a NP Complete in general as well as in several restricted cases. This paper presents a List Scheduling algorithm using Particle Swarm Optimization (PSO) based on the concept of Tabu Search (TS). This approach combines the excellence of both PSO and TS. This is different from the existing methods since the procedure adaptively incorporates information about Tabu lists into PSO algorithm. The proposed algorithm outperforms other algorithms in the aspects of performance and scalability. The experimental results manifest that the proposed hybrid method is effective and efficient in finding near optimal schedule length.</abstract><pub>IEEE</pub><doi>10.1109/ICETET.2008.245</doi><tpages>6</tpages></addata></record>
fulltext fulltext_linktorsrc
identifier ISSN: 2157-0477
ispartof 2008 First International Conference on Emerging Trends in Engineering and Technology, 2008, p.384-389
issn 2157-0477
2157-0485
language eng
recordid cdi_ieee_primary_4579929
source IEEE Xplore All Conference Series
subjects Algorithm design and analysis
DAG Scheduling
Optimal scheduling
Particle swarm optimization
Processor scheduling
Program processors
Schedules
Scheduling
Tabu Search
Task Scheduling
title DAG Scheduling on Cluster of Workstations Using Hybrid Particle Swarm Optimization
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-27T14%3A15%3A23IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-ieee_CHZPO&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=DAG%20Scheduling%20on%20Cluster%20of%20Workstations%20Using%20Hybrid%20Particle%20Swarm%20Optimization&rft.btitle=2008%20First%20International%20Conference%20on%20Emerging%20Trends%20in%20Engineering%20and%20Technology&rft.au=Padmavathi,%20S.&rft.date=2008-07&rft.spage=384&rft.epage=389&rft.pages=384-389&rft.issn=2157-0477&rft.eissn=2157-0485&rft_id=info:doi/10.1109/ICETET.2008.245&rft.eisbn=0769532675&rft.eisbn_list=9780769532677&rft_dat=%3Cieee_CHZPO%3E4579929%3C/ieee_CHZPO%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-i90t-c7f73a4637cbbc678264d1d13592d055666f1acac87dfb0896cdccd5dad1bc193%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rft_ieee_id=4579929&rfr_iscdi=true