معرفی یک الگوریتم جست و جوی ممنوع برای حل مسئله‌ی تک سطری چیدمان

نویسنده

دانشکده‌ی مهندسی صنایع، دانشگاه صنعتی شریف

چکیده

طراحی چیدمان عبارت است از تعیین یک چینش مناسب برای تعدادی تجهیزات به‌نحوی که کل هزینه‌های مرتبط با جریان میان قسمت‌ها را کمینه کند. یکی از مسائلی که در طراحی چیدمان کاربرد عملی زیادی دارد، مسئله‌ی چیدمان تک‌سطری یا یک‌ردیفه‌ی امکانات )SRFLP است. این مسئله، مسئله‌یی از رده‌ی NP-Complete است و تلاش‌های فراوانی برای به دست آوردن جواب‌های نزدیک به بهینه یا مدل‌سازی مجدد آن صورت گرفته است. در نوشتار حاضر ابتدا به بررسی حالتی خاص در S‌R‌F‌L‌P می‌پردازیم و قضیه‌ی سودمندی را در رابطه با جواب بهینه‌ی این حالت اثبات می‌کنیم. سپس یک الگوریتم جست‌وجوی ممنوع )T‌Sرا به‌کمک جواب بهینه‌ی حالت خاص مذکور برای حل SRFLP توسعه داده و نحوه‌ی عملکرد آن را بررسی می‌کنیم. نتایج محاسباتی نشان‌گر کارآیی و قدرت محاسباتی چشم‌گیر الگوریتم پیشنهادی در مقایسه با سایر الگوریتم‌های مشابه برای حل مسئله است، به‌نحوی که جواب نزدیک به بهینه برای مسائل SRFLP که حتی تا ۲۰۰ قسمت دارند در زمان بسیار اندکی به دست می‌آید.

کلیدواژه‌ها

عنوان مقاله [English]

TABU ALGORITHM FOR THE SINGLE ROW FACILITY LAYOUT PROBLEM

نویسنده [English]

  • Hamed Samarkand
Industrial Engineering, Sharif University of Technology
چکیده [English]

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.

کلیدواژه‌ها [English]

  • facility problem
  • linear ordering problem
  • tabu search algorithm

فایل ها

هم رسانی

ارجاع به این مقاله

آمار