Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Cost-efficient scheduling for deadline constrained grid workflows
University of Tehran, Iran.ORCID iD: 0000-0001-5332-1033
School of Computer Science, Iran.
Sharif University of Technology, Iran.
2018 (English)In: Computing and informatics, ISSN 1335-9150, Vol. 37, no 4, p. 838-864Article in journal (Refereed) Published
Abstract [en]

Cost optimization for workflow scheduling while meeting deadline is one of the fundamental problems in utility computing. In this paper, a two-phase cost-efficient scheduling algorithm called critical chain is presented. The proposed algorithm uses the concept of slack time in both phases. The first phase is deadline distribution over all tasks existing in the workflow which is done considering critical path properties of workflow graphs. Critical chain uses slack time to iteratively select most critical sequence of tasks and then assigns sub-deadlines to those tasks. In the second phase named mapping step, it tries to allocate a server to each task considering task’s sub-deadline. In the mapping step, slack time priority in selecting ready task is used to reduce deadline violation. Furthermore, the algorithm tries to locally optimize the computation and communication costs of sequential tasks exploiting dynamic programming. After proposing the scheduling algorithm, three measures for the superiority of a scheduling algorithm are introduced, and the proposed algorithm is compared with other existing algorithms considering the measures. Results obtained from simulating various systems show that the proposed algorithm outperforms four well-known existing workflow scheduling algorithms. 

Place, publisher, year, edition, pages
Slovak Academy of Sciences , 2018. Vol. 37, no 4, p. 838-864
Keywords [en]
Dynamic programming; Grid computing; Mapping; Scheduling, Communication cost; Cost-based scheduling; Critical Paths; Critical sequence; Slack time; Utility computing; Workflow; Workflow scheduling, Iterative methods
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:ri:diva-67735DOI: 10.4149/cai_2018_4_838Scopus ID: 2-s2.0-85055169886OAI: oai:DiVA.org:ri-67735DiVA, id: diva2:1810126
Available from: 2023-11-07 Created: 2023-11-07 Last updated: 2023-11-09Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Dehlaghi Ghadim, Alireza

Search in DiVA

By author/editor
Dehlaghi Ghadim, Alireza
In the same journal
Computing and informatics
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 7 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf