دانلود مقاله ISI انگلیسی شماره 22809 + ترجمه فارسی
عنوان فارسی مقاله

ترتیب‌گذاری چند محصولی و تعیین‌ اندازه-لات تحت عدم‌حتمیت: الگوریتم ممتیک

کد مقاله سال انتشار مقاله انگلیسی ترجمه فارسی
22809 2012 13 صفحه PDF 40 صفحه WORD
خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
عنوان انگلیسی
Multi-product sequencing and lot-sizing under uncertainties: A memetic algorithm
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Engineering Applications of Artificial Intelligence, Volume 25, Issue 8, December 2012, Pages 1598–1610

فهرست مطالب ترجمه فارسی
چکیده
کلیدواژه‌ها
1.مقدمه
2.تدوین مسئله
شکل 1. راه‌حلی برای ترتیب‌گذاری و مسئله تعیین‌اندازه-لات.
شکل 2. نمایش فرایند تولید در طی زمان بدون کالاهای برگشتی و از کار افتادگی‌ها.
شکل 3. مثالی از جریان آیتم همراه با کالاهای برگشتی و از کار افتادگی‌ها.
3.بررسی منابع
4.چارچوب تفکیک‌پذیری
4.1.محاسبه کل سطح خدمات برای راه‌حلی عملی
4.2.بهینه‌سازی از طریق تجزیه
5.مسئله فرعی تعیین‌ اندازه-لات 
5.1.انتخاب الگوریتم ممتیک و ساختارش
شکل 4. طرح MA.
شکل 5. نمونه راه‌حل وقتی n=7.
5.2.رمزگذاری راه‌حل‌ها و تناسب
5.3.خلق جمعیت ابتدایی
5.4.اپراتور‌های ژنتیک: تقاطع، جهش و انتخاب جایگزین
5.4.1.انتخاب و تقاطع
5.4.2.عملیات تقاطع
5.4.3.جهش
5.4.4.عملیات جهش
5.4.5.انتخاب جایگزین
5.4.6.فرایند بروزرسانی
5.4.7.حذف ابزار همزاد
5.5.الگوریتم جستجوی محلی
5.5.1.جستجوی محلی
6. آزمایش‌های کامپیوتری
6.1. تولید نمونه مسئله 
6.1.1. پارامترهای MA
6.2. روش‌های مورد استفاده برای مقایسه
6.3. محدودیت‌های روش DP
جدول 1. زمان CPU و تعداد نمونه‌های حل شده برای مطلوبیت برای DP.
6.4. نتایج MA و LS در برابر راه‌حل‌های مطلوب
6.5. مقایسه MA با LS برای مسائلی در مقیاس بزرگ
جدول 2. نتایج LS و MA در برابر راه‌حل‌های مطلوب به دست آمده با DP.
جدول 3. زمان اجرای میانگین MA و LS 
شکل 6. تغییر زمان CPU برای MA.
جدول 4. مقایسه راه‌حل‌های به دست آمده برای MA, LS, G1, G2 و G3 (160 نمونه برای هر مجموعه).
7. نتیجه‌گیری
کلمات کلیدی
تعیین اندازه دسته تولید - ترتیب - عملکرد تصادفی - بهینه سازی - الگوریتم ممتیک -
ترجمه چکیده
این مقاله به ترتیب‌گذاری چندمحصولی اتفاقی و مسئله تعیین‌ اندازه-لات برای خط تولیدی می‌پردازد که اقلام را به صورت گروهی تولید می‌کند. دو نوع عدم‌حتمیت دیده شده است: زمان انجام کار تصادفی تحت القاء از کار افتادگی دستگاه و بازده تصادفی برای کالاهای برگشتیِ قسمت. علاوه بر این، اوقات راه‌اندازی وابسته توالی نیز گنجانده شده‏اند. این مطالعه به حداکثرسازی احتمالِ تولید مقدار موردنیاز اقلام از هر نوعی برای افق برنامه‌ریزی محدود می‌پردازد. رویکرد تجزیه برای جداسازی ترتیب‌گذاری و الگوریتم‌های تعیین‌ اندازه-لات استفاده شده است. آثار قبلی نشان داده‌اند مسئله فرعی ترتیب‌گذاری را می‌توان به صورت موثر حل کرد، اما حل مسئله فرعی تعیین‌ اندازه-لات هنوز دشوار است. در این مقاله، الگوریتم ممتیک برای مسئله فرعی دوم پیشنهاد شده است. نتایج محاسباتی نشان می‌دهند الگوریتم‌های ایجاد شده قابل استفاده به شکلی اثربخش برای نمونه‌های صنعتی در مقیاس بزرگ هستند.
ترجمه مقدمه
در این مقاله، تعیین‌ اندازه-لات چند محصولی و مسئله ترتیب‌گذاری تحت عدم‌حتمیت بررسی شده است. منبع مشکل ناشی از کارخانجات تولیدی نیمه‌رسانای خودکار است که در آن درصدی غیرقابل اغماض از کالاهای برگشتی و از کار افتادگی دیده می‌شود. با این حال، این موقعیت می‌تواند مربوط به هر خط تولید خودکار باشد که تحت عدم‌حتمیت کار می‌کند و رویکرد پیشنهادی به آسانی قابل تعمیم به خطوط تولید مختلف است. نمونۀ ارائه شده در اینجا مربوط به تجربه‌مان در طراحی خط تولید با سرعت ثابت برای تولید چند نوع الگوی رسانا است. این بخش‌ها برای کسب ماژول‌های الکترونیک (مدارهای چاپی) استفاده شده‌اند. از آنجایی که کارخانه نیمه‌رسانای مورد نظر تا حد زیادی خودکار است، پرسنلی غیر از پرسنل حفظ و نگهداری در کل روز ندارد. کارخانه با سه شیفت کار می‌کند. به خصوص، فعالیت اصلی شیفت روز تعریف برنامه تولید برای 24 ساعت بعد و شروع فرایند تولید است. شیفت‌های غروب و شب، که تنها متشکل از پرسنل حفظ و نگهداری است، اطمینان می‌دهند که خط تولید به کار ادامه می‌دهد، اما نمی‌توانند برنامه تولید را تغییر دهند. در نتیجه، برنامه تولید برای 24 ساعت تنظیم شده است و قابل تنظیم برای کالاهای برگشتی یا از کارافتادگی‌هایی که ممکن است در شیفت‌های بعد رخ دهد نخواهد بود. بعد از پردازش، بخش‌ها (الگوهای رسانا) در سیستم ذخیره خودکار قرار داده می‌شوند، و برای مونتاژ ماژول‌های الکترونیک استفاده می‌شوند. سیستم ذخیره خودکار گران است و محدودیت حجم دارد. در نتیجه، در صورت امکان، باید با محدودیت ذخیره یک روزه کار کند. بنابراین، این خط و سیستم ذخیره باید درست سروقت قادر به تامین خط مونتاژ بعدی باشد. به عبارت دیگر، سیاست ذیل اعمال شده است: تمام اقلام مورد استفاده برای مونتاژ در دوره r+1 باید در سیستم ذخیره تا انتهای دوره برنامه‌ریزی r باشد. در شروع دورۀr، تقاضا برای تمام اقلام برای مونتاژ در دوره برنامه‌ریزی r+1 شناخته شده اند (با در نظر گرفتن موجودی فعلی در سیستم ذخیره خودکار، در صورت وجود، و برنامه‌های تولید خط مونتاژ برای دوره r و r+1). بنابراین، برای هر دورۀr، سوال ذیل بایستی پاسخ داده شود: چند آیتم از هر نوعی باید برای تولید در ابتدای دوره r تولید شود تا مقدار لازم برای تمام عناصر در دوره تولید بعدی r+1 خط مونتاژ به دست آید؟ با این نوع تولید، درصد غیرقابل اغماضی از کالاهای برگشتی وجود دارد، چرا که برخی عناصر انتهایی با کیفیت غیرقابل قبول تولید شده‌اند. کنترل کیفی در پایان خط بدون کنترل کیفی واسطه‌ای انجام می‌شود. علاوه بر این، دستگاه‌های خط اغلب به صورت مختصر به خاطر از کار افتادگی‌ها متوقف شده‌اند. این توقف‌ها منجر به مسئله کنترل تولید جدید و بسیار جالب می‌شود که با تعیین‌ اندازه-لات و برنامه زمان‌بندی تحت عدم‌حتمیت‌ها مواجه است. دو نوع خط‌مشی ممکن وجود دارد که در تناقض هستند. برای کاهش تاثیرگذاری از کار افتادگی‌های تصادفی، زمان ایمنی (تفاوت بین دوره افق برنامه‌ریزی و زمان لازم برای تولید تمام لات‌ها) قابل افزایش است، اما در این مورد، لازم است اندازه لات‌ها کاهش یابد، بنابراین برنامه تولید به صورت آسان‌تر به کالاهای برگشتی می‌پردازد. از سوی دیگر، اندازه لات‌ها را می‌توان افزایش داد تا تاثیر کالاهای فروش‌نرفته تصادفی کاهش یابد، اما این خط به از کار افتادگی‌های تصادفی، به خاطر زمان ایمنی ناکافی، حساس‌تر است. زمان کافی برای تعمیر تمام این از کار افتادگی‌ها وجود ندارد و این خط قادر به تولید مقدار کالای مورد نیاز نخواهد بود. علاوه بر این، بین پردازش دو محصول متفاوت زمان راه‌اندازی برای پیکربندی مجدد تسهیلات تولید ضروری است. زمان راه‌اندازی به نوع محصول تولیدی قبلی و اقلام جدید برای پردازش وابسته است. بنابراین، برای هر دو خط‌مشی مذکور در بالا، فعالیت دیگری موثر بر زمان ایمنی وجود دارد. در این مقاله، دوباره تدوین احتمالی این تعیین‌ اندازه-لات و مسئله برنامه زمان‌بندی را بررسی خواهیم کرد، موضوعی که در ابتدا در دولگوی (2002) بیان شد. برای این مسئله، نخستین رویکرد در دولگوی و همکاران (2005) پیشنهاد شده بود: محققین نشان داده‌اند این مسئله قابل تبدیل به مسئله دستگاه مجزا با زمان‌های راه‌اندازی وابسته به ترتیب‌گذاری است و راه‌حل مطلوبش را می‌توان با استفاده از تجزیه به چند مسئله فرعی بهینه‌سازی به دست آورد: شمارش، ترتیب‌گذاری و تعیین‌ اندازه-لات. توجه کنید دو مسئله انتهایی ان‌پی-سخت هستند اما مسئله فرعی ترتیب‌گذاری را می‌توان به مسئله فروشنده سیار کاملاً شناخته شده تبدیل کرد، در این مسئله تعداد زیادی الگوریتم کارآمد هست. برای مسئله فرعی تعیین‌ اندازه-لات، در دولگوی و همکاران (2005)، محققین ایده‌ای مطرح کردند بدین مضمون که چطور رویکرد برنامه‌ریزی پویا (DP) برای حل این مسئله فرعی قابل استفاده‏ است. با این حال، تنها چارچوب تجزیه و اظهار DP برگشتی برای تعیین‌ اندازه-لات فراهم شده بود. بنابراین، سوال در مورد کارآمدی این رویکرد برای مواردی با اندازه کوچک، متوسط و بزرگ هنوز بی‌پاسخ است. این سوال نیازمند تحقیقات بیشتر است که محرک مقاله فعلی نیز هست. رویکردی جامع با نیت بررسی مسائل در اندازه صنعتی ارائه می‌کنیم. این تحقیق از رویکرد تجزیه کلی پیشنهادی قبلی استفاده خواهد کرد. DP در چند نمونه عددی آزمایش خواهد شد و الگوریتم ممتیک (MA) براساس جستجوی محلی (LS) و الگوریتم ژنتیک (GA) برای مواردی در مقیاس بالا پیشنهاد خواهند شد. مابقی مقاله به شرح ذیل سازمان‌دهی شده است. فرض‌های کلی و بیان مسئله در بخش 2 ارائه شده‌اند. بررسی منابع مرتبط در بخش 3 مطرح شده است. بخش 4 چارچوب راه‌حل را معرفی می‌کند: چگونه عدم‌حتمیت‌ها مدل‌سازی‌ شده‌اند و تجزیه انجام شده است. در بخش 5، الگوریتم ممتیک (MA) همراه با عناصرش ارائه شده است. در بخش 6، چند نتیجه تجربی در مقایسه با الگوریتم‌ها (DP,LS,MA) گزارش شده است. بخش 7 نظریات انتهایی و چشم‌اندازهای تحقیقاتی آتی را مطرح می‌کند.
پیش نمایش مقاله
پیش نمایش مقاله ترتیب‌گذاری چند محصولی و تعیین‌ اندازه-لات تحت عدم‌حتمیت: الگوریتم ممتیک

