کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
478137 1446025 2014 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An evaluation of semidefinite programming based approaches for discrete lot-sizing problems
ترجمه فارسی عنوان
ارزیابی روشهای مبتنی بر برنامه نویسی نیمهتمام برای مسائل مربوط به اندازه گیری گسسته
کلمات کلیدی
ساخت، مشکل بزرگنمایی و برنامه ریزی گسسته، هزینه ها و زمان تغییر انتقال وابسته به دنباله، برنامه نویسی باینری درجه دوم محدوده محدود. آرامش نیمه عمیق، هواپیما برش
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی


• We study a lot-sizing problem with sequence-dependent changeover costs and times.
• This problem is formulated as a quadratically constrained quadratic binary program.
• We compute lower bounds using a semidefinite rather than a linear relaxation.
• Comparison with the best known linear relaxations shows a significant improvement.
• The SDP relaxation provides the optimal integer value for 83% of the small-size instances.

The present work is intended as a first step towards applying semidefinite programming models and tools to discrete lot-sizing problems including sequence-dependent changeover costs and times. Such problems can be formulated as quadratically constrained quadratic binary programs. We investigate several semidefinite relaxations by combining known reformulation techniques recently proposed for generic quadratic binary problems with problem-specific strengthening procedures developed for lot-sizing problems. Our computational results show that the semidefinite relaxations consistently provide lower bounds of significantly improved quality as compared with those provided by the best previously published linear relaxations. In particular, the gap between the semidefinite relaxation and the optimal integer solution value can be closed for a significant proportion of the small-size instances, thus avoiding to resort to a tree search procedure. The reported computation times are significant. However improvements in SDP technology can still be expected in the future, making SDP based approaches to discrete lot-sizing more competitive.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 237, Issue 2, 1 September 2014, Pages 498–507
نویسندگان
, , ,