A bi-objective heuristic approach for green identical parallel machine scheduling

Sustainability in manufacturing has become a fundamental topic in the scientific literature due to the preeminent role of manufacturing industry in total world energy consumption and carbon emission. This paper tackles the multi-objective combinatorial optimization problem of scheduling jobs on multiple parallel machines, while minimizing both the makespan and the total energy consumption. The electricity prices vary according to a time-of-use policy, as in many cases of practical interest. In order to face this problem, an ad-hoc heuristic method is developed. The first part of the method, called Split-Greedy heuristic, consists in an improved and refined version of the constructive heuristic (CH) proposed in Wang, Wang, Yu, Ma and Liu (2018). The second part, called Exchange Search, is a novel local search procedure aimed at improving the quality of the Pareto optimal solutions. The experimental results prove the effectiveness of the proposed method with respect to three competitors: CH, NSGA-III, and MOEA/D.