یک اکتشاف ترکیبی مبتنی بر جستجوی درختی برای تنظیمات مسئله کوله پشتی
چکیده
مسائل تنظیمات کوله‌پشتی (KPS) در تحقیقات اخیر با توجه به کاربرد بالقوه آن‌ها در مدل‌سازی مسائل مالی و صنعتی واقعی مختلف، از جمله پذیرش سفارش و برنامه‌ریزی تولید، توجه فزاینده‌ای را به خود معطوف کرده است. مسئله KPS شامل انتخاب درست آیتم‌ها از یک مجموعه از خانواده متلاشی آیتم‌ها برای ورود یک کوله‌پشتی است، و در عین حال ارزش آن را به حداکثر می‌رساند. یک آیتم فقط در صورتی انتخاب می‌شود که تنظیمات برای خانواده‌ای که به آن تعلق دارد ، انجام شود. در این مقاله، ما یک اکتشاف جستجوی درختی را برای KPS ارائه می‌دهیم که ترکیبی را ایجاد می‌کند که با شکل کوتاه جستجوی درختی به‌طور استراتژیک حرکت می‌کند. ما یک تکنیک جدید احتراز از تکرار را اتخاذ می‌کنیم که شامل تبدیل مسئله KPS به یک شاخص عدد صحیح است. کارایی روش پیشنهادی توسط آزمایشات محاسباتی از جمله یک مجموعه از نمونه‌هایی که به‌طور تصادفی ایجادشده‌اند، ارزیابی می‌شود. نتایج، تأثیر تکنیک احتراز از تکرار را در قالب ارتقاء کیفیت راه‌حل و زمان محاسبه نشان می‌دهند. کارایی روش پیشنهادی توسط توانایی آن برای ایجاد راه‌حل‌های بهینه و نزدیک به بهینه در یک زمان محاسباتی کوتاه مورد تأیید قرار گرفت.
1. مقدمه
ما به تنظیمات مسئله کوله‌پشتی به‌عنوان KPS اشاره خواهیم کرد. این آیتم به‌عنوان یک مسئله کوله‌پشتی با تخفیف هزینه‌های اضافی تنظیمات ثابت، هم در تابع هدف و هم در قیدها توضیح داده می‌شود. این مسئله خصوصاً در کاربردهای برنامه‌ریزی تولید در جاییکه نیاز به تنظیمات قبل از راه اندازی تولید وجود دارد، متداول است. توجه ما به این مدل، در اصل توسط مسائل عملی در یک پروژه تولیدی با یک تولید کننده و تأمین کننده پیشرو از صنایع بسته بندی شیشه ای کشت و گوارش برانگیخته شد. این شرکت چندین نوع محصول شامل شیشه ، بطری‌های دردار، و قوطی‌ها را تولید می‌کند. مهم‌ترین مرحله در روند تولید، مرحله شکل‌دهی است. در واقع، برای تغییر شکل محصول از یک خانواده محصول به خانواده‌ای دیگر ، ماشین‌آلات تولید باید تنظیم شوند و قالب‌های ماشین قالب‌گیری نیز باید تعویض شوند. این تغییرات در روند تولید مستلزم تنظیمات با زمان و هزینه قابل‌توجهی است. فرض کنید که شرکت در زمان T تعدادی سفارش (کار) دریافت می‌کند که متعلق به خانواده محصولات N است. هر خانواده محصول i دارای کارهای ni می‌باشد. همچنین فرض کنید که این کارها باید در دوره برنامه‌ریزی بعدی تولید شوند و ظرفیت تولید شرکت ثابت است و نمی‌تواند در مدت کوتاهی تغییر یابد. بر این اساس، شرکت باید تصمیم بگیرد که چطور سفارشات را با در نظر داشتن حداکثر مجموع سود انتخاب کند. این نشان‌دهنده یک مورد بخصوص است که شامل مدل تنظیمات مسئله کوله‌پشتی می‌باشد و می‌تواند برای حل این مسئله مورداستفاده قرار گیرد.
abstract
Knapsack Problems with Setups (KPS) have received increasing attention in recent research for their potential use in the modeling of various concrete industrial and financial problems, such as order acceptance and production scheduling. The KPS problem consists in selecting appropriate items, from a set of disjoint families of items, to enter a knapsack while maximizing its value. An individual item can be selected only if a setup is incurred for the family to which it belongs. In this paper, we propose a tree search heuristic to the KPS that generates compound moves by a strategically truncated form of tree search. We adopt a new avoid duplication technique that consists in converting a KPS solution to an integer index. The efficiency of the proposed method is evaluated by computational experiments involving a set of randomly generated instances. The results demonstrate the impact of the avoiding duplication technique in terms of enhancing solution quality and computation time. The efficiency of the proposed method was confirmed by its ability to produce optimal and near optimal solutions in a short computation time.
1. Introduction
We will refer to the Knapsack Problem with Setup as KPS. It is described as a knapsack problem with additional fixed setup costs discounted both in the objective function and in the constraints. This problem is particularly prevalent in production planning applications where resources need to be set up before a production run. Our interest in this model was originally motivated by practical problems at a production project with a leading manufacturer and supplier of agro-alimentary glass packing industry. This company produces several types of products, including bottles, flacons, and pots. The most important phase in the manufacturing process, is the phase of shaping. In fact, to change the production from one product family to another, the production machinery must be set up and molds must be changed in the molding machine. These changes in the manufacturing process require significant setup time and costs. Assume at time T, the company receive some orders (jobs), wich belong to N product families. Each product family i, has ni jobs. Also assume that these jobs should be produced in the next planning period and the company’s manufacturing capacity is fixed and can’t be changed in the short term. Accordingly, the company needs to decide on how to choose orders so as to maximize the total profit. This represents a typical case involving a knapsack problem with setup model that can be used to solve this problem.
چکیده
1. مقدمه
2. ترکیب مبتنی بر جستجوی درختی برای KPS
2.1. نکات مقدماتی
2.2. رویکرد TST
2.3. احتراز از تکرار
3. نتایج آزمایشی
4. نتیجه‌گیری
abstract
1. Introduction
2. Tree search based combination for the KPS
2.1. Preliminary considerations
2.2. The TSC approach
2.3. Avoid duplication
3. Experimental results
4. Conclusion
- ترجمه فارسی مقاله با فرمت ورد (word) با قابلیت ویرایش، بدون آرم سایت ای ترجمه
- ترجمه فارسی مقاله با فرمت pdf، بدون آرم سایت ای ترجمه