In recent years, the research interest in energy-efficient scheduling has been increasing [3, 4]. Besides the traditional performance-oriented criteria, such as makespan, the authors also consider energy optimization, in order to make the production cost-efficient and environmentally friendly. In this work, we study a single machine scheduling problem to minimize the total energy cost (TEC) of the production, assuming the power-saving states of the machine as well as time-of-use (TOU) energy pricing. The integration of the power-saving states and the TOU pricing was initially proposed by Shrouf et al. [5], who designed an integer linear programming (ILP) model for the single machine problem with the fixed order of the jobs. Later, Aghelinejad et al. [1] improved and generalized the existing ILP model to consider even an arbitrary order of the jobs, in which case the problem is NP-hard [2]. However, in both [1] and [5], only small instances of the problem have been solved optimally. One of the reasons for the inefficiency of the models is that the proposed ILP models explicitly formulate the transition behavior of the machine, and optimize it jointly with the scheduling of the jobs. In consequence, the size of the ILP models is large, and only the medium instances can be solved optimally.
展开▼