Single row facility layout using multi-start simulated annealing

Gintaras Palubeckis

doi:10.1016/j.cie.2016.09.026

Return

Single row facility layout using multi-start simulated annealing

2017-01-01

PRE

Gintaras Palubeckis *

DOI：10.1016/j.cie.2016.09.026

Original

Original request for help

Save

Abstract

En 中文

In the single row facility layout problem (SRFLP), we are given a set of n facilities, their lengths, and a flow cost matrix. The problem asks to arrange the facilities along a straight line so as to minimize the sum of the products of the flow costs and center-to-center distances between facilities. We develop a multi-start simulated annealing (MSA) algorithm for solving this problem. The algorithm employs two move types, pairwise interchanges of facilities and insertions. We propose O(n)-time procedures for computing gains of both types of moves. They make our algorithm very fast compared to the traditional approaches, which are based on a straightforward procedure for obtaining the move gain in O(n(2)) time. When the temperature during the cooling process drops to.a certain level, the computation is accelerated with the use of an additional technique which is reminiscent of a local search algorithm (it takes O(1) time to compute the move gain and O(n(2)) time to perform the required calculations when a move is accepted). We report computational results for SRFLP instances of size up to 1000 facilities. The results demonstrate the superiority of the MSA algorithm over the state-of-the-art methods. The source code implementing MSA is made publicly available as a benchmark for future comparisons. (C) 2016 Published by Elsevier Ltd.

Keywords:

Combinatorial optimization

Heuristics

Facility layout

Simulated annealing

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.