چکیده:
در این مقاله، مساله برش دو بعدی با تقاضا مورد بررسی قرار میگیرد. در این مساله با برش ورقهای مستطیل شکل بزرگ، مستطیلهای کوچکتر مورد نیاز باید به نحوی تولید شوند که ضمن تامین تقاضا برای آنها، ضایعات یا تعداد ورقهای مصرفی حداقل شود. مساله برش، جزء مسائل NP-Hard است که روشهای دقیق قادر، به حل عملی آنها نیستند. لذا در این مقاله با استفاده از الگوریتم پرواز پرندگان، الگوریتمی فراابتکاری برای حل مساله برش دو بعدی با تقاضا ارائه شده است. برای بهبود کارایی این الگوریتم و جلوگیری از همپوشانی در مساله برش، الگوریتم ابتکاری CUL به کار گرفته شد.
خلاصه ماشینی:
لذا در این مقاله با استفاده از الگوریتم پرواز پرندگان ، الگوریتمی فراابتکاری برای حل مسأله برش دو بعدی با تقاضا ارائه شده است .
همچنین برای بررسی نتایج الگوریتم پیشنهادی (ترکیب الگوریتم های PSO و CUL) نرم افزاری تهیه شد که با در نظر گرفتن طول و عرض صفحه اصلی و با توجه به اندازه های قطعات و تعداد مورد تقاضا، بهترین الگوی برش ممکن را ارائه میدهد.
در سال های اخیر، محققان بسیاری به شاخه های متفاوت مسأله برش پرداخته اند و روش های متعددی برای بهینه سازی این مسأله توسعه داده شده است [٢٢، ٢٥، ٢٦، ٣٤، ٥٣، ٥٧].
بیزلی [٥] برای یافتن یک سبک برش بهینه یا حل مسأله برش بدون تقاضا، از روش برنامه ریزی پویا استفاده کرد و رابطه های بازگشتی را بر این مبنا ارائه داد که حداکثر ارزش یک مستطیل برای تبدیل آن به قطعات ، در یکی از سه حالت برش ندادن ، برش دادن عمودی یا برش دادن افقی آن ایجاد میشود.
از روش های فرا ابتکاری نیز برای حل مسأله برش استفاده شده است .
از پژوهش های دیگری که در آنها از رویکرد ابتکاری برای حل مسأله برش دوبعدی استفاده شده است ، میتوان به [٢٨، ٣٩] اشاره کرد.
لذا الگوریتمی فرا ابتکاری در این مقاله ارائه شده است که با استفاده از الگوریتم پرواز پرندگان ، به حل مسأله برش پرداخته است .
Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation.
A Hybrid Algorithm Based on PSO and Genetic Operation and Its Applications For Cutting Stock Problem.