Novel Constant-Factor Approximation Algorithm for the Two-Dimensional Rectangular Cutting Problems
Publish place: کنفرانس بین المللی مهندسی و علوم کاربردی
Publish Year: 1394
نوع سند: مقاله کنفرانسی
زبان: English
View: 411
This Paper With 15 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
ICEASCONF01_079
تاریخ نمایه سازی: 9 مرداد 1395
Abstract:
Recently the problem of two-dimensional (rectangular) cutting has been one of the famous problems which have attracted many researchers’ attention and several methods for its optimization have been presented. The two-dimensional cutting problem can be solved by using algorithms for the two-dimensional knapsack problem. In the two-dimensional cutting problem, there is a large rectangular piece which is considered as the main piece and also there are some other rectangular pieces with smaller areas than the main piece. The purpose of this problem is to cut the largest rectangular sheet so that the smaller sheets can be produced while the resulted wastes to be minimized. Solving the problem of two dimensional cutting is really important in each industry in which sheet cutting is required, because of minimizing the wastes. The existing precise algorithms for solving this problem possess exponential time complexity. In fact, this is a NP-hard problem. Consequently, a precise algorithm is not practically useful especially with a lot of inputs. So other methods should be used to solve these problems. One of them is approximation algorithms. The main contribution of this paper with the aim of reducing wasted parts is to present an approximation algorithm with approximation ratio, where the height and width of each piece is at most K. The computational results also verify the improvements of our algorithm.
Authors
Hajar Aflatouni
Faculty of Electrical, Computer and Information Technology Engineering, Qazvin Branch Islamic Azad University, Qazvin, Iran
Keivan Borna
Faculty of Mathematics and Computer Science, Kharazmi University, Tehran, Iran
مراجع و منابع این Paper:
لیست زیر مراجع و منابع استفاده شده در این Paper را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود Paper لینک شده اند :