عنوان پایان‌نامه
بررسی کارایی تنها الگوریتم تقریبی موجود برای مسئله پوشش سطل ها در حالت کلی وبهینه کردن ضریب تقریب آن
- رشته تحصیلی
- مهندسی کامپیوتر- آلگوریتم ها و محاسبات
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس یک فنی شماره ثبت: 85..;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 72717;کتابخانه پردیس یک فنی شماره ثبت: 85..;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 72717
- تاریخ دفاع
- ۲۵ خرداد ۱۳۹۴
- دانشجو
- سمیه جباری
- استاد راهنما
- دارا معظمی, امین قدوسیان
- چکیده
- مسئله پوشش سطلها یک مسئله NP-Hard است که در دسته مسائل بهینه‌سازی ترکیبیاتی نیز قرار می‌گیرد. در این مسئله m سطل و n شئ وجود دارند. هرسطل دارای دو ویژگی نیاز و سود و هر شئ نیز دارای ویژگی اندازه است. اشیاء قابلیت تکه شدن ندارند. مسئله قرار دادن اشیاء در سطلها می‌باشد به نحوی که هر سطل حداقل به اندازه نیازش پر شود که در این شرایط سود سطل به دست می‌آید. هدف مسئله به دست آوردن بیشترین سود است. مسئله پوشش سطلها درسه حالت کلی مورد بررسی قرار می‌گیرد: حالت کلاسیک که در آن سود و نیاز سطل برابر با یک است. در حالت سایز متغیر، سود و نیاز سطل برابر است، اما هر مقداری می‌تواند اختیار کند و در مدل سوم که حالت کلی مسئله می‌باشد، مقدار سود و نیاز هر سطل مستقل از هم هستند. در این تحقیق، حالت کلی مسئله پوشش سطلها مورد بررسی قرار می‌گیرد. حالت کلی مسئله پوشش سطلها تنها در یک تحقیق مورد بررسی قرار گرفته که نتیجه آن ارائه یک الگوریتم تقریبی با ضریب 5 می‌باشد. برای حل این مسئله، راهکارهای زیر را پیشنهاد کرده‌ایم: الگوریتم دقیق با پیچیدگی محاسباتی O^* (n!): این الگوریتم تنها برای نمونه مسائل کوچک قابل اجراست. مدلILP: با استفاده از نرم افزاهای پیشرفته بهینه سازی، می‌تواند راه‌حل بهینه را حتی برای نمونه‌های نسبتا بزرگ مسئله به دست دهد. الگوریتم ابتکاری: این الگوریتم می‌تواند یک جواب تقریبی برای مسئله بیابد. هدف از ارائه این الگوریتم یافتن راه‌حلی نزدیک به راه‌حل بهینه برای نمونه مسائل بزرگ می‌باشد. به منظور بررسی کارایی این الگوریتم، الگوریتم‌های دقیق، ابتکاری و تقریبی این مسئله پیاده سازی وراه‌حلهای به دست آمده برای نمونه های مختلف مسئله با هم مقایسه شده‌اند.
- Abstract
- We are given m bins, where each bin has profit and demand. Furthermore, there are n items, where item has size property. A bin is covered if the set of items assigned to it has total size at least its demand. In that case, the profit of the bin is earned and the objective is to maximize the total profit. This problem is an NP-Hard and combinatorial optimization problem. This problem studied in three cases: In classic case the revenue and demand of each bin is unit. In variable-sized demand and revenue of each bin is equal but can get any value. In generalized case there are bins that their demand and revenue values are independent. In this search we consider Generalized Bin Covering problem. To the best of our knowledge, this problem have been treated before only in one paper and a 5-approximation algorithm proposed. We introduce an exact algorithm that its time complexity is? O?^* (n!). For almost large and large instaces a heuristic algorithm presented. These algorithms implemented and their results compared. Additionally an ILP model of this problem formulated to gain the optimal solution by advanced optimization software for almost large instances.