چکیده انگلیسی

The paper deals with a stochastic multi-product sequencing and lot-sizing problem for a line that produces items in lots. Two types of uncertainties are considered: random lead time induced by machine breakdowns and random yield to take into account part rejects. In addition, sequence dependent setup times are also included. This study focuses on maximizing the probability of producing a required quantity of items of each type for a given finite planning horizon. A decomposition approach is used to separate sequencing and lot-sizing algorithms. Previous works have shown that the sequencing sub-problem can be solved efficiently, but the lot-sizing sub-problem remains difficult. In this paper, a memetic algorithm is proposed for this second sub-problem. Computational results show that the algorithms developed can be efficiently used for large scale industrial instances.

مقدمه انگلیسی

In this paper, a multi-product lot-sizing and sequencing problem under uncertainties is studied. The source of the problem is derived from an automated semiconductor manufacturing plant where there are non-negligible percentages of rejects and breakdowns. However, this situation can concern any automatic production line working under uncertainties and the proposed approach could be easily extended to different types of production lines. The example given here is from our experience of designing a paced line to produce several types of conductor patterns. These parts are used to obtain electronic modules (printed circuits). Since the considered semi-conductor factory is greatly automated, there is no staff other than maintenance for almost the whole day. The facility functions with three shifts. Specifically, the main task for the day shift is to define the production plan for the next 24 h and start the manufacturing process. The evening and night shifts, which consist of maintenance personnel only, insure the production line continue to function, but cannot change the production plan. As a consequence, the production plan is set for 24 h and will not be adjusted to take into account rejects or breakdowns that may occur in the later shifts. After processing, parts (conductor patterns) are placed in an automatic storage system, and they are used for the assembly of electronic modules. The automatic storage system is expensive and restricted in volume. Consequently, it should work with one day stock limit, if possible. So, this line and storage system should be able supply the next assembly line just-in-time. In other words, the following policy is applied: all the items used for assembly in period r+1 must be in the storage system by the end of planning period r. At the beginning of the period r, the demand for all items types for assembly in the planning period r+1 is known (taking into account the current stocks in the automatic storage system, if they exist, and the production plans of the assembly line for period r and r+1). Thus, for each period r, the following question has to be answered: how many items of each type must be released to production in the beginning of the period r to obtain the necessary quantity for all components in the next production run r+1 of the assembly line? With this sort of production, there is a non-negligible percentage of rejects, because some finished components are produced with unacceptable quality. Quality control is made at the end of the line with no intermediate quality control. In addition, the machines of the line are often stopped briefly because of breakdowns. This leads to a new and very interesting production control problem dealing with optimal lot-sizing and scheduling under uncertainties. There are two types of possible policies which are in conflict. To diminish the influence of random breakdowns, the safety time (the difference between the duration of the planning horizon and the time necessary to produce all lots) can be increased, but in this case, it is necessary to reduce the sizes of lots, so the production plan can be more easily perturbed by rejects. On the other hand, the size of lots can be increased to diminish the impact of random rejects, but the line will be more sensitive to random breakdowns, because of insufficient safety time. There would be not enough time to repair of all these breakdowns and the line cannot produce the necessary quantity of items. Moreover, a set-up time is necessary between processing of two different products for reconfiguration of manufacturing facility. The set-up time depends on type of already manufactured product and new items to process. Thus, for the both policies mentioned above, there is an additional level of action affecting the safety time. In this paper, we will reexamine the probabilistic formulation of this lot-sizing and scheduling problem, initially evoked in Dolgui (2002). For this problem, a first approach was suggested in Dolgui et al. (2005): authors have shown that this problem can be reduced to a single machine problem with sequence-dependent set-up times and that its optimal solution can be obtained using a decomposition into several optimization sub-problems: enumerating, sequencing and lot-sizing. Note that the latter two problems are NP-hard but the sequencing sub-problem can be transformed in a well-known Traveling Salesman Problem, for which there exist a large number of effective algorithms. For lot-sizing sub-problem, in Dolgui et al. (2005), the authors presented an idea how dynamic programming (DP) approach could be used to solve it. Nevertheless, only the decomposition framework and a recursive DP expression for lot-sizing were provided. No evaluating tests were performed. Thus, the question on the effectiveness of this approach for small, medium and large size cases is still open. This needed to be explored further which is the motivation of the current paper. We present a global approach intended to treat actual problems of industrial sizes. This study will employ the earlier proposed overall decomposition approach. DP will be tested on several numerical examples and a memetic algorithm (MA) based on a local search (LS) and a genetic algorithm (GA) will be suggested for large scale cases. The rest of the paper is organized as follows. Overall assumptions and problem statement are presented in Section 2. A review of related literature is given in Section 3. Section 4 introduces the solution framework: how the uncertainties are modeled and decomposition is accomplished. In Section 5, a Memetic Algorithm (MA) with its elements is presented. In Section 6, several experimental results comparing the algorithms (DP, LS, MA) are reported. Section 7 contains some concluding remarks and further perspectives.

