DagSemProc.05031.12.pdf
- Filesize: 131 kB
- 4 pages
Document
Getting rid of stochasticity: applicable sometimes
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 5031
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2005-06-17
Cite As Get BibTex
Han Hoogeveen and Marjan Van den Akker. Getting rid of stochasticity: applicable sometimes. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)
https://doi.org/10.4230/DagSemProc.05031.12
Abstract
We consider the single-machine scheduling problem of minimizing the number of late jobs. This problem is well-studied and well-understood in case of deterministic processing times. We consider the problem with stochastic processing times, and we show that for a number of probability distributions the problem can be reformulated as a deterministic problem (and solved by the corresponding algorithm) when we use the concept of minimum success probabilities, which is, that we require that the probability that a job complete on time is `big enough'. We further show that we can extend our approach to the case of machines with stochastic output.
Subject Classification
Keywords
- Scheduling
- sequencing
- single machine
- number of late jobs
- stochastic processing times
- minimum success probability
- dynamic programming unreliable machines
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads