In this research, unequal area facility layout and relayout problems are studied under uncertainty. Two important notions, robustness to uncertainty and flexibility for future changes are introduced and incorporated into the usual objective of cost minimization under the assumption of dependent product demands. A tabu search heuristic procedure has been developed and successfully applied to the following versions of the stochastic facility layout problem. First, uncertainty is assumed only for product demand, i.e., volume uncertainty, and a method using a robustness measure which weights the quality of alternative layouts over a continuous metric of scenarios is proposed. Second, a simulation approach is proposed to deal with volume uncertainty and routing flexibility in the same layout design. Third, expansion flexibility is studied by assuming that the facility is able to expand towards one side (i.e., the last bay). Departments which are most likely to expand in the future are encouraged to be located in the last bay by penalizing layouts which do not locate them in the defined vertical border. A multi-objective tabu search approach has been proposed to solve the stochastic facility relayout problem, in which material handling cost and relayout cost are optimized. This procedure uniformly and randomly rotates the objective function between the two objectives of the problem in each step and, by doing so, eliminates the problems of weighting each objective and scaling the two objectives. The developed approach is flexible in handling various aspects of the stochastic facility relayout problem such as fixed portions (i.e., monuments), addition of new departments, and changes in the department and facility areas. Next, the developed multi-objective tabu search approach is adapted to solve some versions of the stochastic facility layout problem. The first problem is one with volume uncertainty where the robustness measure and the variance of the material handling cost are both optimized. The second problem considers expansion flexibility, where the robustness measure of the material handling cost and the expansion penalty are both optimized. This research is a novel in using tabu search for multi-objective optimization by alternating the objectives. Computational experiments show that both the TS and MOTS approaches are effective and tractable. CPU time per replication ranges from a few seconds to a few minutes.