The in-Port vessel Scheduling and tug Assignment Problem (PSAP) aims at determining the schedule for a given set of vessel movements, and their escorting tugs within a port. In this paper, we propose, compare and discuss models and algorithms for determining solutions for the PSAP. Specifically, we introduce two mathematical programming models and we derive from them four heuristics: two based on the time limited execution of a commercial solver, and two on a receding horizon principle. Finally, we present the results of a computational study aiming at assessing the performance of the considered algorithms on problem instances obtained from the Port of Venice, a medium size Italian port. The receding horizon based heuristics show good performances. They provide good quality solutions for the majority of the instances within a reasonable computational time.