کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10347533 699240 2013 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times
ترجمه فارسی عنوان
یک الگوریتم دقیق برای یک مسئله کمبود وزن با یک ماشین با زمان تنظیم وابسته به دنباله
کلمات کلیدی
مساله تضعیف کل وزن تنها ماشین، زمان نصب وابسته به دنباله، الگوریتم دقیق، آرامش لاگرانژی، برنامه نویسی دینامیک،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی
This study proposes an exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times. The algorithm is an extension of the authors' previous algorithm for the single-machine scheduling problem without setup times, which is based on the SSDP (Successive Sublimation Dynamic Programming) method. In the first stage of the algorithm, the conjugate subgradient algorithm or the column generation algorithm is applied to a Lagrangian relaxation of the original problem to adjust multipliers. Then, in the second stage, constraints are successively added to the relaxation until the gap between lower and upper bounds becomes zero. The relaxation is solved by dynamic programming and unnecessary dynamic programming states are eliminated to suppress the increase of computation time and memory space. In this study a branching scheme is integrated into the algorithm to manage to solve hard instances. The proposed algorithm is applied to benchmark instances in the literature and almost all of them are optimally solved.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 40, Issue 1, January 2013, Pages 344-352
نویسندگان
, ,