Single row facility layout using multi-start simulated annealing

The single row facility layout problem (SRFLP) is considered.A fast multi-start simulated annealing algorithm is proposed.Both interchange and insertion move gains are computed in linear time.A technique to accelerate computation for lower temperatures is applied.Numerical results are reported for SRFLP instances of size up to 1000 facilities. 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.