مقاله انگلیسی رایگان در مورد اکتشاف ترکیبی بر اساس جستجوی درختی برای تنظیم مسئله کوله‌ پشتی( الزویر )

مقاله سال 2016

مسائل تنظیمات کوله‌پشتی (KPS) در تحقیقات اخیر با توجه به کاربرد بالقوه آن‌ها در مدل‌سازی مسائل مالی و صنعتی واقعی مختلف، از جمله پذیرش سفارش و برنامه‌ریزی تولید، توجه فزاینده‌ای را به خود معطوف کرده است. مسئله KPS شامل انتخاب درست آیتم‌ها از یک مجموعه از خانواده متلاشی آیتم‌ها برای ورود یک کوله‌پشتی است، و در عین حال ارزش آن را به حداکثر می‌رساند. یک آیتم فقط در صورتی انتخاب می‌شود که تنظیمات برای خانواده‌ای که به آن تعلق دارد ، انجام شود. در این مقاله، ما یک اکتشاف جستجوی درختی را برای KPS ارائه می‌دهیم که ترکیبی را ایجاد می‌کند که با شکل کوتاه جستجوی درختی به‌طور استراتژیک حرکت می‌کند. ما یک تکنیک جدید احتراز از تکرار را اتخاذ می‌کنیم که شامل تبدیل مسئله KPS به یک شاخص عدد صحیح است. کارایی روش پیشنهادی توسط آزمایشات محاسباتی از جمله یک مجموعه از نمونه‌هایی که به‌طور تصادفی ایجادشده‌اند، ارزیابی می‌شود. نتایج، تأثیر تکنیک احتراز از تکرار را در قالب ارتقاء کیفیت راه‌حل و زمان محاسبه نشان می‌دهند. کارایی روش پیشنهادی توسط توانایی آن برای ایجاد راه‌حل‌های بهینه و نزدیک به بهینه در یک زمان محاسباتی کوتاه مورد تأیید قرار گرفت.

1. مقدمه
ما به تنظیمات مسئله کوله‌پشتی به‌عنوان KPS اشاره خواهیم کرد. این آیتم به‌عنوان یک مسئله کوله‌پشتی با تخفیف هزینه‌های اضافی تنظیمات ثابت، هم در تابع هدف و هم در قیدها توضیح داده می‌شود. این مسئله خصوصاً در کاربردهای برنامه‌ریزی تولید در جاییکه نیاز به تنظیمات قبل از راه اندازی تولید وجود دارد، متداول است.
توجه ما به این مدل، در اصل توسط مسائل عملی در یک پروژه تولیدی با یک تولید کننده و تأمین کننده پیشرو از صنایع بسته بندی شیشه ای کشت و گوارش برانگیخته شد. این شرکت چندین نوع محصول شامل شیشه ، بطری‌های دردار، و قوطی‌ها را تولید می‌کند. مهم‌ترین مرحله در روند تولید، مرحله شکل‌دهی است. در واقع، برای تغییر شکل محصول از یک خانواده محصول به خانواده‌ای دیگر ، ماشین‌آلات تولید باید تنظیم شوند و قالب‌های ماشین قالب‌گیری نیز باید تعویض شوند. این تغییرات در روند تولید مستلزم تنظیمات با زمان و هزینه قابل‌توجهی است. فرض کنید که شرکت در زمان T تعدادی سفارش (کار) دریافت می‌کند که متعلق به خانواده محصولات N است. هر خانواده محصول i دارای کارهای ni می‌باشد. همچنین فرض کنید که این کارها باید در دوره برنامه‌ریزی بعدی تولید شوند و ظرفیت تولید شرکت ثابت است و نمی‌تواند در مدت کوتاهی تغییر یابد. بر این اساس، شرکت باید تصمیم بگیرد که چطور سفارشات را با در نظر داشتن حداکثر مجموع سود انتخاب کند. این نشان‌دهنده یک مورد بخصوص است که شامل مدل تنظیمات مسئله کوله‌پشتی می‌باشد و می‌تواند برای حل این مسئله مورداستفاده قرار گیرد.