du.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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
Using ant colonies for solve the multiprocessor task graph scheduling
Dalarna University, School of Technology and Business Studies, Computer Engineering.
2006 (English)Independent thesis Advanced level (degree of Master (Two Years))Student thesis
Abstract [en]

The problem of scheduling a parallel program presented by a weighted directed acyclic graph (DAG) to the set of homogeneous processors for minimizing the completion time of the program has been extensively studied as academic optimization problem which occurs in optimizing the execution time of parallel algorithm with parallel computer. In this paper, we propose an application of the Ant Colony Optimization (ACO) to a multiprocessor scheduling problem (MPSP). In the MPSP, no preemption is allowed and each operation demands a setup time on the machines. The problem seeks to compose a schedule that minimizes the total completion time. We therefore rely on heuristics to find solutions since solution methods are not feasible for most problems as such. This novel heuristic searching approach to the multiprocessor based on the ACO algorithm a collection of agents cooperate to effectively explore the search space. A computational experiment is conducted on a suit of benchmark application. By comparing our algorithm result obtained to that of previous heuristic algorithm, it is evince that the ACO algorithm exhibits competitive performance with small error ratio.

Place, publisher, year, edition, pages
Borlänge, 2006. , 61 p.
Keyword [en]
Multiprocessor scheduling problems, ant colony algorithm, ant system, pheromone trail, makespan.
Identifiers
URN: urn:nbn:se:du-2381OAI: oai:dalea.du.se:2381DiVA: diva2:518120
Uppsok
Technology
Supervisors
Available from: 2006-10-31 Created: 2006-10-31 Last updated: 2012-04-24Bibliographically approved

Open Access in DiVA

fulltext(637 kB)472 downloads
File information
File name FULLTEXT01.pdfFile size 637 kBChecksum SHA-512
eaac20d9974167d85ce0e1502e0ab11efe65b28b7b438f078740f3a1e84d0f9d9bec8dadc20c271298a93ec442bbc1bd59c46bd660e7424071881ddf63796a96
Type fulltextMimetype application/pdf

By organisation
Computer Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 472 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 951 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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