Abstract: In order to rationalize cigarette brand change in production, cigarette production scheduling was optimized with genetic algorithm. On the basis of production conditions, the relations between the duration of brand change and machine adjustment was analyzed; and genetic algorithm was modified by increasing probability of mutation and probability of crossover to prevent the algorithm from falling into the local optimization. The modified genetic algorithm could quickly find out the global optimal solution, give out the shortest time needed for brand change and the optimal production schedule. The simulation results showed that the optimal production schedule could save time by 240 min. An experiment carried out according to the optimal simulation schedule indicated that the time consumed for brand change was shortened by 105 min, and the production efficiency was promoted effectively. This method provides technical supports for perfecting cigarette production plan and optimizing scheduling strategy.