In this paper, we address an important practical situation, namely where the usual replenishment lead time (when the supplier's production facility is operating) is a random variable and the supplier shuts down for an interval of known duration (for maintenance, vacation, etc.) each year. The demand rate is constant and any demand when out of stock is assumed to be lost. Under such circumstances we develop a heuristic procedure to decide when to initiate replenishment as well as the associated order-up-to-levels. Through the use of simulation (which accurately estimates the average costs per unit time), the heuristic is shown to perform excellently in a selection of small size problems when one can find the optimal solution. For a large number of problems of more realistic size, the use of simulation reveals that the heuristic achieves substantial cost savings when compared with a simpler, baseline approach. The heuristic itself does not require the use of simulation. The sensitivity of total expected costs to various parameters (such as the length of the shutdown interval and characteristics of the lead time distribution) is discussed.