DC FieldValueLanguage
dc.contributor.authorDavidović, Tatjanaen_US
dc.date.accessioned2020-06-30T10:46:56Z-
dc.date.available2020-06-30T10:46:56Z-
dc.date.issued2000-12-01-
dc.identifier.issn0354-0243-
dc.identifier.urihttp://researchrepository.mi.sanu.ac.rs/handle/123456789/3272-
dc.description.abstractThe multiprocessor scheduling problem has usually been "solved" by using heuristic methods. A large number of such heuristics can be found in the literature, but none of them can efficiently be applied to the problem in its most general form. The efficiency of any scheduling heuristic depends on both the task graph structure and the multiprocessor system architecture. List-scheduling heuristics are the most common ones in use. They are based on the definition of the task priority list determining the order in which tasks will be scheduled (assigned to one of the processors). A task can be assigned to a processor in many different ways, but variations of the earliest start heuristics are the most frequent in use. In this paper a scheduling strategy based on the use of multiple task priority lists combined with several assignment heuristics is suggested in order to find optimal (near-optimal at the worst) solutions for a large class of arbitrary task graphs. It is shown that performing an exhaustive search overall feasible task priority lists is not too expensive for scheduling dense task graphs.en_US
dc.publisherFaculty of Organizational Sciences, University of Belgradeen_US
dc.relation.ispartofYugoslav Journal of Operations Researchen_US
dc.subjectCommunication delay | Multiprocessors | Precedence graphs | Schedulingen_US
dc.titleExhaustive list-scheduling heuristic for dense task graphsen_US
dc.typeArticleen_US
dc.identifier.scopus2-s2.0-23144454478-
dc.contributor.affiliationMathematical Institute of the Serbian Academy of Sciences and Arts-
dc.relation.firstpage123-
dc.relation.lastpage136-
dc.relation.issue1-
dc.relation.volume10-
dc.description.rankM50-
item.cerifentitytypePublications-
item.grantfulltextnone-
item.openairetypeArticle-
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
item.fulltextNo Fulltext-
crisitem.author.orcid0000-0001-9561-5339-
Show simple item record

SCOPUSTM   
Citations

4
checked on Jun 23, 2024

Page view(s)

40
checked on May 9, 2024

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.