Energy-efficient single-machine scheduling with group processing features under time-of-use electricity tariffs

• A novel and practical single machine scheduling problem under TOU tariffs is studied. • Two MILP models including T-MILP and P-MILP are formulated. • Four properties and a block-based dynamic programming algorithm is presented. • A tailored iterative greedy algorithm is developed to tackle large-scale instances. This work studies a novel single machine scheduling problem with group-processing features under time-of-use tariffs, which is derived from the realistic hot milling process in modern steel manufacturing industry. The objective is to minimize the total energy cost while adhering to a bounded maximum completion time. We first propose two mixed integer linear programming (MILP) models: a time-indexed MILP and a period-based MILP. Next, we analyze the problem’s properties and design a block-based dynamic programming algorithm. To solve instances of practical size, an improved iterative greedy algorithm is introduced. In the algorithm, a problem-specific heuristic is presented to construct an initial solution. Both block-based and job-based disruption and reconstruction strategies, along with six local search operators, are designed to direct the algorithm towards promising regions. Moreover, a deep search strategy based on a 0–1 programming model is developed to optimize the sequence of jobs within each price interval. Computational results indicate that: (i) the efficiency of the period-based MILP is superior to the time-indexed MILP; (ii) the dynamic programming algorithm exhibits higher performance in solving some small-scale instances compared to the period-based MILP; and (iii) the proposed algorithm is highly effective for both small- and large- scale instances, which can provide effective support for the production management of enterprises.