Power of Pre-Processing: Production Scheduling with Variable Energy Pricing and Power-Saving States

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F20%3A00344046" target="_blank" >RIV/68407700:21230/20:00344046 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/68407700:21730/20:00344046

Výsledek na webu

<a href="https://doi.org/10.1007/s10601-020-09317-y" target="_blank" >https://doi.org/10.1007/s10601-020-09317-y</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10601-020-09317-y" target="_blank" >10.1007/s10601-020-09317-y</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Power of Pre-Processing: Production Scheduling with Variable Energy Pricing and Power-Saving States

Popis výsledku v původním jazyce

This paper addresses a single machine scheduling problem with non-preemptive jobs to minimize the total electricity cost. Two latest trends in the area of the energy-aware scheduling are considered, namely the variable energy pricing and the power-saving states of a machine. Scheduling of the jobs and the machine states are considered jointly to achieve the highest possible savings. Although this problem has been previously addressed in the literature, the reported results of the state-of-the-art method show that the optimal solutions can be found only for instances with up to 35 jobs and 209 intervals within 3 hours of computation. We propose an elegant pre-processing technique called SPACES for computing the optimal switching of the machine states with respect to the energy costs. The optimal switchings are associated with the shortest paths in an interval-state graph that describes all possible transitions between the machine states in time. This idea allows us to implement efficient integer linear programming and constraint programming models of the problem while preserving the optimality. The efficiency of the models lies in the simplification of the optimal switching representation. The results of the experiments show that our approach outperforms the existing state-of-the-art exact method. On a set of benchmark instances with varying sizes and different state transition graphs, the proposed approach finds the optimal solutions even for the large instances with up to 190 jobs and 1277 intervals within an hour of computation.

Název v anglickém jazyce

Power of Pre-Processing: Production Scheduling with Variable Energy Pricing and Power-Saving States

Popis výsledku anglicky

This paper addresses a single machine scheduling problem with non-preemptive jobs to minimize the total electricity cost. Two latest trends in the area of the energy-aware scheduling are considered, namely the variable energy pricing and the power-saving states of a machine. Scheduling of the jobs and the machine states are considered jointly to achieve the highest possible savings. Although this problem has been previously addressed in the literature, the reported results of the state-of-the-art method show that the optimal solutions can be found only for instances with up to 35 jobs and 209 intervals within 3 hours of computation. We propose an elegant pre-processing technique called SPACES for computing the optimal switching of the machine states with respect to the energy costs. The optimal switchings are associated with the shortest paths in an interval-state graph that describes all possible transitions between the machine states in time. This idea allows us to implement efficient integer linear programming and constraint programming models of the problem while preserving the optimality. The efficiency of the models lies in the simplification of the optimal switching representation. The results of the experiments show that our approach outperforms the existing state-of-the-art exact method. On a set of benchmark instances with varying sizes and different state transition graphs, the proposed approach finds the optimal solutions even for the large instances with up to 190 jobs and 1277 intervals within an hour of computation.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/EF16_026%2F0008432" target="_blank" >EF16_026/0008432: Klastr 4.0 - Metodologie systémové integrace</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2020

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

CONSTRAINTS

ISSN

1383-7133

e-ISSN

1572-9354

Svazek periodika

25

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

19

Strana od-do

300-318

Kód UT WoS článku

000590007500001

EID výsledku v databázi Scopus

2-s2.0-85096046542