Stability of scheduling with random processing times on one machine

• Autorzy: Paweł Rajba , Mieczysław Wodecki
• Języki publikacji: EN

Abstrakty

EN

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.

Kategorie tematyczne

• 90C59: Approximation methods and heuristics

• Wydawca: Institute of Mathematics Polish Academy of Sciences
• Czasopismo: Applicationes Mathematicae
• Rocznik: 2012
• Tom: 39
• Numer: 2
• Strony: 169-183

Daty

wydano

2012

Twórcy

autor

Paweł Rajba

• Institute of Computer Science, University of Wrocław, 50-383 Wrocław, Poland

autor

Mieczysław Wodecki

• Institute of Computer Science, University of Wrocław, 50-383 Wrocław, Poland

Identyfikatory

DOI

10.4064/am39-2-5