Multiple inbound containers are piled up at the same stack in container terminals, which causes re-handles during the retrieval or carry-out process by road trucks. This inefficiency of the retrieval operation comes from the fact that the retrieval sequence of inbound containers is extremely uncertain and the retrieval sequence is not from the top to the bottom. This study discusses how the re-handling operations can be reduced by utilizing information on the estimated truck arrival times which may be collected from GPS in a smartphone owned by the truck driver. Algorithms for scheduling the pre-marshaling operation and determining the storage locations of re-handled containers are proposed. This study relaxed the constraint that a yard crane may relocate a container into another slots only in the same bay. The performances of the proposed algorithms are compared with each other by simulation studies.