Please use this identifier to cite or link to this item:
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
dynamic programming
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.
Electronic ISSN: 0974-0635
Appears in Collections:Department of Applied Informatics

Files in This Item:
File Description SizeFormat 
StochasticScheduling.pdfpreprint369,09 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.