This paper presents a new formulation for the discrete space berth-scheduling problem at marine container terminals. This formulation reflects an environmentally friendly berth-scheduling policy with the objectives of (a) maximizing berth productivity by minimizing the total service time and delayed departures for all vessels and (b) minimizing the total emissions and fuel consumption for all vessels while in transit to their next port of call. A genetic algorithms–based heuristic is presented to solve the resulting problem, and computational examples are presented to evaluate the proposed berth-scheduling policy.