مقالات مهندسی صنایع
مقالات مهندسی صنایع

On the optimality of exact and approximation algorithms for scheduling problems

برنامه ریزی مسائل بر پایه بهینه بودن الگوریتم دقیق و تقریبی

We consider the classical scheduling problem on parallel identical machines to minimize the makespan. There is a long history of study on this problem, focusing on exact and approximation algorithms. It is thus natural to consider whether these algorithms can be further improved in terms of running times. We provide strong lower bounds on the running times of exact and approximation schemes for the classical scheduling problem based on Exponential Time Hypothesis, showing that the best known approximation and exact algorithms are almost the best possible in terms of the running time.

نویسندگان: Lin Chen-Klaus Jansen- Guochuan Zhang

ژورنال: Computers &Operations Research

سال انتشار: 2018

 

دانلود مقاله:

http://www.phdyar.ir/wp-content/uploads/2018/09/On-the-optimality-of-exact-and-approximation-algorithms-for-scheduling-problems.pdf

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *