In container terminals, heavier containers are loaded onto a ship before lighter ones to keep the ship balanced. To achieve efficient loading, terminal operators usually classify incoming export containers into a few weight groups and group containers belonging to the same weight group in the same stack. However, since the weight information available at the time of the container’s arrival is only an estimate, a stack often includes containers belonging to different weight groups. This mix of weight groups necessitates extra crane works or container re-handlings during the loading process. This paper employs a simulated annealing algorithm to derive a more effective stacking strategy to determine the storage locations of incoming containers of uncertain weight. It also presents a method of using machine learning to reduce occurrences of re-handling by increasing classification accuracy. Experimental results have shown that the proposed methods effectively reduce the number of re-handlings than the traditional same-weight-group-stacking (SWGS) strategy.