Back to Search
Start Over
Minimizing the Stretch When Scheduling Flows of Divisible Requests
- Source :
- Journal of Scheduling, Journal of Scheduling, Springer Verlag, 2008, ⟨10.1007/s10951-008-0078-4⟩, Journal of Scheduling, 2008, ⟨10.1007/s10951-008-0078-4⟩
- Publication Year :
- 2008
- Publisher :
- HAL CCSD, 2008.
-
Abstract
- International audience; In this paper, we consider the problem of scheduling distributed biological sequence comparison applications. This problem lies in the divisible load framework with negligible communication costs. Thus far, very few results have been proposed for this model. We discuss and select relevant metrics for this framework: namely max-stretch and sum-stretch. We explain the relationship between our model and the preemptive single processor case, and we show how to extend algorithms that have been proposed in the literature for the single processor model to the divisible multi-processor problem domain. We recall known results on closely related problems, we show how to minimize the max-stretch on unrelated machines either in the divisible load model or with preemption, we derive new lower bounds on the competitive ratio of any online algorithm, we present new competitiveness results for existing algorithms, and we develop several new online heuristics. We also address the Pareto optimization of max-stretch. Then, we extensively study the performance of these algorithms and heuristics under realistic scenarios. Our study shows that all previously proposed guaranteed heuristics for max-stretch for the single processor model are inefcient in practice. In contrast, we show that our online algorithms based on linear programming are in practice near-optimal solutions for max-stretch. Our study also clearly suggests heuristics that are efcient for both metrics, although a combined optimization is in theory not possible in the general case.
- Subjects :
- Mathematical optimization
021103 operations research
Competitive analysis
Linear programming
Computer science
0211 other engineering and technologies
General Engineering
Symmetric multiprocessor system
0102 computer and information sciences
02 engineering and technology
Management Science and Operations Research
01 natural sciences
Multi-objective optimization
Scheduling (computing)
010201 computation theory & mathematics
Artificial Intelligence
Problem domain
Online algorithm
[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Heuristics
Software
Subjects
Details
- Language :
- English
- ISSN :
- 10946136 and 10991425
- Database :
- OpenAIRE
- Journal :
- Journal of Scheduling, Journal of Scheduling, Springer Verlag, 2008, ⟨10.1007/s10951-008-0078-4⟩, Journal of Scheduling, 2008, ⟨10.1007/s10951-008-0078-4⟩
- Accession number :
- edsair.doi.dedup.....a92d128009271a92cf2322faf94398ae