ترجمه فارسی عنوان مقاله

یک الگوریتم "ابر-اکتشافی جستجوی پساگرد" برای مسئله "زمانبندی فروشگاه مونتاژ توزیع شده"

عنوان انگلیسی

A backtracking search hyper-heuristic for the distributed assembly flow-shop scheduling problem

کد مقاله	سال انتشار	تعداد صفحات مقاله انگلیسی
93142	2017	12 صفحه PDF

منبع

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

Journal : Swarm and Evolutionary Computation, Volume 36, October 2017, Pages 124-135

فهرست مطالب ترجمه فارسی

چکیده

کلمات کلیدی

1.مقدمه

2. مسئله زمانبندی جایگرد فروشگاه مونتاژ توزیع شده

شکل 1. نمونه ای از DAPFSP

شکل 2. نمودار BSA

شکل 3. نمونه ای از طرح کدگذاری راه حل

3. الگوریتم ابراکتشافی جستجوی پساگرد

3.1 الگوریتم جستجوی پساگرد

شکل 4. شبه کد LLH بهبودیافته

شکل 5. چارچوب طرح BS-HH

شکل 6. رویه اصلی BS-HH

جدول 2. ترکیبات مقادیر پارامتر

جدول 3. آرایه متعامد و مقادیر AM

جدول 4. مقدار AM و رتبه اهمیت هر پارامتر

شکل 7. روند سطح عامل BS-HH

جدول 5. نتایج آماری الگوریتم های مختلف روی نمونه های کوچک

3.2 طرح کدگذاری و کدگشایی راه حل

3.3. روش های اکتشافی سطح پایین (LLHs)

جدول 6. نتایج آماری الگوریتم های مختلف روی نمونه های کوچک

شکل 8. نمودار گانت راه حل جدید بدست آمده توسط برای نمونه های

جدول 7. تست t الگوریتم های مختلف روی نمونه های کوچک

شکل 9. نمودارهای جعبه ای برای مقادیر ARPD الگوریتم های مقایسه شده در حل نمونه های کوچک

3.4. طرح BS-HH

شکل 10. نمودارهای جعبه ای برای مقادیر ARPD الگوریتم های مقایسه شده در حل نمونه های بزرگ

جدول 9. تست t برای الگوریتم های مختلف روی نمونه های بزرگ

جدول 8. نتایج آماری الگوریتم های مختلف روی نمونه های کوچک

جدول 9. زمان CPU الگوریتم های مختلف روی نمونه های بزرگ

جدول 11. تست t برای الگوریتم های مختلف روی نمونه های کوچک

جدول 12. تست t الگوریتم های تکاملی روی نمونه های بزرگ

4. نتایج محاسباتی

4.1 تنظیم پارامترها

شکل 11. نمودار گانت بهترین راه حل بدست آمده توسط BS-HH برای نمونه I_100_10_4_30_6

4.2 اثر LLH بهبود یافته در BS-HH

4.3. مقایسه با اکتشافات مختلف

4.4 مقایسه با EAs

5. نتیجه گیری

جدول AI بهترین راه حل های شناخته شده برای 76 نمونه کوچک

جدول A2 بهترین راه حل های شناخته شده برای 99 نمونه بزرگ

ترجمه کلمات کلیدی

بیش از حد اکتشافی، الگوریتم جستجوی عقبگردان، توزیع مونتاژ، برنامه ریزی جریان انبار،

کلمات کلیدی انگلیسی

Hyper-heuristic; Backtracking search algorithm; Distributed assembly; Flow-shop scheduling;

ترجمه چکیده

مسئله زمانبندی فروشگاه مونتاژ توزیع شده (DAPFSP) به عنوان یک کلاس مهم از مسائل در سیستم‌های زنجیره تامین مدرن و سیستم های تولید شناخته می شود. در این مقاله، الگوریتم ابر-اکتشافی جستجوی پساگرد (BS-HH) برای حل DAPFSP پیشنهاد شده است. در طرح BS-HH، ده قوانین اکتشافی ساده و موثر برای طراحی مجموعه ای از روش های اکتشافی سطح پایین (LLHs) طراحی شده اند و الگوریتم جستجوی پساگرد به عنوان استراتژی سطح بالا برای اصلاح LLH ها برای کار بر روی فضای راه حل استفاده می شود. علاوه بر این، یک طرح کارآمد رمزگذاری و رمزگشایی پیشنهاد می شود تا یک زمانبندی عملی تولید کند. اثربخشی BS-HH بر روی دو مجموعه معیار معمول ارزیابی شد و نتایج محاسباتی برتری طرح پیشنهادی BS-HH را نسبت به الگوریتم های پیشرفته موجود نشان می دهند.

ترجمه مقدمه

