چکیده: یکی از مسائل عمده در صنعت شیشه کمینه کردن اتلاف برش ایجاد شده هنگام بریدن قطعات بزرگ به تکه‌های کوچک می‌باشد.
در بحث و کاربردها قطعات در کارگاه تولید میشوند.
بسیاری از اندازه‌های متفاوت قطعات قابل کاربرد هستند و قید و بندهای فنی تعدد الگوهای برش را به تولید تنها یک نوع تکه در قطعه محدود می‌سازد.
بنابراین در یفاتن زیر مجموعه بهینه‌ای از الگوهای برش متمرکز نمی‌شویم بلکه در انتخاب زیرمجموعه بهینه‌ای شامل تعداد محدودی از اندازه‌ها برای قطعات بریده شده تلاش می‌کنیم.
در این مقاله در مورد فرموله کردن برنامه خطی ۰-۱ جهت حل این مسئله براساس الگوی «متوسط P» بحث می‌کنیم.
اطلاعات به دست آمده از آزمون این برنامه در عمل، کاهش قابل ملاحظه‌ای را در اتلاف ناشی از برش در عملیات کارگاه موردنظر نشان میدهد.
و به طور واضح در روشهای دقیق مرسوم، از ملاحظات محاسبه زمان به نتایج بهتری می‌رسد.
لغات کلیدی: کمینه کردن اتلاف برش، مسئله ترکیب، مسئله «متوسط P»، برنامه ریزی اعداد صحیح (interger program) ۱.
معرفی یکی از مسائل عمده بسیاری از تولیدکنندگان کمینه کردن اتلاف برش ناشی از بریدن قطعات بزرگ به تکه‌های کوچک می‌باشد.
این مسئله به طور عمومی به عنوان «برش قطعات» شناخته میشود [۵] و به نحو گسترده‌ای و به روشهای مختلف، مطابق با دیدگاه فنی فرایند تولید، محدودیتها و اهداف آن، مورد مطالعه قرار گرفته است.
یک بخش مهم و مشکل مسئله هنگامی است که سازماندهی (نصب) نیز شامل میشود.
هدف این مقاله معرفی روشی جدید برای حل کردن دسته‌ای از مسائل برش قطعات به همراه سازماندهی می‌باشد.
این روش بر پایه فرموله‌سازی مسئله با توجه به الگوی «متوسط P» بهترین راه حل را در یک نسبت ثابت و پر بازده‌تر از روشهای دقیق کلاسیک استفاده شده برای مسائل مشابه، تقریب می‌کند.
در این مقاله، این روش را درباره مشکلی که از همین نوع و در یکی از مشهورترین کارخانه‌های شیشه جهان وجود دارد، امتحان می‌کنیم.
یک فاز کلیدی فرایند تولید شیشه، که یک قسمت مرتبط با کل اتلاف برش ایجاد شده می‌باشد، از برش قطعات مستطیلی بزرگ به تکه‌های کوچک به سایزهای مختلف تشکیل شده است.
در بسیاری از صنایع، کمینه کردن اتلاف برش ناشی از چندین فازی، یک مسئله دوبعدی برش قطعات است که یافتن بهترین چینش تکه‌های مورد نیاز در قطعات اندازه‌ای مشخص، مطلوب است.
یک ترکیب تکه‌ها در یک قطعه ساده الگوی برشی را که چندین بار قابل تکثیر است، معرفی می‌کند و عموماً شامل تکه‌هائی از سایزهای مختلف میشود.
در کاربرد ما: (۱) قطعات در کارگاه تولید میشوند و تعداد زیادی از اندازه‌های متفاوت قطعات قابل کاربرد هستند.
(۲) معیارها و محدودیتهای سازماندهی و تکنولوژیکی تعدد الگوهای برش را به تولید نوع ساده‌ای از تکه‌ها در قطعات محدود می‌کند.
با توجه به (۱) و (۲) فوق، توجه اصلی به انتخاب اندازه‌های قطعات میشود نه الگوهای برش.
از آنجا که اندازه‌های قطعات متغیرهای تصمیم‌گیری هستند و نه داده‌های مسئله، می‌توان در کل اندازه ایده‌آل قطعات بدون اتلاف برش را که به عنوان اجتماع اندازه‌های تکه‌ها به دست می‌آیند را انتخاب نمود.
اگرچه، با توجه به هزینه‌های نصب و طیف (تولورانس) برش، امکان تولید همه اندازه های قطعات ایده‌آل مورد نیاز برای پوشش دادن تکه‌های مورد نیاز در طول دوره برنامه ریزی موجود نیست.
بنابراین یک راه برای رسیدن به اتلاف برش صفر، در عمل، قابل دستیابی نیست.
علاوه بر این، این مثال ساده نشان میدهد که ممکن است قطعه ایده‌آل و استانداردی برای کمینه شدن اتلاف برش یافت نشود.
مثال ۱: فرض کنید ما باید d1=4.8 تکه 145×57 و d2=4.8 تکه 135×60 (سانتی‌متری) تولید کنیم.
و هزینه‌های نصب ما را مجبور به استفاده از تنها یک سایز قطعه می‌نماید.
همچنین تصور کنید، با توجه به طیف شکاف دهنده‌ها و تولورانس تنها دو سایز قطعه استاندارد و ایده‌آل قابل کاربرد است: 580×285 برای مورد ۱ و 540×300 برای مورد ۲ (هر قطعه از ۲۰ تکه حاصل شده است).
یافتن اندازه نهائی قطعه باعث ایجاد (10216) 10071 مترمربع اتلاف برش خواهد شد.
در حالی که یک قطعه 580×300؛ که برای هیچ کدام از دو نوع تکه ایده‌ال نیست.
تنها 497 مترمربع اتلاف ایجاد خواهد نمود.
بحث فوق در مورد تمایل برای «مسئله ترکیب» (Assorment Problem) ویژه، که می‌خواهیم مجموعه محدودی از «اندازه‌های قطعات» که به ما اجازه تولید کارگاه و جزئیات فرایند را توصیف می‌کنیم که به این مسئله مربوط هستند.(۱۰۱) و در مورد مسائل مشابهی که در این حوزه با آن مواجه می‌شویم بحث می‌کنیم.
(۱۰۲) ادامه مقاله به ترتیب ذیل سازماندهی شده است.
در بخش ۲ یک تعریف رسمی سهل‌الوصول و آسان به شکل برنامه خطی صحیح (integer linear programming) در بخش ۲-۱ توصیف میشود یک فرض ساده‌کننده در بخش ۲-۲ پیشنهاد میشود و نتایج آن تحلیل میشوند.
براساس این فرض در بخش ۲-۳ یک مدل «متوسط P» (p-mediam) برای کمینه کردن اتلاف برش و ترکیب معرفی و بررسی می‌کنیم و آن را به فرموله‌سازی برنامه خطی ۰-۱ با محدودیتهای جانبی که ویژگیهای فرایند واقعی است متصل می‌نمائیم.
بخشی راجع به پیچیدگی روشهای توصیف شده و مسائل بهینه سازی مربوطه در بخش ۲-۴ خواهیم داشت.
در بخش ۳ از اطلاعات این زمینه، روشها و راه‌کارها آزمون خواهد شد.
نتایج محاسباتی کاربری و بازدهی مدل (p-mediam) متوسط P را نشان می‌دهند که در هر دو بخش روشهای حال حاضر کارگراهی (با کاهش قابل توجه اتلاف برش) و روشهای دقیق جاری (با راه‌حلهای مشابه به دست آمده در زمانی فوق‌العاده کوتاه‌تر)، به نتایج بهتری می‌رسد.
۱-۱.
ویژگی‌ها و امتیازات فرایند پایه‌ای فرایند تولید متشکل از سه فاز عمده می‌باشد: (شکل ۱ را ببینید) ۱.
شناوری: شیشه در کوره ذوب میشود.
نواری از شیشه صاف کوره را ترک می‌کند و روی یک تسمه جریان می‌یابد.
صفحات مستطیلی (قطعات) دارای اندازه‌های پهنا [610 و 450] و ارتفاع [321 و 280] (داده‌ها به سانتی‌متر هستند) میباشند که به وسیله تغییر پهنای نوارها و برشگرهای عمودی حاصل میشوند.
یک هزینه (ثابت) هنگام اتلاف شیشه طی نصب، به ازای هر تغییر در پهنا وجود خواهد داشت در حالی که تغییرات ارتفاع هزینه نصب ایجاد نخواهد کرد.
در انتهای مرحله قطعات بسته‌بندی میشوند و به انبار فرستاده میشوند.
۲.
برش آف لاین (offline cotting): قطعات از انبار آورده شده به قسمتهای مستطیلی کوچکتری (مطابق با نیازها) بریده میشوند (تکه‌ها).
پنج ماشین برش که هر کدام با یک سیستم محافظه خارجی تجهیز شده‌اند.
با پیشرفت تولید، محافظ با تکه‌هائی از یک اندازه پر میشود تا هنگامی که بسته‌بندی کامل شود و به دنبال آن، محافظ (بافر) تخلیه میشود.
از آنجا که تکه‌های در حال انتقال امکان گردش ندارند، همه تکه‌های الگوی برش به روش یکسانی جا می‌افتند.
۳.
شکل دهی: یک یا چند قسمت معین از هر تکه مستطیلی بعد از قالب‌گیری و خم‌کاری به دست می‌آید.
چهار نوع شیشه رنگی تولید میشود.
از آنجا که تغییر رنگ گران‌ترین است (می‌تواند سه روز ببرد) طرح تولید اصلی به طور چرخه‌ای در فرایندهائی از ۱۰ روز تا ۲ ماه، سازماندهی شده است و در هر فرایند از همان رنگ تولید میشود.
بنابراین برنامه‌ریزی افق تولید مرحله شناوری (float) با همه چرخه تولید مطابقت دارد.
به عبارتی با دوره بین دو فرآیند از تولید یک رنگ واحد.
همانگونه که قبل از این ملاحظه شد تکه‌های نهائی مستقیماً در مرحله شناوری تولید نمی‌شوند بلکه قطعات تولید میشوند که اجزای میانی جهت برش مجدد در مراحل بعدی هستند.
این روش جهت ساماندهی سفارشهای خارج از طرح و برنامه به کار گرفته میشود.
در حقیقت سفارشات مشتریان در مراحل پیشرفته تنها در یک ماه کاملا شناخته میشود.
در حالی که طول افق طرح‌ریزی براساس برآورد ملزومات محاسبه میشود.
اگرچه امکان ترکیب اندازه‌های مختلف قطعات به توسعه به کارگیری مواد کمک خواهد کرد[۷].
ترکیب اندازه‌های قطعات در انبار باید در مقدار معینی، به منظور برآمدن نیازهای تحویل قطعه و کاهش هزینه‌های نصب، برای ماشینهای برش، حفظ شود.
منابع اتلاف از چهار نوع هستند: ● نقص و عیب شیشه (به مقدار ۸-۹ درصد تولید کل) ● اتلاف برش به ازای تغییرات پهنا و برش آف‌لاین (offline) (۴-۵٪) ● شکستگیهای هنگام تحویل (تقریباً ۳٪) ● شکستگیهای هنگام برش آف‌لاین (offline cutting) (کمتر از ۱ درصد) در این مقاله ما روی اتلاف برش به ازای تغییرات پهنا و برش آف‌لاین متمرکز می‌شویم.
این اتلاف ۳۰٪ اتلاف کل را شامل میشود و می‌تواند با برنامه‌ریزی اندکی در حد قابل ملاحظه‌ای کاهش یابد.
در بحث ما، اتلاف برش با تفاوت بین سطح کل ماده استفاده شده و سطح کل ماده به دست آمده و مطلوب محاسبه میشود.
بر این اساس «بیش تولیدی» (over production) به عنوان افت محاسبه میشود.
در حقیقت، اگر نوعی «تکه» (item) بیش تولید شود، بیش تولیدی شامل برش تنها یک قطعه خواهد شد، و هزینه سازماندهی این تکه‌ها از ارزش خود تکه‌ها بیشتر خواهد شد.
۱-۲.
مسائل مرتبط Al-khayal et al [۱] (مرجع شماره ۱) آل خیال محیط صنعتی مشابهی را توصیف می‌کند اما مسئله متفاوتی را بررسی می‌کند.
در این حالت تکه‌های (item) مورد نیاز، در واقع، مستقیماً از نوار شیشه‌ای بریده میشوند و با استفاده از «خطوط محرک» (spurlines) تخلیه میشوند.
برخلاف بحث ما، اندازه‌های متفاوت «تکه» با یک الگوی برش یکسان می‌تواند تولید شود.
علاوه بر این، از آنجائی که نصب‌های واقع شده در خطوط محرک (spurlines) به اندازه تکه‌ها وابسته است الزاماً تکه‌ها باید آسان و به سهولت لیست‌بندی شوند.
بنابراین یک مسئله دو بعدی برش قطعه به همراه مسئله لیست‌بندی خواهیم داشت.
در متون موجود، مسئله برش قطعه که در آن الگوهای برش به منظور داشتن اجزاء میانی و قسمتهای نهائی به کار گرفته شوند، غالباً «چند مرحله‌ای» (multistage) نامیده میشوند.
منابع [۶] و [۱۲] را ببینید.
اگرچه فرایندی که در این مقاله مورد نظر است از بیش از یک مرحله تشکیل شده است، مسئله ما به طور مناسبی نمی‌تواند در چنین زمره‌ای قرار گیرد.
در حقیقت هیچ الگوی برشی مولد اندازه‌های مختلف قطعه ها در مرحله شناوری به کار نرفته است.
اما پهناهای مختلف قطعه به سادگی با باریک و عریض کردن نوار شیشه‌ای به دست می‌آیند و اتلاف در این مرحله تنها در طی تغییرات پهنا رخ میدهد.
با توجه به برخی موارد، مسئله ما با یک قطعه برش با اندازه‌های متعدد قطعه مرتبط است.
در متون، دلایل متعددی برای این مسئله یافته میشود، آغاز آن با کارهای اساسی «گیلمور» (Gilmore) و «گوموری» (Gomory) [۷] و اخیراً با «اسچیلینگ» [Schilling] و «جورجیادیس» (Georgiadis) [۹] و «بلو» (Belov) و «اسچتاور» (Scheithouer)[۳] مسئله تقریباً همیشه با فرموله‌سازی کلاسیک گیلمور و گوموری مدل‌سازی میشود، که تعدد اندازه‌های قطعه با حل مسئله مشخص قیمت‌گذاری هر اندازه قطعه سازماندهی میشود.
بلو و اسچتاور گزارش می‌دهند که صرفاً به حساب آوردن اندازه‌های متفاوت قطعه برخاسته از ترکیب غیرمنفی صحیح طول‌های تکه‌ها کافیست و بر این اساس برنامه‌ریزی الگوریتم پویا و فعال تولید الگوهای برش شاخص را آماده می‌کنند.
در حقیقت چنین الگوریتمی می‌تواند به آسانی برای هدف ما تغییر یابد و متحول شود.
علاوه بر این، در مورد ما، فرض (۲) (ii) مسئله قیمت‌گذاری را کم اهمیت خواهد نمود.
اگرچه هنگامی که فرموله‌سازی گیلمور و گوموری برای محدود کردن بیشترین تعداد اندازه‌های استفاده شده سازگار شود، آسان‌سازی آن جهش‌ها ضعیفی خواهد داشت و روش، غیر عملی خواهد شد.
(این عیب، همچنین هنگامی که کسی بخواهد تعداد الگوهای برش مختلف استفاده شده را کاهش دهد یا به حداقل برساند، رخ میدهد) ([۴] [۱۰] [۱۱] را ببینید) مسئله انتخاب بهترین لیست اندازه‌های قطعه‌ها که ترکیب آنها را محدود کند و اتلاف برش را به کمترین برساند به عنوان «مسئله انتخاب ترکیب» یا «مسئله انتخاب اندازه ـ قطعه» (Assortment or stock-size selection pmb.) معروف است.
یک برنامه‌ریزی فرموله‌سازی صحیح و خودآموز حل این مسئله در مرجع [۸] آورده شده است.
با توجه به فرض ۲ (ii) این مسئله تعمیمی از ماست که به هر حال NP-hard باقی می‌ماند.
بخش ۲-۴ را ببینید.
خصوصی‌سازی بیشتر مسئله، که بتوان تنها یک تکه را در هر قطعه برید در منبع [۲] ذکر شده است که الگوریتم برنامه پویای چند جمله‌ای ـ زمان پیشنهاد شده است.
فرموله‌سازی مسئله و روشهای حل: در این بخش در مورد مسئله ذیل بحث می‌کنیم: مسئله ۲: چه اندازه‌های متفاوت قطعه در فرایند جهت برآوردن نیاز تکه‌ها با توجه به موارد زیر باید تولید شود؟
میزان تغییرات پهنا را به مقدار معینی محدود سازد q ترکیب اندازه‌های مختلف قطعه را به مقدار معینی محدود سازد p مساحت قطعات استفاده شده را تا حد ممکن کاهش دهد.
چه هنگام یک اندازه تنهای تکه از هر اندازه قطعه می‌تواند بریده شود؟
با توجه به پارامترهای p و q نمونه‌ای از مسئله ۲ به صورت زیر تعریف شده است: ● J= مجموعه اندازه‌های مختلف قابل دسترس قطعات J=n ● I= مجموعه اندازه‌های مختلف تکه که در فرایند تولید میشود.
I=m ● di= پیش نیاز i امین اندازه تکه Ii جائی که هر تکه یا قطعهIJj با اندازه‌اش همراه است، به صورت زوجی از اعداد صحیح (wj,hj) داده میشود.
۲-۱ فرموله‌سازی به عنوان برنامه‌ریزی خطی صحیح (integer) برای Ii و Jj قرار می‌دهیم aij ماکزیمم عدد تکه‌های I امین اندازه که می‌تواند از قطعه با j امین اندازه بریده شود.
پارامتر aij با یک الگوی برش