Algorithms for adjusting shapes of departments in block layouts on the grid-based plane

Many existing algorithms for facility layout problems give block layouts in which departments have irregular shapes. This paper presents algorithms to modify shapes of departments in a given block layout with such departments. With the suggested algorithms, a given block layout is converted into a new block layout in which departments are of rectangular shapes without a significant change in the relative positions of the departments. Results of computational experiments show that the suggested algorithms give block layouts that are at least as good as original layouts in terms of the total transportation distance.