ارائة الگوریتم‏ های کارآمد برای حل مسأله زمانبندی جریان کارگاهی انعطاف‏ پذیر با ماشین‏های موازی غیرمرتبط و زمان‏ های راه‏ اندازی وابسته به توالی با هدف کمینه‏ سازی مجموع زودکرد و دیرکرد

مقدمه

در مسأله جریان کارگاهی انعطاف‍پذیر کارها باید در چند مرحله پردازش شود و حداقل یکی از مراحل بیش از دو ماشین موازی دارد. ماشین‍های موازی می‍توانند یکسان[1]،  یکنواخت[2] و یا غیر‍مرتبط[3] باشند.

 در ماشین­های موازی یکسان سرعت پردازش کارها روی همة ماشینهای یکسان است؛ اگر کار jام، روی هر یک از ماشین ها انجام شود، زمان پردازش آن برابر است با P_j. در ماشین­های موازی یکنواخت، ماشین­هایی مشابه با سرعت پردازش متفاوت، به کار گرفته می شود؛ سرعت پردازش ماشین iام برابر v_i است، اگر کار jام، به طور کامل روی ماشین iام انجا م شود، زمان پردازش آن برابر است با P_ij = P_j /v_i ، در ماشین­های موازی غیر مرتبط ماشین­هایی متفاوت به کار گرفته می­شود و ماشین i کار j  را با سرعت v_ij پردازش می­کند؛ اگر کار jام، به طور کامل روی ماشین iام انجا م شود، زمان پردازش آن برابر است با P_ij = P_j /v_ij.

در بیشتر پژوهش­های پیشین ماشین‍ها به صورت یکسان در نظر گرفته‍ شده‍اند. در مسائل دنیای واقعی، معمولاً ماشین‍های جدید را به صورت موازی با ماشین‍های قدیمی قرار می‍دهند تا ظرفیت تولید افزایش یابد. در این نوشتار زمان­های آماده­سازی وابسته به توالی عملیات است، که در بسیاری از مسائل توالی عملیات در صنایع نساجی ، تولید نیمه‍رساناها، تولید کاشی و سرامیک و صنایع رنگ کاربرد دارد. تابع هدف مجموع زودکرد و دیرکرد که هزینه‍های نگهداری و هزینه‍های عدم تحویل به موقع محصول به مشتری را کاهش می‍دهد.

مسأله جریان کارگاهی انعطاف‍پذیر با دو مرحله با تعدادی ماشین موازی یکسان در مرحله اول و یک ماشین در مرحله دوم و با تابع هدف کمینه­سازی بیشترین زمان تکمیل را گاپتا و همکاران(1997) بررسی کردند.  بوتاگنولاز(2000) مسأله جریان کارگاهی انعطاف‍پذیر با محدودیت پیشنیازی بین کارها و محدودیت زمان‍های اتلاف بین مراحل و با تابع هدف کمینه­سازی بیشترین زمان تاخیر بررسی و شش روش ابتکاری جدید ارائه کردند. تران و مینگ ننگ (2011) مسأله جریان کارگاهی انعطاف پذیر را با محدودیت ظرفیت انبارهای میانی و بدون در نظر گرفتن آن با هدف­های کمینه­سازی بیشترین زمان تکمیل، مجموع موزون زمان در جریان ساخت و مجموع موزون زمان‍های تاخیر بررسی و الگوریتم جریان آب  [4] را ارائه کردند. لیو و چانگ (2000) یک روش دقیق ویک روش ابتکاری برای حل مسأله جریان کارگاهی انعطاف‍پذیر با زمان‍های آماده­سازی وابسته به توالی ارائه کردند و اسکین (2003) این  مسأله را با هدف کمینه­سازی بیشترین زمان تکمیل بررسی کرد، ویک مدل عدد صحیح، چند روش ابتکاری و یک روش الگوریتم ژنتیک با کلیدهای تصادفی ارائه کرد. نادری و همکاران (2009) برای مسأله جریان کارگاهی انعطاف‍پذیر چند هدفه با زمان‍های آماده­سازی وابسته به توالی و زمان حمل و نقل، الگوریتمی ترکیبی مبتنی بر شبیه‍سازی تبرید و یک روش جستجوی ساده ارائه کردند.

