سال انتشار: ۱۳۸۶

محل انتشار: اولین کنفرانس بین المللی تحقیق در عملیات ایران

تعداد صفحات: ۴

نویسنده(ها):

فرهاد جنتی –
اقبال حسینی –

چکیده:

درسه دههُ اخیر استفاده از فرمهای آزاد شدهrelaxations)) برای حل مسالهُ پوشش مجموعه(SCP) مورد توجه محققین قرار گرفته است. با توجه به NP-Complete بودن مسالهُ SCP ، فرمهای آزاد شدهُ آن از اهمیت خاصی برخوردارند. فرمهای آزاد شده مبتنی بر شبکه به واسطهُ داشتن سرعت زیاد جذابیت زیادی دارند. در این مقاله یک فرم آزاد شده جدید برای SCP ارائه می دهیم که کرانهای پایین به مراتب بهتری نسبت به فرمهای آزاد شده دیگر مبتنی بر شبکه بدست می دهد. همچنین استراتژیهایی قوی برای تخصیص هزینه در فرم آزاد شده مبتنی بر مسالهُ کارگماری ( ASP2 ) از مسالهُ SCP ، ارائه شده و نتایج محاسباتی امیدوار کننده ایی حاصل شده است