Xiaoping Li; Tianze Jiang; Ruiz García, R. (2016). Heuristics for periodical batch job scheduling in a MapReduce computing framework. Information Sciences. 326:119-133. https://doi.org/10.1016/j.ins.2015.07.040
Por favor, use este identificador para citar o enlazar este ítem: http://hdl.handle.net/10251/78868
Title:
|
Heuristics for periodical batch job scheduling in a MapReduce computing framework
|
Author:
|
Xiaoping Li
Tianze Jiang
Ruiz García, Rubén
|
UPV Unit:
|
Universitat Politècnica de València. Facultad de Administración y Dirección de Empresas - Facultat d'Administració i Direcció d'Empreses
|
Issued date:
|
|
Abstract:
|
Task scheduling has a significant impact on the performance of the MapReduce computing
framework. In this paper, a scheduling problem of periodical batch jobs with makespan minimization
is considered. The problem is ...[+]
Task scheduling has a significant impact on the performance of the MapReduce computing
framework. In this paper, a scheduling problem of periodical batch jobs with makespan minimization
is considered. The problem is modeled as a general two-stage hybrid flow shop
scheduling problem with schedule-dependent setup times. The new model incorporates the
data locality of tasks and is formulated as an integer program. Three heuristics are developed
to solve the problem and an improvement policy based on data locality is presented to enhance
the methods. A lower bound of the makespan is derived. 150 instances are randomly
generated from data distributions drawn from a real cluster. The parameters involved in the
methods are set according to different cluster setups. The proposed heuristics are compared
over different numbers of jobs and cluster setups. Computational results show that the performance
of the methods is highly dependent on both the number of jobs and the cluster setups.
The proposed improvement policy is effective and the impact of the input data distribution on
the policy is analyzed and tested.
[-]
|
Subjects:
|
MapReduce
,
Periodical job
,
Schedule-dependent setup times
,
Heuristics
,
Makespan
|
Copyrigths:
|
Reserva de todos los derechos
|
Source:
|
Information Sciences. (issn:
0020-0255
)
|
DOI:
|
10.1016/j.ins.2015.07.040
|
Publisher:
|
Elsevier
|
Publisher version:
|
http://dx.doi.org/10.1016/j.ins.2015.07.040
|
Project ID:
|
info:eu-repo/grantAgreement/NSFC//61272377/
info:eu-repo/grantAgreement/SRFDP//20120092110027/
info:eu-repo/grantAgreement/MINECO//DPI2012-36243-C02-01/ES/REALISTIC EXTENDED SCHEDULING USING LIGHT TECHNIQUES/
|
Thanks:
|
This work is supported by the National Natural Science Foundation of China (No. 61272377) and the Specialized Research Fund for the Doctoral Program of Higher Education (No. 20120092110027). Ruben Ruiz is partially supported ...[+]
This work is supported by the National Natural Science Foundation of China (No. 61272377) and the Specialized Research Fund for the Doctoral Program of Higher Education (No. 20120092110027). Ruben Ruiz is partially supported by the Spanish Ministry of Economy and Competitiveness, under the project "RESULT - Realistic Extended Scheduling Using Light Techniques" (No. DPI2012-36243-C02-01) partially financed with FEDER funds.
[-]
|
Type:
|
Artículo
|