نتیجه گیری انگلیسی

A real-life problem of optimal lot-sizing and sequencing for a production line with random breakdowns and rejects was studied. The line considered manufactures intermediate components of different types for subsequent assembly into modules. The problem is to choose sequences and lot sizes. The objective is to maximize the probability to have a sufficient number of components by the end of a given planning horizon, i.e. maximize the overall service level. The benefit of this optimization is evident, because without any additional resources, production cost can be reduced by limiting the stoppages for the assembly line that follows. With an optimal decomposition procedure which uses a complete enumeration to search for the optimal last lot, sequencing and lot-sizing decisions can be considered separately. The sequencing sub-problem can be reduced to the well studied Asymmetric Traveling Salesman Problem and thus be solved with known methods. For lot-sizing, a local search and a memetic algorithm were proposed. Some experimental results were shown and discussed. The algorithms developed were compared with a dynamic programming procedure for small size instances and between them for large size problems. The MA and LS developed can find good solutions for large problems and thus this approach can be applied to large scale industrial problems. Future work may entail using simulation methods to replace the evaluation function (fitness) in order to consider problems with various probability distributions or integrating other uncertainty phenomena (e.g. uncertain manufacturing time). For example, by using simulation we could study problems in which the quantity and/or seriousness of breakdowns increases with the age of machines, etc. It will be interesting also to develop a metaheuristics approach to resolve the entire problem without decomposition and compare the results with and without decomposition.

خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.