Metaheuristics for the Single Row Facility Layout Problem

Abstract

The single row facility layout problem (SRFLP) is the problem of arranging a set of facilities with given lengths on a line so as to minimize the weighted sum of the distances between all pairs of facilities. The problem is NP-hard and it has been used to model numerous practical applications such as the arrangement of rooms in hospitals, departments in office buildings or in supermarkets, arrangement of machines in flexible manufacturing systems, assignment of files to disk cylinders in computer storage, and design of warehouse layouts.

SRFLPs have been solved in the literature using exact and approximate techniques. Exact approaches have only been able to obtain optimal solutions for small sized instances with up to 42 facilities. Owing to the computational complexity, researchers have resorted to construction and improvement heuristics including neighborhood search techniques to solve large size instances. There are only a limited number of studies on the applications of these heuristics. This dissertation presents 15 different metaheuristic implementations to solve SRFLP instances of large sizes.

The first three implementations presented in the dissertation are single solution based heuristics. The first two, TS-2OPT and TS-INSERT are tabu search implementations. TS-2OPT uses a 2-opt neighborhood whereas TS-INSERT uses an insertion neighborhood to drive the local search. The dissertation presents book keeping techniques that help to reduce the time complexity of neighborhood search from O(n4) to O(n3), thereby speeding up an exhaustive search of the neighborhood by more than 90% over the existing implementations. We have used this speed up technique in all the metaheuristic implementations that use the 2-opt and insertion neighborhoods. The third single solution based implementation is a Lin-Kernighan neighborhood search based heuristic called LK-INSERT. The other 12 implementations presented in the dissertation are population based metaheuristics where a set of solutions is improved over generations to obtain good quality solutions. The first is a genetic algorithm implementation called GA-KG. The next four implementations are different versions of a scatter search algorithm based on the use of diversification generation method and the combination method. We present two diversification generation methods and two combination methods to develop scatter search implementations called SS-1A, SS-2A, SS-1P, and SS-2P. The last seven metaheuristics are path-relinking algorithms. A path-relinking algorithm starts with a set of good quality initial solutions and then tries to trace those paths between the solutions that have not been explored by the method that generated the initial good quality solutions. We use our existing metaheuristic implementations TS-2OPT, TS-INSERT, LK-INSERT, SS-1A, SS-2A, SS-1P, and SS-2P to generate the initial set of good quality solutions for our path-relinking algorithms PR-TS2O, PR-TSI, PR-LKI, PR-SS1A, PR-SS2A, PR-SS1P, and PR-SS2P respectively. These algorithms explore paths between good quality solutions by interpolating between two solutions at a time.

We performed computational experiments with our 15 different metaheuristic implementations on three sets of SRFLP benchmark instances with between 42 and 110 facilities. The first set consists of 20 instances comprising four sets of five instances each with 60, 70, 75, and 80 facilities. The second set of instances comprises seven sets of five instances each with 42, 49, 56, 64, 72, 81, and 100 facilities. The third set consists of three instances with 110 facilities each. Our metaheuristic implementations were able to improve upon the best known solutions for 33 of the 58 benchmark instances and matched the best known solutions for the remaining 25 instances. Among all the implementations presented in this dissertation, scatter search was found to uniformly output the best results for large size SRFLP instances although it took more time than some of the other heuristics studied in this work. We consider scatter search to be the heuristic of choice for solving large sized SRFLP instances.