کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8953637 | 1645960 | 2019 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Precedence theorems and dynamic programming for the single-machine weighted tardiness problem
ترجمه فارسی عنوان
قواعد قضیه و برنامه نویسی پویا برای یک مسئله تضعیف وزن یک ماشین
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
برنامه ریزی، ماشین تک محدودیت های قضیه، تداخل وزنی، برنامه نویسی دینامیک،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
We tackle precedence-constrained sequencing on a single machine in order to minimize total weighted tardiness. Classic dynamic programming (DP) methods for this problem are limited in performance due to excessive memory requirements, particularly when the precedence network is not sufficiently dense. Over the last decades, a number of precedence theorems have been proposed, which distinguish dominant precedence constraints for a job pool that is initially without precedence relation. In this paper, we connect and extend the findings of the foregoing two strands of literature. We develop a framework for applying the precedence theorems to the precedence-constrained problem to tighten the search space, and we propose an exact DP algorithm that utilizes a new efficient memory management technique. Our procedure outperforms the state-of-the-art algorithm for instances with medium to high network density. We also empirically verify the computational gain of using different sets of precedence theorems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 272, Issue 1, 1 January 2019, Pages 43-49
Journal: European Journal of Operational Research - Volume 272, Issue 1, 1 January 2019, Pages 43-49
نویسندگان
Salim Rostami, Stefan Creemers, Roel Leus,