Parallel approaches to the facilities layout problem

1999 1999

Other formats: Order a copy

Abstract (summary)

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.

Indexing (details)

Operations research;
Industrial engineering;
Business community
0796: Operations research
0546: Industrial engineering
0310: Business community
Identifier / keyword
Social sciences; Applied sciences; Facilities layout; Heuristics; Improvement algorithms; Quadratic assignment
Parallel approaches to the facilities layout problem
St Sauver, Joseph Earl
Number of pages
Publication year
Degree date
School code
DAI-B 60/10, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
0599503920, 9780599503922
Richards, Larry
University of Oregon
University location
United States -- Oregon
Source type
Dissertations & Theses
Document type
Dissertation/thesis number
ProQuest document ID
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.