Preemptive Scheduling of a Single Machine with Finite States to Minimize Energy Costs
Optimization and Decision Science: Methodologies and Applications: ODS, Sorrento, Italy, September 4-7, 2017
Sforza, Antonio and Sterle, Claudio
This paper addresses a single machine scheduling problem in which the system may switch among three different states, namely ON (needed for processing the jobs), OFF or Idle. Each state, as well as switching among the different states, consume energy. The objective is schedule n preemptive jobs to minimize the total energy costs. Time varied electricity price are considered. The complexity of this problem is investigated using a new dynamic programming approach. In this approach, a finite graph is used to model the proposed problem. The dimension (number of vertices and edges) of this graph is dependent on the total processing times and the total number of periods. Then, the optimal solution of the problem is provided by calculating the shortest path between the first node and last node representing respectively the first and the last periods. Based on the Dijkstra's algorithm complexity, we prove that the complexity of this problem, is polynomial of degree 3.