کران پایین توسعه یافته بر پایه کار و ماشین در مساله زمانبندی Jobshop با تابع هدف makespan

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

Keywords:

زمانبندی , makespan , Jobshop , کران پایین بر پایه کار , کران پایین بر پایه ماشین