Incremental Computation of Resource-Envelopes in Producer-Consumer Models
Incremental Computation of Resource-Envelopes in Producer-Consumer Models
复制标题
生产者-消费者模型中资源包络的增量计算
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
T. K. Satish Kumar
中科院分区：
文献类型：
--
作者：
T. K. Satish Kumar
交错计划和调度采用了通过在搜索过程中定期注意调度约束来扩展部分计划的思想。用于分析调度和资源消耗约束的技术之一是计算所谓的资源包络。然后可以使用这些信封来导出有效的启发式规则，以指导搜索好的计划和/或最优地调度给定的计划。然而，这种方法成功的关键是能够在作出部分承诺时增量地重新计算信封。生产者-消费者模型中的资源包络问题如下：有向图G=有X={X0，X1…Xn}作为对应于事件的节点集合(X0是世界的开始节点，并且假定被设置为0)，E作为它们之间的有向边的集合。用简单的时间信息[Lb(E)，Ub(E)]注释E中的有向边e=，该简单时间信息指示一致的调度必须在调度Xi(Lb(E)≤Ub(E))之后的Lb(E)和Ub(E)秒之间调度Xj。一些节点(事件)在物理上对应于资源的生产或消耗，并且用指示其对给定资源的生产或消耗的水平的实数r(Xi)进行注释。假设S对所有活动都有一个一致的时间表，时间t的总生产(消费)由Ps(T)(Cs(T))给出。目标是构造包络函数g(T)=max{S是一致调度}(Ps(T)-Cs(T))和h(T)=min{S是一致调度}(Ps(T)-Cs(T))。在本文中，我们提供了计算g(T)和h(T)的有效增量算法，以及在任意给定时刻t实际实现它们的灵活的一致调度。
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 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 G= has X={X0,X1…Xn} as the set of nodes corresponding to events (X0 is the "beginning of the world" node and is assumed to be set to 0) and E as the set of directed edges between them. A directed edge e= in E is annotated with the simple temporal information [LB(e), UB(e)] indicating that a consistent schedule must have Xj scheduled between LB(e) and UB(e) seconds after Xi is scheduled (LB(e)≤UB(e)). Some nodes (events) correspond physically to production or consumption of resources and are annotated with a real number r(Xi) 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 Ps(t) (Cs(t)). The goal is to build the envelope functions g(t)=max{s is a consistent schedule}(Ps(t)- - Cs(t)) and h(t)=min{s is a consistent schedule}(Ps(t) - Cs(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.