مسأله با فرض ماشین‍های موازی غیرمرتبط[5]، در مسألة جریان کارگاهی انعطاف­پذیر، از مسائلی است که کمتر مطالعه شده است؛ البته می‍توان به تحقیقات جانگواتانیک و همکاران (2005، 2008، 2009) اشاره کرد. همچنین، یواریما و همکاران (2009) مسأله جریان کارگاهی انعطاف‍پذیر با ماشین‍های موازی غیرمرتبط، زمان‍های راه‍اندازی وابسته به توالی، محدودیت زمان‍های در دسترس بودن ماشین‍ها و محدودیت انبارهای میانی را با تابع هدف کمینه­سازی مجموع زمان‍های تکمیل بررسی و برای حل از الگوریتم ژنتیک استفاده کردند.

جانیاک و همکاران (2007) مسألة جریان کارگاهی انعطاف‍پذیر با تابع هدف مجموع زودکرد و دیرکرد با و زمان انتظار را در نظر گرفتند و سه الگوریتم فراابتکاری و سه الگوریتم سازنده را برای آن ارائه کردند. بهنامیان و زندیه (2011) مسأله جریان کارگاهی انعطاف‍پذیر با محدودیت زمان انتظار و تابع هدف مجموع زودکرد و مربع دیرکرد را بررسی و الگوریتم رقابت استعماری گسسته را برای حل ارائه کردند.

تابع هدف مجموع زودکرد و دیرکرد تنها در مسائل جریان کارگاهی انعطاف‌پذیر با ماشین‌های یکسان درنظر گرفته شده است. در این پژوهش این تایع هدف در مسأله جریان کارگاهی با ماشین‌های موازی غیرمرتبط بررسی می­شود.

در این نوشتار یک مسأله خاص از مسائل جریان کارگاهی انعطاف‍پذیر با زمان‍های راه‍اندازی وابسته به توالی، ماشین‍های غیر‍مرتبط و تابع هدف مجموع زودکرد و دیرکرد بررسی می‍شود، و ساختار آن به شرح ذیل است: در بخش دوم مسأله زمان‍بندی جریان کارگاهی انعطاف‍پذیر با زمان‍های آماده­سازی وابسته به توالی تشریح می­شود سپس در بخش سوم روش تحقیق و مدل­سازی مسأله ارائه شده است که برای حل مسألة مورد نظر الگوریتم‍های مبتنی بر شبیه‍سازی تبرید و بهینه‍سازی انبوه ذرات ارئه می‏شود و در بخش چهارم نتایج محاسباتی الگوریتم‏های ارئه شده، گزارش می­شود. در نهایت نتایج این پژوهش در بخش پنج جمع­بندی می­شود.

1-               تشریح مسأله زمان‍بندی جریان کارگاهی انعطاف‍پذیر با زمان‍های آماده­سازی وابسته به توالی

2-      در این پژوهش مسألة زمان­بندی در یک سیستم جریان تولید کارگاهی انعطاف­پذیر بررسی می­شود که در آن هر مرحله حداقل یک ماشین قرار دارد و به صورت موازی هستند و کارها در دو مرحله پردازش می­شوند؛ زمان‍های آماده­سازی، وابسته به توالی است، و بعد از اتمام پردازش هر کار در هرمرحله و شروع کار بعدی در نظر گرفته می‏شود که وابسته است به ترتیب این دو کار و ماشینی که پردازش روی آن انجام می‍شود. ماشین‍های هر مرحله، غیرمرتبط هستند. پارامترها و متغیرهای مسأله قطعی است و تمام داده‍ها از پیش تعیین شده و ثابت هستند. تابع هدف کمینه­سازی مجموع زودکرد و دیرکرد است که باعث می­شود هزینه‍های نگهداری و هزینه‍های عدم تحویل به موقع محصول به مشتری، کاهش یابد.

مفروضات مسأله به شرح ذیل است:

