معرفي يك الگوريتم جست‌وجوي ممنوع براي حل مسيله‌ي تك‌سطري چيدمان

A TABU ALGORITHM FOR THE SINGLE ROW FACILITY LAYOUT PROBLEM

طراحي چيدمان عبارت است از تعيين يك چينش مناسب براي تعدادي تجهيزات به‌نحوي كه كل هزينه‌هاي مرتبط با جريان ميان قسمت‌ها را كمينه كند. يكي از مسايلي كه در طراحي چيدمان كاربرد عملي زيادي دارد، مسيله‌ي چيدمان تك‌سطري يا يك‌رديفه‌ي امكانات (SRFLP ) است. اين مسيله، مسيله‌يي از رده‌ي NP-Complete است و تلاش‌هاي فراواني براي به دست آوردن جواب‌هاي نزديك به بهينه يا مدل‌سازي مجدد آن صورت گرفته است. در نوشتار حاضر ابتدا به بررسي حالتي خاص در SRFLP مي‌پردازيم و قضيه‌ي سودمندي را در رابطه با جواب بهينه‌ي اين حالت اثبات مي‌كنيم. سپس يك الگوريتم جست‌وجوي ممنوع (TS) را به‌كمك جواب بهينه‌ي حالت خاص مذكور براي حل SRFLP توسعه داده و نحوه‌ي عملكرد آن را بررسي مي‌كنيم. نتايج محاسباتي نشان‌گر كارآيي و قدرت محاسباتي چشم‌گير الگوريتم پيشنهادي در مقايسه با ساير الگوريتم‌هاي مشابه براي حل مسيله است، به‌نحوي كه جواب نزديك به بهينه براي مسايل SRFLP كه حتي تا 200 قسمت دارند در زمان بسيار اندكي به دست مي‌آيد.

A special class of facility layout problem is the Single-Row Facility Layout Problem (SRFLP), which consists in finding a linear placement of rectangular facilities with varying dimensions on a straight line. In this research, we first prove a theorem to find the optimal solution of a special case of SRFLP. The theorems’ results are useful when a new algorithm, based on a tabu search, is presented for the SRFLP in this paper. Computational results of the proposed algorithm show the efficiency of the algorithm compared to other heuristics. The proposed algorithm can easily find near-optimal solutions for instances consisting of 200 departments in less than one minute. However, the largest instances reported to be solved by other methods had only 80 departments and took more than 10 hours to reach the solution.