Title

Preemptive Scheduling of a Single Machine with Finite States to Minimize Energy Costs

In

Optimization and Decision Science: Methodologies and Applications: ODS, Sorrento, Italy, September 4-7, 2017

Volume

17

Pages

591–599

Publisher

Sforza, Antonio and Sterle, Claudio

Year

2017

Publisher's URL

Indexed by

Abstract

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.

Affiliations

Offprint