Dynamic planning and scheduling algorithm based on temporal constraint network

Rui Xu*, Xiao Fei Xu, Ping Yuan Cui

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)188-194
Number of pages7
JournalJisuanji Jicheng Zhizao Xitong/Computer Integrated Manufacturing Systems, CIMS
Volume10
Issue number2
Publication statusPublished - Feb 2004
Externally publishedYes

Keywords

  • Dynamic algorithm
  • Planning and scheduling
  • Shortest path
  • Temporal constraint network

Fingerprint

Dive into the research topics of 'Dynamic planning and scheduling algorithm based on temporal constraint network'. Together they form a unique fingerprint.

Cite this