Part of the work of operating and managing a multiproduct pipeline is preparing batch schedules. If the number of products conveyed by the pipeline is large, the number of stations is large and the scheduling horizon is long, it will be difficult to draft feasible batch schedules and the work of optimizing batch schedules is more difficult. The accuracy and the computational time of optimization algorithms directly determine whether the algorithms can be applied in reality. This paper proposes the parallel Simulated Annealing (SA) algorithm to optimize delivery schedules of a single-source and multiple-depots products pipeline. Parallel SA can simultaneously generate several new solutions in every iteration, which can improve the efficiency of every iteration. Parallel SA adopts a two-stage framework to construct every new solution. The first stage uses the method of constructing a neighborhood of a variable to adjust the old delivery schedule, which is further fine-tuned based on a heuristic rule about the proper connection of delivery operations in the second stage. The effectiveness of the parallel SA algorithm is illustrated based on a real-world multiproduct pipeline, which provides bases for applying the proposed algorithm for production.