Advertisement
Published in:
2010 | OriginalPaper | Chapter
Fully Polynomial Time Approximation Schemes for Scheduling Divisible Loads
Author : Joanna Berlińska
Published in: Parallel Processing and Applied Mathematics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper we study divisible loads scheduling in heterogeneous systems with high bandwidth. Divisible loads represent computations which can be arbitrarily divided into parts and performed independently in parallel. We propose fully polynomial time approximation schemes for two optimization problems. The first problem consists in finding the maximum load which can be processed in a given time. It turns out that this problem can be reduced to minimization of a half-product. The second problem is computing the minimum time required to process load of a given size. The FPTAS solving this problem uses a dual approximation algorithm approach.