Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Scheduling distributed clusters of parallel machines: primal-dual and LP-based approximation algorithms
Murray R., Khuller S., Chao M. Algorithmica80 (10):2777-2798,2018.Type:Article
Date Reviewed: Aug 17 2018

As large amounts of data continue to accumulate at never-before-seen rates, it becomes uneconomical to store it at a single location, not to mention storing copies at different locations. One solution is to partition the data and store it in groups of computers called clusters. Such arrangements allow for the processing of jobs with input data located in different clusters. Distributed data processing should then be realized locally, while preserving adequate response times and avoiding excessive network traffic.

This situation brings us to the concurrent open shop problem. The paper proposes two scheduling algorithms, CC-TSPT and CC-ATSPT, extending previous work done in the field. Both algorithms depend on the efficient calculation of subjob permutations that may guarantee optimal total weighted completion time for the jobs in question. The resulting schedule is then used in all clusters.

The authors present some background and a thorough description of the problem and its variables. They do this through a series of postulates and proofs that build the mathematical and logical foundation for the proposed improved algorithms. They analyze cases for which all computers in a cluster are identical, and then proceed to extend their results to cases in which machines are not identical and subjobs can be more or less arranged in a homogeneous workload based on machine speed. A major open question remains regarding algorithm efficiency when calculating approximately optimal schedules for each cluster using permutations.

Reviewer:  Carla Sánchez Aguilar Review #: CR146208 (1811-0577)
Bookmark and Share
 
Scheduling (D.4.1 ... )
 
 
Approximation (G.1.2 )
 
 
Distributed Systems (C.2.4 )
 
 
General (D.2.0 )
 
Would you recommend this review?
yes
no
Other reviews under "Scheduling": Date
The gradient model load balancing method
Lin F., Keller R. (ed) IEEE Transactions on Software Engineering 13(1): 32-38, 1987. Type: Article
Sep 1 1987
Preemptive scheduling of a multiprocessor system with memories to minimize maximum lateness
Lai T., Sahni S. SIAM Journal on Computing 13(4): 690-704, 1984. Type: Article
Jul 1 1985
Scheduling independent tasks on uniform processors
Dobson G. SIAM Journal on Computing 13(4): 705-716, 1984. Type: Article
Apr 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy