The cross-docking center is an intermediate node in a distribution network, it presents a great advantage especially for perishables as it provides fast customers deliveries without storage in between or less than 24 hours. Receiving shipments from different suppliers, sorting them according to their characteristics, and transferring them to different demand points in the minimum standby time requires many operations. Reaching this goal leads to optimize a combination of a hybrid flowshop scheduling problem during the cross-docking process from inbounding to outbounding and a Vehicule Routing Problem (VRP) from the outbound trucks of the cross-docking center to the customers. The makespan is the objective to be minimized in this research. To solve such original problem, two matheuristics are proposed where each of them is based on two phases that combine the strengths of the linear programming and the heuristic algorithms. Indeed, we determine a set of variables in the first phase which will be used in the second phase to find the makespan value. Finally, computational experiments on instances from the literature and newly generated are reported and show the good performance of the proposed methods to solve large instances in a very competitive running time.