Uvažování o čase v zahnízděných temporálních sítích s alternativami

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F08%3A00100903" target="_blank" >RIV/00216208:11320/08:00100903 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Temporal Reasoning in Nested Temporal Networks with Alternatives

Popis výsledku v původním jazyce

Temporal networks play a crucial role in modeling temporal relations in planning and scheduling applications. Temporal Networks with Alternatives (TNAs) were proposed to model alternative and parallel processes in production scheduling, however the problem of deciding which nodes can be consistently included in such networks is NP-complete. A tractable subclass, called Nested TNAs, can still cover a wide range of real-life processes, while the problem of deciding node validity is solvable in polynomialtime. In this paper, we show that adding simple temporal constraints (instead of precedence relations) to Nested TNAs makes the problem NP-hard again. We also present several complete and incomplete techniques for temporal reasoning in Nested TNAs.

Název v anglickém jazyce

Temporal Reasoning in Nested Temporal Networks with Alternatives

Popis výsledku anglicky

Temporal networks play a crucial role in modeling temporal relations in planning and scheduling applications. Temporal Networks with Alternatives (TNAs) were proposed to model alternative and parallel processes in production scheduling, however the problem of deciding which nodes can be consistently included in such networks is NP-complete. A tractable subclass, called Nested TNAs, can still cover a wide range of real-life processes, while the problem of deciding node validity is solvable in polynomialtime. In this paper, we show that adding simple temporal constraints (instead of precedence relations) to Nested TNAs makes the problem NP-hard again. We also present several complete and incomplete techniques for temporal reasoning in Nested TNAs.

Druh

D - Stať ve sborníku

CEP obor

JC - Počítačový hardware a software

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2008

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Znalosti 2008

ISBN

978-80-227-2827-0

ISSN

—

e-ISSN

—

Počet stran výsledku

12

Strana od-do

—

Název nakladatele

Vydavatelstvo Slovenskej technickej univerzity

Místo vydání

Bratislava

Místo konání akce

Bratislava

Datum konání akce

1. 1. 2008

Typ akce podle státní příslušnosti

CST - Celostátní akce

Kód UT WoS článku

—