A tabu search approach for the dynamic space allocation problem [electronic resource] /

by Jaramillo, Juan R.

TABU SEARCH APPROACH TO SOLVE THE DYNAMIC SPACE ALLOCATION PROBLEM Juan R. Jaramillo The dynamic space allocation problem (DSAP) is the assigning of activities to workspaces and idle resources to storage spaces while minimizing the total distance traveled by the resources during project duration. The inputs of the DSAP are: the schedule of project activities and the resources required to perform the activities, the layout of the floor plan, the capacity of the storage spaces, and the distances between locations. The output is a sequence of layouts containing the assignments of the activities and their resources to workspaces, as well as the idle resources to storage spaces. The DSAP is related to some known problems in the literature such as the quadratic assignment problem (QAP) and the dynamic facility layout problem (DFLP). The DSAP belongs to the family of combinatorial intractable problems, and only extremely small problems can be solved in reasonable time using exact methods. This research presents a mathematical formulation, a clustering algorithm based on group technology concepts and storage policies used to solve the storage layout problem, and a tabu search heuristic (TS) for solving the DSAP. In addition, a set of 72 test problems was developed to test these algorithms. Because of the complexity of the problem only 25 problems were solved to optimality. TS was tested by considering five different initial solutions: two solutions obtained by the clustering algorithm; two solutions generated by assigning activities and idle resources to locations, and one solution using a random pair-wise exchange algorithm. In general, the TS heuristic performed better when using the solutions obtained from the clustering algorithm as the initial solutions.