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 language | English |
---|---|
Pages (from-to) | 188-194 |
Number of pages | 7 |
Journal | Jisuanji Jicheng Zhizao Xitong/Computer Integrated Manufacturing Systems, CIMS |
Volume | 10 |
Issue number | 2 |
Publication status | Published - Feb 2004 |
Externally published | Yes |
Keywords
- Dynamic algorithm
- Planning and scheduling
- Shortest path
- Temporal constraint network