A Bi-Objective Heuristic for Green Identical Parallel Machine Scheduling

In recent years sustainability in manufacturing has become a fundamental topic in the scientific literature. Several authors highlighted the preeminent role of manufacturing industry in total world energy consumption and carbon emission (Garetti and Taisch, 2012; Liu et al., 2014), which in turn is the primary cause for triggering the greenhouse effect. In this connection, this work 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 (TOU) policy, as in many cases of practical interest. In order to face this problem, an ad-hoc heuristic has been 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 et al., 2018). The second part, called Exchange-Search, is a novel local search procedure aimed at improving the quality of the Pareto-efficient solutions. The experimental results prove the efficacy of the proposed method with respect to two challenging competitors, i.e., the CH heuristic itself, and the NSGA-II algorithm.