کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
479543 1446002 2015 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A branch-price-and-cut algorithm for multi-mode resource leveling
ترجمه فارسی عنوان
الگوریتم شاخه ای قیمت و برش برای تطبیق منابع چند حالته
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی


• We present a new model and algorithm for a RCPSP with availability constraints.
• We propose a non-trivial, non-obvious Dantzig–Wolfe reformulation.
• We translate standard precedence inequalities into our new formulation.
• Our model gives significantly tighter lower bounds
• We increase the size of instances that can be solved to optimality to 50 jobs.

We propose a new mixed integer programming formulation and solution algorithm for a multi-mode resource-constrained project scheduling problem with availability constraints (calendars) and the objective to minimize the resource availability cost. Our model exploits the problem structure and has an exponential number of variables, which necessitates a column generation approach. The linear programming relaxation is strengthened by adding valid inequalities that need to be carefully separated in order to show the desired effect. Integer optimal solutions are obtained by an exact state-of-the-art branch-price-and-cut algorithm.Classical time-indexed mixed integer programming formulations for similar problems quite often fail already on instances with only 30 jobs, depending on the network complexity and the total freedom of arranging jobs. A reason is the typically very weak linear programming relaxation. Our model can be interpreted as a non-trivial Dantzig–Wolfe reformulation of a time-indexed formulation. In particular, for larger instances our reformulation gives significantly tighter dual bounds, enabling us to optimally solve instances with 50 multi-mode jobs. This outperforms the classical formulation by far.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 245, Issue 1, 16 August 2015, Pages 70–80
نویسندگان
, , ,