Parallel approaches to the facilities layout problem
The facilities layout problem (FLP) can be described: “Assign N departments to N equal sized work cells, minimizing the cost of moving materials between departments given an inter-departmental flow matrix.”
This problem is computationally hard, with complexity proportional to ∼N!. Thus, rather than focusing on optimal solution methods, research has focused on heuristics that yield good (if not strictly optimal) solutions within acceptable computational envelopes. The most notable FLP heuristic is Armour and Buffa's CRAFT (1963), which takes an initial (possibly random) layout and then does selective sequential pairwise or threeway exchanges of adjacent or equal sized departments to drive down the layout's total cost for problems N < 40. </p>
We restrict our focus to moderately large FLP's (MLFLP's) where N = 100. For this size problem, multiple departments can move simultaneously during an iteration since enough other departments remain fixed to provide “layout continuity.” By moving multiple departments simultaneously during an iteration, we reduce the total number of iterations (and total CPU time) required to arrive at a final solution.
Working with MLFLP's, we can also vary the maximum distance each department moves during an iteration (the “move radius”), balancing the ability to quickly move to a distant cell against potential disruption to the layout's continuity. For “small” radii, even if departments aren't exactly where they were expected to be, they will still be “close enough” for the purposes of the other departments, and even a modest relaxation of the move radius can dramatically reduce the iteration count.
We also show that our FLP heuristic may be ported to a distributed parallel architecture machine (a “Beowulf cluster”) for additional speed improvements.
The distributed approach of this heuristic shifts attention from an unrealistic overarching decision making criterion to a more realistic one recognizing the primacy of department-level goals.
0546: Industrial engineering
0310: Business community