Road maintenance scheduling is inherently a multi-objective combinatorial optimisation problem: decision-makers must simultaneously minimise agency maintenance costs, maximise network pavement condition, minimise road user costs, and ensure equitable spatial distribution of maintenance resources — objectives that are fundamentally in conflict and cannot be simultaneously optimised by scalar single-objective methods. This paper presents a rigorous multi-objective genetic algorithm (GA) framework, specifically the Non-dominated Sorting Genetic Algorithm II (NSGA-II), for optimal scheduling of road maintenance activities across a network of 12 primary road corridors in South Sudan over a 5-year rolling planning horizon. The framework integrates: (i) a mechanistic pavement deterioration model calibrated to South Sudanese tropical climate and traffic conditions from 2021–2023 MoRB condition survey data; (ii) a comprehensive road user cost model incorporating vehicle operating costs (VOC) as a function of the International Roughness Index (IRI), travel time delay costs, and accident frequency-condition relationships derived from Sub-Saharan Africa data; (iii) a discrete chromosome encoding scheme representing four maintenance action types for each road segment in each planning year; and (iv) NSGA-II with non-dominated sorting, crowding distance assignment, and binary tournament selection to approximate the complete Pareto-optimal front. Results demonstrate that NSGA-II generates a Pareto front of 86 non-dominated solutions, spanning a total agency cost range of USD 1.82–7.20 million over 5 years. The balanced Pareto-knee solution (Solution B) achieves 36.5% cost savings relative to current MoRB practice while improving average network IRI from 5.8 to 4.1 m/km and reducing roa