Manual

Table of Contents

• About
• Introduction
• Acknowledgments
• Definitions
• Basic Use
  • Launch FLAP
  • Configure the Facility
  • Pick a Layout Heuristic
  • Pick a FLP Heuristic
  • Run the FLP Heuristic
  • View Output
• Facility
  • Configuration
  • Reinitialization
• Departments
  • Configuration
• Objective Function
• Layout Heuristics
  • Row-Fit
  • Banding
• Layout Types
  • Infeasible
  • Rejected
  • Accepted
  • Random Initial
• Department List Manipulation
  • Randomize Initial Order
  • FLP Heuristics
    • Two-Optimization
    • Simulated Annealing
  • Running a FLP Heuristic
• Information Retrieval
  • Facility Layout
  • Trial History
• Mouse Manipulation
  • Resizing the Facility
  • Moving Departments
• Java Related Issues
  • Random Numbers
  • Applet vs Application
  • Performance
• Links

About

Introduction

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 process.

Acknowledgments

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.

Definitions

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.

Facility

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.

Department

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.

Layout

The final placement of the departments in the facility using a layout heuristic.

Flow

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.

Cost

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.

Heuristic

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.

Trial

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.

Basic Use

• Launch FLAP

  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.

• Configure the Facility

  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.

• Pick a Layout Heuristic

  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.

• Pick a FLP Heuristic

  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 two-optimization.

• Run the FLP Heuristic

  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.

• View Output

  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 Euclidean distances.

Facility

• Configuration

  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 300.
  • Height, ranges from 100 to 1000. The default is 300.

  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 "Edit" menu.

  You can come back and edit any of the facility properties anytime by clicking on "Configure Facility..." under the "Edit" menu.

• Reinitialization

  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.

Departments

• Configuration

  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 configuration dialog.

  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 to 100.

  You can come back anytime to edit the department dimensions or flow values by clicking on "Configure Facility..." under the "Edit" menu.

Objective Function

Layout Heuristics

• Row-Fit

  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.

• Banding

  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 constant.

  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.

Layout Types

• Infeasible

  An infeasible layout is one that which the layout heuristic cannot place all departments in the confines of the facility. These layouts are automatically rejected by the FLP heuristics as their cost is infinite. Those departments that cannot fit entirely in the facility are drawn with a red color. If the department is not partially in the facility, it will not be drawn in the facility screen.

  Note: An initial layout, whether infeasible or not, is always accepted.

• Rejected

  A rejected layout is one which the current FLP heuristic has not chosen as a layout in the heuristic's goal of optimizing the cost. Each heuristic rejects layouts based on whatever guidelines the heuristic operates under. The layout may a feasible layout (one which all departments fit into the facility), however the cost may be larger than that seen in other feasible layouts. For example, two-optimization only accepts those layouts which lower the cost. Any layout whose cost is greater than those seen previously are rejected.

• Accepted

  Accepted layouts are layouts which a FLP heuristic has accepted in its efforts to find a decent cost layout. An accepted layout does not always have a lower cost than those seen previously. For example, simulated annealing accepts layouts with higher costs than previously seen within a certain degree. This is done to jump out of local minimums in the cost function.

• Random Initial

  The layout placed by randomly configuring the facility will be a random initial layout. This is accepted regardless of it being infeasible. Another way to get a random initial layout is by clicking on "Randomize Initial Layout" under the "Edit" menu.

Department List Manipulation

• Randomize Initial Order

  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.

• FLP Heuristics

  • Two-Optimiztion

    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

    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 the following:

    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 time.

    To configure the simulated annealing parameters, simply select "Simulated Annealing..." from the FLP menu. The following is a list of configurable parameters:

    • Starting temperature is the initial temperature which the hueristic uses. The default is 100. The feasible ranges is 1-10000.
    • 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.

• Running a FLP Heuristic

  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 left.

  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 selected.

Information Retrieval

• Facility Layout

  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.

• Trial History

  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 opened.

Mouse Manipulation

• Resizing the Facility

  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.

• Moving Departments

  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

Java Related Issues

• Random Numbers

  The random function used throughout FLAP is the Java API supplied random number generator. The first time the function is used, it is seeded with the current time (in milliseconds). The random function in the java.lang.Math class uses an instance of java.util.Random. An instance of this class is used to generate a stream of pseudorandom numbers. The class uses a 48-bit seed, which is modified using a linear congruential formula. (See Donald Knuth, The Art of Computer Programming, Volume 2, Section 3.2.1.)

• Applet vs Application

  The only part of FLAP that is really an applet is the window launching button. The rest of FLAP can either be run as a stand-alone application. To run FLAP as an application, you will need a JVM implementation installed on your computer. The Java Developers Kit contains a Java bytecode interpreter to run stand-alone Java applications. To run FLAP as a stand-alone application, download this tar file, unpack it and run "java FacilityFrame" (if using the JDK).

  The advantages to running FLAP as an application is speed, and the reduction of the delay of downloading all the Java class files whenever they are needed by the FLAP applet.

• Performance

  To run FLAP as fast as possible, make the window as small as possible, use a JIT JVM, run FLAP as a stand-alone application, don't look at the flow table, and buy a mainframe.

Links

• Facilities Layout Problem (FLP):
  • Plant Layout
  • Blocplan
• Nondeterministic-Polynomial Problems (NP-Complete):
  • Definition
• Two-Optimization/Local search/Pairwise exchange/N-change:
  • Local search
• Simulated Annealing:
  • Description
  • Description
• Operations Research:
  • Ops Research.com

Copyright © 1998 The Regents of the University of California