Approximation algorithms and heuristics for task scheduling in data-intensive distributed systems

Autor(es)

Povoa, Marcelo G. ^{[1, 2]} ; Xavier, Eduardo C. ^[1]

Afiliação do(s) autor(es)

^[1] Univ Estadual Campinas, Inst Comp, Ave Albert Einstein 1251, BR-13083852 Campinas, SP - Brazil

^[2] Google, Ave Andradas 3000, BR-30260070 Belo Hozitonte - Brazil

• Tipo de documento: Artigo Científico
• Fonte: International Transactions in Operational Research; v. 25, n. 5, p. 1417-1441, SEP 2018.
• Citações Web of Science: 0

Resumo

In this work, we are interested in the problem of task scheduling on large-scale data-intensive computing systems. In order to achieve good performance, one must construct not only good task schedules but also good data allocation across nodes on the system, since before a task can be executed, it must have access to data distributed on the system. In this article, we present a general formulation of a static problem that combines both scheduling and replication problems in data-intensive distributed systems. We show that this problem does not admit an approximation algorithm. However, considering a restricted version of the problem that considers some practical constraints, an approximation algorithm can be designed. From a practical perspective, we introduce a novel heuristic for the problem that is based on nodes clustering. We compare the heuristic with two adapted approaches from other works in the literature by computational simulations using an extensive set of instances based on real computer grids. We show that our heuristic often obtains the best solutions and also runs faster than other approaches. (AU)

• Processo FAPESP: 16/23552-7 - Problemas de corte e empacotamento: abordagens práticas e teóricas
• Beneficiário: Rafael Crivellari Saliba Schouery
• Linha de fomento: Auxílio à Pesquisa - Regular
• Processo FAPESP: 14/02104-0 - Escalonamento de tarefas com localidade de dados em grids
• Beneficiário: Marcelo Galvão Póvoa
• Linha de fomento: Bolsas no Brasil - Mestrado
• Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
• Beneficiário: Flávio Keidi Miyazawa
• Linha de fomento: Auxílio à Pesquisa - Temático