Aiming at the discrete job-shop logistics scheduling problem with Automated Guided Vehicles (AGVs), a multi-objective discrete job-shop logistics scheduling optimization model is constructed to minimize the time penalty cost of the transfer task and the total travel distance of the vehicle. A multi-objective hybrid Variable Neighborhood Search Genetic Algorithm (VNSGA-II) based on Pareto optimization is designed. Based on the genetic algorithm, the Pareto stratification and crowding-degree calculation method of NSGA-II are used to evaluate the population to achieve multi-objective optimization. The elite individuals are protected by adding the optimal memory to improve the optimization ability of the algorithm and avoid falling into the local optimum. Moreover, the local optimization ability of the variable neighborhood search algorithm is used to design six random neighborhood structures in light of the model features in this paper, thereby solving the optimal value. For a lower cost, the insertion neighborhood based on the critical AGV and the exchange neighborhood adjustment based on the critical transfer task are proposed. Finally, with a discrete job-shop logistics scheduling problem as an example, VNSGA-II, Nondominated Sorting Genetic Algorithm II (NSGA-II), and Strong Pareto Evolutionary Algorithm 2 (SPEA2) are adopted respectively. The results show that VNSGA-II can get a better Pareto solution set, which verifies the effectiveness and feasibility of the algorithm.