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.
['Zhaohui Liu', 'Wen-Chiung Lee', 'Jen-Ya Wang']
Resource consumption minimization with a constraint of maximum tardiness on parallel machines