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

Result code in 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>

Alternative codes found

RIV/68407700:21730/20:00344046

Result on the web

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

Result language

angličtina

Original language name

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

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

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

Project

<a href="/en/project/EF16_026%2F0008432" target="_blank" >EF16_026/0008432: Cluster 4.0 - Methodology of System Integration</a><br>

Continuities

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

Publication year

2020

Confidentiality

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

Name of the periodical

CONSTRAINTS

ISSN

1383-7133

e-ISSN

1572-9354

Volume of the periodical

25

Issue of the periodical within the volume

3

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

19

Pages from-to

300-318

UT code for WoS article

000590007500001

EID of the result in the Scopus database

2-s2.0-85096046542