Geodesic
Stability of scheduling with random processing times on one machine
Paweł Rajba 1   ; Mieczysław Wodecki 1
1 Institute of Computer Science University of Wrocław 50-383 Wrocław, Poland
Applicationes Mathematicae, Tome 39 (2012) no. 2, pp. 169-183 Cet article a éte moissonné depuis la source Institute of Mathematics Polish Academy of Sciences

Voir la notice de l'article

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\parallel \sum{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.
DOI : 10.4064/am39-2-5
Keywords: consider strong np hard single machine scheduling problem deadlines minimizing total weight late jobs single machine parallel sum processing times deterministic values random variables having erlang distributions problem study tolerance random parameter changes solutions constructed according tabu search metaheuristics present measure called stability allows evaluation algorithm based its resistance random parameter changes experiments prove random model solutions stable deterministic model

Paweł Rajba  1   ; Mieczysław Wodecki  1

1 Institute of Computer Science University of Wrocław 50-383 Wrocław, Poland 
@article{10_4064_am39_2_5,
     author = {Pawe{\l} Rajba and Mieczys{\l}aw Wodecki},
     title = {Stability of scheduling with
 random processing times on one machine},
     journal = {Applicationes Mathematicae},
     pages = {169--183},
     year = {2012},
     volume = {39},
     number = {2},
     doi = {10.4064/am39-2-5},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.4064/am39-2-5/}
}
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
SP  - 169
EP  - 183
VL  - 39
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.4064/am39-2-5/
DO  - 10.4064/am39-2-5
LA  - en
ID  - 10_4064_am39_2_5
ER  - 
%0 Journal Article
%A Paweł Rajba
%A Mieczysław Wodecki
%T Stability of scheduling with
 random processing times on one machine
%J Applicationes Mathematicae
%D 2012
%P 169-183
%V 39
%N 2
%U http://geodesic.mathdoc.fr/articles/10.4064/am39-2-5/
%R 10.4064/am39-2-5
%G en
%F 10_4064_am39_2_5
Paweł Rajba; Mieczysław Wodecki. Stability of scheduling with
 random processing times on one machine. Applicationes Mathematicae, Tome 39 (2012) no. 2, pp. 169-183. doi: 10.4064/am39-2-5

Cité par Sources :