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

محل انتشار: سیزدهمین کنفرانس سالانه انجمن کامپیوتر ایران

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

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

سیدمهدی تشکری هاشمی – عضو هیات علمی، دانشکده ریاضی و علوم کامپیوتر دانشگاه صنعتی امیرکبیر
پیمان جهانبازی – کارشناس ارشد علوم کامپیوتر، دانشکده ریاضی و علوم کامپیوتر دانشگاه صن
علی کارگرنژاد – عضو هیات علمی، دانشکده فنی گروه مهندسی کامپیوتر دانشگاه آزاد اسلامی

چکیده:

در این مقاله، دو کران پایین جدید به نامهای کران پایین توسعه یافته بر پایه ماشین و کران پایین توسعه یافته بر پایه کار درمساله زمانبندیjobshop را تابع هدف makespan ارائه می شود. به
منظور محاسبه کران های پایین توسعه یافته وضعیت هایی بررسی می شوند که در آن امکان پردازش عملیات ها توسط ماشینها وجود ندارد. با استفاده از کران های پایین ارائه شده می توان تخمینبهتری نسبت به پاسخ بهینه مساله به دست آورد. هر اندازه کران پایین به مقدار بهینه واقعی نزدیکتر باشد ارزیابی پاسخهای بدست آمده از الگوریتم های مختلف با دقت بیشتری انجام می شود.
کران های پایین توسعه یافته بر روی ۸۰ مساله محک موجود محاسبه شدند. پس از محاسبه کران های پایین توسعه یافته، آنها با کران ها ی موجود مقایسه می شوند، نتایج نشان می دهد که در ۵۵ درصد موارد نتایج موجود نسبت به نتایج قبلی بهبود داشته است.