بخشی از مقاله
برنامه کاربردی برش موادخام و حل مشکل یک شرکت سازنده
این مقاله یک برنامه کاربردی مشهور را برای حل مشکل شرکتهای تولیدکننده ارائه می‌کند. هدف از برش یک بعدی، بریدن موادخام با طول طراحی شده به تعداد زیاد از الوارهای طویل می‌باشد. شرکتی که ما این تحقیقات را برای آنها انجام دادیم با مشکلات برش الوارهای فلزی جهت پروژه‌های خود مواجه شده بود. ما چندین راه حل مختلف را به حل مشکل
شرکت مذکور نزدیک دیدیم. ۱. طراحی و ساخت یک نرم‌افزار. ۲. گسترش نرم‌افزار شخصی خودمان و ۳. مقایسه این نرم‌افزار با نرم‌افزارهای تجاری موجود در اینترنت. در این مقاله ما تمام آزمایشات خویش را به وسیله این سه روش خلاصه نموده‌ایم. در این مقاله ما همچنین یک benchmark از بسته‌های نرم‌افزاری تجاری موجود در بازار که قابل دسترس هستند ارائه می‌نماییم. سرانجام ما یک محیط visual را جهت افزایش کارایی در حل مشکلات برش و نشان دادن قابلیت اجرایی این مقاله با استفاده از دیتاهای شرکت روی دو پروژه در دست ساخت ارائه خواهیم نمود.
محیط‌های انقیاد: سیستم‌های طراحی پشتیبانی، سیم‌های مدیریت اطلاعات.
معرفی: مواجه شدن شرکتها با برش موادخام بسیار مرسوم است که این مشکل مشمول شرکتهای ساخت و ساز نیز می‌شود. طبق دستورالعمل الوارهای آهنی با طول مطمئن و به تعداد مشخص مورد نیاز واقع می‌شود. این الوارها از الوارهای بلندتری بریده می‌شود که طول آنها بلندتر از 200cm است. مشکل پیدا کردن بهترین و بهینه‌ترین الگوی برش به گونه‌ای است که کل تعداد الوارهای بلند به طور قابل توجهی می‌نیمم شود. موضوعی که به محدودیت الوارهای فلزی کوتاه‌تر به تعداد مورد نیاز منجر می‌شود.
ظهور مشکل: شرکت Mimga Makina که در سال ۱۹۸۳ تأسیس شده یک شرکت تاسیس شده تحت سرپرستی گروه MIMAGO است. هدف اولیه در تأسیس شرکت تولید نیازهای فلزی شرکت سرپرستی کننده بود. محصولات بعدی شرکت بسیار متنوع بودند و بازار بزرگی در بین پیمانکاران پیدا کرده بودند. در حال حاضر شرکت طراحی، تولید و مدیریت اسکلت و داربست‌های متناسب برای سیستم‌ها در تمامی انواع ساخت و سازها مانند سدها، پل‌ها، مراکز تجاری و مراکز صنعتی را انجام می‌دهد و مدیریت می‌نماید. تا به این تاریخ پروژه‌های متعددی که به وسیله Mimag تکمیل شده است که عبارتند از: ۱. ساخت‌ساز خانه (۲۰۰ سایت) ۲. نصب صنعتی، راه‌آهن برقی، سیلوها و صنایع مختلف و کارهای متعددی دیگر که اجرا می‌شوند.
بتون‌های تقویت شده که در اثر ترکیب فلز و استیل به وجود می‌آید در پروژه‌های متعددی توسط Mimag مورد استفاده قرار گرفت که این امر به دلیل مسائل اقتصادی و پایداری آنها بوده است.
یکی از پروژه‌هایی که شرکت Mimag آن را هدایت کرده است «هیدروپروسس pisel/Kerosen و دوباره ساخت CCR» بوده است که در پالایشگاه Zmit از ناحیه Tupras اجرا شده
است.
(Turkey Turpas یکی از بهترین شرکتها است که عایدات بسیار زیادی از طریق فروش به دست آورده است. مقاوم‌سازی عمودی و افقی بعضی از سیلوها در پروژه ذکر شده بود
. اطلاعات واقعی که ما استفاده کرده‌ایم، از پروژه «سیستم رفتاری مصرف آب» که در Adana هدایت شده است می‌باشد. این پروژه جهت مقاوم‌سازی تخته سنگها بود. جهت مشخص کردن مقدار الوار فلزی استفاده شده در بتون مقاوم‌سازی شده، روشهای مختلفی جهت می‌نیمم کردن مقدار براده آهن استفاده شده به کار برده شده الوارهای فلزی استاندارد استفاده در بتون‌های فلزی مقاوم شده 1200cm هستند و قطرهای مختلفی از 6mm تا 50mm دارند (شکل b1) این فلزات مختلف با طولها و قطرهای مختلف می‌بایستی با روشی کارا جهت می‌نیمم کردن براده آهن استفاده شود. مدل ریاضی برای برش یک بعدی در زیر آمده است:
مجموعة الگوها I: مجموعه‌ها
مجموعة طولها J:
تعداد الوارهای بریده شده مطالق الگوی i Xi: متغیرهای طرح
تعداد تکه‌ها با طول j داخل ی الوار با الگوی I aij=: پارامترها
تعداد تکه‌های مورد نیاز از طول j bj:
{
هدف طرح می‌نیمم کردن اعمال قابل مشاهده (۱) است که شامل تعداد کل الوارهای فلزی مورد استفاده می‌باشد. مجموعه محدودیتهای (z) از بریدن شدن تعداد کافی از الوارهای کوتاه‌تر از الوار بلند اطمینان می‌دهد. متغیرهای طرح همگی به مقادیر غیر منفی محدود می‌شوند.
یکی که می‌توانست مشکل را به صورت بهینه حل کند به وسیله استفاده از حل کننده p/mp ارائه شد برای حل مقادیر بزرگی از موجودیت‌ها خوانندگان می‌توانند به مقاله Gomory , Gilmore در سال ۱۹۶۱ رجوع کنند.
حل کردن از طریق مدلسازی به صورت GAMS: اولین راه حلی که ما برای حل مشکل شرکت Migma دنبال نمودیم استفاده از مدل GAMS جهت ساختن و حل کردن یک فرمولاسیون lp بود.
ما مدل GMS خودمان را بر پایه اطلاعات به دست آمده در Kalvelgen در سال ۲۰۰۳ نهاده‌ایم.
ما در ابتدا یک مدل lp برای یکی از پروژه‌های پروژه Tupras ساختیم که این
مدل شامل ۸ طول مختلف بر طبق ضمیمه A بود. یک فایده استفاده از GAMS این است که می‌توانید اطلاعات را به صورت ماتریس و بردار بنویسند. فایده دیگر این است که می‌توانید مطمئن باشید راه‌حل بهینه پیدا می‌شود. به هر حال اشکالات بزرگی هم این نظریه دارد که عبارتند از:
۱. الگو نمی‌تواند توسط زبان مدلسازی GAMS پیاده شود. آن الگوها باید توسط یک برنامه مجزا که برای اهداف کلی‌تری نوشته شده است مثل C++ پیاده سازی شود.
۲. اضافه کردن الگوی جدید نیازمند شکافتن مدل GAMS و اضافه کردن یک سطر جدید به مکان مربوطه است. مدلسازی GAMS بسیار به نشانه‌های غیرصحیح حساس است و می‌دهد پیغام خطای «تفسیر سخت» را هنگامی که نشانه‌های استفاده شده غلط باشند بدهد.
گسترش برنامه بهینه‌سازی lp
کمبودهای استفاده از یک سیستم مثل سیستم GAMS ما را به سوی گسترش یک برنامه بهینه برای حل مسائل هدایت نمود. ما یک برنامه C++ نوشته بودیم که فراهم کننده الگوی اطلاعات ورودی به مدل GAMS بود. به هر حال این اجرای اولیه یکسری از حلقه‌های مجاور را نیز اجرا می‌کرد (یک لوپ برای هر طول جدید) که این امر جهت به وجود آمدن یک الگوی ساده صورت می‌گرفت. همانطور که اجرا نیاز به اعمال تغییرات source codes جهت اطلاعات زیر پروژه‌ای جدید دارد بنابراین هر زیر پروژه نیز تعداد مختلفی از طورها مورد نیازش واقع می‌شود. در ضمن هر تغییر کد در GAMS سبب می‌شد که چون این نرم‌افزار یک نرم‌افزار تجاری بود با هر بار تغییر، مصرف کننده نیاز به یک خرید جدید داشته باشد. بنابراین نیاز به داشتن یک سیستم مدلسازی open-source و شارژ مجانی ضروری به نظر می‌رسید.
p-solve یک حلال مجانی مبتنی بر الگوریتم معکوس برای حل مشکلات برنامه‌نویسی خطی (lp) و کلیکی جهت حل مشکلات lp و Mlp می‌باشد. همانگونه که فکر می‌شد این نرم‌افزار توسط ANSIC گسترش داده شد که می‌تواند توسط سایر زبانها برنامه‌نویسی مثل C++ و java و C# و ویژوال بیسیک به خوبی فراخوانی شود. ما همچنین کد را به برنامه java تغییر دادیم تا استفاده کنندگان بتوانند از قابلیتهای فراوان این برنامه استفاده کنند. ما از "java wrapper" که جهت فعال کردن ارتباط بین موتور اصلی lp-solver با java استفاده می‌شود، استفاده نمودیم. و کد خود را به صورت Eclipse IDE در آوردیم.
برنامه جاوای ما اطلاعات را از یک فایل متنی می‌خواند و سپس به طور مؤ
ثری یک آرایه که جایگزین الگو (مدل) ما بود را به وجود می‌آورد سپس LP-solve را جهت ساختن و حل کردن یک مدل LP فراخوانی می‌نمود.
در حال حاضر برنامه ما یک اینترفیس می‌نیمم شده دارد (می‌نیمم شده به دلیل اینکه GUL وقت cpu را می‌گیرد و حل مسئله برش به کندی انجام می‌شود). برنامه مسئله برش را برای مدلهای کوچک تا ۱۷ نوع طول ظرف مدت ۱ دقیقه حل می‌نماید. اگر طولهای م
ختلف بیشتر شده و به ۲۵ طول مختلف افزایش یابد بیشتر از ۱۰ دقیقه برای حل آن وقت لازم است. راه حل ممکن برای حل این مشکل برش یعنی از طولها از طولهای بلندتر است.
استفاده از نرم‌افزارهای تجاری
یک راه‌حل دیگر برای حل مسئله Mimag احتمال کردن نرم‌افزارهای برش تجاری موجود در روی اینترنت بود. این بسته‌های نرم‌افزاری از طریق جست و جو در موتور گوگل با نوشتن کلمات " 1 dimensional cutting stock prog" در دسترس قرار می‌گیرند. ۳۰ صفحه اول صفحات لیست تمام نرم‌افزارهای اجرایی این موضوع می‌باشند فقط ۷ بسته نرم‌افزاری به صورت نسخه نمایشی بر روی اینترنت بود که می‌توانست موجودیت‌های بیشتر از ۲۵ طول مختلف را برای ما انجام دهد. این نرم‌افزارها و وب سایت آنها در ضمیمه B لیست شده‌اند.
Benchmark کردن نتایج:
بعضی از سوالات مهمی که ممکن در ذهن بیاید در زیر آمده است:
اثرات بسته‌های نرم‌افزاری دانلود شده چگونه می‌تواند با برنامه ما قابل قیاس باشد؟
برنامه تجاری مختلف را چگونه می‌توان با هم مقایسه کرد؟
آیا استفاده از دو نرم‌افزار مختلف در یک زمان برای هر زیر پروژه و اجرای بهتر هر یک از این دو راه حل کار درستی است؟
ایا دسته بندی کردن زیر پروژه‌ها و انتخاب بهترین راه حل بر هر دسته از این زیر پروژه‌ها کارایی را افزایش می‌دهد؟
ما جوابهایی را برای سه سؤال اول بر پایه اطلاعات Mimga پیدا کردیم. برای پاسخ به سؤال چهارم، ما نیاز به داشتن یک نمای عینی که نیازمند کشیدن یک چارت برای مشخص کردن زیر پروژه‌ها است، داریم. ما این نمای عینی را در بخش بعدی آماده نموده‌ایم.
همانگونه که در جدول ۱ دیده می‌شود برنامه جاوا نوشته شده توسط ما فراتر از کارایی‌های همه برنامه‌های تجاری بود. این امر از لحاظ طبیعی قابل انتظار بود زیرا ما از تئوری بهینه‌سازی می‌دانیم که راه حل lp مقادیر بهینه شده‌ای را در اختیار ما می‌گذارد. مورد بعدی که می‌بایست توجه شود این است که هیچکدام از این بسته‌های نرم‌افزاری تجاری به مقدار بهینه تعداد کل الوارها نرسیده‌اند. بنابراین این امر نشان می‌دهد که بسته‌های نرم‌افزاری یک الگوریتم بهینه نیستند اما می‌توانند تکنیکهای ابتکاری را به اجرا در آورند. ما متوجه شدیم که پنج بسته نرم‌افزاری اول راه‌حل‌های بسیار نزدیک به راه حل بهینه بر پایه قیمت، در
دسترس بودن، پشتیبانی online و به ما می‌دهند. در یک نگاه کلی نرم‌افزار 6، نرم‌افزار 7 به طور خالص (کامل) اجرایی شدند. شرکتها از استفاده از نرم‌افزار 7 خودداری می‌کنند. زیرا این نرم‌افزار گران‌ترین نرم‌افزار بین نرم‌افزارهای ما هستند نرم‌افزار 7 فقط با ارسال اطلاعات
به Excel از دیگران مشخص می‌شود. نرم‌افزار 6 بهترین Gul را در قیاس با دیگرا
ن در اختیار دارد. بنابراین انتخاب نرم‌افزار باید بر پایه پارامترهایی مثل:
۱. تست کارایی ۲. نسبت قیمت ۳. قابلیت ورود و خروج ۴. Gul باشد. ما از پاسخگویی به سؤالات ۱ و ۲ دور شدیم در جواب باید گفت که تا زمانی که بسته‌های نرم‌افزاری وظایف خویش را بسیار نزدیک به حالت بهینه عملی می‌کنند هیچ نیازی به استفاده از ۲ بسته نرم‌افزاری دیگر نیست
