کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8960187 | 1646386 | 2018 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An exact exponential branch-and-merge algorithm for the single machine total tardiness problem
ترجمه فارسی عنوان
یک الگوریتم شاخه ای و یکپارچگی دقیق برای یک مسئله ترد شدن کامل دستگاه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم دقیق نمایشی، تک ماشین کامل تکذیب، شعبه و ادغام
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
This paper proposes an exact exponential algorithm for the single machine total tardiness problem. It exploits the structure of a basic branch-and-reduce framework based on the well known Lawler's decomposition property that solves the problem with worst-case complexity in time Oâ(3n) and polynomial space. The proposed algorithm, called branch-and-merge, is an improvement of the branch-and-reduce technique with the embedding of a node merging operation. Its time complexity converges to Oâ(2n) keeping the space complexity polynomial. This improves upon the best-known complexity result for this problem provided by dynamic programming across the subsets with Oâ(2n) worst-case time and space complexity. The branch-and-merge technique is likely to be generalized to other sequencing problems with similar decomposition properties.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 745, 12 October 2018, Pages 133-149
Journal: Theoretical Computer Science - Volume 745, 12 October 2018, Pages 133-149
نویسندگان
Michele Garraffa, Lei Shang, Federico Della Croce, Vincent T'kindt,