طرح تقریب برای یک مساله زمانبندی با محدودیت دسترسی ماشین

این مقاله به مطالعه یک طرح تقریب کارا بر روی مساله زمانبندی کارها روی تک ماشین با محدودیت دسترسی ماشین در یک بازه مشخص و با هدف مینیمم سازی ماکزیمم زمان تحویل کارها می پردازد. طرح های تقریب با زمان چندجمله ای که بر اساس مقایسه جواب الگوریتم مطرح شده برای حل مساله با جواب بهینه بنا شده اند، معیاری برای سنجش کارایی الگوریتم حل یک مساله خاص هستند. در این مطالعه یک طرح تقریب کارای بهبود یافته با زمان چند جمله ای ارائه شده است. این طرح که بر اساس الگوریتم برنامه ریزی پویا بنا شده است، پیچیدگی زمانی کمتری نسبت به طرح های تقریب پژوهش های قبلی دارد.

کلیدواژه ها:

زمانبندی ، طرح تقریب ، الگوریتم ابتکاری ، برنامه ریزی پویا