Abstract: The parallel machine scheduling problem in the MapReduce system with deteriorating effect of installation time and step deteriorating effect of processing time is considered. Each job consists of one map task and one reduce task. The map task can be split and processed on several machines simultaneously, while the reduce task has to be processed on a single machine and it cannot be started unless the map task has been completed. The processing of reduce task can't be interrupted. We consider the workpiece installation with linear deteriorating effect and processing time with step deteriorating effect on parallel identical machines in the MapReduce system, aiming at minimizing the makespan. We formulate the problem as a mixed integer linear programming model, and give a lower bound of the problem. An improved grey wolf algorithm which uses the simplex difference disturbance mechanism, are proposed to solve the model. Numerical experiments are carried out to demonstrate the efficiency of the MILP and the proposed algorithms, comparing the results of the improved grey wolf algorithm, greedy algorithm and genetic algorithm with the lower bounds of the problem.

Key words: step deteriorating, deteriorating effects, parallel machine scheduling, MapReduce, grey wolf algorithm (GWO)