• وقفه مجاز نیست.
• زمانی که کارها پردازش خود را روی ماشین‍ها آغاز می‍کنند، قبل از این که به مرحله بعد بروند باید پردازش خود را به اتمام برسند.
• پردازش یک کار در هر مرحله نمی‍تواند به چند قسمت تقسیم شود و هر کار باید فقط روی یک ماشین پردازش انجام شود.
• زمان در دسترس بودن کارها در مرحله اول برابر صفر است.
• قبل از شروع اولین کار در هر مرحله، زمانی به عنوان زمان آماده­سازی وجود دارد.
• ماشین­ها بدون هیچ خرابی در دسترس هستند.
• زمان پردازش هر مرحله از کارها از تقسیم زمان پردازش استاندارد بر سرعت پردازش هریک از ماشین­ها به دست می‍آید.

روش تحقیق و مدل­سازی مسأله.

 در این پژوهش برای تحلیل مناسب مسأله یک مدل برنامه­ریزی عدد صحیح آمیخته ارائه می­شود که با توجه به پیچیدگی محاسباتی آن، برای حل مسائل نمونه با ابعاد بزرگ، باید از روش‏های ابتکاری/ فراابتکاری استفاده کرد؛ به همین علت در این پژوهش برای حل مسألة زمان­بندی از الگوریتم­های فراابتکاری مبتنی بر بهینه­سازی انبوه ذرات و شبیه‏سازی تبرید استفاده شده است.

الگوریتم­های پیشنهادی از دو بخش تشکیل شده است، در بخش اول هدف کمینه­سازی بیشترین زمان تکمیل و دیرکرد است و در بخش دوم، هدف کمینه­سازی مجموع زودکرد و دیرکرد، با تغییر زمان شروع و خاتمه کارها در مرحله آخر، است.

برای تعیین هزینه و زمان‍بندی کامل از الگوریتم پیشنهادی جانیاک (2007) استفاده می­شود.

2- 1  پارامترها و متغیرهای مدل

برای بیان مسأله و مدل­سازی آن از پارامترها و متغیرهای زیر استفاده می­شود:

J: مجموعه کارها

S: مجموعة مراحل

M_s: تعداد ماشین در مرحله s

d_j: موعد تحویل

P_sjm: زمان پردازش کار j روی ماشینm در مرحلهs

SUP_skjm: زمان آماده­سازی کار k بعد از کار j روی ماشین m در مرحلهs

M: یک عدد بزرگ

C_sjm: زمان تکمیل کار j روی ماشین m در مرحلهs

K_sj: زمان ترک کار j از مرحلهs

E_j: زودکرد کار j

T_j: دیرکرد کار j

 2-1-1 مدل ریاضی

تابع هدف در این مسأله کمینه­سازی مجموع دیرکرد و زودکرد است که در عبارت (1) بیان می­شود، و برای تعیین مقدارهای زودکرد و دیرکرد به صورت عدد صحیح در مدل ریاضی، عبارت‍های (3)، (4)، (15) و (16) در نظر گرفته می­شود. عبارت (2) رابطه دیرکرد و زودکرد را با موعد تحویل مشخص می‍کند. عبارت (5) تضمین می‍کند که زمان پردازش هر کار بزرگتر یا مساوی زمان پردازش و زمان آماده­سازی کار j در مرحله اول است. با در نظر گرفتن عبارت (6) به دنبال آن هستیم که پردازش هیچ کدام از کارها روی یک ماشین همزمان نشود. عبارت (7) تضمین می‍کند که زمان تکمیل هر کار بزرگتر یا مساوی زمان تکمیل آن کار در مرحله قبل به علاوه زمان پردازش و زمان آماده­سازی آن کار باشد..

عبارت­های (8) و (9) مقدار k_sj را برابر زمانی  قرار می‍دهد که کار j مرحله را ترک  می‍کند. عبارت (10) نشان می‍دهد که در هر مرحله هر کار فقط روی یک ماشین پردازش می‍شود. عبارت (11) نشان‍دهنده این است که هر کار باید به دنبال کار دیگری مثل کار i فقط روی یک ماشین پردازش شود. عبارت (12) نشان‍دهنده این است که ممکن است کاری قبل از کار دیگر روی یک ماشین برنامه‍ریزی شده یا نشده باشد ولی آن کار حداکثر با یک کار دیگر باید دنبال شود. در عبارت‍های (13) و (14) برای محاسبه زمان آماده­سازی، کار صفر به عنوان اولین کاری است که روی تمام ماشین‍ها پردازش می‍شود

