GRASP with path relinking for the single row facility layout problem

The single row facility layout problem (SRFLP) is an NP-hard problem that consists of finding an optimal arrangement of a set of rectangular facilities (with equal height and different lengths), placing them next to each other along a line. The SRFLP has practical applications in contexts such as ar...

Full description

Saved in:
Bibliographic Details
Published in:Knowledge-based systems 2016-08, Vol.106, p.1-13
Main Authors: Rubio-Sánchez, Manuel, Gallego, Micael, Gortázar, Francisco, Duarte, Abraham
Format: Article
Language:English
Subjects:
Algorithms
Computational efficiency
Computing time
Construction
Facilities management
Facilities planning and design
GRASP
Mathematical models
Metaheuristics
Path relinking
Searching
State of the art
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The single row facility layout problem (SRFLP) is an NP-hard problem that consists of finding an optimal arrangement of a set of rectangular facilities (with equal height and different lengths), placing them next to each other along a line. The SRFLP has practical applications in contexts such as arranging rooms along corridors, setting books on shelves, allocating information on magnetic disks, storing items in warehouses, or designing layouts for machines in manufacturing systems. This paper combines the greedy randomized adaptive search procedure (GRASP) methodology, and path relinking (PR) in order to efficiently search for high-quality solutions for the SRFLP. In particular, we introduce: (i) several construction procedures, (ii) a new fast local search strategy, and (iii) an approach related to the Ulam distance in order to construct short path relinking trajectories. We also present a new set of large challenging instances, since previous sets do not allow to determine significant differences among advanced metaheuristics. Experiments show that our procedure outperforms state-of-the-art methods in all of the scenarios we considered. Firstly, the GRASP with PR finds the best known solutions for previous instances used in the literature, but employing considerably less computing time than its competitors. Secondly, our method outperforms the current state-of-the-art methods in 38 out of 40 new instances when running for the same amount of computing time. Finally, nonparametric tests for detecting differences between algorithms report p-values below 10−11, which supports the superiority of our approach.
ISSN:0950-7051
1872-7409
DOI:10.1016/j.knosys.2016.05.030