مشخصات مقاله:
عنوان فارسی مقاله:
یک اکتشاف ترکیبی مبتنی بر جستجوی درختی برای تنظیمات مسئله کوله پشتی
عنوان انگلیسی مقاله:
A tree search based combination heuristic for the knapsack problem with setup
کلمات کلیدی مقاله:
مشکلات کوله پشتی، برپایی، جستجو درخت ترکیبی، فیلتر و فان متاگیر، اجتناب از تکرار
مناسب برای رشته های دانشگاهی زیر:
مهندسی کامپیوتر
مناسب برای گرایش های دانشگاهی زیر:
مهندسی الگوریتم ها و محاسبات و مهندسی نرم افزار
وضعیت مقاله انگلیسی و ترجمه:
مقاله انگلیسی را میتوانید به صورت رایگان با فرمت PDF از باکس زیر دانلود نمایید. ترجمه این مقاله با فرمت WORD – DOC آماده خریداری و دانلود آنی میباشد.
فهرست مطالب:
چکیده
1. مقدمه
2. ترکیب مبتنی بر جستجوی درختی برای KPS
2.1. نکات مقدماتی
2.2. رویکرد TST
2.3. احتراز از تکرار
3. نتایج آزمایشی
4. نتیجه‌گیری
قسمتی از مقاله انگلیسی و ترجمه آن:
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. مقدمه
ما به تنظیمات مسئله کوله‌پشتی به‌عنوان KPS اشاره خواهیم کرد. این آیتم به‌عنوان یک مسئله کوله‌پشتی با تخفیف هزینه‌های اضافی تنظیمات ثابت، هم در تابع هدف و هم در قیدها توضیح داده می‌شود. این مسئله خصوصاً در کاربردهای برنامه‌ریزی تولید در جاییکه نیاز به تنظیمات قبل از راه اندازی تولید وجود دارد، متداول است.
توجه ما به این مدل، در اصل توسط مسائل عملی در یک پروژه تولیدی با یک تولید کننده و تأمین کننده پیشرو از صنایع بسته بندی شیشه ای کشت و گوارش برانگیخته شد. این شرکت چندین نوع محصول شامل شیشه ، بطری‌های دردار، و قوطی‌ها را تولید می‌کند. مهم‌ترین مرحله در روند تولید، مرحله شکل‌دهی است. در واقع، برای تغییر شکل محصول از یک خانواده محصول به خانواده‌ای دیگر ، ماشین‌آلات تولید باید تنظیم شوند و قالب‌های ماشین قالب‌گیری نیز باید تعویض شوند. این تغییرات در روند تولید مستلزم تنظیمات با زمان و هزینه قابل‌توجهی است. فرض کنید که شرکت در زمان T تعدادی سفارش (کار) دریافت می‌کند که متعلق به خانواده محصولات N است. هر خانواده محصول i دارای کارهای ni میباشد. همچنین فرض کنید که این کارها باید در دوره برنامه‌ریزی بعدی تولید شوند و ظرفیت تولید شرکت ثابت است و نمی‌تواند در مدت کوتاهی تغییر یابد. بر این اساس، شرکت باید تصمیم بگیرد که چطور سفارشات را با در نظر داشتن حداکثر مجموع سود انتخاب کند. این نشان‌دهنده یک مورد بخصوص است که شامل مدل تنظیمات مسئله کوله‌پشتی میباشد و می‌تواند برای حل این مسئله مورداستفاده قرار گیرد.