Abstract: Because there is an analogous structure between the distillation separation sequence and the binary tree,the distillation separation sequence can be described as a binary tree data structure, and then, by using the method of graph theory, the change mechanism of neighboring split position in binary tree is built, as a result,a kind of effective evolutional neighborhood structure has been constructed.Adaptive mechanism and parallel technology are introduced into tabu search algorithm.This means that according to memorial frequency information the tabu length and the number of candidates are adaptively adjusted, and multitask parallel technology is realized through the arrangement of the search assignment.The numeric experiment shows that the adaptive and parallel tabu search can solve successfully large-scale distillation separation sequence synthesis problem.