Journal
COMPUTERS & OPERATIONS RESEARCH
Volume 85, Issue -, Pages 172-183Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2017.04.004
Keywords
Energy-efficient scheduling; Single machine; Bi-objective scheduling; Power-down mechanism; epsilon-constraint method
Categories
Funding
- National Natural Science Foundation of China [71471145, 71571032, 71071129]
Ask authors/readers for more resources
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 epsilon - 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 epsilon - 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. (C) 2017 Elsevier Ltd. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available