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
Branch and Bound Algorithm for Multiprocessor Scheduling
Dalarna University, School of Technology and Business Studies, Computer Engineering.
2009 (English)Independent thesis Advanced level (degree of Master (Two Years))Student thesis
Abstract [en]

The multiprocessor task graph scheduling problem has been extensively studied as academic optimization problem which occurs in optimizing the execution time of parallel algorithm with parallel computer. The problem is already being known as one of the NPhard problems. There are many good approaches made with many optimizing algorithm to find out the optimum solution for this problem with less computational time. One of them is branch and bound algorithm. In this paper, we propose a branch and bound algorithm for the multiprocessor scheduling problem. We investigate the algorithm by comparing two different lower bounds with their computational costs and the size of the pruned tree. Several experiments are made with small set of problems and results are compared in different sections.

Place, publisher, year, edition, pages
Borlänge, 2009. , 42 p.
Keyword [en]
Multiprocessor scheduling problems, Branch and Bound, Lower Bound, Upper Bound, Task Graph Scheduling, Critical Path
Identifiers
URN: urn:nbn:se:du-3790OAI: oai:dalea.du.se:3790DiVA: diva2:518609
Uppsok
Technology
Supervisors
Available from: 2009-03-12 Created: 2009-03-12 Last updated: 2012-04-24Bibliographically approved

Open Access in DiVA

fulltext(288 kB)777 downloads
File information
File name FULLTEXT01.pdfFile size 288 kBChecksum SHA-512
7c9ffcdd3e5aab1298e7ed73441869987a55c1c79f83f02b73562dc2ff6a17717791c9a8cd6213cf30fa997b6feb7f8cc4c8ecf2c91f637b56488b51f6d4f933
Type fulltextMimetype application/pdf

By organisation
Computer Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 777 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: 771 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