Stability of scheduling with random processing times on one machine

Volume 39 / 2012

Paweł Rajba, Mieczysław Wodecki Applicationes Mathematicae 39 (2012), 169-183 MSC: Primary 90C59. DOI: 10.4064/am39-2-5

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

Authors

  • Paweł RajbaInstitute of Computer Science
    University of Wrocław
    50-383 Wrocław, Poland
    e-mail
  • Mieczysław WodeckiInstitute of Computer Science
    University of Wrocław
    50-383 Wrocław, Poland
    e-mail

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image