2- 2                    الگوریتم­های پیشنهادی برای حل مسأله

در اینجا با توجه به پیچدگی الگوریتم حل، دستیابی به جواب بهینه، حتی برای مسائل با ابعاد کوچک، مستلزم صرف وقت زیادی خواهد بود؛ بنابراین در این شرایط بهتر است که از روش­های ابتکاری/فراابتکاری برای حل مسأله استفاده شود.

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

2 - 2 - 1    الگوریتم پیشنهادی ایجاد زمان‍بندی کامل

ابتدا زمان در دسترسی کارها در مرحله اول را برابر صفر است.

با فرض مشخص بودن توالی مرحله اول، در مرحلة دوم با استفاده از قاعده FIFO توالی کارها تعیین می­شود.

، زمان تکمیل کار j  روی ماشین m در مرحله s و  زمان آماده­سازی کار j  روی ماشین m در مرحله s است. در صورتیکه کار قبل از کار j، به کار j  روی ماشین  mتغییر یابد، زمان تکمیل هر کار روی هر ماشین به ترتیب زیر محاسبه می‍شود‍ و ماشینی انتخاب می‍شود‍ که کمترین زمان تکمیل را داشته باشد :

ماشین انتخاب شده را m^* بنامید؛ سپس زمان در دسترس بودن ماشین m^* در مرحله s و زمان در دسترسی کار j در مرحله s به روز می­شود.

زمان تکمیل کار  j،  را برابر زمان تکمیل کار j روی ماشین m* در مرحله  s ( ) است.

برای مرحله آخر و برای هر ماشین :  توالی کارهایی است، که قرار است روی ماشین m پردازش شوند، و  مجموعه کارهایی است، که بدون بیکاری و وقفه به صورت متوالی بر روی ماشین m  بعد از کار j پردازش می­شوند و  جایگاه آخرین کار در گروه  است و  زیرمجموعه‍ای از گروه  است که زودکرد دارند و   برابر کمترین مقدار زودکرد در گروه و  نشان­دهندة j امین کار در توالی روی ماشین m است.  نشان‍دهنده زمان بیکاری بعد از گروه  است و از رابطه (19) محاسبه می‍شود:

      (19)                    

st نشان دهنده زمان شروع کار و C نشان دهنده زمان تکمیل است.

در صورتی‏که دو شرط زیر برقرار باشد :

1)

2)  تعداد کارهای دارای زودکرد بیش از تعداد کارهای با دیرکرد باشد.

کار j ام و گروه  به اندازه t به سمت راست جابه‏جا می شود، که از رابطه (20) به دست می‍آید:

    (20)             

سپس گروه  ، مقادیر E، ، ، مجموع زودکرد و دیرکرد محاسبه شود. این روند تا زمانی که یکی از شرط‏ها نقض شود، تکرار می‍شود. به این ترتیب یک برنامه زمان‍بندی کامل که متناسب با تابع هدف است، به دست می‍آید.

الگوریتم مبتنی بر شبیه‍سازی تبرید

برای حل مدل پیشنهادی از الگوریتم مبتنی بر شبیه­سازی تبرید استفاده می­شود (جانیاک و همکاران،2007). در الگوریتم پیشنهادی، مراحل تعریف نحوة نمایش جواب، تولید جمعیت اولیه، جستجوی همسایگی، مکانیزم کاهش دما و پذیرش جواب و جستجوهای محلی، باید اجرا شوند:

الف) نحوه نمایش جواب

در اینجا برای نمایش جواب،  توالی کارها در مرحله اول در نظر گرفته می­شود.

ب) تولید جمعیت اولیه

برای تولید جمعیت اولیه سه روش­ تصادفی، مبتنی بر قاعدة EDD[6][7] و مبتنی بر الگوریتم NEH بررسی می‏شود.

ج) جستجوی همسایگی

برای پیمایش در فضای شدنی باید جواب شدنی دیگری با تغییر جواب فعلی ایجاد شود که جواب همسایه نامیده می‍شود. برای به دست آوردن جواب همسایه روش‍های جابجایی^[8] و جاسازی^[9] بررسی می­شود. طول جستجوی همسایگی برای مقادیر 5، 10 و 15 بررسی می­شود.

