Paper #84
Energy-Efficient Identical Parallel-Machine Scheduling with Time-of-use Costs to Minimize Makespan
Presenting author: Mehdi Jammali
Session: O04
Abstract
We study the scheduling of jobs on identical parallel machines billed under a time-of-use electricity tariff, with the goal of minimizing the completion time of the last job while keeping the total energy cost within a fixed budget. The duration of a job shortens with its position on a machine, following a DeJong learning curve. On 60 benchmark instances we compare nine methods: a weak reference rule, five classical heuristics (list scheduling, longest-processing-time assignment, price-aware insertion, simulated annealing, and a genetic algorithm), and three reinforcement-learning policies trained with the learning effect active. When only the completion time matters, the strong heuristics closely rival the learned policies at a fraction of their running time. Under an active energy budget, however, the strong heuristics lose feasibility almost everywhere, and the energy-aware methods, led by the learning-based policies, deliver the lowest feasible completion time.