ارايه‌ي الگوريتم جست‌وجوي ممنوع با استراتژي تنوع براي حل مسيله‌ي چيدمان پوياي تسهيلات

A Tabu Search-based Algorithm with Diversification Strategy for Dynamic Facility Layout Problem

در ارتباط با «مسيله‌ي چيدمان تسهيلات» تحقيقات زيادي صورت گرفته است. هدف آن يافتن موقعيت دپارتمان در سطح كارخانه براي دوره‌هاي زماني است، به‌گونه‌يي كه دپارتمان‌ها هم‌پوشاني نداشته باشند و مجموع هزينه‌ي جابه‌جايي و چيدمان مجدد كمينه‌ ‌شود. به‌منظور اطمينان از عملكرد خوب سيستم توليدي بايد تغييرات پارامترهاي مسيله در طي زمان در نظر گرفته شود. با توجه به پويابودن تسهيلات توليدي، مسيله‌ي چيدمان تسهيلات در حالت ايستا يك سناريوي واقعي نيست. در اين مقاله مسيله‌ي چيدمان پوياي تسهيلات با فرض تساوي مساحت دپارتمان‌ها به‌وسيله‌ي الگوريتم فراابتكاري جست‌وجوي ممنوع با استراتژي تنوع ــ شامل ساختار حافظه مبتني بر تكرار، تابع جريمه و ليست ممنوع پويا ــ حل شده است. رويكرد پيشنهادي با دو مجموعه داده شاخص و معروف از ادبيات موضوع ارزيابي شده است. نتايج به دست آمده حاكي از آن است كه الگوريتم پيشنهادي در مقايسه با الگوريتم‌هاي قبلي عملكرد بهتري داشته و در بيشتر موارد جواب هاي بهتري ارايه داده است.

The facility layout problem is determination of the position of a department in a specific facility. The simplest case of a facility layout problem is FLP with equal size departments, where the amount of material flowing between pairs of departments does not change during the planning horizon. This problem is called the static facility layout problem (SFLP), with equal size departments, and was modeled by Koopmans and Beckmann as a quadratic assignment problem (QAP). The dynamic facility layout problem (DFLP) is a well-researched problem to find the positions of departments on a plant floor for multiple periods (material ?ow between departments change during the planning horizon). The change in material flow between pairs of departments in consecutive periods may require the rearrangement of departments during the planning horizon, in order to keep material handling costs low. The objective of our research is to minimize the sum of the material handling and rearrangement costs. Because of the combinatorial structure of the problem, only small sized problems can be solved in reasonable time using exact techniques. As a result, construction and improvement heuristics are developed for the proposed problem. So, in this paper, a tabu search heuristic, with a diversification strategy that includes frequency-based memory, penalty function and dynamic tabu list size, are developed to solve the dynamic facility layout problem with equal departments. The frequency-based memory structure is used to memorize the trace of repeated movement, and the dynamic tabu list is applied to give variation to the search space. The implementation of the proposed method is demonstrated using some benchmark problems and the results are discussed in detail. Computational experiments show that the proposed heuristic out-performed heuristics presented in the literature, with respect to solution quality.