Abstract: Bayesian network is a powerful tool used to uncertain inference and data analysis.The network inference is an important content of Bayesian network.The variable-elimination (VE) algorithm is used to simplify Bayesian network inference algorithm with the decomposition of the joint distribution.This paper proposed an elimination ordering algorithm based on the maximum deficiency search algorithm,making VEalgorithm execute in parallel,reducing the time complexity of the Bayesian network inference.