دانلود مقاله یک الگو با مدل «متوسط P» جهت کمینه‌ کردن اتلاف ترکیب و برش با کاربردی در صنعت شیشه

چکیده: یکی از مسائل عمده در صنعت شیشه کمینه کردن اتلاف برش ایجاد شده هنگام بریدن قطعات بزرگ به تکه‌های کوچک می‌باشد.

در بحث و کاربردها قطعات در کارگاه تولید می‌شوند.

بسیاری از اندازه‌های متفاوت قطعات قابل کاربرد هستند و قید و بندهای فنی تعدد الگوهای برش را به تولید تنها یک نوع تکه در قطعه محدود می‌سازد.

بنابراین در یفاتن زیر مجموعه بهینه‌ای از الگوهای برش متمرکز نمی‌شویم بلکه در انتخاب زیرمجموعه بهینه‌ای شامل تعداد محدودی از اندازه‌ها برای قطعات بریده شده تلاش می‌کنیم.

در این مقاله در مورد فرموله کردن برنامه خطی ۰-۱ جهت حل این مسئله براساس الگوی «متوسط 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 با یک الگوی برش «اشباع» (saturating) مطابقت دارد.

بدون انحراف از کلیت موضوع، دقیقا چنین الگوئی با هر زوج (i,j) بنا می‌شود، قرار می‌دهیم xij، درجه و سطح فعالیت آن (Activation).

همچنین قرار می‌دهیم: Cij=wjhj مساحت قطعه Jj (البته در بین همه اندازه‌های قطعات که مقدار یکسانی از تکه‌های نوع i تولید می‌کنند، تنها آنکه کمترین سطح را داراست شامل خواهد شد) فرموله‌سازی گیلمور ـ گوموری از مسئله جهت کمینه کردن اتلاف برش کلی (محاسبه شده طبق بخش ۱-۱) به صورت زیر است: (۱) min c(x)= (۲) برای Ii، (۳) برای J j، Ii، (integer) صحیح و 0 Xij یک راه حل برای برنامه صحیح فوق، الزاماً، شامل ماکزیمم مقدار مجاز «اندازه‌های مختلف قطعات» و «تغییرات پهنا» نخواهد شد.

(عبارات (i) و (ii) از مسئله ۲) بنابراین ثابت‌ها و متغیرهای اضافی باید افزوده شود.

