全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

基于时间约束网络的动态规划调度算法

, PP. 0-0

Keywords: 时间约束网络,规划调度,动态算法,最短路径

Full-Text   Cite this paper   Add to My Lib

Abstract:

为解决与时间有关的规划调度问题,提出了一种基于时间约束网络的动态算法。该算法与传统的计算最短路径方法不同,它只需计算受到新增约束影响的局部网络。同时,给出了算法的最坏时间复杂性,并进行了证明。最后,以Job-Shop调度系统为例进行了仿真验证,结果表明,该算法可快速地判断约束网络的一致性,并计算每个工序的最早可能开始时间。

References

[1]  ALLEN J F. Maintaining knowledge about temporal intervals[J]. Communications of the ACM, 1983, 26(11):832-843.
[2]  ALLEN J. Planning as temporal reasoning[A]. KR91: Principles of Knowledge Representation and Reasoning[C]. Cambridge,MA,USA:Morgan Kaufmann Publishers,1991.3-14.
[3]  BADALONI S, BERATI M. Hybrid temporal reasoning for planning and scheduling[A]. Proceedings of 3rd Workshop on Temporal Representation and Reasoning (TIME96)[C]. Los Alamitos,CA:IEEE,1996. 39-44.
[4]  VRBSKY S V,TOMIC S.Satisfying temporal consistency constraints of real-time databases[J]. The Journal of Systems and Software, 1999, 45(1):45-60.
[5]  MUSCETTOLA N, NAYAK P P,PELL B,WILLIAMS B.Remote agent: to boldly go where no AI system has gone before[J]. Artificial Intelligence, 1998,103(1-2):5-47.
[6]  DECHTER R, MEIRI I, PEARL J. Temporal constraint network[J]. Artificial Intelligence,1991,49(1-3):61-95.
[7]  SCHWALB E, VILA L. Temporal constraints:a survey[J].Constraints:An International Journal,1998, 3(2-3):129-149.
[8]  SCHWALB E, DECHTER R. Processing disjunctions in temporal constraint networks[J]. Artificial Intelligence,1997,93(1-2):29-61.
[9]  DUAN Fanding. A fast algorithm for shortest-path - SPFA[J]. Journal of Southwest Jiaotong University, 1994,29(2):207-212(in Chinese).[段凡丁.关于最短路径的SPFA快速算法[J].西南交通大学学报, 1994,29(2):207-212.]
[10]  ZWICK U. All pairs shortest paths in weighted directed graphs - exact and almost exact algorithms[A]. Proceedings of the 39th IEEE Annual Symposium on Foundations of Computer Science (FOCS98)[C].Los Alamitos,CA:IEEE,1998.310-319.
[11]  CHEN Enhong, XUE Hanhong. On solving constraint satisfaction based job-shop scheduling problems[J]. Journal of Software, 1998,9(2):946-948(in Chinese).[陈恩红, 薛瀚宏. 基于约束满足的Job-Shop 调度问题求解方法研究[J]. 软件学报, 1998, 9(2):946-948].
[12]  WEISSER P, COCHRAN S,LANE S,et al. Modeling temporal relations in task hierarchies for job shop scheduling[A].Proceedings of the Second International Conference on Computer Integrated Manufacturing[C]. Troy, New York:Rensselaer Polytechnic Institute,1990.39-46.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133