Abstract: This paper studied a milk run based cross docking scheduling problem with uncertain transportation time. By describing problem formally, a mixed integer linear programming is built under uncertain situation. A twostage heuristic and a tabu search algorithm are presented. Numerical experiments under small and large scale situations are given to verify efficiencies of the proposed heuristics.