Scheduling of construction machinery customer service involves service vehicle, servicer, and engineering machinery. This study establishes a model with the goal of minimizing the total completion time under the premise that the service resources are sufficient and an engineer assigns at most one task, combining with path length, skill matching, service time, and other factors. Considering the combination of service vehicle, service person, and engineering machinery as a special three-part graph matching problem, a hybrid genetic algorithm solution based on the minimum weight matching of bipartite graphs is proposed. The roulette selection operator and dynamic mutation probability of the embedded elite strategy are introduced. The superiority of the algorithm is proved by a large-scale case study.