An extended event graph with negative places and tokens for time window constraints
An extended event graph with negative places and tokens for time window constraints
复制标题
DOI：
10.1109/tase.2005.851236
复制
发表时间：
2005-10
影响因子：
5.6
通讯作者：
Tae-Eog Lee;Seong-Ho Park
中科院分区：
文献类型：
--
作者：
Tae-Eog Lee;Seong-Ho Park
我们将持有时间为负的库所和令牌数量为负的令牌引入计时事件图中，以建模和分析时间窗口约束。对负事件图(NEG)这种扩展的事件图，我们扩展了使能和激发规则。我们基于NEG为其活动的电路，给出了充要条件，即对于每个跃迁，都存在一个无限序列的可行激发周期。我们证明了令牌数为正的电路的最小周期时间与最大电路比相同。我们还证明了当存在令牌数为负的电路时，最大周期时间是有界的，并且与这类电路的最小电路比率相同。给出了一个半导体制造中带有晶圆停留时间约束的机器人组合设备的调度实例。实践者注意-现代人造系统的调度和控制问题，包括自动化制造系统，如半导体制造的集群式工具、微电路和实时软件系统，通常被建模为离散事件系统。这样的系统通常对某些事件的计时有严格的时间限制。我们的结果可用于判断是否存在满足所有时间约束的可行调度，计算可行周期时间的范围，以及确定具有最小周期时间的稳定调度。通过使用可行条件，还可以调整系统配置、任务时间和任务顺序，使系统在满足时间约束的同时满足目标周期时间。这种做法已经被用于实际的丛式工具工程。在实现时间受限系统的实时调度器和控制器方面，我们得到了更多的结果。
We introduce places with negative holding times and tokens with negative token counts into a timed event graph in order to model and analyze time window constraints. We extend the enabling and firing rules for such an extended event graph named a negative event graph (NEG). We develop necessary and sufficient conditions based on the circuits for which the NEG is live, that is, an infinite sequence of feasible firing epochs exist for each transition. We prove that the minimum cycle time is the same as the maximum circuit ratio of the circuits with positive token counts. We also show that when there exists circuits with negative token counts, the maximum cycle time is bounded and the same as the minimum circuit ratio of such circuits. A scheduling example for a robot-based cluster tool with wafer residency time constraints for semiconductor manufacturing is explained. Note to Practitioners-Scheduling and control problems for modern man-made systems, including automated manufacturing systems such as cluster tools for semiconductor manufacturing, microcircuits, and real-time software systems, are usually modeled as discrete event systems. Such systems often have strict time constraints on timings of some events. Our results can be used for identifying whether there can be a feasible schedule that satisfies all time constraints, computing the range of the feasible cycle times, and determining a steady schedule with the minimum cycle time. By using the feasibility condition, we also can accommodate the system configuration, the task times, and the task sequence so that the system can satisfy the time constraints while meeting the target cycle time. Such practice is already used for real cluster tool engineering. We have more results on implementing a real-time scheduler and controller for time constrained systems.