Abstract: In order to further optimize the production flow, the production scheduling problem in tobacco primary processing was mapped with TSP (Traveling Salesman Problem). Optimization models were established separately on the basis of 3 conditions (without time constraint, with time constraint and multi-line production), and the models were solved with the modified genetic algorithm. The production data of 16 batches of 4 brands in Ningbo Cigarette factory were introduced into the established models, and the calculated results were compared with the actual production data. The results showed that a number of batch production scheduling plans could be obtained via optimization methods, and all the obtained plans were in compliance with the time window requirements. Comparing with the actual production data, the number of brand switching decreased obviously. The optimization effects of the methods are remarkable and their calculation efficiency meets production requirements. This method provides a support for promoting the lean management level in tobacco primary processing.