There are a variety of problems in the label printing production process, such as multi-variety, small batch, high-degree customization and uncertainties in some working procedures. Aiming at these problems, a flexible job-shop scheduling model with the goal of minimizing the maximum completion time was established, and an improved Genetic Algorithm (GA) was proposed. First of all, integer coding was adopted based on the standard genetic algorithm. Secondly, the roulette method was used in the selection operation stage, and the convergence of the algorithm was guaranteed by introducing the elite solution retention strategy. Finally, dynamic adaptive crossover and mutation probabilities were proposed to ensure that the algorithm optimized in a wide range to avoid prematurity in the early stage, and the algorithm converged timely to ensure that the excellent individuals obtained previously were not destroyed in the later stage. In order to verify the feasibility of the proposed improved genetic algorithm, the Ft06 benchmark example was first used to compare the proposed algorithm with the standard genetic algorithm. The results showed that the optimal solution of the improved genetic algorithm (55 s) was better than the optimal solution of the standard genetic algorithm (56 s), and the number of iterations of the improved genetic algorithm was significantly better than that of the standard genetic algorithm. Then, through the 8×8, 10×10 and 15×10 standard examples of Flexible Job-shop Scheduling Problem (FJSP), the effectiveness, stability and optimization performance of the algorithm were verified. On all of three standard test examples, the improved genetic algorithm obtained the optimal solution in a short time. Finally, when the proposed algorithm was used to solve the production scheduling problem of the label printing job-shop, the processing efficiency was increased by 50.3% compared to the original one. Therefore, the proposed improved genetic algorithm can be effectively applied to solve the production scheduling problem of label printing job-shop.