Journal Home Online First Current Issue Archive For Authors Journal Information 中文版

Strategic Study of CAE >> 2009, Volume 11, Issue 9

Space contracting and decomposing algorithm based on Backbone

Shandong Institute of Standardization, Jinan 250014, China

Funding project:国家“八六三”计划资助项目(2006AA04A129) Received: 2008-03-13 Available online: 2009-09-14 16:25:02.000

Next Previous

Abstract

The scale and complexity of search space are important factors to decide the solving difficulty of an optimization problem. The information of solution space may lead searching to optimal solutions. Based on the known space structure of job shop scheduling problem, a space contracting and decomposing algorithm is proposed. This algorithm makes use of the good solutions found by searching algorithms, contracts the search space and decomposes it into one or several optimal regions combined with the concept of Backbone of combinatorial optimization solutions. And optimization of small-scale problems is carried out in optimal regions. Statistical analysis is not necessary before or through solving in this algorithm, and solution information is used to estimate the landscape of search space, which enhances the speed and solution quality. The experiments results testify the efficiency of this new algorithm.

References

[ 1 ] Slaney J, Walsh T.Backbones in optimization and approximation [ A] .In Proceedings of the 17th International Joint Conference on Artificial Intelligence ( IJCAI -2001 ) [ C] , 2001 : 254 -259

[ 2 ] Martin O C, Monasson R, Zecchina R.Statistical mechanics methods and phase transitions in combinatorial problems [ J ] . Theoretical Computer Science, 2001 , 265 ( 1 -2 ) : 3 -6 link1

[ 3 ] Matthew J S, Stephen F S.How the landscape of random job shop scheduling instances depends on the ratio of jobs to machines[ R] . Pittsburgh: School of Computer Science, Carnegie Mellon Univer- sity, CMU -CS -05 -162 , 2005

[ 4 ] Zeng Sanyou , Kang Lishan , Ding Lixin.A new method of evolu- tionary algorithm for mixed-integer nonlinear optimization problem [ J ] .Wuhan Univ ( Nat Sci Ed) , 2000 , 46 ( 5B) : 554 -558

[ 5 ] 谢胜利,黄强,董金祥.求解JSP的遗传算法中不可行调度的方案[J].计算机集成制造系统-CIMS,2002,8(11):902-906 link1

Related Research