د) مکانیزم کاهش دما و پذیرش جواب

مکانیزم کاهش دما با استفاده از عبارت (21) تعیین می­شود:که در آن α ضریب کاهش دما و ثابتی کمتر از یک است. n نشان دهنده تعداد دفعات کاهش دما است مکانیزم پذیرش جواب‍های تولید شده به این صورت است که اگر جواب بهتر شود آن جواب پذیرفته شود، در غیر این صورت با استفاده از عبارت (22) مقدار y محاسبه شود.

سپس یک مقدار تصادفی تولید می­شود و با مقدار y مقایسه می­شود، اگر مقدار عدد تصادفی به دست آمده کمتر از y باشد جواب پذیرفته شود، در غیر این صورت جواب رد می­شود.

در این عبارت Z∆ برابر اختلاف بین جواب جاری و جواب همسایگی است و T بیانگر دمای جاری سیستم است. الگوریتم با مقادیر 1000، 1500 و 1800 برای دمای اولیه و نرخ کاهش دما با مقادیر 0.1، 0.2 و  تحلیل می­شود. که  حداکثر تعداد تکرارها است.

ه) جستجو محلی

در الگوریتم پیشنهادی برای ارتقاء جواب‍های به دست آمده از این الگوریتم از جستجوهای محلی تصادفی استفاده می‍شود. به این منظور از دو نوع جستجوی همسایگی بر روی بهترین جواب به دست آمده از الگوریتم شبیه سازی تبرید استفاده می‍شود. یک جستجو بر روی مرحله اول و سپس جستجو بر روی مرحله آخر. جستجو بر روی مرحله اول به این علت اهمیت دارد که کوچکترین تغییر در زمان‍بندی مرحله اول می‍تواند تغییر قابل توجهی در زمان‍بندی کلی و مقدار تابع هزینه ایجاد ‍کند. به این منظور در هر یک ازجستجو‍های محلی تصادفی، چهار همسایگی در نظر گرفته شده است:

یک ماشین و دو کار که بر روی آن پردازش می‍شوند به صورت تصادفی انتخاب ‍شده و با هم جابه‏جا می‍شوند.

یک ماشین و یک کار که روی آن پردازش می‍شود انتخاب شده و کار در موقعیت دیگری به صورت تصادفی قرار می­گیرد.

دو ماشین و دو کار که بر روی آن‍ها پردازش می‍شوند به صورت تصادفی انتخاب و دو کار با هم جابه‏جا می‍شوند.

یک کار از ماشین اول به طور تصادفی انتخاب شده و در موقعیتی که به طور تصادفی روی ماشین دوم انتخاب شده است، جایگزین می‍شود.

برای به دست آوردن برنامه زمان‍بندی کامل و تابع هدف از الگوریتم بخش 3-2-1 استفاده می‍شود. به منظور تعیین مقدار مناسب پارامترهای الگوریتم­های پیشنهادی از روش طراحی آزمایش­های تاگوچی استفاده می­شود؛ مزیت این روش این است که می­توان با انجام آزمایش­های کمتر، مقدار پارامترهای الگوریتم را طوری تنظیم کرد که میزان تغییرپذیری جواب به­دست­آمده از الگوریتم (متغیر پاسخ) کمینه شود.

با توجه به نتایج حاصل از طراحی آزمایش­های تاگوچی پارامترهای الگوریتم پیشنهادی مبتنی بر شبیه­سازی تبرید به شرح زیر است:

روش تولید جمعیت اولیه مبتنی بر EDD، حداکثر تکرار ها 20، تعداد همسایگی 10، دمای اولیه 1500، نرخ کاهش دما .

در شکل 1 شبه کد الگوریتم پیشنهادی مبتنی بر شبیه­سازی تبرید ارائه شده است.

الگوریتم پیشنهادی مبتنی بر بهینه سازی انبوه ذرات

