Please use this identifier to cite or link to this item:
https://ruomo.lib.uom.gr/handle/7000/500
Title: | A Dynamic Programming Formulation of Scheduling Non-Deterministic Activities with Stochastic Durations |
Authors: | Refanidis, Ioannis |
Type: | Article |
Subjects: | FRASCATI::Natural sciences::Computer and information sciences |
Keywords: | Intelligent Calendar Applications scheduling dynamic programming heuristics |
Issue Date: | Sep-2011 |
Publisher: | Ceser publications |
Source: | International Journal of Artificial Intelligence |
Volume: | 7 |
Issue: | A11 |
First Page: | 1 |
Last Page: | 18 |
Abstract: | Scheduling personal activities is a non-deterministic stochastic constraint optimization problem. Activities may have discontinuous temporal domains and arbitrary stochastic duration distributions; they may be non-deterministic, that is they succeed with some probability; they have utilities, whereas several non-trivial constraints and preferences may hold over them, etc. In this article we propose a framework based on dynamic programming to model the problem and compute optimal policies. We also propose a heuristic-based relaxation of the dynamic programming model, trying to confront the curse of dimensionality. With the relaxed approach we obtain lower bounds of the overall utility in significantly less time. An empirical analysis compares the two approaches in terms of effectiveness and efficiency. |
URI: | http://www.ceser.in/ceserp/index.php/ijai/issue/view/173 https://ruomo.lib.uom.gr/handle/7000/500 |
Electronic ISSN: | 0974-0635 |
Appears in Collections: | Department of Applied Informatics |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
StochasticScheduling.pdf | preprint | 369,09 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.