Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Dynamic sequencing of tasks insSimple temporal networks with uncertainty
Ecole Nationale d'Ingénieurs de Tarbes, Tarbes, France.
Ecole Nationale d'Ingénieurs de Tarbes, Tarbes, France.
2001 (English)Conference paper, Published paper (Refereed)
Abstract [en]

Planning or scheduling systems that handle tasks with uncertain durations mightuse an extension of the Simple Temporal Network (STN) with a distinction between controllable and contingent variables and constraints. Temporal consistency is then redefined in terms of Dynamic Controllability, which means the ability to decide the precise timing of tasks only at execution time, depending on observations made, and still satisfying all no constraints. This property has been recently proven to be checkable in polynomial time through a simple path consistency-like algorithm. In this paper, we are interested in using such a model in scheduling applications, in which tasks may compete for the same resource, and should thus be sequenced. Such constraints make the problem NP-hard, and cannot be directly expressed in an STN. In the presence of uncertainty, one might also wish to postpone task sequencing until execution time. This paper provides the characterization of such a Dynamic Sequencing ability. Then, we propose an incomplete checking method still relying on the STNU for the sake of temporal reasoning efficiency, adding further filtering techniques to account for sequencing constraints.

Place, publisher, year, edition, pages
2001. p. 39-48
National Category
Computer Sciences
Research subject
Computer and Systems Science
Identifiers
URN: urn:nbn:se:oru:diva-29133OAI: oai:DiVA.org:oru-29133DiVA, id: diva2:622591
Conference
Constraints and Uncertainty (CP workshop)
Available from: 2013-05-22 Created: 2013-05-22 Last updated: 2018-01-11Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

http://www.cs.ucc.ie/~kb11/CP2001Uncertainty/Final/vidal.pdf

Search in DiVA

By author/editor
Bidot, Julien
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 34 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf