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

Mohammadmohsen Aghelinejad (1) , Yassine Ouazene (1) , Alice Yalaoui (1)

1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels

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

Domains: Operations Research [cs.RO]

Mohammadmohsen Aghelinejad, Yassine Ouazene, Alice Yalaoui. Preemptive Scheduling of a Single Machine with Finite States to Minimize Energy Costs. Optimization and Decision Science: Methodologies and Applications, Sep 2017, Sorrento, Italy. pp.591-599, ⟨10.1007/978-3-319-67308-0_59⟩. ⟨hal-02859859⟩