Considering employing the electric vehicles to deliver parts to stations for assembly lines based on point-to-point delivery strategy，an improved multi-objective cuckoo search algorithm is presented. First，the scheduling problem of material delivery is formally described，and the number of electric vehicles and the maximum handling time are selected as the components of the objective function based on overall consideration of power limit and on-time delivery requirements. After that，a fusion encoding mechanism reflecting directly the vehicle and sequence of the delivery is put forward in the algorithm. Then，a task allocation rule is designed to generate the initial solutions，and Gaussian mutation and elite selection strategy are incorporated into the search process based on chaotic dynamic step size to improve global search ability of the algorithm as well as the quality of the solutions. Furthermore, two local search operators are proposed to enhance the algorithm′s ability for deep optimization. Finally，the simulation results verify the feasibility and effectiveness of the proposed scheduling algorithm.