دوره 19، شماره 4 - ( 9-1401 )
جلد 19 شماره 4 صفحات 36-17 |
برگشت به فهرست نسخه ها
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Seifaddini M. Differential Approximation Schemes for Scheduling Problems on Single machine with Availability Constraint. jor 2022; 19 (4) :17-36
URL: http://jamlu.liau.ac.ir/article-1-2080-fa.html
URL: http://jamlu.liau.ac.ir/article-1-2080-fa.html
سیف الدینی مریم. طرح تقریب دیفرانسیلی برای مساله زمانبندی روی تک ماشین با محدودیت دسترسی. تحقیق در عملیات در کاربردهای آن. 1401; 19 (4) :17-36
دانشگاه گیلان، گروه علوم کامپیوتر، گیلان، ایران
چکیده: (677 مشاهده)
مسایل زمانبندی همواره مورد توجه گسترده محققان حوزههای مختلف بوده است. از آنجایی که اغلب این مسایل و تقریبا همه مسایل دنیای واقعی در ردۀ مسایل NP- سخت بهینه‌سازی ترکیبیاتی و علوم کامپیوتر قرار میگیرند؛ لذا پیدا کردن راه حل مناسب، راه حلی که در زمانی معقول (زمان چندجمله‌ای) قابل اجرا باشد، دشوار است. یکی از راهکارهای مطرح‌شده برای حل این مشکل، به کارگیری راهکار تقریب است. طرح های تقریب با زمان چندجمله ای و طرح تقریب دیفرانسیلی که بر اساس مقایسه جواب الگوریتم مطرح‌شده برای حل مساله با جواب بهینه و جواب بدترین حالت بناشده است، در دسته روش های تقریب قرار می گیرند. کیفیت جواب الگوریتم ارایه‌شده برای یک مساله از طریق طرح تقریبی قابل ارزیابی است. این مقاله ضمن مرور طرح های تقریب کارا بر روی دو مساله زمانبندی کارها بر روی تک ماشین با اهداف مینیمم سازی ماکزیمم زمان تحویل کارها و مینیمم‌سازی مجموع وزن‌دار اتمام کارها، روش ها و ابزارهای لازم برای اثبات وجود یک طرح تقریبی را ارایه می دهد. همچنین در این مقاله با استفاده از طرح تقریب با زمان چندجمله ای (PTAS) یک طرح تقریب دیفرانسیلی برای مساله مینیمم‌سازی ماکزیمم زمان تحویل کارها که تا کنون مورد بررسی قرار نگرفته است، مورد مطالعه قرار گرفته است.
ارسال پیام به نویسنده مسئول
| بازنشر اطلاعات | |
 |
این مقاله تحت شرایط Creative Commons Attribution-NonCommercial 4.0 International License قابل بازنشر است. |
