One of the most important issues in port connectivity refers to the availability of accessible waterways and their traffic management. This puts a lot of pressure especially into capacity restricted transport corridors, where their inefficient use may not only result in a loss of the port competitiveness but also in an increase of the volume of ship emissions polluting the environment. In this context, the Waterway Ship Scheduling Problem is proposed; its goal is to schedule incoming and outgoing ships through different waterways for accessing or leaving the port in such a way that the ships’ waiting time is minimized. This objective allows, on the one hand, to avoid bottlenecks or congestions through scheduling the waterway traffic, and on the other hand, reduce vessel emissions while they are waiting at the anchorage either for entering or leaving. A mathematical model and heuristics are proposed. Real scenarios based on the Yangtze Delta (Shanghai) are tackled for assessing the performance of the heuristic and the improvement upon real-world terminal operations.