Preemptive Scheduling of a Single Machine with Finite States to Minimize Energy Costs - Archive ouverte HAL Access content directly
Conference Papers Year : 2017

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

(1) , (1) , (1)
1

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
Not file

Dates and versions

hal-02859859 , version 1 (08-06-2020)

Identifiers

Cite

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⟩

Collections

CNRS UTT LOSI
10 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More