Energy-conscious unrelated parallel machine scheduling under time-of-use electricity tariffs

Abstract This paper investigates an energy-conscious unrelated parallel machine scheduling problem under time-of-use (TOU) electricity pricing scheme, in which the electricity price varies throughout a day. The problem lies in assigning a group of jobs to a set of unrelated parallel machines and then scheduling jobs on each separate machine so as to minimize the total electricity cost. We first build an improved continuous-time mixed-integer linear programming (MILP) model for the problem. To tackle large-size problems, we then propose a two-stage heuristic. Specifically, at the first stage, jobs are assigned to machines aiming at minimizing the total electricity cost under the preemptive circumstance. At the second stage, the jobs assigned to each machine are scheduled using an insertion heuristic. Computational results on a real-life instance for turning process and random test instances demonstrate that the proposed MILP approach is able to solve small-size problems while the two-stage heuristic is appropriate for large-size problems. The case study for turning process also reveals that the proposed optimization approaches can contribute to cleaner production.