بررسي نسبت تقريب ديفرانسيلي براي مسئله زمانبندي بر روي يك تك ماشين با بازه غيرقابل دسترس

هدف اين مقاله بررسي وجود تقريب ديفرانسيلي براي مسئله زمانبندي بر روي يك تك ماشين با بازه غيرقابل دسترس است. بر خلاف پژوهش هاي پيشين تابع هدف مسئله مورد مطالعه مينيمم‌سازي ماكزيمم تأخير است. ويژگي چالش برانگيز تابع هدف در اين مسئله، نامعلوم بودن زمان رخداد مقدار ماكزيمم تاخير است. اين پيچيدگي سبب خواهد شد كه اساسا وجود يك نسبت ثابت ديفرانسيلي براي آن بديهي نباشد و در صورت وجود، بدست آوردن آن به سادگي امكان پذير نخواهد بود. در اين راستا، دو الگوريتم براساس قانون جكسون ارائه شده است. اين الگوريتم ها نتوانستند در حالت كلي يك نسبت ثابت ديفرانسيلي ارائه دهند. اما در بعضي حالات تقريب خوبي از جواب بهينه ارائه كردند.