Shared storage policy allows more flexible use of space than that allowed by the dedicated storage policy. This paper addresses duration-of-stay based shared storage in an automated storage/retrieval system. An integer programming model is formulated to obtain optimal solution for small and medium sized problems. A graph based heuristic approach is developed to solve large scale problems in reasonable time. The computational results indicate that the approach is very effective in finding high quality solutions, in terms of both total travel time and space requirements.