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

摘要/Abstract

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

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

Abstract: For solving the temporal-relating planning and scheduling problem, a dynamic algorithm is proposed based on temporal constraints network (TCN). Unlike the traditional work in all shortest path algorithm, this algorithm only computes the partial network influenced by the new introduced constraint rather than the whole network. The worst time complexity of the algorithm (O (2ne)) is given and proved. Taken the typical Job-Shop scheduling problem as an example, the simulation system is designed to verify the proposed algorithm, and the result has shown that it can quickly judge the consistence of the constraints and work out the earliest start time of the operator.

Key words: temporal constraint network, planning and scheduling, dynamic algorithm, shortest path

中图分类号:

TP18

徐瑞，，徐晓飞，崔平远. 基于时间约束网络的动态规划调度算法[J]. .

XU Rui,, XU Xiao-fei, CUI Ping-yuan. Dynamic Planning and Scheduling Algorithm Based on Temporal Constraint Network[J]. .

参考文献

［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.

[1]	董宗然,林焰. 基于最短路径快速算法的船舶管路自动敷设方法[J]. 计算机集成制造系统, 2014, 20(12): 2962-2972.
[2]	石源，莫蓉，刘红军，彭维，万能. 面向模型局部搜索的最短路径集最优匹配方法[J]. , 2012, 18(02): 0-0.
[3]	孙凯，杨根科，潘常春. 设备参数变化的批量轧制调度问题模型与算法[J]. , 2011, 17(07): 0-0.
[4]	杨育，杨洁,，王小磊，梁宗雁，梁学栋. 基于发明问题解决理论的客户协同产品创新设计方法[J]. , 2010, 16(01): 0-0.
[5]	窦建平，戴先中，孟正大，李俊. 基于图论的可重构制造系统单零件流水线构形优化[J]. , 2010, 16(01): 0-0.
[6]	段翰聪,, 唐晖, 卢显良, 周旭, 赵志军. 分布式协作系统快速可靠组播算法[J]. , 2007, 13(09): 0-0.
[7]	周永华，陈禹六，赵天奇. 多方案经营过程模型选择策略[J]. , 2001, 7(12): 0-0.