| 一种基于PFSP性质的深度优先搜索算法 |
| |
| 引用本文： | 李文超,严洪森.一种基于PFSP性质的深度优先搜索算法[J].控制与决策,2009,24(8). |
| |
| 作者姓名： | 李文超 严洪森 |
| |
| 作者单位： | 1. 东南大学,自动化学院,教育部复杂工程系统测量与控制重点实验室,南京,210096;江苏大学交通运输系,江苏,镇江,212013
2. 东南大学,自动化学院,教育部复杂工程系统测量与控制重点实验室,南京,210096 |
| |
| 基金项目： | 国家863计划专题基金项目，国家自然科学基金项目 |
| |
| 摘 要： | 三机以上同顺序Flow-shop问题(PFSP)是著名的NP完全问题.在充分利用PFSP自身特性的基础上,提出一种可变路径的深度优先搜索算法.该算法在搜索过程中根据需要采用两种不同邻域,在必要时将PFSP转化为一个指派问题,自动变更搜索路径,以避免陷入局部最优解.数值仿真实验表明,该算法对于大规模PFSP能取得良好的计算结果.
|
| 关 键 词： | 同序Flow-shop问题 指派问题 深度优先搜索 |
Depth-first search algorithm based on special properties of PFSP |
| |
| LI Wen-chao,YAN Hong-sen.Depth-first search algorithm based on special properties of PFSP[J].Control and Decision,2009,24(8). |
| |
| Authors: | LI Wen-chao YAN Hong-sen |
| |
| Affiliation: | 1a.School of Automation;1b.Key Laboratory of Measurement and Control of CSE;Ministry of Education;Southeast University;Nanjing 210096;China;2.Department of Transportation;Jiangsu University;Zhenjiang 212013;China. |
| |
| Abstract: | The permutation flow-shop problem(PFSP) with more than three machines is a famous NP-complete problem.A variable path depth-first search algorithm is proposed by making good use of the characteristic of PFSP.The algorithm searches in two different kinds of neighborhood and PFSP is transformed into an assignment problem when necessary to avoid being trapped in a local optimal solution.Numerical experiments show that the proposed algorithm has excellent performance for large-scale flow-shop problem. |
| |
| Keywords: | Permutation flow-shop problem Assignment problem Depth-first search |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
