Gap Reduction Techniques for Online Stochastic Project Scheduling
| Autor: | Pascal Van Hentenryck, Grégoire Dooms |
|---|---|
| Rok vydání: | 2008 |
| Předmět: |
Nonlinear Sciences::Chaotic Dynamics
Mathematical optimization Nonlinear Sciences::Adaptation and Self-Organizing Systems Computer science Distributed computing Reservation ComputerApplications_COMPUTERSINOTHERSYSTEMS Stochastic optimization Computer Science::Digital Libraries Gap reduction Scheduling (computing) |
| Zdroj: | Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems ISBN: 9783540681540 CPAIOR |
| DOI: | 10.1007/978-3-540-68155-7_8 |
| Popis: | Anticipatory algorithms for online stochastic optimization have been shown very effective in a variety of areas, including logistics, reservation systems, and scheduling. For such applications which typically feature purely exogenous uncertainty, the one-step anticipatory algorithm was shown theoretically to be close to optimal when the stochasticity of the problem, measured by the anticipatory gap, is small. This paper studies the behavior of one-step anticipatory algorithms on applications in which the uncertainty is exogenous but the observations are endogenous. It shows that one-step anticipatory algorithms exhibit a much larger anticipatory gap and proposes a number of gap-reduction techniques to address this limitation. The resulting one-step anticipatory algorithms are shown to outperform significantly the state-of-the-art dynamic-programming approach on an online stochastic resource-constrained project scheduling application. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|