کندی و ابرهارت (1995) الگوریتمی برای بهینه‏سازی مسائل با تابع هدف غیر خطی و متغیر تصمیم پیوسته ارائه کردند. این الگوریتم بر این اصل استوار است که در هر لحظه هر ذره مکان خود را در فضای جستجو با توجه به بهترین مکانی که تا کنون در آن قرار گرفته است و بهترین مکانی که در کل همسایگی‍اش وجود دارد، تنظیم می‍کند. در این الگوریتم هر ذره در فضای جستجو به دنبال نقطه بهینه حرکت می‍کند و دارای سرعت است. مسائل زمان‍بندی از نوع مسائل گسسته هستند و الگوریتم بهینه‍سازی انبوه ذرات ماهیتاً پیوسته است؛ بنابراین، از روش ارائه شده در تاسگیتایرن و همکاران (2004) استفاده می‍شود. برای  به کارگیری الگوریتم پیشنهادی، مراحل زیر باید اجرا شوند:

• تعریف نحوة نمایش جواب
• تولید جمعیت اولیه
• جستجو، تعیین موقعیت و سرعت ذرات
• عملگرهای جهش و تقاطع

شکل 1- شبه کد الگوریتم مبتنی بر شبیه سازی تبرید.

الف)تعریفنحوه نمایش جواب ها

به منظور تبدیل مقادیر پیوسته به مقادیر گسسته از روش کوچکترین ارزش مکانی (SPV) استفاده می­شود. هر ذره با  یک بردار بیان می­شود، که تعداد آرایه های این بردار برابر با تعداد کارها است. هر ذره بیانگر یک توالی از کارهاست و برای تعیین آن مقادیر تصادفی تولید شده برای هر یک از آرایه­های این بردار به ترتیب صعودی مرتب می­شوند. در جدول 1، مثالی از نحوه نمایش جواب برای پنج کار ارئه شده است؛ در این مثال به ازی هر کار یک مقدار تصادفی تولید شده است، که کوچکترین آنها مربوط به کار 5 است، لذا این کار در اولین موقعیت برای پردازش قرار می­گیرد؛ موقعیت سایر کارها به همین ترتیب تعیین می­شود.

.جدول 1 -نمایش جواب در الگوریتم مبتنی PSO

ب) تولید جمعیت اولیه

در این مرحله، جمعیت اولیه به صورت تصادفی تولید می­شود. الگوریتم با مقادیر 20، 30 و 40 برای اندازة جمعیت اولیه تحلیل می­شود.

ج)جستجو، تعیین موقعیت و سرعت ذرات

هر ذره در جمعیت اولیه دارای سرعت صفر است. سرعت و موقعیت هر ذره با استفاده از عبارت­های (23) و (24) در هر تکرار به روز می‍شود..

مقادیر i، it، X وV به ترتیب نشان‍دهنده شماره ذره، شماره تکرار، بردار موقعیت ذره و بردار سرعت است. rand یک مقدار تصادفی بین صفر و یک است.  نشان‍دهنده بهترین موقعیتی است که ذره تاکنون یافته است و بهترین موقعیتی است که ذرات موجود تاکنون به آن دست یافته‍اند. هر دوی این مقادیر بر اساس تابع برازندگی تعیین می‍شوند.

برای تنظیم پارامترهای مربوط به موقعیت و سرعت ذرات الگوریتم با مقادیر ،  و  برای اختلاف بین حداقل و حداکثر موقعیت ذرات، و با مقادیر ،   (و   برای اختلاف بین حداقل و حداکثر سرعت ذرات، تحلیل می­شود.

   و  ضرایب یادگیری هستند. برای ایجاد توازن بین جستجوی محلی و جستجوی کلی، در محاسبه بردار سرعت از ضریب وزنی اینرسی(w) استفاده می شود. در این پژوهش این ضریب به صورت یک معادله خطی کاهشی به صورت w(  درنظر گرفته شده است.

الگوریتم با مقادیر 1، 25/1 و 2 برای ضرایب یادگیری  ،   و مقادیر 85/0، 9/0 و 99/0 برای  و تعیین ضریب وزنی اینرسی، تحلیل می­شود.

د) عملگرهای جهش و تقاطع

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

یکی از انواع عملگرهای تقاطع، عملگر OPX است (جانگواتاناکیت ؛ 2009). در این عملگر دو والد انتخاب می­شود و دو نقطه به صورت تصادفی بر روی آنها انتخاب می­شود، ژن­های موجود بین این دو نقطه از والد اول به فرزند اول منتقل می­شود، و مقدار بقیه موقعیت­ها از والد دوم به ترتیب از چپ به راست، برای فرزند اول در نظر گرفته می­شود؛ برای فرزند دوم نیز به صورت مشابه تعیین می­شود
( شکل 2 ).

الگوریتم با در نظر گرفتن مقادیر 6/0، 7/0 و 8/0 برای نرخ تقاطع و حالتهای زیر برای تعیین نوع عملگر تقاطع تحلیل می­شود:

1)   OPX

