کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5080289 1477570 2013 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A branch & bound algorithm for cutting and packing irregularly shaped pieces
ترجمه فارسی عنوان
الگوریتم شاخه ای و محدود برای برش و بسته بندی قطعات بی شکل
کلمات کلیدی
برش و بسته بندی، نستیدن، فرمول عدد صحیح، شعبه و مرز
موضوعات مرتبط
مهندسی و علوم پایه سایر رشته های مهندسی مهندسی صنعتی و تولید
چکیده انگلیسی
Cutting and packing problems involving irregular shapes, usually known as Nesting Problems, are common in industries ranging from clothing and footwear to furniture and shipbuilding. Research publications on these problems are relatively scarce compared with other cutting and packing problems with rectangular shapes, and are focused mostly on heuristic approaches. In this paper we make a systematic study of the problem and develop an exact Branch & Bound Algorithm. The initial existing mixed integer formulations are reviewed, tested and used as a starting point to develop a new and more efficient formulation. We also study several branching strategies, lower bounds and procedures for fixing variables, reducing the size of the problem to be solved at each node. An extensive computational study allows us first to determine the best strategies to be used in the Branch & Bound Algorithm and then to explore its performance and limits. The results show that the algorithm is able to solve instances of up to 16 pieces to optimality.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: International Journal of Production Economics - Volume 145, Issue 2, October 2013, Pages 463-477
نویسندگان
, , ,