Dynamic planning and scheduling algorithm based on temporal constraint network

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.