الگوریتم ژنتیک برای بسته بندی دوبعدی جعبه های دارای تاریخ های سررسید

قیمت: 41,000 تومان

دانلود رایگان مقاله

خرید ترجمه مقاله

عنوان فارسی

الگوریتم ژنتیک برای بسته بندی دوبعدی جعبه های دارای تاریخ های سررسید

عنوان لاتین

A genetic algorithm for two-dimensional bin packing with due dates

این مقاله متغیر جدیدی از مسئله ی بسته بندی دوبعدی جعبه ها را در نظر می گیرد که در آن به هر مستطیل یک تاریخ سررسید تخصیص یافته است و هر یک دارای زمان پردازش ثابتی می باشند. در نتیجه هدف نه تنها کاهش تعداد جعبه ها می باشد، بلکه همچنین کاهش حداکثر تأخیر مسطیل ها نیز می باشد. محرک این مسئله برش برگه های موجودی و افزایش بازده بالقوه ای که احتمالا توسط ترسیم روی مجموعه ی بزرگتری از قیمت های تقاضا توسط ترکیب سفارش ها حاصل شود، می باشد، همچنین هدف این مسئله اطمینان از سطح خاصی از خدمت به مشتری می باشد. ما یک الگوریتم جدید ژنتیک برای جستجوی فضای راه حلی ارائه می دهیم، که از یک آزمون تعیین جا برای کدگشایی ژن براساس بهترین آزمون برازش طراحی شده برای مسائل بسته بندی نواری استفاده می کند. الگوریتم ژنتیک یک عملگر ابتکاری متقاطع به کار می برد که چندین فرزند را از هر جفت والد در نظر می گیرد. بعلاوه، هدف دوگانه بصورت سلسله مراتبی بهینه سازی شد که در آن هدف اصلی بصورت دوره ای بین حداکثر تأخیر و تعداد جعبه ها تناوب می یابد. در نتیجه، این روش چندین راه حل غیر-غالب با تبادل های مختلف فراهم می آورد. دو روش دیگر به کار رفته اند. یکی از آن ها براساس جستجوی یکپارچه ی ممنوعه می باشد، که بطور مناسب برای رفع این مسئله بازبینی، اصلاح شده است. دیگری بطور مناسبی تصادفی سازی شده و بعنوان معیاری برای مقایسه ی نتایج عمل می کند. نتایج محاسباتی جامع ارائه شده اند، که نشان می دهند که جستجوی یکپارچه ی ممنوعه در کاهش جعبه ها به خوبی عمل می کند، اما الگوریتم ژنتیک کمی بهتر عمل می کند. هنگامیکه حداکثر تأخیر هم در نظر گرفته می شود، الگوریتم ژنتیک بسیار بهتر می باشد.

This paper considers a new variant of the two-dimensional bin packing problem where each rectangle is assigned a due date and each bin has a fixed processing time. Hence the objective is not only to minimize the number of bins, but also to minimize the maximum lateness of the rectangles. This problem is motivated by the cutting of stock sheets and the potential increased efficiency that might be gained by drawing on a larger pool of demand pieces by mixing orders, while also aiming to ensure a certain level of customer service. We propose a genetic algorithm for searching the solution space, which uses a new placement heuristic for decoding the gene based on the best fit heuristic designed for the strip packing problems. The genetic algorithm employs an innovative crossover operator that considers several different children from each pair of parents. Further, the dual objective is optimized hierarchically with the primary objective periodically alternating between maximum lateness and number of bins. As a result, the approach produces several non-dominated solutions with different trade-offs. Two further approaches are implemented. One is based on a previous Unified Tabu Search, suitably modified to tackle this revised problem. The other is randomized descent and serves as a benchmark for comparing the results. Comprehensive computational results are presented, which show that the Unified Tabu Search still works well in minimizing the bins, but the genetic algorithm performs slightly better. When also considering maximum lateness, the genetic algorithm is considerably better.