In this paper a new approach for the facility layout problem is presented. This approach combines genetic algorithms with linear programming to design the facilities on fixed aisle skeletons (spine shape, T shape, etc). For a given shape, a string in the genetic process gives the ordering of the departments. This ordering is used as input for a linear program that computes the fitness of that string as a potential solution to the problem. The genetic search then loops with its operators (selection, cross-over, mutation) correctly adapted. Some tests on problems taken in the literature are reported.