قرار می‌دهیم: ● K= مجموعه پهناهای مختلف کاربردی قطعه‌ها ● J Jk= مجموعه همه اندازه‌های کاربردی قطعه‌های همراه با پهنای kام K)(k قرار می‌دهیم Ik, yi متغیرهای تصمیم‌گیری ۰-۱ تعریف شده برای J j، K k به صورت ذیل: } { یک راه‌حل کاربردی برای مسئله ۲ باید در محدوده ذیل باشد: (۴) برای Ii و J j، Xij (۵) (۶) برای J jو Kk و Zk yj (۷) (۸) ۰ که ] Mij=[یک کران بالا برای سطح فعال الگوی (i,j) است.

۲-۲ یک فرض ساده کننده: اگرچه مسئله (۱) – (۳)، حتی با یک اندازه تکه، مشکل است (بخش ۲-۴ را ببینید).

برنامه‌های تجاری به طور معمول نمونه‌های عملی را در چند ثانیه حل می‌کنند.

اگرچه افزودن نصب‌ها، مکرراً، اینگونه مسائل را دشوار می‌‌سازد.

در واقع، با توجه به محدودیت‌های فعالسازی (۴)، آسان‌سازی خطی مسئله (۱) ـ (۸)، عموماً، برای راه‌انداختن یک روش کارای branch-and-bound (شاخه و جهش) بسیار ضعیف است.

برای مواجه با این معضل، اجازه دهید فرض ساده‌کننده زیر را داشته باشیم.

فرض ۲-۱ هر اندازه تکه Ii باید دقیقاً با یک قطعه اندازه J j تولید شود.

در حقیقت فرض ۲-۱ می‌تواند به راه‌حلهای بهتری منجر شود.

(sub option) همانگونه که در مثال زیر نشان داده شده است.

مثال ۳ فرض کنید می‌خواهیم ۱۳ تکه ۱۰×۱۰ (سانتی‌متری) تولید کنیم، و قطعات A و B با اندازه‌های CA= 20×25 و CB= 20×35 موجودند.

یک الگوی جامع که قطعه A (قطعه B) را شامل شود ۴ (۶) تکه حاصل می‌کند.

در یک روش حل بهینه صرف‌نظر از فرض ۲-۱، می‌توان یک قطعه A و ۲ قطعه B را انتخاب نمود با مصرف کلاً ۱۰۹ سانتی‌متر مربع، در ماده خام.

اگرچه یک راه‌حل بهینه با در نظر گرفتن فرض ۲-۱، ۴ قطعه A می‌دهد با مصرف کلی 2cm2 ماده خام.

قرار می‌دهیم.

d=min iI{di} {Cj/aij} , C=maxjJ{Cj} موارد ذیل می‌تواند ثابت شود.

قضیه‌ها: قرار می‌دهیم X* پاسخ بهینه مسئله ۲.

آنگاه یک پاسخ کاربردی X سازگار با فرض ۲-۱ وجود خواهد داشت و همچنین (۹) برهان: قرار می‌دهیم J:Xij*>0}J(i)={j مجموعه‌ قطعه‌های فعال شده با X* جهت تولید تکه I برای هر Ii، ji اندازه قطعه به شکل: برای همه J(i)j.

یک پاسخ X که نیاز Ii را پوشش دهد با تولید صرفاً di قسمت از قطعه ji به طور مشخص قابل دستیابی است، به عنوان اینکه «اندازه‌های مختلف قطعه» و «تغییرات پهنا» که فعال می‌سازد بیش از X* نباشد.

فرض کنید X* هر Ii را با تولید di1 قسمت از قطعه ۱ پوشش دهد و di2 از قطعه ۲ و ...

و din از قطعه n و di1+di2+di3+…=din هزینه‌های X,X* به روشنی ایجاب می‌کند که: C(x) C(x*) که ما نسبت‌ها را گرد (تقریب) نمی‌کنیم و، در نخستین جهش، بدترین حالت که در آن آخرین قطعه استفاده شده تا تنها یک تکه را ببرد، در نظر می‌گیریم.

از این رو: از آنجا که wihiCj/aij برای هر Ii و Jj داریم که I{wihi}C=mini.

بنابراین در چنین موارد تولید ماده (جرم)، همانگونه که در مورد کارگاه‌ها در این مقاله ذکر شد، فرض ۲-۱ اثر عملیاتی بر کمینه شدن اتلاف برش ندارد (بخش ۳ را برای جزئیات بیشتر ببینید).

اما از دیدگاه محاسباتی فریت آن کاملاً مرتب است.

فرض ۲-۱ در واقع برنامه صحیح (integer) (۳)-(۱) را به partition matroid تبدیل می‌کند، و به عبارتی ساده‌تر، فرموله‌سازی ترکیباتی خالص (و پر بازده‌تری) از مسئله ۲ ارائه می‌کند، همانگونه که در بخش بعد خواهیم دید.

۲-۳ یک الگوی «متوسط – p» "p-median" قرار می‌دهیم: Cij= مساحت قطعه استفاده شده هنگام تولید همه پیش نیازهای تکه i با قطعه j و J)I , j(i همچنین قرار می‌دهیم yij متغیرهای تصمیم‌گیری ۰-۱ (تابع علامت یا همانی م) برای Ii و Jj با شرح ذیل { و قرار می‌دهیم Zk , yi همانگونه که در بخش ۲ تعریف شده‌اند.

یک پاسخ تقریبی (در مورد قضیه‌ها) برای مسئله ۲ با تحلیل برنامه خطی ۰-۱ زیر به دست می‌آید: (۱۰) min (۱۱) Ii (۱۲) Jj Ii yiyij (۱۳) (۱۴) Kk و Jkj Zkyi (۱۵) (۱۶) عدد صحیح و ۰ هدف فرمولهای ۱۶ تا ۱۰ کمینه کردن اتلاف کلی برش است.

محدودیتهای ۱۱ تا ۱۳ و عبارات (۱۶) ناحیه کاربردی یک مسئله «متوسط ـ p» (p-mediam) را توصیف می‌کند.

در حالت خاص، محدودیتهای (۱۱) مطلوبیت را تضمین می‌کنند و محدودیتهای (۱۲) قطعه j را هنگام استفاده برخی تکه‌های (i) فعال می‌کنند.

محدودیت (۱۳) ترکیب اندازه‌های قطعه تولید شده را محدود می‌کند.

افزون شرط‌های (۱۴) (۱۵) اجازه کنترل تعداد تغییرات پهنا را می‌دهد.

به ویژه شرط (۱۴) متغیرهای Zk را فعال می‌سازد و شرط (۱۵) تغییرات را به ماکزیمم مجاز q محدود می‌سازد.

قضیه ۴ بیان می‌کند.

نتیجه ۵: برنامه (۱۶) – (۱۰) کاملاً دقیق است که پاسخ‌های بهینه آن به پاسخ بهینه مسئله ۲ میل می‌کند همانگونه که پیش نیازهای مینیمم تکه‌ها افزایش می‌یابد.

فرمولهای (۱۶) – (۱۰) می‌تواند با افزودن نامعادلات مناسب توسعه یابد.

پیشنهاد ۶: آسان‌سازی خطی برنامه (۱۶)(۱۰) یک پاسخ (۱۷) نیز هست بنابراین ما به سادگی باید نشان دهیم آسان‌سازی خطی فرمولهای (۱۶)(۱۰) با نامعادلات زیر پیاده‌سازی می‌شود.

, iI , kK برهان: به طور واضح، هر پاسخ صحیح (۱۶)-(۱۰) یک پاسخ (۱۷) نیز هست.

بنابراین ما، به آسانی، باید نشان دهیم آسان‌سازی خطی فرمول (۱۶)-(۱۰) یک پاسخ منفصل و چند تکه می‌پذیرد که با برخی از موارد شرط (۱۷) از هم جدا می‌شوند.

در واقع تصور کنید قطعه‌های (۱) و (۲) پهنای یکسانی دارند.

سپس: Y11=y21=X12=X22=0.5 , y1=y2=0.5 , Z1=0.5 پاسخی است برای z1y1z1 , yi1y2 (i=1,2) yi2 اما اذعان نمی‌کند z2z1 , yz1+yz2y11+y12 مشاهده کنید که اگرچه نامعادلات (۱۴) می‌تواند با نامعادلات (۱۷) در فرمولهای (۱۶)-(۱۰) جایگزین شوند.

آخری و نهائی در تأثیر عمومی قالب، در آسان‌سازی خطی مسئله، همانگونه که در مثال ذیل نشان داده شده، نیست.

مثال ۷: مجدداً تصور کنید قطعات ۱ و ۲ پهنای یکسانی دارند.

آنگاه نکته: Y11+y12z16 y21+y22z2 اما تأئید نمی‌کند که z1z1 , y1y2 ۲-۴ نکته‌ای درباره پیچیدگی (میزان دشواری) پیچیدگی محاسباتی مسئله ۲ فوراً با مشاهده برنامه (۳)-(۱) معلوم می‌شود.

که برای یک تکه منفرد از اندازه واحدی نوشته شده است، به ما اجازه می‌دهد تا اعداد صحیح و مثبت x1, …,xn را با جست و جو و چک‌کردن بیابیم.

dc1x1+c2x2+…+cnxndَ که در آن: َdd0 بنابراین مسئله برای m=1 دشوار است و مستقلاً در هر جهش در تعداد اندازه‌های قطعه یا تغییرات «پهنا» به عبارتی حتی اگر p=q=n.

همانگونه که در بخش ۲-۳ گفته شد: فرض ۲-۱ تقریب زدن پاسخ مسئله ۲ را از طریق یک الگوی متوسط – p ویژه (p-mediam) ممکن می‌سازد.

هر گاه p=q=n الگو به یک partition mutrnid تبدیل می‌شود و می‌تواند از طریق الگوریتم greedy حل شود.

به علت بی‌اساس بودن p و q ما نمی‌توانیم پیچیدگی الگو برای مسئله «متوسط - p» عمومی را کسب کنیم.

از آنجا که Cijها در حقیقت نامطلوب و ناخوشایند هستند (آنها در واقع به عنوان کمترین سطح قابل برش همه تکه‌های مورد نیاز اندازه i از قطعه‌های اندازه j هستند).

می‌توان ثابت کرد: قضیه ۸: مسئله ۲ حتی تحت فرض ۲-۱ NP-hard است.

برهان: با کاهش از پوشش مجموعه: مجموعه F از زیر مجموعه‌های مختلف مجموعه معین S داده شده است و یک عدد صحیح k، زیر مجموعه C از F را می‌دهد به نحوی که هر عنصر S حداقل به یک عضو C متعلق باشد و kc از نسخه تصمیم‌گیری، نمونه‌ای از مسئله ۲، شامل عدد صحیح و مثبت c که نشان دهنده جهش بالاتری به سطح قطعات استفاده شده در پاسخ است، می‌باشد.

ترسیم نمونه‌ای که p=k و تکه‌ها (قطعه‌ها) دارای تطابق یک به یک با عناصر S (از F) باشند.

تکه‌ها و قطعه‌ها پهنای یکسان w را دارند و q=1.

ارتفاع hi از تکه Ii با i امین عدد نخستین ni معادل است.

قرار می‌دهیم SiCS عضوی از F.

ارتفاع قطعه مطابق Jj با ni sjhj=IIi داده می‌شود (توجه کنید که اندازه‌های تکه و قطعه همگی از یکدیگر متفاوتند) برای تعریف پیش‌نیاز di از تکه Jj، توجه کنید که مجموعه Fi از اعضای F شامل عناصر مطابق S است و sj}F/iFi={sj سپس: di=1 cm {hj/sjFi} در نهایت c=w که ما برای پاسخ‌های با اتلاف برش صفر جست و جو می‌کنیم.

(توجه کنید که ساختار می‌تواند در زمان و فضای چند جمله‌ای عمل شود: در واقع ni (m+n+1))2m2) بیت خواهد بود.

یک پاسخ نمونه بالا مجموعهP از J J*از اندازه های متفاوت قطعه که از آن می‌توان دقیقاً di تکه برای هر اندازه Ii بدون اتلاف برش بریده شود را می‌دهد.

به مجموعه J*}F/jC={Sj توجه می‌کنیم.

ملاحظه می‌کنیم که برای هر Jj و Ii ، hi، hj را تقسیم می‌کند اگر و تنها اگر sjI بنابراین به منظور داشتن پاسخ با اتلاف برش صفر، قطعه j می‌تواند برای تولید فقط تکه‌های sj استفاده شود.

از این رو برای هر Ii s ) (iوجود دارد J*c)jsj) به نحوی که i از j بریده می‌شود (i متعلق است به sj).

