One of the more important problems in container terminal is related to the Container Stacking Problem. A container stack is a type of temporary store where containers await further transport by truck, train or vessel. The main efficiency problem for an individual stack is to ensure easy access to containers at the expected time of transfer. Since stacks are ’last-in, first-out’, and the cranes used to relocate containers within the stack are heavily used, the stacks must be maintained in a state that minimizes on-demand relocations. In this paper, we present a new domain-dependent planning heuristic for finding the best configuration of containers in a bay. Thus, given a set of outgoing containers, our planner minimizes the number of relocations of containers in order to allocate all selected containers in an appropriate order to avoid further reshuffles.