With the advent of lean supply-chain management, cross-docking has become increasingly popular among shippers. Operating a cross-dock facility requires assigning receiving and shipping doors to trailers. The assignment determines the amount of freight handling within the cross-dock facility and therefore its efficiency. Due to the immense complexity of optimal formulations, dock-door assignment has been typically solved using heuristics. This paper discusses the existing approaches, and suggests a new optimal formulation, and a new heuristic approach for assigning cross-dock doors to trailers. In the process, the reader gains insight into several important issues related to dock door assignment.