A Total Penalty Cost Minimization Algorithm For MapReduce Batch Job Scheduling

In recent years, MapReduce framework has gradually become more and more popular because of its large data processing advantages. Many companies use MapReduce as a tool for their services and production. Researchers have done a lot of work on MapReduce. Batch offline jobs with quality of service requirements were submitted to the cloud service provider, then the service provider can determine the optimal scheduling of a certain goal by off-line analysis to help make decisions on the current service request.In this thesis, the offline MapReduce job scheduling is modeled as a generalization of the two stage hybrid flow shop problem, and integer programming model is established. In the model, the data preparation time is considered as the transmission time of the data to be processed, and data locality is considered to reduce the transmission cost. The optimization objective of the problem is to minimize the total delay penalty cost for a batch of offline jobs. In this thesis, An initial solution generation algorithm based on job sequence and an iterative greedy algorithm are proposed to solve the problem and optimize the quality of the solution. Generally, there is less application scenarios for iterative greedy algorithm in MapReduce en-vironment, but in this thesis, namely cluster resources fixed, optimization goal is to minimize the total penalty cost iterative greedy algorithm has better effect.In the experiment part, the variance analysis technique is used to analyze the related param-eters of the algorithm, and the influence of the above parameters on the quality of the solution of the algorithm is analyzed. Through the experiment of simulation, the results show that the proposed algorithm has better effect on solving the minimization of the total penalty cost.