بنابراین C پوششی از S با عناصر p=k خواهد بود.

بالعکس، قرار می‌دهیم C پوششی از S و Ci کلیه مجموعه‌های C شامل si وFiِsj}ِC/i={sj Ci و قرار می‌دهیم J* (قرار می‌دهیم J*i) شامل همه اندازه‌های قطعه مطابق اعضای C (از Ci).

از آنجا که hj/hi (صحیح) تعداد تکه‌های اندازه hi تولید شده با قطعه منفردی از اندازه hj است، سطوح فعالسازی xij از الگوهای J*ij باید معادله dinphantine زیر را تأیید نمایند.

که وجود di/hn عدد صحیح برای هر cik.

پاسخ xij=dihi/hj برای xij=0 و j=k و برای kj را می‌پذیرد.

چنین پاسخی به وضوح فرض ۲-۱ را تأئید می‌کند.

جدول ۱ و شکل ۲ وابستگی پیچیدگی مسئله به فرضها و محدودیت‌های مختلف را نشان می‌دهد.

جدول ۱: پیچیدگی مسائل ذکر شده fijz شکل ۲ کاهش‌های زمان ـ چند جمله‌ای بین مسائل مورد بحث ۳ تجربه محاسباتی یک آزمون محاسباتی قبلی روی داده‌های حقیقی کسب شده از کارگاه انجام شد.

آزمون برآورد می‌کند: ● اندازه الگوهای بهینه‌سازی جهت متغیرها و ثابت‌ها ● ذخایر تلف شده ● جهش تئوری (۹) و تقریب حقیقی و واقعی ● محاسبه زمان و مقدار گره‌های (nodes) شاخه و جهش (branch-and-bound) کاوش شده کلیه برنامه‌های صحیح با cplex8.0 با تنظیمات اولیه (default setting) یک pentium III 400MHZ با RAM, 120mb انجام شد.

۱۰ نمونه مسئله حقیقی حل شد.

برای هر نمونه جدول ۲ تعداد m از هر نوع تکه تولید شده را گزارش می‌کند.

همچنین ماکزیمم مجاز ترکیب (p) و تغییرات پهنا (q)، تولید کلی مورد نیاز (مقدار تکه‌ها) و شبکه پیش نیازها و ملزومات ماده‌ای (مترمربع).

اندازه‌های برنامه های صحیح مطابق (تعداد متغیرها و ثابت‌های نتیجه‌گیری شده بعد از پیش پردازش (pre-processing) نیز برای الگوی متوسط ـ p (۱۶)-(۱۰) و پیاده‌سازی آن (۱۷)-(۱۰)، درج نشده‌اند.

جدول ۲: ۱۰ نمونه مسئله از کارگاه: تعداد تکه‌های مختلف مورد نیاز، مقدار مجاز اندازه‌های مختلف قطعه و تغییرات پهنا، تکه‌های مورد نیاز در کل، شبکه ملزومات ماده‌ای و اندازه‌های برنامه های صحیح حل شده.

جدول ۳ پاسخ‌های مختلف به ۱۰ نمونه مسئله کارگاهی: عملیات فعلی کارگاهی برنامه (۱۷)(۱۰) ـ برنامه (۸)-(۱۰) جدول ۳ پاسخ‌های به دست آمده با کاربرد را نشان می‌دهد.

(ستون ۱)، در مقایسه با آنهائی که از طریق برنامه‌های صحیح محاسبه شده‌اند (۱۷)-(۱۰) (دومین ستون) و (۸)-(۱) (سومین ستون).

دومین و سومین ستون به دو قسمت تقسیم شده‌اند تا درصد ذخیره شده توسط دو الگو را نشان دهند.

ذخیره شده‌های به دست آمده از دو مدل سازگارند: برای الگوی «متوسط ـ p» (۱۷)-(۱۰)، تغییر می‌کنند بین 385٪ و 29/78٪ برای الگوی (۸)(۱) بین 60/8٪ و 61/78٪.

در واقع برای یک شبکه ملزومات کلی 908/189/4 مترمربع، کاربر اتلاف 81/2٪ می‌افزاید که معادل 393/118 مترمربع خواهد بود.

با الگوی «متوسط ـ P» چنین اتلافی 10/48٪ کاهش می‌یابد یعنی 446/61 مترمربع.

پاسخ بهینه تقریباً همان است: کاهش اتلاف 28/48٪ معادل 068/61 مترمربع.

این روش مناسب الگوی (۱۷)(۱۰) به جزئیات در جدول ۴ آورده شده است که برای هر نمونه، نسبت تقریبی به دست آمده در عمل با تئوری داده شده در قضیه ۴ مقایسه شده است.

خلأ قابل ملاحظه نمونه VR+31، استنثا و پیش‌نیاز کوچک d برای نوع تکه منفرد می‌باشد.

جدول ۴ مقایسه بین جهش تئوری (قضیه ۴) و تقریب عملی حاصل شده از برنامه (۱۷)(۱۰) در ۱۰ نمونه مسئله کارگاهی در نهایت جدول ۵ عملکرد محاسباتی حاصل شده از همه نمونه‌ها با پیاده‌سازی الگوی «متوسط ـ P» و «متوسط ـ P» (۱۶)-(۱۰) و الگوی (۸)-(۱).

را بیان می‌کند.

عملکرد با زمان (ثانیه ها) cpu توصیف می‌شود.

همچنین تعداد گره‌های شاخه ـ و ـ جهش (bromch and bound) کاوش شده با Cplex8.0 و خلاء انباشتگی (پاسخهای جاری در قیاس با بهتری جهش کوتاه‌تر) اطلاعات برای پارامتر نهائی، بعد از پیش پردازش Cplex8.0 در تنظیمات اولیه d(default setting) جمع‌آوری می‌شوند.

علامت (*) در ستون cpu نشان می‌دهد که بهینه‌سازی پاسخهای جاری نمی‌تواند بعد از ۱۰۰۰ ثانیه نشان داده شوند.

این هرگز با الگوی «متوسط ـ p» رخ نمی‌دهد.

گرچه در ۶ نمونه مدل (۸)(۱) رخ داده است.

جدول همچنین براثر نامعادلات (۱۷) در نمونه‌های مختلف دلالت می‌کند: VR38، VR+38 و مهمترین آن VR+31، DPT32 جدول ۵ زمانها (ثانیه‌ها‌ی) cpu گره‌های کاوش شده (Cplex8.0) و انباشتگی خلاء در پاسخ ۱۰ مسئله نمونه کسب شده و از کارگاه از طریق برنامه (۱۷)-(۱۰) و (۱۶)-(۱۰) و (۸)-(۱) مراجع: 1.

Al-Khayyal F PM… دشواریمسئلهیک اندازه قطعه در تکهیک اندازه تکه در قطعهP اندازه‌های قطعهسختقطعه برشـــسختمسئله (۳)-(۱)ـ×ـآسانمسئله (۳)(۱)+ فرض ۲-۱××ـسختقطعه برش با نصبــ×سختمسئله ۲ـ××سخت(۱۶)-(۱۰) مسئله = ۲-۱ فرض + مسئله ۲××× ۱۶-۱۰۱۶-۱۰۱۶-۱۰۱۶-۱۰سطح کلی مورد نیاز (m2)qpmمسئله نمونهثابتمتغیرثابتمتغیرسطح کلی مورد نیاز (m2)qpmمسئله نمونه (۸)(۱)(۸)(۱)۱۷-۱۰۱۷-۱۰(کاربر) اتلاف ٪مسئله نمونهذخیره شدهاتلاف ٪ذخیره شده ٪اتلاف ٪اتلاف ٪ تقریب عملی ٪جهش تئوری ٪مسئله نمونه (۸)(۱)(۸)(۱)(۸)(۱)(۱۶)(۱۰)(۱۶)(۱۰)(۱۶)(۱۰)(۱۷)(۱۰)(۱۷)(۱۰)(۱۷)(۱۰)مسئله نمونه٪ خلاءگرهCpu٪ خلاءگره‌هاCpuخلا٪گرهCpu