کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6895039 1445936 2018 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Valid inequalities for two-period relaxations of big-bucket lot-sizing problems: Zero setup case
ترجمه فارسی عنوان
نابرابری های معتبر برای آرام کردن دو دوره ای از مشکلات بزرگ اندازه سطل بزرگ: مورد راه اندازی صفر
کلمات کلیدی
ترجمه چکیده
در این مقاله، زیربنای دو دوره ای برای مسائل بزرگ اندازه سطل بزرگ مورد بررسی قرار گرفته ایم که پتانسیل زیادی برای بدست آوردن مرزهای قوی نشان داده اند. به ویژه، ما مورد خاصی از زمان صفر تنظیم را مورد بررسی قرار می دهیم و دو مجموعه عدد صحیح مختلط را نشان می دهد که آرام سازی این زیر مشکل ها را نشان می دهد. ما ساختار چندضلعی این مجموعه ها را تجزیه می کنیم، خانواده های مختلفی از نابرابری های معتبر را به نمایش می گذاریم و شرایط آنها را مشخص می کنیم. سپس این نابرابری ها را به شکل جدیدی گسترش می دهیم تا فضای اصلی دو موضوع زیر را بررسی کنیم و همچنین یک خانواده جدید از نابرابری های معتبر در فضای اصلی ارائه دهیم. برای بررسی قدرت واقعی نابرابری های پیشنهاد شده، الگوریتم های جداسازی دقیق را پیشنهاد می کنیم که به صورت محاسباتی بر روی طیف وسیعی از مشکلات آزمون تست شده اند. علاوه بر این، ما یک چارچوب اکتشافی برای جداسازی را برای گسترش آزمایشات محاسباتی به نمونه های بزرگ تر توسعه می دهیم. این آزمایش های محاسباتی نشان می دهد که نابرابری های پیشنهاد شده می تواند در واقع به طور قابل ملاحظه ای بهبود مرز های پایه را بطور قابل توجهی ایفا کند.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی
In this paper, we investigate two-period subproblems for big-bucket lot-sizing problems, which have shown a great potential for obtaining strong bounds. In particular, we investigate the special case of zero setup times and identify two important mixed integer sets representing relaxations of these subproblems. We analyze the polyhedral structure of these sets, deriving several families of valid inequalities and presenting their facet-defining conditions. We then extend these inequalities in a novel fashion to the original space of two-period subproblems, and also propose a new family of valid inequalities in the original space. In order to investigate the true strength of the proposed inequalities, we propose and implement exact separation algorithms, which are computationally tested over a broad range of test problems. In addition, we develop a heuristic framework for separation, in order to extend computational tests to larger instances. These computational experiments indicate the proposed inequalities can be indeed very effective improving lower bounds substantially.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 267, Issue 1, 16 May 2018, Pages 86-95
نویسندگان
, ,