Incremental computation of resource-envelopes in producer-consumer models

From Semantic Portal Wiki

{{#vardefine:category|Publication}}{{#vardefine:templatename|i.publication}}{{#vardefine:package|smwbp_instance_templates}}

Edit

[[abstract::Interleaved planning and scheduling employs the idea of extending partialplans by regularly heeding to the scheduling constraints during search.One of the techniques used to analyze scheduling and resource consumptionconstraints is to compute the so-called {\it resource-envelopes}. Theseenvelopes can then be used to derive effective heuristics to guide thesearch for good plans and/or dispatch given plans optimally. The key tothe success of this approach however, is in being able to recompute theenvelopes incrementally as and when partial commitments are made. Theresource-envelope problem in producer-consumer models is as follows: Adirected graph $\mathcal{G}=\langle \mathcal{X}, \mathcal{E} \rangle$ has$\mathcal{X}=\{X_0, X_1 \ldots X_n\}$ as the set of nodes corresponding toevents ($X_0$ is the ``beginning of the world node and is assumed to beset to $0$) and $\mathcal{E}$ as the set of directed edges between them. Adirected edge $e=\langle X_i, X_j \rangle$ in $\mathcal{E}$ is annotatedwith the simple temporal information $[LB(e), UB(e)]$ indicating that aconsistent schedule must have $X_j$ scheduled between $LB(e)$ and $UB(e)$seconds after $X_i$ is scheduled ($LB(e) \le UB(e)$). Some nodes (events)correspond physically to production or consumption of resources and areannotated with a real number $r(X_i)$ indicating their levels ofproduction or consumption of a given resource. Given a consistent schedule$s$ for all the events, the total production (consumption) by time $t$ isgiven by $P_s(t)$ ($C_s(t)$). The goal is to build the envelope functions$g(t) = max_{\{s \hspace{0.05cm} \mbox{is a consistent schedule}\|]]

Reference: {{#vardefine:pagename|incremental computation of resource-envelopes in producer-consumer models }}

1. [[]]

bibtex

{{#vardefine:pagename|Incremental computation of resource-envelopes in producer-consumer models }}{{#vardefine:key| }}

abstract: Interleaved planning and scheduling employs the idea of extending partialplans by regularly heeding to the scheduling constraints during search.One of the techniques used to analyze scheduling and resource consumptionconstraints is to compute the so-called {\it resource-envelopes}. Theseenvelopes can then be used to derive effective heuristics to guide thesearch for good plans and/or dispatch given plans optimally. The key tothe success of this approach however, is in being able to recompute theenvelopes incrementally as and when partial commitments are made. Theresource-envelope problem in producer-consumer models is as follows: Adirected graph $\mathcal{G}=\langle \mathcal{X}, \mathcal{E} \rangle$ has$\mathcal{X}=\{X_0, X_1 \ldots X_n\}$ as the set of nodes corresponding toevents ($X_0$ is the ``beginning of the world node and is assumed to beset to $0$) and $\mathcal{E}$ as the set of directed edges between them. Adirected edge $e=\langle X_i, X_j \rangle$ in $\mathcal{E}$ is annotatedwith the simple temporal information $[LB(e), UB(e)]$ indicating that aconsistent schedule must have $X_j$ scheduled between $LB(e)$ and $UB(e)$seconds after $X_i$ is scheduled ($LB(e) \le UB(e)$). Some nodes (events)correspond physically to production or consumption of resources and areannotated with a real number $r(X_i)$ indicating their levels ofproduction or consumption of a given resource. Given a consistent schedule$s$ for all the events, the total production (consumption) by time $t$ isgiven by $P_s(t)$ ($C_s(t)$). The goal is to build the envelope functions$g(t) = max_{\{s \hspace{0.05cm} \mbox{is a consistent schedule}\

download:

• paper:
• slides:

(P_s(t) - C_s(t))$ and $h(t) = min_{\{s \hspace{0.05cm} \mbox{is aconsistent schedule}\}} (P_s(t) - C_s(t))$. In this paper, we provideefficient incremental algorithms for the computation of $g(t)$ and $h(t)$,along with flexible consistent schedules that actually achieve them forany given time instant $t$. }}