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

مسایل زمانبندی همواره مورد توجه گسترده محققان حوزه های مختلف بوده است. از آنجایی که اغلب این مسایل و تقریبا همه مسایل دنیای واقعی در ردۀ مسایل np- سخت بهینه سازی ترکیبیاتی و علوم کامپیوتر قرار می گیرند؛ لذا پیدا کردن راه حل مناسب، راه حلی که در زمانی معقول (زمان چندجمله ای) قابل اجرا باشد، دشوار است. یکی از راهکارهای مطرح شده برای حل این مشکل، به کارگیری راهکار تقریب است. طرح های تقریب با زمان چند جمله ای و طرح تقریب دیفرانسیلی که بر اساس مقایسه جواب الگوریتم مطرح شده برای حل مساله با جواب بهینه و جواب بدترین حالت بناشده است، در دسته روش های تقریب قرار می گیرند. کیفیت جواب الگوریتم ارایه شده برای یک مساله از طریق طرح تقریبی قابل ارزیابی است. این مقاله ضمن مرور طرح های تقریب کارا بر روی دو مساله زمانبندی کارها بر روی تک ماشین با اهداف مینیمم سازی ماکزیمم زمان تحویل کارها و مینیمم سازی مجموع وزن دار اتمام کارها، روش ها و ابزارهای لازم برای اثبات وجود یک طرح تقریبی را ارایه می دهد. همچنین در این مقاله با استفاده از طرح تقریب با زمان چندجمله ای (ptas) یک طرح تقریب دیفرانسیلی برای مساله مینیمم سازی ماکزیمم زمان تحویل کارها که تا کنون مورد بررسی قرار نگرفته است، مورد مطالعه قرار گرفته است.

differential approximation schemes for scheduling problems on single machine with availability constraint

scheduling problems have been considered by researchers from different aspects, and it has been widely addressed in the literature. most scheduling problems, and almost all that arise in real-world applications, are np-hard, therefore finding a proper and feasible solution, a solution that is performed in a reasonable time (polynomial time), is difficult. approximation scheme, among different methods, is one approach that can overcome difficulties. polynomial-time approximation and differential approximation schemes are categorized as approximation approaches based on comparing the proposed algorithm with optimum and worst-case solutions.as the first attempt, the paper investigates differential approximation schemes for the minimization of maximum delivery time. in this paper, the main methods and tools for proving the existence of an approximation scheme are presented. to do so, a differential approximation scheme is proposed by employing a polynomial-time approximation scheme (ptas). the paper also reviews efficient approximation schemes on single machine problems with objective functions minimization of maximum delivery time, and minimizing the total weighted completion time. also, in this paper, using the polynomial time approximation scheme (ptas), a differential approximation scheme has been studied for the problem of minimizing the maximum delivery time of works, which has not been investigated so far.