Facility layout problems, i.e., optimal placement of production units in a plant, become an inseparable part of manufacturing systems design and management. They are known to greatly impact the system performance. This paper proposes a new formulation of the facility layout problem where workstations are to be placed into a hall. Within the hall, obstacles and communications can be defined. Each workstation can have multiple handling spaces attached to its sides and oriented links can be defined between workstations. A new evolutionary-based approach to solve this facility layout problem is proposed in single-objective as well as multi-objective variant. The method is experimentally evaluated on a set of standard VLSI floorplanning benchmarks as well as on the data set created specifically for the proposed facility layout problem. Results show the method is both competitive to the state-of-the-art floorplanners on the VLSI benchmarks and produces high-quality solutions to the proposed facility layout problem.