The industrial energy consumption is the main part of the total energy consumption in china. For the industries, we should not only concentrate on the demand of due date, but also keep an eye on the energy usage. This paper studies scheduling problem where a set of jobs are scheduled on several lines to trade off between the total energy usage and total tardiness. By formally describing the new scheduling problem and analyzing the problem's complexity, a mixed integer linear programming model is first built. A branch-and-bound algorithm, heuristic algorithm, tabu-search algorithm and Simulated Annealing Algorithm are further proposed. Numerical experiments are carefully designed to test the performance of algorithms based on several factors of the problem. Empirical studies verify the effectiveness and efficiency of algorithms.This paper aims to provide decision support for the high energy consumption industries to trade off between the energy consumption and the tardiness. Also, the model and the algorithms in this paper can be used to provide theory support for the production scheduling in the high-energy consumption industries. |