Resource consumption minimization with a constraint of maximum tardiness on parallel machines

•Scheduling with minimizing the total resource consumption.•A branch-and-bound algorithm to search for the optimal solution.•A lower bound based on job preemption.

In response to the effects of global warming and environmental concerns, energy consumption has become a crucial issue. In this study, we consider a parallel-machine scheduling problem where the objective is to minimize the sum of resource consumption and outsourcing cost given that the maximum tardiness of all jobs does not exceed a given bound. We show that the problem is polynomially solvable for the pre-emption case and strongly NP-hard for the non-preemption case. A branch-and-bound algorithm and a hybrid metaheuristic algorithm are proposed to obtain exact and approximate solutions. Some experimental results are given to evaluate the algorithms.