In this article we formulate the berth allocation problem as a bi-objective mixed-integer programming problem with the objective to maximize berth throughput and reliability of the schedule under the assumption that vessel handling times are stochastic parameters, being a function of other stochastic parameters (that is, quay crane breakdowns, quay-to-yard transport vehicle productivity, yard congestion, and so on). A combination of an exact algorithm, a Genetic Algorithms-based heuristic and a Monte Carlo simulation are proposed as the solution approach for the resulting problem. Based on a number of simulation experiments, it is shown that the proposed modeling approach is effective and outperforms berth allocation solutions where reliability is not considered.