一种基于PFSP性质的深度优先搜索算法
来源期刊：控制与决策2009年第8期
论文作者：李文超 严洪森
文章页码：1203 - 2421
关键词：同序Flow-shop问题;指派问题;深度优先搜索;
摘 要：三机以上同顺序Flow-shop问题（PFSP）是著名的NP完全问题.在充分利用PFSP自身特性的基础上,提出一种可变路径的深度优先搜索算法.该算法在搜索过程中根据需要采用两种不同邻域,在必要时将PFSP转化为一个指派问题,自动变更搜索路径,以避免陷入局部最优解.数值仿真实验表明,该算法对于大规模PFSP能取得良好的计算结果.
李文超1,2,3，严洪森1,2
1. 东南大学自动化学院2. 东南大学教育部复杂工程系统测量与控制重点实验室3. 江苏大学交通运输系
摘 要：三机以上同顺序Flow-shop问题（PFSP）是著名的NP完全问题.在充分利用PFSP自身特性的基础上,提出一种可变路径的深度优先搜索算法.该算法在搜索过程中根据需要采用两种不同邻域,在必要时将PFSP转化为一个指派问题,自动变更搜索路径,以避免陷入局部最优解.数值仿真实验表明,该算法对于大规模PFSP能取得良好的计算结果.
关键词：同序Flow-shop问题;指派问题;深度优先搜索;
