Table of Contents
This manual explains how to use the Facilities Layout
Applet/Application (FLAP) for achieving decent solutions to
the Facilities Layout Probelm (FLP). NP-Complete and FLP theories are
not discussed in depth and a decent understanding of both concepts are
required before reading this manual. Also, prior knowledge of
optimization or approximization heuristics is needed. For more
information regarding such concepts please see the links section.
The FLAP is a program designed to facilitate the understanding and
comparison of various sophisticated Facility Layout Problem (FLP)
The FLP is a part of a well known family of problems called
NP-Complete. The idea is to place fixed area departments in a facility
of fixed dimensions. Generally, there are two ways to place these
departments, either keeping their length and width dimensions intact
or modifying their dimensions but keeping the area intact.
Using user-controlled animation, FLAP is a graphical gateway into the
visualization of various FLP heuristics. The user has full control
over the type of FLP problem to be solved, the data generated, the
process of solving the problem at hand, and the visualization of the
The algorithms in FLAP are based on work by Simchi-Levi, and Donaghey
& Pire. The row-fit layout technique is based on the "place and slide"
algorithm in Simchi-Levi's "Facilities Layout and Planning"
program. The banding technique is based on ideas first conceived in
Donaghey & Pire's "BLOCPLAN" program. Also, the simulated annealing
heuristic used in FLAP is based on the one found in Dr. Goldschmidt's
FLAP was designed and implemented by Sidarth Khoshoo under the direction,
and design of Professor Phil Kaminsky of the UC Berkeley Industrial
Engineering and Operations Research department.
The following are instructions to get a quick and easy start to FLAP:
- Facilities Layout Problem (FLP)
- One of many NP-Complete problems that grow exponentially with each
addition of a new item. The problem is simple, place fixed areas
departments in a fixed size container to minimize the overall cost.
- The container of the departments to be placed in a
layout. Represents the "office space" or maximum area used to place
the departments. In FLAP, this is the main screen under the menu
bar. The facility bounds are the edges of this main screen. The
facility's defined width and height are mapped to this blank screen.
- Represents a fixed area of variable width and length (depending on
the environment it is in). In FLAP, it is represented by a rectangle
in the facility.
- Department List
- The list of departments used for the Facilities Layout Problem
(FLP) heuristics and layout algorithms. The initial order of this list
can be random.
- The final placement of the departments in the facility using a
- The value of traveling from departments i to j. In FLAP, flows can
be randomly generated or user specified. They may not necessarily be
symmetric as in the random generation case.
- Objective Function
- This is the function used to determine a cost of a layout. The
distance type used for the calculation can be configured to be either
Euclidean or rectilinear.
- The cost FLAP uses to gauge the various heuristics is the sum of
the flow times the distance for all pairs of departments. The distance
used can either be Euclidean or rectilinear between the centers of the
departments in the virtual facility plane. The centers are the geometric
center of the rectangular departments. They can be specified to be
elsewhere within the department.
- An algorithm that reaches a reasonable solution to optimizing the
cost of a FLP layout. In FLAP, there are two types, FLP and
layout. The FLP goal is to optimize the department list in terms of
cost by choosing the optimal list order. Layout heuristics place the
departments in order of the department list. The word heuristic and
algorithm are used interchangeably in this manual.
- A single run of a FLP heuristic on the facility.
- Status Bar
- Contains useful user messages concerning heuristics and graphical
actions. Also prints the current cost during each trial.
Launch FLAP either as an applet from a Java enabled
web-browser or as an application from a command prompt using a
Java byte-code interpreter. As an applet, simply press the
"Launch Facilities Layout Applet" button.
After launching the FLAP main window, you need to configure
the facility. Under the "Edit" menu, click on the "Configure
Facility..." option. This will bring up a dialog window which
has some initial default values. If the "Random Dimensions and
Flows" option is selected, clicking "Next >" will configure
the facility with random dimensions for the Departments and
random flows for the flow matrix.
After configuring the facility, pick a layout heuristic for
the desired FLP problem to visualize. Under the "Heuristics"
menu, choose the "Layout" submenu. There are several
heuristics to choose from, the default is the row-fit layout.
After picking a layout heuristic, pick a FLP heuristic. Under
the "Heuristics" menu, choose the "FLP" submenu. There are
several FLP heuristics to choose from, the default is
Run the FLP heuristic by pressing the "Run" button below the
status bar. During the animation of the heuristic, you can
change the speed and possibly some other optimizing options in
the area next to the "Run" and "Pause" buttons.
After running several trials, you can view the output under
the "View" menu. The most important information is the best
cost for a trial. The objective function defaults to using
There are three basic facility properties to configure: the
size, the department list, and the flow matrix. To configure
the facility click on the "Configure Facility..." option under
the "Edit" menu. The first dialog you will see configures the
facility's number of departments, width, and height. There are
default values for basic use. Here are the ranges for the
three parameters and their integer default values:
- Number of departments, ranges from 1 to 50. The
default is 10.
- Width, ranges from 100 to 1000. The default is
- Height, ranges from 100 to 1000. The default is
Another way to configure the facility dimensions can be done
using the mouse, see below. In this dialog window there is
also an option to randomly generate the rest of the facility
data using the Java API pseudorandom number generator. This
simplifies the delay of creating large windows with many
entries for input. For example, a flow matrix for 30
departments will contain 870 entries and will take quite some
time to construct. If the random option is selected, the
departments will occupy 65% of the facility area.
The subsequent dialogs from the current one (if the random
option is not selected) configure various properties of the
departments. The initial order of the department list is the
order seen in the department dimensions dialog. It can be
randomized by clicking on "Randomize Initial Layout" under the
You can come back and edit any of the facility properties
anytime by clicking on "Configure Facility..." under the
To reinitialize the facility, that is to erase all current
data and properties, click "Reinitialize Facility..." under
the "Edit" menu. Note that this will erase all departmental
information as well.
The objective function determines the cost of a layout. The total cost
is simply the sum of the flow between two departments times the
distance between them. The distance can either be Euclidean or
rectilinear. This can be configured by choosing "Objective
Function..." from the Edit menu.
Departments can be configured while configuring the facility
by clicking on "Configure Facility..." under the "Edit"
menu. If the "Random Dimensions and Flows" option is selected,
the department properties will be randomly generated.
After configuring the facility properties, you can configure
the department dimensions by clicking "Next >" (if the random
option is not selected). A dialog will pop up with entries for
the number of departments to be created. You can enter your
own values or still randomly generate the dimensions by
clicking the "Random Dimensions" button. Only 65% of the total
facility area is used for the sum of the departments'
area. Each department width and height that is randomly
generated is determined using the golden ratio on the random
area determined. The centers of the departments (used for cost
calculation) are the geometric centers.
Each department will have an identifying number when drawn in
the facility screen. The dimensions for the department with a
specific id is the same as seen in the department dimension
The next property to determine is the flow matrix. After
configuring the dimensions for all the departments in the
department list, pressing "Next >" will pop up a dialog window
containing entries for the flow matrix.
Note: Generating the flow matrix is a VERY time consuming
expense. You will see a dialog that displays how much of the
flow matrix is constructed as it is constructed. It is advised
that you click on "Random Flows & OK" in the dialog containing
the department dimensions.
If you do want to enter the flow values between every pair of
departments, you can do so or have them randomly generated
again. At the bottom of the flow matrix dialog is the button
"Random Flows". This generates random flows for all entries in
the flow matrix. Clicking "OK" will configure the departments
as well as the facility. Flow values must be in the range of 1
You can come back anytime to edit the department dimensions or
flow values by clicking on "Configure Facility..." under the
The goal of the layout heuristics is to lay out the departments in the
facility in the order of the department list. Different layout
heuristics are applied to different types of FLP problems.
At the crux of the FLP is to manipulate the list of departments to
achieve an optimal cost.
The row-fit layout places departments in row that "fit" in the
facility. It goes through the department list and places
departments in a row (from left to right) until no more
departments can be placed in the current row. It stops when
placing the next one would be out of the bounds on the right
of the facility.
After placing a department, it tries to "push" it up as far as
possible. Note that this algorithm does not push the
departments left after pushing them up, therefore complete
packing is not done. This algorithm keeps the departments
length and width as is. Keep in mind a FLP
heuristic or the user may rotate the department.
The banding layout places departments in bands or rows as in
the row-fit layout. This heuristic, however, modifies the
dimensions of each department in the list so complete packing
is done. The area of each department, however, is kept
This heuristic creates a new facility whose area is determined
by the sum of the areas of the departments. The new facility's
dimensions are modeled after the original facility's
dimensions by using the aspect ratio of the outer
facility. Each department in a band has the same height but
each width is determined by the individual area. The sum of
the department widths in a band are constant for each band,
therefore keeping to the aspect ratio of the facility's
dimensions. This algorithm ensures that there is at least one
department per band. The algorithm uses the average area per
band as a guideline for which departments to place in a band.
To choose the number of bands for this layout heuristic, click
on "Banding..." under the "Layout" submenu of the "Heuristics"
menu. The default is 3. The lower bound on the number of bands
is 1, where all the departments would be placed in one
band. The upper bound is the number of departments in the
facility, where each department would be in a separate band.
Note: The banding layout heuristic disables the rotation
variant on any FLP algorithm.
The most readily available place for information about facility
related actions is on the status bar underneath the facility
screen. Check here frequently for messages about the results of
various user actions or heuristics.
Once the facility is configured with an initial department
list, you can randomize the order of the list. Many FLP
heuristics will yield different results depending on the order
of the initial list. You can randomize the order by clicking
on "Randomize Initial Layout" under the "Edit" menu.
Two-Optimization is a well known heuristic used in
many NP-Complete problems. It can be used to optimize
(lower the overall cost) on already low-cost layouts
determined by other FLP heuristics.
Basically, it performs a switch between every pair of
departments i and j. If a switch lowers the overall
cost it is accepted otherwise it is rejected. Also the
rotation part of two-optimization rotates all the
departments starting from i to the end of the list. If
rotation is enabled, a switch will be accepted on the
grounds of the rotation lowering the best
cost. Rotation can be selected by clicking on
"Two-Optimization..." under the FLP heuristics
menu. The default for is no rotation.
Simulated annealing is very similar to
two-optimization except certain layouts with worse
costs are accepted within a certain probability. This
heuristic requires much tuning to the particular
problem so deviating from the default values may not
be very fruitful unless you understand the specific
layout parameters. The probability of a worse layout
(in terms of the objective value) is accepted based on
randNum < e^(cost delta/temperature)
where the randNum is a random generated number between
0.0 and 1.0, and where the cost delta is the
difference between the current lower cost and the new
higher cost (negative), and where the temperature is
the current temperature somewhere in the range of the
starting and stopping temperatures.
The implementation in FLAP also has a rotation variant
as in the two-optimization. Please note that this
variant dramatically increases the heuristic's running
time. As in two-optimization, this variant switches all
department's dimension starting from the first
department, of the recently switched pair, to the end
of the department list.
Note: The default speed for simulated annealing of
execution is set to as fast as possible. Simulated
annealing usually takes longer than other
heuristics. You may, however, change the speed any
To configure the simulated annealing parameters,
simply select "Simulated Annealing..." from the FLP
menu. The following is a list of configurable
- Starting temperature is the initial
temperature which the hueristic uses. The
default is 100. The feasible ranges is
- Stopping temperature is the ending
temperature which the heuristics uses. The
default is 80. The feasible range is 1-10000.
- Percent reduction of temperature per
iteration is by how much to reduce the
temperature per each iteration. The default is
15%. The range is 1-100%.
- Iterations per phase or temperature is the
total number of loops attempts of accepting a
layout for a given temperature. The default is
100. The range is 1-1000.
Please note that rejected layouts will not be shown in
simulated annealing since the number of iterations
is very high. Only the accepted layouts are shown
after each phase.
All the necessary input controls for a FLP heuristic during
its trial can be found under the status bar. There are two
buttons, "Run" and "Pause" which can change to "Stop" and
"Resume" (respectively) depending on the situation. Initially,
when no FLP heuristic is running, only the "Run" button is
enabled. Press this and it will change to "Stop". Also the
"Pause" button will be enabled. During a heuristic, you can
either pause or stop the heuristic entirely. Stopping causes
the heuristic to reset. If you press "Run" again after
stopping, the heuristic will start from its beginning.
Note: Pressing stop should be done with caution. It leaves the
facility with the cheapest accepted layout.
Besides controlling when a heuristic can run, you can control
the speed of animation. This is helpful to find out exactly
what a heuristic is doing to the department list. By moving
the "bubble" or "thumb" of the scrollbar to the right, you can
speed the heuristic up or vice versa if you move it to the
Another animation option that you can control is the animation
of rejected layouts. Since many layouts will be rejected by
a heuristic, turning this off will only show the animation of
accepted layouts which may happen very infrequently. You can
select or deselect this by clicking on the "Show Rejected"
item under the status bar. By default, this option is
FLAP supports some basic mouse manipulation of the departments and
layout. Sometimes a heuristic will not find a single feasible solution
given specific facility data. Using one of the following can aid
heuristics to finding a lower cost.
Facility layout information can be retrieved by clicking on
the "Facility Info" item under the "View" menu. This will show
the current FLP heuristic, layout algorithm, facility
dimensions, and the current department list along with the
properties of each of the departments.
A dialog window will pop up with three buttons:
- Refresh, refreshes the data in the window.
- Clear, clears the data in the window.
- Dismiss, closes the dialog window.
You can view this information even while running a
heuristic. Pressing "Refresh" will take the current layout
(either rejected or accepted) that the FLP heuristic is
looking at. You are better off slowing down the heuristic or
pausing to get the information desired.
To view the costs determined by previous trials, click on
"Trial History" under the "View" menu. It tells you which
heuristics were used and the cost determined. Only
20 trials are stored, for each trial after that the oldest
trial will be thrown out.
Please see above (Information Retrieval | Facility Layout) for
a description of the buttons and actions of the dialog window
For more specific information about FLAP and Java, please see the
Besides resizing the facility in the facility configuration
dialog window, you can configure the facility by clicking on
the blue square (in the bottom right corner) in the facility
screen. Drag the mouse within the facility to decrease the
facility width and/or height or drag the mouse outside the
FLAP window to increase the facility width and/or height. You
should see blue lines showing the position of the mouse. This
action is only permissible while no FLP heuristic is running.
Note: Changing the facility dimensions while using the banding
layout causes the banding layout to use the new aspect ratio
of the facility width and height.
You can move an individual department to a location devoid of
other departments by simply clicking on a department and
dragging it to a new location. The cost of the layout will be
recomputed. If you start a FLP heuristic from a manipulated
layout, the heuristic uses the current layout as the current
best layout so no reversion will happen.
Using this action, you can pack the departments any which way
you desire. It may not be obvious, however, what a low-cost
solution is if the flows were randomly generated. You can use
this action to move an infeasible department (drawn in red)
into the facility if there is room.
Rotating a department is possible by clicking on the
department and pressing the 'r' key. This is helpful if the
current layout and subsequent layouts can benefit by rotating
and placing one department to a new location.
Note: This action does not modify the department list
- Facilities Layout Problem (FLP):
- Nondeterministic-Polynomial Problems (NP-Complete):
- Two-Optimization/Local search/Pairwise exchange/N-change:
- Simulated Annealing:
- Operations Research:
Back to the Facilities Layout Applet/Application
Copyright © 1998 The Regents of the University of California