Energy-efficient single-machine scheduling with release dates under time-of-use electricity tariffs

The global trend of increasing resource utilization in industry has drawn great attention from researchers and practitioners. Industrial managers are increasingly optimizing their production strategies based on time-of-use (TOU) electricity tariffs to reduce energy consumption costs. This study investigates a new energy-efficient single-machine scheduling problem with release dates under TOU electricity tariffs. It consists in sequencing a set of jobs with release dates to a machine under TOU pricing to minimize the total energy cost given a bounded maximum completion time. We first formulate the problem using the widely used time-indexed mixed-integer linear programming (T-MILP). Due to its time-consuming disadvantage, a new period-based MILP (P-MILP) model is developed based on the characteristics of the problem. Given the NP-hardness of the problem, a two -stage heuristic (TSH) algorithm is proposed to solve practical-sized problems. Specifically, in the first stage, a constructive heuristic is designed to obtain an initial solution, and in the second one, a tailored tabu search is devised to yield a better satisfactory solution. Numerical experiments are conducted on a real-life case and 1150 randomly generated instances with up to 1000 jobs. Computational results show that (i) the proposed models can save the total electricity cost by about 30% compared with an existing empirical scheduling method when solving small-sized instances; (ii) the efficiency of P-MILP is about 140.94% higher than that of T-MILP; and (iii) the proposed TSH algorithm can efficiently obtain high-quality solutions for practical-sized instances with gaps of less than 7% compared to the lower bounds, which can effectively support production managers to save the energy costs in practical production.