2.9 SRFLP with Departments of Equal Length
27
solution and hence do not help to tighten the relaxation. This is true for most classes
of inequalities of interest. It is therefore essential to have a way to identify which
inequalities within each class will be useful for a given relaxation. This process is
called separation.
For a given class of inequalities, a separation algorithm takes a given point P as
input and gives one of two possible outputs:
• one inequality in the given class that is not satisfied by P , or
• the conclusion that no such inequality exists, i.e., the point P satisfies all the
inequalities in the class.
Note that not all separation algorithms are efficient; we are particularly interested
in those that run in polynomial time. Effective separation algorithms are an essential
component of the most successful approaches for solving instances of the SRFLP
and other facility layout problems. For small values of n, the classes of inequalities
that we have presented can often be separated by full enumeration because the
inequalities are all given explicitly. Given a current solution, it is straightforward to
check whether each inequality is violated, and if so, to compute the amount of the
violation. Some of the most violated inequalities can then be added to the relaxation.
For larger values of n, either heuristic or more sophisticated separation algorithms
must be used.
2.9 SRFLP with Departments of Equal Length
We now consider the special case of the SRFLP in which all the departments
have the same length. This is also called the equidistant SRFLP or the singlerow equidistant facility layout problem (SREFLP) because it involves placing the
departments in a given set of equally spaced locations along a straight line. We can
assume without loss of generality that i = 1 for all departments i, and all the
models in this chapter can be directly applied to the SREFLP.
The minimum-backtracking row layout problem (MBRLP) is a version of the
SREFLP that arises in the sequencing of machines along an automated production
line. The quantity of workflow from one machine to another is a directed quantity,
and the ideal sequencing is one in which there is no need for materials to flow
backwards along the production line. This is often not possible, and we wish to
find the sequencing of machines that minimizes the total distance backtracked. This
turns out to be an SREFLP with a different objective function.
The formal statement of the MBRLP is as follows. Given n departments and
directed flows f ij from i to j for i, j = 1, . . . , n, where f ij and f ji are different
in general and f ii = 0, the objective is to find a one-to-one assignment of the
departments to n locations equally spaced along a straight line so as to minimize
the total weighted backward distance, where each pairwise backward distance is
weighted by its corresponding flow.
27
solution and hence do not help to tighten the relaxation. This is true for most classes
of inequalities of interest. It is therefore essential to have a way to identify which
inequalities within each class will be useful for a given relaxation. This process is
called separation.
For a given class of inequalities, a separation algorithm takes a given point P as
input and gives one of two possible outputs:
• one inequality in the given class that is not satisfied by P , or
• the conclusion that no such inequality exists, i.e., the point P satisfies all the
inequalities in the class.
Note that not all separation algorithms are efficient; we are particularly interested
in those that run in polynomial time. Effective separation algorithms are an essential
component of the most successful approaches for solving instances of the SRFLP
and other facility layout problems. For small values of n, the classes of inequalities
that we have presented can often be separated by full enumeration because the
inequalities are all given explicitly. Given a current solution, it is straightforward to
check whether each inequality is violated, and if so, to compute the amount of the
violation. Some of the most violated inequalities can then be added to the relaxation.
For larger values of n, either heuristic or more sophisticated separation algorithms
must be used.
2.9 SRFLP with Departments of Equal Length
We now consider the special case of the SRFLP in which all the departments
have the same length. This is also called the equidistant SRFLP or the singlerow equidistant facility layout problem (SREFLP) because it involves placing the
departments in a given set of equally spaced locations along a straight line. We can
assume without loss of generality that i = 1 for all departments i, and all the
models in this chapter can be directly applied to the SREFLP.
The minimum-backtracking row layout problem (MBRLP) is a version of the
SREFLP that arises in the sequencing of machines along an automated production
line. The quantity of workflow from one machine to another is a directed quantity,
and the ideal sequencing is one in which there is no need for materials to flow
backwards along the production line. This is often not possible, and we wish to
find the sequencing of machines that minimizes the total distance backtracked. This
turns out to be an SREFLP with a different objective function.
The formal statement of the MBRLP is as follows. Given n departments and
directed flows f ij from i to j for i, j = 1, . . . , n, where f ij and f ji are different
in general and f ii = 0, the objective is to find a one-to-one assignment of the
departments to n locations equally spaced along a straight line so as to minimize
the total weighted backward distance, where each pairwise backward distance is
weighted by its corresponding flow.