We consider the facility layout problem with machine capacities (and hence multiple machines of each type) and random demand. We develop a very efficient heuristic allowing us to find good solutions to the stochastic case whenever good solutions can be found for the corresponding deterministic problem with uncapacitated machines of the same dimension. Hence, this problem represents a case where a specific deterministic model, even when solved heuristically, produces a very good solution to a stochastic model.