Sequential and Parallel Algorithms to Solve the Dynamic Facility Layout Problem
TimeTuesday, July 246:30pm - 8:30pm
DescriptionWe implement sequential and parallel algorithms to solve the Dynamic Facility Layout Problem. (DFLP). Applications of this problems occur in the design of flexible manufacturing systems, scheduling of jobs to machines, and planning of layouts for hospital and healthcare facilities. DFLP relates to find an optimal assignment of facilities or units to locations that minimizes the total cost of material handling and relocation over a time horizon. The DFLP is an extension to the Quadratic Assignment Problem, an NP-hard combinatorial optimization problem of practical and theoretical importance due to its complexity. The solution methods contrasted are: (1) the Dijkstra algorithm and (2) a linear programming solution to the network model. The first method is parallelized using OpenMP.
For problems with more than 15 facilities, the algorithms were run under two variants since not all the permutations of feasible arrangements can be input directly to the network model. In variant one, the permutations are selected randomly. In the second one, permutations are sorted based on the material handling cost for each time period and only the best subsets of them are selected. The experimental phase is performed in the Stampede Cluster at the Texas Advance Computing Center using 24 instances artificially generated by a previous author. Speed up for the parallelized version of the Dijkstra algorithm vs. the serial version is significant. Accuracy of our two best solutions is superior to three out of the five previous works included in the comparison.