Heuristic scheduling strategies for linear-dependent and independent jobs on heterogeneous grids

Min Yi Tsai, Ping Fang Chiang, Yen Jan Chang, Wei Jen Wang

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

16 Scopus citations

Abstract

Grid computing came into being an active research area because of the advances in wide-area network technologies and the low cost of computing resources. One motivation of grid computing is to aggregate the power of distributed resources and integrate the resources into a unified platform. To minimize the total completion time of the submitted computing jobs to a grid platform, people employ various scheduling algorithms to dispatch the jobs to the resources. However, it has been proved that the optimal scheduling algorithm is NP-hard. Therefore, many people turn to use heuristic approaches for grid scheduling. In this paper, we introduce ten common scheduling heuristics to schedule a combination of job-chains (linear-dependent jobs) and independent jobs on a heterogeneous environment. We implemented these methods on a grid simulator to evaluate their performance under different circumstances. The results of scheduling job-chains and independent jobs on a heterogeneous environment are quite different from previous studies, and we provide our explanations for the differences. We also propose a hybrid method based on our observation, and the simulation results show that it has good performance in terns of makespan.

Original languageEnglish
Title of host publicationGrid and Distributed Computing - International Conference, GDC 2011, Held as Part of the Future Generation Information Technology Conference, FGIT 2011, Proceedings
Pages496-505
Number of pages10
DOIs
StatePublished - 2011
EventInternational Conference on Grid and Distributed Computing, GDC 2011, Held as Part of the 3rd International Mega-Conference on Future-Generation Information Technology, FGIT 2011 - Jeju Island, Korea, Republic of
Duration: 8 Dec 201110 Dec 2011

Publication series

NameCommunications in Computer and Information Science
Volume261 CCIS
ISSN (Print)1865-0929

Conference

ConferenceInternational Conference on Grid and Distributed Computing, GDC 2011, Held as Part of the 3rd International Mega-Conference on Future-Generation Information Technology, FGIT 2011
Country/TerritoryKorea, Republic of
CityJeju Island
Period8/12/1110/12/11

Keywords

  • Grid computing
  • Heuristics
  • Job dependency
  • Job scheduling

Fingerprint

Dive into the research topics of 'Heuristic scheduling strategies for linear-dependent and independent jobs on heterogeneous grids'. Together they form a unique fingerprint.

Cite this