یک الگوریتم تقریبی با ضریب تقریب ثابت جدید برای مسئله برش دو بعدی مستطیلی
یک الگوریتم تقریبی با ضریب تقریب ثابت جدید برای مسئله برش دو بعدی مستطیلی
هاجر افلاطونی1 کیوان برنا2
1) دانش آموخته کارشناسی ارشد مهندسی کامپیوتر، دانشگاه آزاد اسلامی، واحد قزوین، ایران
2) عضو هیأت علمی گروه علوم کامپیوتر، دانشگاه خوارزمی، تهران، ایران،
کد IOI مقاله
:
XYCZ-AADZF
محل انتشار :
کنفرانس بین المللی مهندسی و علوم کاربردی(iceasconf.com)
چکیده :
یکی از مسائل شناخته شده در سالهای اخیر که توجه محققان بسياري را به خود جلب کرده و روشهاي متعددي براي بهينه سازي اين مسأله ارائه شده است، مسأله برش دو بعدی می باشد. مسئله برش دو بعدی از جمله مسائلي است كه با استفاده از الگوريتم هاي مسئله كوله-پشتي دوبعدي قابل حل است. در مسأله برش دوبعدي يك قطعه مستطيل شكل بزرگ، که به عنوان قطعه اصلی در نظر گرفته می شود و تعدادي قطعات مستطيل شكل ديگر كه مساحت آنها نسبت به مساحت قطعه مستطيل شكل بزرگ، كوچكتر است وجود دارد. هدف از حل اين مسئله آن است كه ورق مستطيل شكل بزرگ را به گونه اي برش دهيم كه ضمن اينكه ورق هاي مستطيل شكل كوچكتر توليد مي شوند، ضايعاتي كه در اثر برش ايجاد مي شود تا حدامكان به حداقل برسد. حل مسئله برش دوبعدی در هر صنعتي كه برش صفحات در آن مورد نياز باشد، از نظر كاهش ضايعات حائز اهميت خواهد بود .الگوريتم دقيقي كه براي حل اين مسئله وجود دارد داراي پيچيدگي زماني نمايي است. در واقع اين مسأله جزء مسائل NP-hard است. در نتيجه الگوريتم دقيق براي حل مسائلي كه داراي ورودي زياد باشد كاربرد عملي ندارد. براي حل اين گونه مسائل بايد از روش هاي ديگري استفاده كرد. يكي از اين روش ها استفاده از الگوريتم هاي تقريبي مي باشد. در اين مقاله با هدف کاهش ضایعات قطعه اصلی، الگوريتمي تقريبي با ضریب تقریب 1+1/2K(1-K) (ارتفاع و عرض هر قطعه به جز قطعه اصلی باید کمتر، مساوی k باشد) براي حل مسأله برش ارائه می دهیم. نتایج پیاده سازی الگوریتم پیشنهادی و مقایسه های صورت گرفته، برتری روش این مقاله را تأیید می کند.
کلمات کلیدی : مسأله برش دوبعدي الگوريتم تقريبي ضریب تقریب