کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5127837 | 1489063 | 2017 | 16 صفحه PDF | دانلود رایگان |
- 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(n2) 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(n2) 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.
Journal: Computers & Industrial Engineering - Volume 103, January 2017, Pages 1-16