Energy-efficient bi-objective single-machine scheduling with power-down mechanism

This paper considers a single-machine scheduling problem with power-down mechanism to minimize both total energy consumption and maximum tardiness. The aim is to find an optimal processing sequence of jobs and determine if the machine should be executed a power-down operation between two consecutive jobs. To formulate the problem, a mixed-integer linear programming (MILP) model is developed. Then a basic ε − constraint method is proposed to obtain the complete Pareto front of the problem. Considering the particularity of the problem, we also develop local search, preprocessing technique and valid inequalities to strengthen the basic ε − constraint method. Finally, to obtain approximate Pareto fronts for large-size problems, we utilize the method of cluster analysis to divide the jobs into several sorted clusters according to their release times and due dates. Any job in a preceding cluster must be processed before all jobs in a subsequent cluster. Thus, the solution space is reduced significantly. Computational experiments on benchmark and randomly generated instances demonstrate the effectiveness of the proposed exact and approximation approaches.