Abstract: In order to promote the efficiency and decrease the cost in cigarette blend maintenance, a method based on non-negative matrix factorization (NMF) was proposed. The cigarette blend maintenance data of a certain tobacco corporation for three years were analyzed. The cigarette blend matrix was factorized into a base matrix and a matrix of single grade strips with NMF strategy to find out the rules of match between single grade strips suggested by the cigarette blend data, and further to recommend substituting schemes, then carried out the selection of single grade strip substitution and obtained the optimal single grade strip substituting scheme following a heuristic rule based on similarity. The results showed that:1) NMF cigarette blend maintenance model could retrieve the single grade strips which had been removed from the cigarette blend, and maintain blend integrity. 2) NMF model could recommend the single grade strips that formed a good match with other tobacco portions in the maintained blend. 3) Both one-versus-one substitution and many-versus-many substitution based on average similarity could effectively maintain the consistencies of sensory quality and smoke indices of the original cigarette brand.