هستند.
زمانیکه عملیاتی بر روی ماشین آغاز میگردد تا تکمیل این عملیات امکان توقف آن وجود ندارد73.
3-3- نمادهای مدل
3-3-1- اندیسها
j : اندیس مربوط به قطعهها (i=1, … , n).
i : اندیس مربوط به ماشینها (j=1, … , m).
o : اندیس مربوط به عملیاتهای هر قطعه (o=1, … ,nj).
p,p’ : اندیس مربوط به موقعیتهای ماشینها در هر سلول (p,p’=1, … ,Um).
k,k’ : اندیس مربوط به مکانهای سلولها (k,k’=1, … ,NC).
3-3-2- پارامترهای ورودی
n : تعداد انواع قطعهها.
m : تعداد انواع ماشینها.
Lm : حداقل تعداد ماشین در هر سلول.
Um : حداکثر تعداد ماشین در هر سلول.
NC : تعداد سلولهای تشکیلی.
nj : تعداد عملیاتهای قطعه j ام.
tjo : مدت زمان پردازش عملیات o قطعه j ام.
Ni : مجموعه عملیاتهایی که بر روی ماشین i پردازش میشوند.
bjoi : 1 ، اگر عملیات o قطعه j ام بر روی ماشین i پردازش شود. 0 ، در غیر اینصورت.
Te : واحد زمان جابجایی بین سلولی قطعهها (بین دو سلول).
Ta : واحد زمان جابجایی درون سلولی قطعهها (بین ماشینهای درون یک سلول).
dkk’ : فاصله بین مکانهای دو سلول k و k’.
dpp’ : فاصله بین موقعیتهای دو ماشین p و p’.
A : یک عدد مثبت بزرگ.
3-3-3- پارامترهای خروجی
Tjoo’ : زمان جابجایی قطعه j ام بین دو عملیات متوالی o و o’ از مسیر پردازش آن قطعه (o’=o+1)
gjo : زمان تکمیل عملیات o قطعه j ام.
g(j) : زمان تمکیل آخرین عملیات قطعه j ام (زمان تکمیل کار قطعه j ام)
3-3-4- متغیرهای تصمیمگیری
Yjk : 1 ، اگر قطعه j به سلول k اختصاص یابد. 0 ، در غیر اینصورت.
Wik : 1 ، اگر ماشین i به سلول k اختصاص یابد. 0 ، در غیر اینصورت.
Xikp : 1 ، اگر ماشین i در سلول k در موقعیت p ام قرار بگیرد. 0 ، در غیر اینصورت.
Zjoj’o’ : 1 ، اگر عملیات o قطعه j ام مقدم بر عملیات o’ قطعه j’ ام باشد. 0 ، در غیر اینصورت.
{ ∀(o,o’) ϵ Ni , ∀i , j≠j’ }
3-4- مدل ریاضی
Min ∑_(j=1)^n▒g_((j)) (1)
S.T
∑_(K=1)^nc▒Y_jk =1 , ∀j (2)
∑_(j=1)^n▒〖Y_jk≥1 , ∀k (3)〗
Y_jk≤∑_(k=1)^NC▒〖 b_j1i . W_ik 〗 ,∀i , ∀j (4)
∑_(K=1)^NC▒W_ik =1 ,∀i (5)
L_m≤∑_(i=1)^m▒〖W_ik , ∀k〗 (6)
∑_(i=1)^m▒W_ik ≤U_m ,∀k (7)
∑_(p=1)^Um▒〖X_ikp≤W_ik ,∀i, ∀k〗 (8)
∑_(i=1)^m▒〖X_ikp≤1 , ∀p, ∀k 〗 (9)
∑_(k=1)^NC▒〖∑_(P=1)^Um▒〖X_ikp=1〗 ,∀i 〗 (10)
〖 T〗_joo’=∑_(k=1)^NC▒∑_(i=1)^m▒∑_(i^’=1)^m▒∑_(p=1)^Um▒∑_(p^’=1)^Um▒〖b_joi.b_jo’i’. X_ikp. X_i’kp’.d_pp’. Ta〗+∑_(k=1)^NC▒∑_(k^’=1)^NC▒∑_(i=1)^m▒∑_(i^’=1)^m▒〖b_joi.b_jo’i’. W_ik. W_i’k’. d_kk’.Te〗 (11)
,∀j , o=1,… ,n_j-1 , o^’=o+1 ,i≠i’ , k≠k’ , p≠p’
g_jo’-g_jo≥ t_jo’+T_joo’ , ∀j , o=1,…,n_j-1 , o^’=o+1 (12)
g_j’o’-g_jo+A(1-Z_joj’o’ )≥ t_j’o’ , ∀i ,for all(o.o’)∈Ni, j≠j’ (13)
g_jo-g_j’o’+A(Z_joj’o’ )≥ t_jo , ∀i ,for all(o.o’)∈Ni, j≠j’ (14)
g_jo≥ t_jo , ∀j, o (15)
g_((j))≥ g_jo , ∀j, o (16)
X_ikp, Y_jk , W_ik , Z_joj’o’ ∈{ 0,1 } (17)
4-4- تشریح مدل
در (1) تابع هدف مدل ارائه شده است که در آن ما به دنبال حداقل کردن زمان تکمیل همه کارها هستیم.
محدودیتهای شماره (2) و (3) به ترتیب تضمین میکنند که هر قطعه تنها به یک سلول میتواند اختصاص یابد و اینکه به هر سلول میبایست حداقل یک قطعه تخصیص پیدا کند.
محدویت شماره (4) باعث میشود قطعه به سلولی اختصاص یابد که اولین عملیات آن توسط یکی از ماشینهای اختصاص یافته با آن سلول پردازش شود.
محدودیت شماره (5) بیان میکند که هر ماشین میبایست فقط به یک سلول نسبت داده شود.
محدودیتهای شماره (6) و (7) مانع از این میشود که تعداد ماشینهای موجود در هر سلول از محدوده حداقل و حداکثر تعداد ماشین مجاز در هر سلول خارج شود.
محدودیت شماره (8) هر ماشین را در یکی از موقعیتهای ممکن در سلول اختصاص یافته به آن ماشین قرار میدهد. به عبارت دیگر استقرار هر ماشین تنها در موقعیتهایی مجاز است که مربوطه به سلول انتخابی برای حضور آن ماشین هستند و نه سلولهای دیگر.
محدودیت شماره (9) از اختصاص بیش از یک ماشین به هر موقعیت از هر سلول ممانعت مینماید.
محدودیت (10) اشاره دارد که هر ماشین باید تنها در یکی از موقعیتهای یک سلول قرار گیرد.
محدودیت شماره (11) زمان جابجایی بین سلولی و درون سلولی را محاسبه میکند.
محدودیت شماره (12) تاکید میکند که عملیاتهای هر قطعه مطابق توالی عملیاتهای مورد نیاز انجام میگیرند.
محدودیتهای (13) و (14) تضمین میکند که هر ماشین در یک لحظه نمیتواند بیش از یک قطعه را پردازش کند.
محدودیت (15) تضمین میکند که زمان تکمیل عملیات o قطعه j بزرگتر مساوی زمان پردازش این عملیات است.
محدودیت (16) زمان تکمیل کار قطعه j را محاسبه میکندو در نهایت محدودیت (17) مشخص میکند که متغیرهای تصمیم ما باینری هستند.
3-2- روش حل با استفاده از الگوریتم ژنتیک
3-2-1- آشنایی با الگوریتم ژنتیک
3-2-1-1- مقدمه
الگوریتم ژنتیک یک روش آماری برای بهینه سازی و جستجو است. الگوریتم ژنتیک جزئی از محاسبات تکاملی است که خود جزئی از هوش مصنوعی میباشد. ویژگیهای خاص این الگوریتم باعث میشود که نتوانیم آن را یک جستجوگر تصادفی ساده قلمداد کنیم. در واقع ایده اولیه این روش از نظریه تکاملی داروین (1859) الهام گرفته شده است و کارکرد آن بر اساس ژنتیک طبیعی استوار میباشد. نظریه تکاملی داروین بدین صورت است که آن دسته از صفات طبیعی که با قوانین طبیعی سازگاری بیشتری دارند، شانس بقاء بیشتری دارند.
ایده محاسبات تکاملی اولین بار در سال ١٩۶٠ توسط رچنبرگ74 که در زمینه استراتژیهای تکاملی تحقیق میکرد بوجود آمد که نظریه او بعدها توسط دیگر محققان توسعه داده شد. اصول اولیه الگوریتم ژنتیک توسط هلند75 و همکارانش در دانشگاه میشیگان در سال ١٩۶٢ ارائه شد. آنان در تحقیقات خود به فرایند سازگاری در سیستم های طبیعی توجه نمودند و برای مدل سازی آن در سیستم های مصنوعی که باید دارای توانایی های اصلی سیستم های طبیعی باشند، تلاش نمودند. نتیجه این تلاشها، پیدایش الگوریتم ژنتیک بود. سپس در سال ١٩٧۵، مبانی ریاضی آن در کتابی توسط هلند با نام «تطابق در سیستمهای طبیعی و مصنوعی»76 منتشر شد. ودر سال 1989 کاربرد آن با انتشار کتابی توسط گلدبرگ77 تسریع یافت. در سال ١٩٩٢، جان کوزا78 الگوریتم ژنتیک را به منظور انجام وظایف خاصی در برنامههایش بکار برد. او این روش را برنامه ریزی تکاملی79 نامید. در برنامه ریزی تکاملی، هدف پیدا کردن الگوریتمی است که بتواند جواب هر صورت مسالهای را پیدا کند. در این روش باید برای الگوریتمها مطلوبیت تعریف کرد تا فهمیده شود که کدام الگوریتم بهتر است.
خاصیت مهم الگوریتم ژنتیک، مقاوم بودن آن است، بطوریکه در آن یک تعادل انعطافپذیر بین کارایی و خصوصیات لازم برای بقا در محیطها و شرایط گوناگون وجود دارد. بطور کلی هر چه سیستم مصنوعی از نظر مقاومت در درجه بالاتری باشد، هزینه طراحی مجدد آن کاهش یافته و حتی حذف میگردد. در واقع چنانچه میزان سازگاری سیستمی افزایش یابد، آن سیستم قادر خواهد بود که به مدت طولانیتر و به نحو مطلوبتری به کار بپردازد. در سیستمهای بیولوژیک میزان انعطاف پذیری، مقاومت و کارایی به شکل شگفتانگیزی زیاد است. سازگاری، بقا، خودترمیمی، هدایت و تولید مثل از دیگر ویژگیهای خاص سیستمهای طبیعی و بیولوژیک می باشد که مهندسان در صددند تا در سیستمهای مصنوعی از آنها تقلید کنند. اما بطور کلی جایی که کارکرد مقاوم مورد نیاز باشد، طبیعت بهتر عمل خواهد کرد.
از الگوریتم ژنتیک در کاربردهای مختلفی مثل بهینهسازی توابع، شناسایی سیستمها و پردازش تصویر استفاده شده است. در زیر برخی از موارد استفاده از الگوریتم ژنتیک در علوم مختلف نشان داده شده است.
بیولوژی: شبیه سازی تکامل یک جمعیت از ارگانیسم های تک سلولی
علوم کامپیوتر: جستجو برای تکامل تابع ارزشیابی
مهندسی: شناسایی سیستمهای دینامیکی
فیزیک: حل معادلات غیر خطی برای انطباق سطوح پتانسیل ملکولی
تجارت: جستجو برای قوانین پیشگویی کننده سود شرکتها
در ادامه پس از آشنایی با مفاهیم اولیه الگوریتم ژنتیک، مراحل اجرای آن بیان می شود.
3-2-1-2- زمینه های بیولوژیکی
بدن تمام موجودات زنده متشکل از سلول می باشد. در هر سلول مجموعه ای از موجودات هم شکل بنام کروموزوم وجود دارند. کروموزومها، رشته های DNA می باشند که هر کدام متشکل از تعدادی ژن یا همان بلوک های DNA هستند. هر ژن یک پروتئین خاص یا در واقع یک خصیصه را کد می کند. به عنوان مثال رنگ چشم می تواند یک خصیصه باشد. مجموعه های ممکن برای یک خصیصه آلل نامیده می شوند. هر ژن در کروموزوم موقعیت خاص خودش را دارد که این موقعیت خاص لوکوس نام دارد. مجموعه کامل همه کروموزومها ژنوم نامیده می شود و یک مجموعه خاص از ژنها در ژنوم، ژنوتیپ نام دارد. ژنوتیپها بعد از تکامل بیشتر به فنوتیپها که همان خصوصیات فیزیکی و روانی مانند رنگ چشم یا هوش و غیره می باشند، تبدیل می شوند.
3-2-1-3- فضای جستجو
وقتی که ما به دنبال حل مسالهای هستیم، معمولا به دنبال جوابهایی میگردیم که بهترین جوابها در میان مجموعه جوابهای موجود باشند. فضای تمام جوابهای قابل قبول، فضای جستجو نامیده میشود.
هر نقطه در فضای جستجو یک جواب قابل قبول را نشان می دهد. هر جواب قابل قبول می تواند بر اساس ارزش یا مطلوبیتش برای مسأله مشخص گردد. هدف از پیدا کردن جواب، که میتواند یک نقطه یا بیشتر در میان جوابهای قابل قبول باشد، پیدا کردن یک نقطه یا بیشتر در فضای جستجو

مطلب مرتبط :   منابع پایان نامه ارشد دربارهTechnology، Agriculture، determination

Written by 

دیدگاهتان را بنویسید