الگوریتم تقریبی برای مساله بسته بندی دو بعدی

تعداد 70 صفحه فایل word

چکیده

ما بسته بندی جعبه ها را از طریق اختلاف جایگشت ها انجام می­دهیم، ما مسأله بسته بندی جعبه دو بعدی را با چرخش و بدون چرخش مورد مطالعه قرار می­دهیم. در این جا ما مجموعه ای از جعبه های مستطیل شکل دو بعدی را ارائه می­دهیم و هدف بسته بندی این موارد به تعداد حداقل جعبه های مربع واحد است. ما در مورد بسته بندی متعامد که در آن لبه های جعبه ها، باید به موازات لبه های جعبه تراز وسط قرار داشته باشد را مورد ملاحظه قرار دادیم. نتیجه اصلی ما تقریب -1.405 برای بسته بندی جعبه دو بُعدی با چرخش و بدون چرخش است که به دلیل نظر یانسن و پرادل تقریب های اخیر 1.5 را بهبود می­بخشد است. ما همچنین نشان می­دهیم که یک کلاس گسترده ای از الگوریتم های مبتنی بر گرد کردن نمی تواند تقریب 1.5 را بهبود بخشد.

کلمات کلیدی: بسته بندی مستطیل، بسته بندی جعبه، برنامه ریزی و مسایل تخصیص منابع، الگوریتم تقریبی، بهینه سازی ترکیبی، تسهیلات برنامه ریزی خطی، نظریه ی اختلاف.