زمانبندی تولید بدلیل اهمیت آن در اتخاذ تصمیمات در سیستم های تولید یک حوزه پژوهشی بسیار فعال است [1-4]. به عنوان یکی از مسائل زمانبندی بهینه سازی ترکیبی، مسئله زمانبندی جایگردی فروشگاه (PFSP) به طور گسترده ای در سیستم های تولید و فرایندهای صنعتی مورد بررسی قرار گرفته است. PFSP با معیار makespan زمانی که تعداد ماشین ها کمتر از سه است یک مسئله NP-hard است [5]. پس از کار جانسون [6]، رویه های متعددی برای حل PFSP پیشنهاد شده اند [7-18]. یک فرض مشترک در میان این مطالعات این است که تنها یک مرکز تولید واحد یا کارخانه وجود دارد و تمام کارها در جایگرد به یک کارخانه اختصاص داده می شوند. با این حال، سیستم های تولید با بیشتر از یک مرکز تولید (یعنی یک سیستم تولید توزیع شده) در عمل رایج تر هستند [19-23]، چون می توانند کیفیت محصول بالاتری کسب کنند و هزینه های توزیع تولید و خطرات مدیریتی را کاهش دهند [24]. زمانبندی در سیستم های توزیع شده چالش برانگیزتر از مسائل زمانبندی فروشگاه های معمول است؛ به خصوص این که تخصیص کار به کارخانه ها و زمانبندی کار در هر کارخانه باید هنگام تصمیم گیری در نظر گرفته شوند. به تازگی، یک فرمت از PFSP معمولی به نام مسئله زمانبندی جایگردی فروشگاه مونتاژ توزیع شده (DAPFSP) توسط هاتامی و همکاران [25] معرفی شده است، که در آن مجموعه ای از محصولات و مجموعه ای از کارخانه ها با PFSP معمولی ترکیب می شوند. هر کار در DAPFSP متعلق به یک محصول است و در یک کارخانه پردازش می شود. همه محصولات در یک کارخانه مونتاژ با یک دستگاه مونتاژ می شوند. هاتامی و همکاران [25] همچنین به حداقل رساندن makespan در کارخانه مونتاژ را در نظر گرفتند و 14 روش اکتشافی بر اساس روش های اکتشافی سازنده و نزول همسایگی متغیر (VND) ارائه کردند. در [26]، یک برآورد از الگوریتم توزیع بر اساس الگوریتم ممتیک (EDAMA) برای حل DAPFSP با هدف به حداقل رساندن زمان تکمیل توسعه داده شد. در کار قبلی ما [27] یک الگوریتم بهینه سازی مبتنی بر بیوگرافی هیبریدی (HBBO) برای حل این مسئله پیشنهاد شده است که چندین روش اکتشافی جدید را برای حل DAPFSP ارائه می کند. روند اخیر در جستجو و بهینه‌سازی نشان می دهد که روش ابراکتشافی به عنوان یک روش جستجوی موثر ظهور کرده است که روش های اکتشافی دیگر را برای ارائه راه حل های نزدیک به بهینه برای مسائل مختلف کنترل می کند [28،29]. به جای جستجوی مستقیم در فضای راه حل، روش های ابراکتشافی بر روی مجموعه ای از روش های اکتشافی سطح پایین (LLHs) کار می کنند و برای پیدا کردن یک دنباله بهینه از روش های اکتشافی تلاش می کنند [30]. در طول چند سال گذشته، ادبیات رو به رشدی در حوزه ابراکتشافی مطرح شده است [28]. به طور خاص، روش های فرااکتشافی برای ساخت طرح های ابراکتشافی مورد استفاده قرار می گیرند، به عنوان مثال، الگوریتم بهینه سازی ازدحام ذرات بر اساس رویکرد ابراکتشافی از کولیناس و همکاران [31]، ابراکتشافی تکاملی از سانز و همکاران [32] و مورنو و همکاران. [33]، ابراکتشافی مبتنی بر جستجوی هارمونی از آنور و همکاران [34] و یک ابراکتشافی مبتنی بر تغذیه باکتریایی از راجنی و کانا (35). با این حال، طبق دانش ما، هیچ رویکرد ابراکتشافی برای حل این مسئله DAPFSP وجود ندارد. انگیزه این مقاله توسعه یک الگوریتم زمان بندی مبتنی بر ابراکتشافی است که می تواند به حل مسئله DAPFSP کمک کند. الگوریتم بهینه سازی جستجوی پساگرد (BSA) یک الگوریتم تکاملی قدرتمند جدید است که به تازگی توسعه یافته است و در مقایسه با سایر الگوریتم های تکاملی، بسیار امیدوار کننده است. بطور ویژه، BSA یک الگوریتم جمعیت دوگانه است که از جمعیت های گذشته و فعلی استفاده می کند، و همچنین یک ساختار ساده دارد. هدف از این مقاله استفاده از الگوریتم جستجوی ابراکتشافی پساگرد موثر (BS-HH) برای حل DAPFSP با هدف به حداقل رساندن مقدار makespan است. در BSHH ، BSA به عنوان استراتژی ابراکتشافی سطح بالا استفاده می شود که روش های حل را به جای راه حل ها مدیریت می کند و مجموعه ای از LLH طراحی شده را بکار می گیرد. آزمایشات و مقایسه ها روی دو مجموعه از معیارهای ارائه شده در هاتامی و همکاران [25] برای تأیید اثربخشی طرح پیشنهادی انجام خواهند شد. بقیه مقاله به شرح زیر است: در بخش 2، DAPFSP به طور خلاصه معرفی می شود. در بخش 3، طرح BS-HH برای DAPFSP پیشنهاد شده است. نتایج محاسباتی روی نمونه های معیار همراه با مقایسه با بعضی از الگوریتم های پیشرفته موجود در بخش 4 ارائه شده اند. در نهایت، نتیجه گیری در بخش 5 مورد بحث قرار گرفته است.

دانلود رایگان 2 صفحه اول مقاله لاتین (PDF)

پیش نمایش مقاله

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

Distributed assembly permutation flow-shop scheduling problem (DAPFSP) is recognized as an important class of problems in modern supply chains and manufacturing systems. In this paper, a backtracking search hyper-heuristic (BS-HH) algorithm is proposed to solve the DAPFSP. In the BS-HH scheme, ten simple and effective heuristic rules are designed to construct a set of low-level heuristics (LLHs), and the backtracking search algorithm is employed as the high-level strategy to manipulate the LLHs to operate on the solution space. Additionally, an efficient solution encoding and decoding scheme is proposed to generate a feasible schedule. The effectiveness of the BS-HH is evaluated on two typical benchmark sets and the computational results indicate the superiority of the proposed BS-HH scheme over the state-of-the-art algorithms.