From Tetherless World Wiki
Citation: T. K. Satish Kumar. (2003) Incremental Computation of Resource-Envelopes in Producer-Consumer Models. In Proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming (CP 2003), September,2003.
| Publication inproceedings ( Edit )
|
| type | InProceedings
|
| bibtype | inproceedings
|
| Bibtex basics
|
| author | T. K. Satish Kumar
|
| title | Incremental Computation of Resource-Envelopes in Producer-Consumer Models
|
| booktitle | Proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming (CP 2003)
|
| year | 2003
|
| month | September
|
| Bibtex more
|
| Access Paper
|
| abstract | [[abstract::Interleaved planning and scheduling employs the idea of extending partial plans by regularly heeding to the scheduling constraints during search.One of the techniques used to analyze scheduling and resource consumption constraints is to compute the so-called {\it resource-envelopes}. These envelopes can then be used to derive effective heuristics to guide the search for good plans and/or dispatch given plans optimally. The key to the success of this approach however, is in being able to recompute the envelopes incrementally as and when partial commitments are made. The resource-envelope problem in producer-consumer models is as follows: A directed 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. A directed edge $e=\langle X_i, X_j \rangle$ in $\mathcal{E}$ is annotated with the simple temporal information $[LB(e), UB(e)]$ indicating that a consistent 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 are annotated with a real number $r(X_i)$ indicating their levels of production or consumption of a given resource. Given a consistent schedule$s$ for all the events, the total production (consumption) by time $t$ is given 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}\|Interleaved planning and scheduling employs the idea of extending partial plans by regularly heeding to the scheduling constraints during search.One of the techniques used to analyze scheduling and resource consumption constraints is to compute the so-called {\it resource-envelopes}. These envelopes can then be used to derive effective heuristics to guide the search for good plans and/or dispatch given plans optimally. The key to the success of this approach however, is in being able to recompute the envelopes incrementally as and when partial commitments are made. The resource-envelope problem in producer-consumer models is as follows: A directed 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. A directed edge $e=\langle X_i, X_j \rangle$ in $\mathcal{E}$ is annotated with the simple temporal information $[LB(e), UB(e)]$ indicating that a consistent 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 are annotated with a real number $r(X_i)$ indicating their levels of production or consumption of a given resource. Given a consistent schedule$s$ for all the events, the total production (consumption) by time $t$ is given 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}\]]
|
(P_s(t) - C_s(t))$ and $h(t) = min_{\{s \hspace{0.05cm} \mbox{is a consistent schedule}\}} (P_s(t) - C_s(t))$. In this paper, we provide efficient incremental algorithms for the computation of $g(t)$ and $h(t)$,along with flexible consistent schedules that actually achieve them for any given time instant $t$.
|paper url=
|pdf url=
|ps url=
|slides url=
|paper=
|pdf=
|ps=
|slides=
}}
| KSL Technical Report ID: KSL-03-08
|
