Abstract: According to the characteristic of permutation flow-shop scheduling problem, a variable neighborhood bee colony algorithm based on crossover and selection strategy is designed. Firstly, the NEH heuristic algorithm is added in the initial population stage to improve the quality of initial solution. At the start of the algorithm iteration, for the purpose of improving the diversity of solution, differential evolution operator is added to crossover and selection. In the local search stage, two variable neighborhood operations of swap and inverse are added to 50% optimal individuals to enhance the search ability of the algorithm. Selecting appropriate parameters through orthogonal experiments, and conducting simulation experiments on Car, Rec and Taillard standard test sets, the results show that the proposed algorithm is superior to other swarm intelligence algorithms compared with it. Finally, the job scheduling problem on the tire production line of a company is solved with the optimization objective of minimizing the makespan. The results are better than the compared algorithm, which further verify the feasibility of the proposed algorithm in solving PFSP.