Energy-efficient scheduling of unrelated parallel machines under time-of-use electricity pricing with release dates

Time-of-use (TOU) electricity pricing is widely applied in industrial energy management, motivating manufacturers to adjust production schedules to time-varying tariffs. This study investigates an energy-efficient scheduling problem in an unrelated parallel-machine setting with job release dates under TOU pricing, aiming to minimise total electricity cost within a bounded planning horizon. The problem is first formulated as a period-indexed mixed-integer linear programming (P-MILP) model and strengthened by two valid inequalities. Given the NP-hard nature of the problem, we develop a two-stage heuristic (TSH) to solve practically sized instances efficiently. The method constructs an initial solution and then enhances it through a customised tabu search. Computational experiments on randomly generated instances show that the two valid inequalities reduce the average CPU time of the P-MILP model by up to 88.7%, while the TSH produces high-quality solutions within practical times and scales to instances with up to 800 jobs, with average optimality gaps below 0.4% relative to the lower bound in large-scale instances. Sensitivity analyses indicate that incorporating TOU pricing affects scheduling performance. Managers should adapt assignment and sequencing to price fluctuations by prioritising off-peak processing for long or energy-intensive jobs, while scheduling urgent or late-released jobs during high-price periods when necessary.