摘要
首先对有顺序约束指派问题进行分析。接着把这一特殊的指派问题用有向无回路图表示出来 ,从而使指派问题的求解转化为求解有向无回路图的划分问题。针对划分问题 ,构建了一种特殊的邻域结构 ,并设计出基于此邻域结构的模拟退火算法。最后 ,通过一个实例对算法的关键环节进行演示 ,通过另一个实例把模拟退火算法同禁忌搜索算法进行比较 ,结果表明该算法能够有效解决此类问题。
This paper analyzes an assignment problem with precedence relation among the elements. Then the assignment problem is illustrated with the directed acyclic graphs. The assignment problem becomes the partition problem of directed acyclic graphs. To the partition problem, the particular neighbourhood structure is constructed. A simulated annealing algorithm with the neighbourhood structure is devised. At last the algorithm was illustrated with an example and compared with tabu search algorithm in another example. The results indicate that the simulated annealing algorithm can effectively solve the assignment problem with precedence relation among the elements.
出处
《系统工程理论方法应用》
2002年第4期330-335,共6页
Systems Engineering Theory·Methodology·Applications
基金
铁道部科技发展项目 ( 2 0 0 0 X0 48-B)
