The most common type of facility layout project is re-layout, which involves rearranging existing equipment in a facility. Project schedule development is an often overlooked yet critical portion of a facility re-layout project. When developing a re-layout project schedule, departments cannot be moved into their final locations until all previous occupants have moved. By incurring the cost of moving departments to temporary locations, it is possible to reduce the overall project duration. A two-criteria mixed-integer programming model is developed that finds the schedule minimizing department move costs subject to precedence constraints. An efficient algorithm uses this model to find all non-dominated time and cost solutions to the re-layout problem. Modifications to the basic model and algorithm handle resource constraints and turnaround space constraints. The algorithm and its modifications are demonstrated on an actual re-layout project.