2)   تک­نقطه­ای

3)   تک­نقطه­ای / OPX

شکل 2- عملگر تقاطع تک نقطه‍ای اصلاح  شده

در این الگوریتم عملگرهای جهش جابجایی، جهش معکوس و جهش احیاء (جدول 2)،  نیز بررسی می­شود. در جهش جابجایی ابتدا دو کار به صورت تصادفی انتخاب می­شوند و با هم جابجا می­شوند؛ در جهش معکوس دو نقطه در طول کروموزوم به صورت تصادفی انتخاب می­شوند و توالی کارها بین این دو نقطه معکوس می­شود در جهش احیاء[10] دو ژن به صورت تصادفی انتخاب می­شود و دو عدد تصادفی جدید تولید شده و جایگزین اعداد قبلی می­شود (جدول2). دراین الگوریتم نیز از روش‍های جستجوی محلی به کار رفته درالگوریتم مبتنی بر شبیه‍سازی تبرید استفاده می‍شود.

جدول 2- جهش احیاء

همچنین، الگوریتم با در نظر گرفتن مقادیر 1/0، 2/0 و 3/0 برای نرخ جهش و حالتهای زیر برای تعیین نوع عملگر جهش تحلیل می­شود:

1)   جهش معکوس/ جابجایی

2)   جهش احیاء / معکوس

3)   جهش احیاء / جابجایی

به منظور محاسبه تابع هزینه و به دست آوردن زمان‍بندی کامل از روش ابتکاری ارائه شده در بخش1.2.3 استفاده می‍شود. باتوجه به این‏که بعد از چندین تکرار جواب‌ها به یک مقدار همگرا می‌شوند، حداکثر تعداد تکرار­ها به عنوان شرط توقف الگوریتم تعیین می‌شود. برای مسائل کوچک، متوسط و بزرگ به ترتیب حداکثر تعداد تکرار­ها 100، 200 و 350 در نظر گرفته شده است.

با توجه به نتایج حاصل از طراحی آزمایش­های تاگوچی پارامترهای الگوریتم پیشنهادی مبتنی بر بهینه­سازی انبوه ذرات به شرح زیر است:

اندازه جمعیت اولیه 40، عملگر جهش معکوس/احیا، عملگر تقاطع OPX، نرخ جهش 3/0 ، نرخ تقاطع 7/0 ،    برابر 2،   برابر 99/0،  برابر ،  برابر .

در شکل 3 شبه کد الگوریتم پیشنهادی مبتنی بر بهینه­سازی انبو ه ذرات ارائه شده است.

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

به منظور ارزیابی عملکرد الگوریتم های ارائه شده 20 مسأله کوچک و 24 مسأله متوسط و بزرگ با پارامترهای مختلف تولید شده است. پارامترهای مسائل با استفاده از روابطی که جانگواتاناکیت و همکاران (2009) ارائه کرده­اند، و از مقادیر تولید شده است.

مجموعه مسائل متوسط و بزرگ شامل 12 ترکیب از تعداد کارها و تعداد مراحل است، که برای هر ترکیب 2 مسأله نمونه ایجاد شده است. و هر مسأله تولید شده 10 بار اجرا شده است. الگوریتم های پیشنهادی با متلب، کدنویسی شده، و همه مسائل بر روی رایانه  پنتیوم آر دو هسته­ای، با 2.6 گیگاهرتز و  2 گیگابایت حافظه اجرا شده­اند.

