×

Scheduling distributed clusters of parallel machines : primal-dual and LP-based approximation algorithms. (English) Zbl 1391.68015

Summary: The Map-Reduce computing framework rose to prominence with datasets of such size that dozens of machines on a single cluster were needed for individual jobs. As datasets approach the exabyte scale, a single job may need distributed processing not only on multiple machines, but on multiple clusters. We consider a scheduling problem to minimize weighted average completion time of \(n\) jobs on \(m\) distributed clusters of parallel machines. In keeping with the scale of the problems motivating this work, we assume that (1) each job is divided into \(m\) “subjobs” and (2) distinct subjobs of a given job may be processed concurrently. When each cluster is a single machine, this is the NP-Hard concurrent open shop problem. A clear limitation of such a model is that a serial processing assumption sidesteps the issue of how different tasks of a given subjob might be processed in parallel. Our algorithms explicitly model clusters as pools of resources and effectively overcome this issue. Under a variety of parameter settings, we develop two constant factor approximation algorithms for this problem. The first algorithm uses an LP relaxation tailored to this problem from prior work. This LP-based algorithm provides strong performance guarantees. Our second algorithm exploits a surprisingly simple mapping to the special case of one machine per cluster. This mapping-based algorithm is combinatorial and extremely fast. These are the first constant factor approximations for this problem.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68W25 Approximation algorithms

Software:

Azure
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Inc Amazon Web Services.: AWS Lambda - Serverless Compute. URL: https://aws.amazon.com/lambda/ 2016 Accessed 3 Apr 2016
[2] Zhi-Long, Chen., Nicholas, G.: Hall. Supply chain scheduling: assembly systems. Working paper., (2000). doi:10.1007/978-3-8349-8667-2 · Zbl 0797.90047
[3] Garg, Naveen; Kumar, Amit; Pandit, Vinayaka, Order scheduling models: hardness and algorithms, FSTTCS 2007: Found Softw Technol Theor Comput Sci, 4855, 96-107, (2007) · Zbl 1135.90345
[4] Gonzalez, Teofilo; Ibarra, Oscar; Sahni, Sartaj, Bounds for LPT schedules on uniform processors, SIAM J Comput, 6, 155-166, (1977) · Zbl 0347.68043
[5] Ronald, L, Graham, eugene L lawler, jan karel Lenstra, and AHG rinnooy kan. optimization and approximation in deterministic sequencing and scheduling: a survey, Ann Disc Math, 5, 287-326, (1979) · Zbl 0411.90044
[6] Mohammad, Hajjat., Shankaranarayanan, P N., David, Maltz., Sanjay, Rao., Kunwadee, Sripanidkulchai.: Dealer : application-aware request splitting for interactive cloud applications. CoNEXT 2012, 157-168 (2012)
[7] Chien-Chun, Hung., Leana, Golubchik., Minlan, Yu.: Scheduling jobs across geo-distributed datacenters. In: proceedings of the sixth ACM symposium on cloud computing (ACM), 111-124 (2015) · Zbl 1202.90139
[8] Leung, JYT; Li, Haibing; Pinedo, Michael, Scheduling orders for multiple product types to minimize total weighted completion time, Disc Appl Math, 155, 945-970, (2007) · Zbl 1113.90060
[9] Mastrolilli, Monaldo; Queyranne, Maurice; Schulz, Andreas S; Svensson, Ola; Uhan, Nelson A, Minimizing the sum of weighted completion times in a concurrent open shop, Oper Res Lett, 38, 390-395, (2010) · Zbl 1202.90139
[10] Microsoft.: Azure Service Fabric. URL: https://azure.microsoft.com/en-us/services/service-fabric/ (2016) Accessed 3 Apr 2016
[11] Queyranne, Maurice, Structure of a simple scheduling polyhedron, Math Progr, 58, 263-285, (1993) · Zbl 0778.90031
[12] Sushant, Sachdeva., Rishi Saket.: Optimal inapproximability for scheduling problems via structural hardness for hypergraph vertex cover. In: IEEE conference on computational complexity (IEEE), 219-229 (2013) · Zbl 0347.68043
[13] Andreas S. Schulz.: Polytopes and scheduling. Ph.D Thesis (1996) · Zbl 0859.90088
[14] Andreas S, Schulz.: From linear programming relaxations to approximation algorithms for scheduling problems : a tour d ’ horizon. Working paper; available upon request (2012)
[15] Sriskandarajah, C; Wagneur, E, Openshops with jobs overlap, Europ J Oper Res, 71, 366-378, (1993) · Zbl 0797.90047
[16] Qiang, Zhang., Weiwei, Wu., Minming, Li.: Resource scheduling with supply constraint and linear cost. COCOA 2012 conference (2012). doi:10.1007/3-540-68339-9_34 · Zbl 1301.90046
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.