ارائه الگوریتمی برای مسئله برش دوبعدی با تقاضا

نویسنده

چکیده

در این مقاله مسئله برش دو بعدی1 با تقاضا، مورد بررسی قرار می‌گیرد. در این مسئله باید با برش ورقهای مستطیل شکل بزرگ، مستطیلهای کوچکتر مورد نیاز به نحوی تولید شوند که ضمن تامین تقاضاهای آنها، ضایعات یا تعداد ورقهای مصرفی حداقل شد. حل این مسئله در هر صنعتی که برش صفحات در آن مورد نیاز باشد از نظر کاهش ضایعات حائز اهمیت خواهد بود. در اکثر مقالات، تقاضای قطعات در نظر گرفته نشده و تنها به مسئله حداقل کردن ضایعات در یک ورق پرداخته شده است. مسئله برش جزء مسائل Np-hard بوده و روشهای دقیق قادر به حل عملی آن نخواهند بود، لذا الگوریتمی فراابتکاری2 با استفاده از روشSA 3برای حل مستقیم مسئله برش با تقاضا، ارائه شده است. در این الگوریتم جواب اولیه با رویه‌ای قانون گرا ایجاد شده و از یک SA داخلی، در فرایند تولید جواب همسایگی در هر تکرار حلقه SA اصلی استفاده شده است این امر موجب کارایی مناسب الگوریتم شده است. به دلیل وجود نداشتن مسائل نمونه به اندازه کافی، روشی برای تولید مسائل تصادفی برش با تقاضا ارائه شده است و به این ترتیب مسائلی در محدوده 10 تا50 نوع قطعه و با تقاضای کل حداکثر 2400 تولید و توسط الگوریتم حل شده است. نتایج محاسباتی نشان دهنده قابل قبول بودن الگوریتم است. این الگوریتم توانسته است برای مسائلی با30 نوع قطعه و تقاضای کل 500 جوابی با ضایعات کمتر از 6 درصد را بیابد

کلیدواژه‌ها


عنوان مقاله [English]

An Algorithm for Two Dimensional Cutting Stock Problems with Demand

نویسنده [English]

  • GH. Moslehi and A. R. Rezaie
چکیده [English]

In this paper, two-dimensional cutting stock problem with demand has been studied.In this problem, cutting of large rectangular sheets into specific small pieces should be carried out hence, the waste will be minimized. Solving this problem is important to decrease waste materials in any industry that requires cutting of sheets. In most previus studies, the demand of pieces has not been usually considered. The cutting problems belong to the category of Np-hard problems. So finding a desirable solution in a suitable time is practically impossible and heuristic methods must be used. A meta-heuristic algorithm using SA approach is presented.Then attempt will be made to regulate the SAs parameters. Initial solutions are produced with a rule based algorithm and two internal and main SAs are used that lead to better performance of the algorithm. Due to lack of benchmark or test problems, two procedures for generating random problems is presented and are used to study efficiency of the algorithm. For this purpose, problems about 10 to 50 types of pieces with maximum demands of 2400 are generated and solved using the proposed algorithm. The results indicate that the algorithm capable of finding a solution with less than 6% of waste for problems with 30 types of pieces and total demands of 500.

کلیدواژه‌ها [English]

  • Two dimensional cutting stock problem
  • Waste
  • Cutting patterns
  • Simulated Annealing

تحت نظارت وف ایرانی