Skip to Main content Skip to Navigation
Conference papers

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

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
Document type :
Conference papers
Complete list of metadata
Contributor : Jean-Baptiste VU VAN Connect in order to contact the contributor
Submitted on : Monday, June 8, 2020 - 9:37:02 AM
Last modification on : Sunday, June 26, 2022 - 1:40:57 AM





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⟩



Record views