Layout planning for facilities with input and output points and shape constraints

Abstract

This dissertation focuses on layout planning for facilities with input and output points and shape constraints. We consider two types of decision problems for layout planning, arrangement of facilities within a floor and determination of locations of input and output points of the facilities. We develop efficient algorithms for two specific problems for each of the two types of decision problems. First, we consider a facility layout problem in which each facility has a predetermined shape and input and output points. In the problem, facilities are placed within a given floor and the spatial coordinates and the orientation of facility are to be determined. We give a mixed integer programming (MIP) model for the problem with the objective of minimizing the sum of rectilinear distances weighted by flow amounts between input and output points of the facilities. Using the MIP model, we develop a two-phase algorithm based on a construction phase and a improvement phase. Secondly, we consider a floorplanning problem in physical design of VLSI to place a set of blocks on a chip with the objective of minimizing area of the chip as well as total wire length. The block have different areas and their shapes are either fixed (predetermined) or flexible (to be determined). We use the sequence-pair suggested by Murata et al. (1996) to represent the topology of non-slicing floorplans and present two methods to obtain a floorplan from a sequence-pair. The two methods are implemented in a simulated annealing (SA) algorithm and used to find the best floorplan. Thirdly, we consider a problem of locating input and output (I/O) points of each department for a given block layout with the objective of minimizing the total distance of material flows between I/O points. Here, distances between the I/O points are computed as the lengths of the shortest path between the I/O points. We develop a procedure to eliminate dominated candidate positions of I/O points and present a linear program...