A neighborhood search (NS) algorithm is proposed for the multi-objective flow shop scheduling problem, aiming to construct a scheduling model that optimizes processing time and total tardiness. This method efficiently explores the solution space by generating new solutions through the swapping of job sequences. Starting from an initial solution in the population, candidate solutions are iteratively generated by altering job sequences and are evaluated using fitness values. As the optimization proceeds, the algorithm gradually converges toward the global optimum. A dominance relationship function is employed to assess the relative superiority of solutions by calculating their distances to reference points across multiple objective dimensions, thus enabling effective quality evaluation. To ensure systematic exploration of the solution space, this study employs a solution generation strategy based on Hamming distance. By constructing the shortest Hamming paths between solutions, this approach preserves desirable characteristics. It also effectively probes unexplored regions of the solution space, thus enhancing the algorithm’s capability to locate the global optimum. Experimental results from 20 test cases of varying scales show that the proposed NS algorithm outperforms the traditional genetic algorithm (GA) and the non-dominated sorting genetic algorithm (NSGA-II) in multi-objective optimization, demonstrating its effectiveness and advantages.