مسیله بسته بندی مستطیل

مساله بسته بندی مستطیل یک مسیله بهینه سازی ترکیبی می-باشد و در بین مسایل ان.پی-کامل قرار میگیرد. در این مساله یک مجموعه ای از مستطیل ها با ابعاد و تعداد مشخص داریم و هدف چیدن بدون همپوشانی و متعامد این مستطیل ها در یک صفحه مستطیلی می باشد. این مسیله کاربردهای فراوان در مسایل زمان بندی و در صنایع پیشرفته برای برش زدن مواد اولیه ای مانند چوب، چرم، کاغذ، شیشه و فلزات کاربرد دارد. به دلیل این که نمی توان به بهترین جواب برای مسیله در زمان مناسب دست یافت، از این رو الگوریتم های تقریبی زیادی برای مسیله دو بعدی بسته بندی مستطیل ارایه شده است که به دو دسته الگوریتم های آروین1 و فراآروین2 تقسیم میشوند. در این مقاله گونه های مختلف مسیله بسته بندی مستطیل به همراه کار های تحقیقاتی انجام شده در این زمینه پرداخته شده است.

Keywords:

مسیله بسته بندی مستطیل , الگوریتم های آروین , الگوریتم های فرا آروین