مسائل نمونه بیان­شده در جدول 3 ابتدا با نرم­افزار GAMS به صورت دقیق، و سپس با الگوریتم­های پیشنهادی حل شده­اند و نتایج محاسباتی در جدول 4 ارائه شده­اند. در ستون­های اول و دوم جدول 4 شمارة مسائل نمونه و اندازة مسأله (تعداد مرحله * تعداد کار) بیان شده است. به عنوان مثال اندازة مسألة نمونة 1 معادل با (3کار * 5مرحله) است. زمان (ثانیه) و مقدار تابع هدف به دست آمده از حل مسائل نمونه با نرم­افزار GAMS در ستونهای سوم و چهارم، زمان(ثانیه) و مقدار تابع هدف به دست آمده از حل مسائل نمونه با استفاده از الگوریتم پیشنهادی مبتنی بر شبیه سازی تبرید در ستون­های پنجم و ششم، ارائه شده است که ستونهای مذکور با عنوان HSA مشخص شده­اند؛ زمان (ثانیه) و مقدار تابع هدف به دست آمده از حل مسائل نمونه با استفاده از الگوریتم پیشنهادی مبتنی بر بهینه­سازی گروه ذرات در  ستونهای هفتم و هشتم، ارائه شده است، و ستون‏های مذکور با  عنوان HPSO مشخص شده­اند.

جدول3- نحوه تولید پارامترهای مسائل نمونه

به منظور مقایسة الگوریتم­ها با یکدیگر، درصد انحراف نسبی (RPD^[11])  محاسبه می­شود. این معیار در بسیاری از پژوهش­های پیشین از جمله پژوهش بهنامیان و زندیه (2011)، از این معیار  استفاده شده است. هرچه میزان درصد انحراف نسبی حاصل از اجرای الگوریتم کمتر باشد، عملکرد الگوریتم و کیفیت جواب بهتر است.

میزان درصد انحراف نسبی (RPD) از رابطه (25) محاسبه می­شود:

که در آن sol مقدار جواب در یک اجرا است و  کمترین مقدار جواب، بین همة اجراهای مربوط به یک مسأله است.

برای مقایسة نتایج الگوریتمها از نظر زمان حل و کیفیت جواب، آزمون مقایسة زوجی با کمک نرم‏افزار مینی تب16[12] استفاده شد.

برای صحت انجام آزمون مذکور لازم است که داده­های نامتعارف در نظر گرفته نشوند، از نرمال بودن داده­ها اطمینان حاصل شود، و اندازة نمونة تصادفی باید به حدی باشد که بتوان اختلاف معنی دار بین میانگین مقادیر زمان حل و کیفیت جواب­ها را تشخیص داد.

همانطور که در جدول 5 مشاهده می­شود در مقادیر مربوط به زمان­های حل و همچنین مقادیر درصد انحراف نسبی (RPD) داده­های نامتعارف وجود ندارد؛ همچنین، چون تعداد مسائل نمونه بیشتر از 20 است نیازی به انجام آزمون نرمال بودن نیست و داده­های جمع­آوری شده برای شناسایی اختلاف معنی­دار بین میانگین زمان­های حل و میانگین کیفیت جواب‏های حاصل از دو الگوریتم، کافی است.

جدول 4 -نتایج حاصل از اجرای الگوریتم ها و نرم‍افزار GAMS

با توجه به نتایج تحلیل آماری انجام شده؛ با سطح اطمینان 95درصد،  میانگین زمان حل الگوریتم مبتنی بر بهینه­سازی گروه ذرات از میانگین زمان حل الگوریتم مبتنی بر شبیه­سازی تبرید کمتر است، و با سطح اطمینان 95درصد  میانگین درصد انحراف نسبی (RPD) الگوریتم مبتنی بر بهینه­سازی گروه ذرات از میانگین درصد انحراف نسبی (RPD) الگوریتم مبتنی بر شبیه­سازی تبرید بزرگتر است است؛ به عبارت دیگر کیفیت جواب الگوریتم مبتنی بر شبیه­سازی تبرید بهتر از کیفیت جواب الگوریتم مبتنی بهینه­سازی گروه ذرات است.

3-   نتیجه‏ گیری

در این مقاله، ابتدا یک مدل ریاضی، برای مسأله زمان‍بندی جریان کارگاهی انعطاف‍پذیر با در نظر گرفتن زمان‍های آماده­سازی وابسته به توالی و تابع هدف مجموع زودکرد و دیرکرد، ارائه شد.

جدول 5- نتایج اجرای الگوریتم‍های پیشنهادی