Authors: Davidović, Tatjana 
Crainic, Teodor Gabriel
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Benchmark-problem instances for static scheduling of task graphs with communication delays on homogeneous multiprocessor systems
Journal: Computers and Operations Research
Volume: 33
Issue: 8
First page: 2155
Last page: 2177
Issue Date: 1-Jan-2006
Rank: M21
ISSN: 0305-0548
DOI: 10.1016/j.cor.2005.01.005
Scheduling program tasks on processors is at the core of the efficient use of multiprocessor systems. Most task-scheduling problems are known to be NP-Hard and, thus, heuristics are the method of choice in all but the simplest cases. The utilization of acknowledged sets of benchmark-problem instances is essential for the correct comparison and analysis of heuristics. Yet, such sets are not available for several important classes of scheduling problems, including multiprocessor scheduling problem with communication delays (MSPCD) where one is interested in scheduling dependent tasks onto homogeneous multiprocessor systems, with processors connected in an arbitrary way, while explicitly accounting for the time required to transfer data between tasks allocated to different processors. We propose test-problem instances for the MSPCD that are representative in terms of number of processors, type of multiprocessor architecture, number of tasks to be scheduled, and task graph characteristics (task execution times, communication costs, and density of dependencies between tasks). Moreover, we define our task-graph generators in a way appropriate to ensure that the corresponding problem instances obey the theoretical principles recently proposed in the literature.
Keywords: Benchmark-problem instances | Communication delays | Multiprocessor systems | Task scheduling
Publisher: Elsevier
Project: Mathematical optimization models and methods with applications 

Show full item record


checked on May 20, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




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