Parallel machine scheduling with setup time in the MapReduce system

This work studies MapReduce model-based parallel machine scheduling. Each job with arbitrary release time and setup time 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, and the processing for any task cannot be interrupted. In this paper, we consider the MapReduce scheduling on parallel identical machines, aiming at minimizing the makespan. We formulate the problem as a mixed integer linear programming model, and develop an improved sine cosine algorithm (ISCA) using differential perturbation and dimension-bydimension Levy perturbation to obtain a near-optimal solution. Computational comparisons between ISCA and genetic algorithm together with the classical SCA algorithm show that the proposed ISCA algorithm outperforms the other two algorithms. Besides, the ISCA is of an average relative deviation of 3.02% from the lower bound of the problem. Numerical computation verifies the effectiveness of the proposed algorithm.