Stability of scheduling with random processing times on one machine

Paweł Rajba, and Mieczysław Wodecki. "Stability of scheduling with random processing times on one machine." Applicationes Mathematicae 39.2 (2012): 169-183. <http://eudml.org/doc/279871>.

@article{PawełRajba2012,
abstract = {We consider a strong NP-hard single-machine scheduling problem with deadlines and minimizing the total weight of late jobs on a single machine ($1 || ∑\{w_iU_i\}$). Processing times are deterministic values or random variables having Erlang distributions. For this problem we study the tolerance to random parameter changes for solutions constructed according to tabu search metaheuristics. We also present a measure (called stability) that allows an evaluation of the algorithm based on its resistance to random parameter changes. Our experiments prove that random model solutions are more stable than the deterministic model ones.},
author = {Paweł Rajba, Mieczysław Wodecki},
journal = {Applicationes Mathematicae},
keywords = {scheduling; weight tardiness; Erlang distribution; tabu search},
language = {eng},
number = {2},
pages = {169-183},
title = {Stability of scheduling with random processing times on one machine},
url = {http://eudml.org/doc/279871},
volume = {39},
year = {2012},
}

TY - JOUR
AU - Paweł Rajba
AU - Mieczysław Wodecki
TI - Stability of scheduling with random processing times on one machine
JO - Applicationes Mathematicae
PY - 2012
VL - 39
IS - 2
SP - 169
EP - 183
AB - We consider a strong NP-hard single-machine scheduling problem with deadlines and minimizing the total weight of late jobs on a single machine ($1 || ∑{w_iU_i}$). Processing times are deterministic values or random variables having Erlang distributions. For this problem we study the tolerance to random parameter changes for solutions constructed according to tabu search metaheuristics. We also present a measure (called stability) that allows an evaluation of the algorithm based on its resistance to random parameter changes. Our experiments prove that random model solutions are more stable than the deterministic model ones.
LA - eng
KW - scheduling; weight tardiness; Erlang distribution; tabu search
UR - http://eudml.org/doc/279871
ER -