基于约束满足问题的产品拆卸序列规划

中国机械工程 ›› 2010, Vol. 21 ›› Issue (17): 2058-2062.

基于约束满足问题的产品拆卸序列规划

宋守许;胡迪;高洋;杨明;张雷

合肥工业大学,合肥,230009

出版日期:2010-09-10 发布日期:2010-09-20
基金资助:
国家自然科学基金资助项目(50735006)；国家科技重大专项(2008BAC46B01)
National Natural Science Foundation of China（No. 50735006）;
National Science and Technology Major Project ( No. 2008BAC46B01)

Product Disassembly Sequence Planning Based on Constraint Satisfaction Problems

Song Shouxu;Hu Di;Gao Yang;Yang Ming;Zhang Lei

Hefei University of Technology, Hefei, 230009

Online:2010-09-10 Published:2010-09-20
Supported by:

National Natural Science Foundation of China（No. 50735006）;
National Science and Technology Major Project ( No. 2008BAC46B01)

摘要/Abstract

摘要：

分析了产品拆卸序列规划与约束满足问题的对应关系,在基于混合图的产品拆卸模型基础上,将产品拆卸序列规划转化为一类约束满足问题。以回溯算法为基础,给出了基于约束满足问题的产品拆卸序列规划求解流程和算法。通过一个简化的洗碗机门体实例说明了方法的可行性和有效性。



关键词:

约束满足问题, 混合图, 拆卸约束图, 拆卸序列规划;回溯算法

Abstract:

By analyzing the corresponding relationship between product disassembly sequence planning and constraint satisfaction problems, a product disassembly sequence planning was mapped into a constraint satisfaction problems based on product disassembly hybrid graph model. Then the processes and algorithms of the product disassembly sequence planning were given based on constraint satisfaction problems using backtracking algorithm. Finally, a simplified dishwasher door example was given to show the feasibility and effectiveness of the proposed method.

Key words: constraint satisfaction problem, hybrid graph, disassembly constraint graph, disassembly sequence planning, backtracking

中图分类号:

TH122

宋守许, 胡迪, 高洋, 杨明, 张雷.

基于约束满足问题的产品拆卸序列规划

[J]. 中国机械工程, 2010, 21(17): 2058-2062.

SONG Shou-Hu, HU Di, GAO Xiang, YANG Meng, ZHANG Lei.

Product Disassembly Sequence Planning Based on Constraint Satisfaction Problems

[J]. China Mechanical Engineering, 2010, 21(17): 2058-2062.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.cmemo.org.cn/CN/

http://www.cmemo.org.cn/CN/Y2010/V21/I17/2058

参考文献

[1]Zussman E, Zhou M C. A Methodology for Modeling and Adaptive Planning of Disassembly Processes[J]. IEEE Transactions on Robotics and Automation, 1999,15(1): 190-194.
[2]李玉玲[1],赵树恩[1].基于Petri网的产品拆卸过程规划[J].农业机械学报,2006,37(7):138-141.
[3]章小红[1],李世其[1],王峻峰[1].基于蚁群算法的产品拆卸序列规划方法[J].计算机辅助设计与图形学学报,2007,19(3):387-391.
[4]薛俊芳[1,2],邱长华[1],向东[3].基于蚁群优化算法的目标拆卸序列规划[J].计算机辅助设计与图形学学报,2007,19(6):742-747.
[5]Wang Hui, Xiang Dong, Duan Guanghong. A Genetic Algorithm for Product Disassembly Sequence Planning [J]. Neurocomputing, 2008, 71: 13-15.
[6]吴昊[1],左洪福[1].基于改进遗传算法的产品拆卸序列规划[J].中国机械工程,2009,10(6):699-703.
[7]张秀芬[1,2],张树有[1].基于粒子群算法的产品拆卸序列规划方法[J].计算机集成制造系统,2009,15(3):508-514.
[8]Minton S, Johnston M D, Laird P. Minimal Conflicts.. a Heuristic Repair Method for Constraint Satisfaction and Scheduling Problems [J]. Artificial Intelligence, 1992, 58(1/3): 161-206.
[9]Selman B, Kautz H. Domain-- independent Extensions to GSAT : Solving Large Structured Satisfiability Problems[C]//Proc. UCAI- 93. Charnbery,France, 1993: 290-295.
[10]Glover F, Laguna M. Tabu Search. Modern Heuristics for Combinatorial Problems [ M]. Oxford, Black- well Scientific Publishing, 1993.
[11]Jing Rong Li, Li Pheng Khoo, Shu Beng Tor. Generation of Possible Multiple Components Disassembly Sequence for Maintenance Using a Disassembly Constraint Graph[J]. International Journal of Production Economics, 2006, 102(1) : 51-65.
[12]薛俊芳[1,2],邱长华[1],向东[3].在Pro/E中自动生成零件拆卸优先约束矩阵[J].工程图学学报,2007,28(3):24-29.
[13]王峻峰[1],付艳[1],彭涛[1],方建新[1],李世其[1].装配／拆卸干涉矩阵的自动生成技术[J].机械科学与技术,2008,27(7):955-958.
[14]Tsang E. Foundations of Constraint Satisfaction[M]. London.. Academic Press, 1993.
[15]孙吉贵[1,2],高健[1,2],张永刚[1,2].一个基于最小冲突修补的动态约束满足求解算法[J].计算机研究与发展,2007,44(12):2078-2084.