intra اگر عملیات j قطعه p روی ماشین m در دوره t در سلول c انجام شود برابر ١ است، در غیر اینصورت برابر صفر است.
h j,p,m,c,t
هزینه حرکت بین سلولی برای هر دسته تولیدی inter هزینه نصب ماشین نوعm
ICm
هزینه حرکت درون سلولی برای هر دسته تولیدی intra اندیس عملیاتهای متعلق به قطعه j

١- مقدمه
از لحاظ انـدازه و روش سـاخت بـا هـم دارنـد در خـانواده یـا کاهش زمان آمادهسازی مـیشـو د. ایـ ن روش هنگـام ی بـه کـار

زمستان
تکنولوژی گروهی روشی اسـت کـه در تولیـ د کارگـاه ی بـرای قطعاتی که دوره تولید آنها نسبتًاً کوتاه است مورد اسـتفاده قـرارمیگیرد. در این روش قطعاتی که اساسًاً غیرمشابه هستند بـدوندرنظر گرفتن مورد استفاده و کاربرد آنها و براساس تشابهاتی که گروههایی گروهبندی میشوند. هر دستهبندی یـ ک خـانواده ازمحصولات نامیده میشـوند و بـرای هـر دسـته یـ ک مجموعـهماشینآلات تخصیص داده میشود. بـه ایـ ن ترتیـ ب بـرا ی هـرخانواده (گروه) یک شبهخـط تول یـ د در داخـل یـ ک سـلول یـ ا کارگاه ایجاد میگـردد. ایـ ن باعـث افـزایش کـارآ یی سیسـتم ومیرود که تشابه چنـد محصـول در طر احـی یـ ا روش سـاختوجود داشته باشد. در داخل هر فرآیند، ماشـین آلات بـراسـاسترتیب ساخت محصول چیده می شوند یعنی بـراسـاس منطقـی خاص گروهبندی میشوند. در واقع تکنولوژی گروهـی ترکی بـی از اس تقرار خ ط تولی د و اس تقرار کارگ اهی اس ت، بن ابراین تکنولوژی گروهی یک استقرار ترکیبی است. در این استقرار هر سلول برای ساخت یک خانواده از محصولات بـ هکـار مـیرود. درواقع تولید سلولی١ بهتر از تولید کارگاهی و تولیـ د محصـولی است. در عصر رقابت و تکنولوژی برای اینکه بتوان محصولات خود را با کمترین هزینه، بالاترین کیفیت و در سریعترین زمـانممکن به دست مشتری رساند، سیستم تولیـ د سـلولی٢ ی کـی از گزینههای خوب بهشمار میآید. استقرار ماشینآلات تعیین شده برای هـر خـانواده از قطعـات بـا بهـرهگ یـری از ی کـی از انـواعاستقرارهای زیر است:
الف) استقرار براساس تکنولوژی گروهی- خطی ب) استقرار براساس تکنولوژی گروهی- سلولی ج) استقرار براساس تکنولوژی گروهی- مرکزی همچنین سیستم تولید سلولی شامل انواع مختلفی است کـه میتوان به موارد زیر اشاره کرد:
الف) سیستم تولید سلولی کلاسیک ب) سیستم تولید سلولی مجازی ج) سیستم تولید سلولی انعطافپذیر د) سیستم تولید سلولی پویا
در این تحقیق تولید سلولی پویا در حالت قطعـ ی بـا هـدفبهینهسازی تعداد سلولها مورد نظر است.
سیستم تولید سلولی پویا٣ در شرایطی استفاده میشود که سیستم دارای تقاضا و ترکیب محصـول متغ یـر در دوره هـای مختلـف اسـت. در ایـن سیسـتم ایسـتگاهاهـ ی کـاری قابـل جابهجایی هستند. در کارخانههایی که برونسپاری قطعات یا قراردادهای فرعی انجام میشود این سیستم استفاده میشـود.در این سیستم کارگاه متمرکز بـوده و انجـام اسـتقرار مجـددآسانتر از سیستم تولید سلولی کلاسیک و مجازی است [١]. در سیستم تولیـ د سـلول ی پویـ ا در پر یـود هـای زمـانی بـرای بهینهسازی سلولها، ماشینآلات جابهجـا مـیشـوند . امـا درطول هر پریود تولید میتوان محصولات را از یک سلول بـهسلول دیگر حرکت داد.
در سیستم تولید سلولی با شرایط قطعـ ی، تقاضـا در هـردوره مشخص و قابل اندازهگیری است اما تقاضا در هر دوره با دوره دیگر میتواند متفاوت باشد.
از مزایای سیستمهای تولید سـلول ی مـیتـوان بـه مـواردکاهش زمان راهاندازی، کاهش زمان تولید، کنترل بهتر فرآیند، استفاده بهینه از فضا، افزایش تخصص کارکنان، کاهش زمـانحمل و نقل اشاره کرد. همچنین معایب سیستم تولید سلولی را میتوان شامل هزینه بالا، حمـل و نقـل هـای بـین سـلولی، مشکلات خرابی، عدم تعادل در بارکاری ماشینها و نیاز بـهنیروی کار تخصصی بیشتر دانست [١]. در ادامـه مقالـه و در بخش دوم به مرور ادبیـ ات در ایـ ن حـوزه پرداختـه خواهـد شد. مسأله در بخش سوم تعریف شده و مدل ریاضی مـرتبطبا آن ارائه میشـو د. متـدولوژ ی هـای حـل مسـأله در بخـش چهارم توضیح داده شده اسـت و همچنـین نتـایج عـدد ی و گزارشهای مرتبط با آن در بخش پـنجم ارائـه مـیشـو د. در انتها نیز بحث و نتیجهگیری بیان شده است.

٢- مرور ادبیات
صفایی و همکاران [٢] و بالاک ریشنن و چانگ [٣] به بـازب ینی تحقیقات انجام شده در زمینه مسائل تشکیل سـل ولی در شـرایط پویا در سیستمهای تولیـ د سـلول ی پرداختنـد. بـالاک ریشـنن وچانگ یک مدل دو مرحلهای برای مسأله تشکیل سلول تولیدی در شـرایط پویـا ارائـه دادنـد، هـدف اصـلی مـدل پیشـنهادی، حداقلسازی هزینـه حمـل و نقـل مـواد و مکـانی یـابی مجـدد ماشینها بود. توکلی مقدم و همکاران [۴] یک مدل برنامهریزی غیرخطــی بــرای تولیــد ســلولی در محــیط پویــا بــا فــرضحداقلسازی هزینه استقرار مجـدد، هز ینـه ثابـت و عمل یـاتی و هزینه حمل بینسلولی ارائه دادند و بـه مقا یسـه الگـوریتم هـای
فراابتکاری جستجوی ممنوعه۴، ژنتیک5، تبرید شبیهسازی شده6برای حل پرداختند. دفرشا و چن [۵] نیز به بررسی تأثیر اهداف برنامهریزی تولید بر تشکیل سلول پویا پرداختنـد. هـدف مـدل پیشنهادی آنها شامل حداقلسازی هزینه عملیاتی ماشین، هزینـهاستقرار مجدد، هزی نه برونسپاری قطعات، هزینه مصـرف ابـزار،هزینه راهاندازی و بالانس بارکاری سلولها بـود. در ایـ ن مـدلحمل درونسلولی قطعات، نگهداری موجـودی و هزینـه تول یـد داخلـ ی درنظـ ر گرفتـ ه نشـ ده اسـ ت. تـ وکل ی مقـ دم و همکاران [6] یک مدل سیستم تولید سلولی بـا تقاضـای پویـ ا و احتمـالی را ارائـه دادنـد. هـدف مـدل پیشـنهادی آنهـا شـامل حداقلسازی هزینههای ماشین، چیدمان مجدد، حمل بینسلولی و درونسـلولی، عبـارت جریمـه مجمـوع انحـراف از میـانگین تقاضای قطعات بود و به کمک الگوریتم تبرید شبیهسازی شـده آن را حل کردند.
سعیدی و صفایی [٧] از یک روش شبکه عصبی برای حـلمسأله تشکیل سلول تولیدی پویا با هدف حـداقل سـازی هزینـهاســتقرار مجــدد، هز ینــه ثابــت و تغ ییــر ماشــین بــا درنظــر گرفتن مسیرهای چندگانه و تکرار ماشـ ینهـا ٧ اسـتفاده کردنـد.
اسکالر [٨] یک مدل عدد صحیح خطی را برای مسـأله تشـکیل سلولی با هدف حداقلسازی هزینه تولید قطعات، هزینـه ثابـتماشین و هزینه جابهجایی ماشین ارائـ ه و آن را بـه کمـک یـ ک الگوریتم جستجوی ممنوعه گ سترش یافته حل کـرد. صـفایی و همکاران [٢] یک مدل سلولی با اهداف هزینه حمل بین سـلولی و درونسلولی ارائـه دادنـد. تأک یـد مـدل پ ی شـنهادی بـر میـ زان جابه جـایی مـواد درون سـلولی و بـ ین سـلولی بـا فـرض تـوالی عملیات، مسیرهای عملیاتی چندگانه و امکان تکرار ماشینها از یک نوع در سلول است و آنها برای حل مدل پیشنهادی از یـ ک الگوریتم ترکیبی تبرید شبیهسازی شده استفاده کردند. دفرشـا وچن [٩] یک مدل ریاضی جـامع بـرای طراحـی سیسـتم تول یـ د سلولی پویا براساس نیازهای ابزاری قطعات و در دسترس بودن ابزار روی ماشینآلات پیشنهاد کردند. این مدل به حداقل سـازی هزینه عملیاتی ماشین، هزینه استقرار مجدد، هزینـه حمـل بـین سلولی، هزینه مصرف ابزار، هزینه برونسپاری قطعات و بالانس بارکاری درونسلولی میپرداخت و برای حـل آن از یـ ک روش الگـوریتم ژنتیـک متـوازی جدیـد اسـتفاده کردنـد. مهـدوی و همکاران [١٠] مدل ریاضی عدد صحیح بـرا ی طراحـی سیسـتمتولید سلولی پویا را با درنظر گـرفتن فـاکتور هـای ن یـروی کـارگسترش دادند. دلجو و همکاران [١١] نیـ ز یـ ک مـدل ر ی اضـی برای تولید سلولی پویا ارائه و آن را با الگـوریتم ژنتیـ ک بهبـود یافته حل کردند.
دورن و همکاران [١٢] مسأله تشکیل سلولهای تول یـدی را مورد مطالعه قرار داده و آن را با استفاده از الگوریتم بهینه سـازی ازدحام ذرات٨ و داده کاوی٩ حل کردند. قطبالدینی و همکاران [١٣] یک مدل بهینهسازی چند هدفه برای مسأله تول یـد سـلول ی پویا بیان کردند. مدل مطرح شده گروهبندی ماشین و قطعـات وهمچنین تخصیص نیروی انسـانی را بـهطـور هـمزمـان در نظـر گرفته است. کوشان به هزینه ثابت و متغیر ماشـ ین، هزی نـه هـای حمل و نقل بین سلولی و درونسلولی، هزی نـه اسـتقرار مجـدد، هزینه راهاندازی تولید و هزینه اسـتهلاک ماشـینآلات پرداختـهاست [١]. کیا و همکاران [١۴] یک مدل ریاضی غیرخطی برای طراحی استقرا ر یک سیستم تول یـد سـلول ی پویـ ا را مطالعـه و ازالگوریتم تبرید شبیهسازی شده کارا برای حل ای ن مسأله استفاده کردند.
در این تحقی ق یک مسأله تولید سـلولی پویـ ا درنظـر گرفتـهشده اسـت کـه در آن تقاضـاهـا در طـول دوره ثابـت ولـی در دورههای مختلف با هـم متفـاوت اسـت . تشـکیل سـلولهـا وچگونگی قرارگیری ماشینها در آن مدنظر بوده است. همچنـین در این مقاله تعداد سلولهای تشکیلی بهعنـوان متغ یـری درنظـرگرفته شده است که بایـ د مشـخص گـردد. هزینـه هـای درنظـرگرفته شده در این تحقیق شامل هزینههای ایجاد سـلول، هز ینـهجابهجایی بـین سـلول ی، هزینـه نصـب و حـذف ماشـینآلات، هزینههای عملیاتی، هزینه قرارگیری ماشـین در یـک سـلول بـادرنظرگیری ارزش زمـانی پـول، هزینـه حمـل و نقـل قطعـاتدرونسلولی و بین سلول ها است. همچنین مـدل ارائـه شـده دراین مقاله برای اولین بار در ادبیات این موضوع توسط الگوریتمبهینهسازی برمبنای جغرافیای زیستی١٠ حل شده و نتایج حاصله با الگوریتم ژنتیک مقایسه شده است.

٣- تعری ف مسأله
مدل ارائه شده در این مقاله یـک مـدل تولیـد سـلولی پویـ ا در شرایط قطعی است و هدف آن پیدا کردن تعداد بهینه سلول هـابا استفاده از حـداقل کـردن هزی نـه ایجـاد سـلول، هزینـه هـای درونسلولی و بینسلولی، هزینههای ثابت و متغیر ماشـ ینآلات، هزینه قرارگیری ماشینآلات در یک سلول، هزینه استقرار مجدد (هزینه نصب و حذف ماشینآلات)، هزینههای عملیاتی و هزینه حمل و نقل ماشینآلات بهازای سلولهای طی شده است.

٣ -١- هزینههای مدل
هزینههای مورد بررسی در این مدل پیشنهادی شامل موارد زیـ ر است:
هزینه ثابت ماشین: مجمـوع هزینـه هـای خر یـد، نگـهداری ماشین در هر دوره.
هزینه متغیر ماشین: شامل هزینه هـای عمل یـات بـرای تول یـد قطعات وابسته به بارکاری اختصاص یافته بـه هـر ماشـین است.
هزینههای حمل و نقل بین سلولی: این هزینه زمـان ی ایجـادمیشود که همه عملیاتهای متوالی یک قطعه در یک سلول انجام نشود و قطعه به سلول دیگری منتقل شود.
هزینههای حمل و نقل درونسلولی: این هزینه زمانی ایجـادمیشود که همه عملیاتهای متوالی یک قطعه در یک سلول انجام شود اما روی ماشینهای مختلفی باشد.
هزینه نصب ماشینآلات: در ازای نصب هر ماشـ ین سیسـتممتحمل هزینه میشود.
هزینه ثابت راهاندازی سلولهای تول یـدی: هزینـه راه انـدازی هر دسته تولیدی درونسلولی برروی ماشینهای مختلف.
هزینه استقرار مجدد: بهازای اضافه کردن یک ماشین جدیـ د به سلول یا حذف کردن یک ماشین از یک سـلول ، سیسـتممتحمـل هزینـه مـیشـود. هزینـه نصـب و هزینـه حـذف ماشینآلات از هم متفاوت است.
هزینه حمل و نقل ماشینآلات بهازای واحد سلول طی شده: در هر بار جابهجایی ماشینآلات، بهازای میزان جابـه جـایی ماشینآلات از یک سلول به سلول دیگر هزینهای تخصیص داده میشود که برای هر ماشین این هزینه متفاوت است.
هزینه ایجاد سلول: در ازای ایجـاد سـلول سیسـتم متحمـلهزینه میشود.

٣ -٢- مفروضات مدل
پارامترهای مدل بهصورت قطعی و معی ن هستند.
ظرفیت هر ماشین مقدار معین و ثابتی اسـت . جهـت تـامین احتیاجات ظرفیت، تکرار ماشینها مجاز است.
ماشینها از۱۰۰ درصد ظرفیت خود استفاده میکنند.
قطعات بهصورت دستهای درون سلول و بین سلول حرکت میکنند. تعداد قطعاتی که درون هر بسته قرار میگیرند برای درون سلولی و بیرون سلولی متفاوت است ولی اندازه ایـ ن دستهها، هم در درون سلولی و هم در بیرون سـلول ی ثابـتاست و تغییر نمیکند.
هزینه حرکت بیرون سلولی ماشین آلات بهازای جابـه جـایی بین سلولها مشخص و معین است و این هزینـه بـرای هـرماشین متفاو ت است.
حداقل و حداکثر تعـداد ماشـینآلات موجـود در سـلولهـامشخص است.
تغییر مکان ماشینها از یک محـل بـه محـل دیگـر در بـین دورهها انجام شده و زمان آن صفر است.
مدت زمان نصب و حذف ماشینآلات صفر است.
مساحت کف کارگاه معلوم و مشخص است.
در صورت ایجاد هـر سـلول، مکـان آن مشـخص و معـین است.
بهدلیل وجود تقاضای متفـاوت در هـر دوره، ممکـن اسـتاستقرار سلولی در یک دوره برای دوره بعدی بهینه نباشد ودر هر دوره نیاز به مکانیابی مجدد ماشینها باشـد.
توالی عملیات: نشاندهنده ترتیـ ب انجـام عمل یـ ات بـرروی قطعه است.
انعطافپذیری ماشین: هر ماشـ ین مـ یتوانـد یـ ک یـ ا چنـدعملیات را با زمانهای مختلف، بدون هزینه اضـاف ی انجـامدهد.

٣- ٣- مدل ریاضی
مدل ری اضـی پی شـنهادی عـدد صـحیح غی رخطـی بـرای مسـأله طراحی تولید سلولی پویا در شرایط قطعی تقاضا بهصورت زیـ ر است:

Min cost= Costi
i1
CN T
Cost= CEdc,tc 1 1t
MFF T
Cost= gm,f,f, t’ Lm (٣) m1 1 1 1f  f t
MT CN
Cost= bm,t,c ICm dc,t (۴) m  1 1 1t c
MT CN
Cost= km,t,c RCm dc,t (۵) m  1 1 1t c
PTMJ CN
Cost= p    1 1tm 1 1 1jc Dp,t h j,m,p,c,t t j,p,m Om(6)
MT CN
Cost= dc,t bm,t,c Cm 1 rt1 (٧) m  1 1 1t c
Cost7 21tT1intra

Dintrap,t j   J1 1 1pP CN Mcm 1 hj1,p,m,c,t 
dc,t  hj,p,m,c,t dc,t(٨)
1684062-777217

Cost8 21tT1inter

Dinterp,t j  J1 1 1pP CNcej1,p,c,t 

dc,t ej,p,c,t dc,t(٩)
محدودیتها:
CN M
a j,p,mh j,p,m,c,t 1 j,p,t c 1m 1 (١٠)
qm,t,c  bm,t,c  km,t,c m,c,t 1 (1١)
M
bm,t,c  LB c,t m1 (1٢)
M
bm,t,c  UB c,t m1 (1٣)
M
h j,p,m,c,t  ej,p,c,t j,p,c,t m1 (1۴)
CN
dc,t 1 t c1 (1۵)
F
gm,f,f ,t 1 m,f,t f1 (16)
M
bm,t,c  CN dtc,t t  m1 (1٧)
CN
dc,t  CNt t  c1 (1٨)
dc,t ,bm,t,c,km,t,c,ej,p,c,t,hj,p,m,c,t,gm,f,f ,t or 0 1 (1٩) CNt 0 , integer(٢٠ )
در تابع هدف رابطه (٢) بیانگر هزینه ایجاد سلول اسـت .
رابطه (٣) بیانگر هزینه جابهجایی ماشین m از یک مکـان بـهمکان دی گر است که بهازای هر ماشـ ین ایـ ن هزینـه متفـاوتاست. رابطه (۴) هزینه نصب ماشین در یـک سـلول را بیـ ان میکند. رابطه (۵) هزینه حذف یک ماشین از یـ ک سـلول ر ا بیان میکند. هزینه ۴ و ۵ به این دلی ل هستند که بهازای نصب یا حذف ماشی ن یک سری عملیات فنی و مهندسی باید انجام شود که همین عملیات باعث ایجاد هزینه میشود. رابطه (6) هزینههای عملیاتی را بیان میکند. بـهازای تعـداد قطعـات ومدت زمان کار ماشین بـرروی قطعـات ایـ ن هزینـه محاسـبهمیشود. رابطه (7) هزینه قرارگیری ماشین درون یک سـلولرا محاسبه میکند. این هزینه با درنظـر گـرفتن ارزش زمـانی پول است. رابطـه (٨) هزی نـه حمـل و نقـل درون سـلولی را محاسبه میکند و نشان میدهد اگر عملیات در یک سلول اما روی دو ماشین مختلف انجام شود، دو عملیـ ات متـوال ی بـهحرکت درونسلولی نیاز دارد. رابطه (٩) هزینه حمـل و نقـل بین سلولی را نشان میدهد که اگر دو عملیات متـوال ی در دو سلول جداگانه انجام شود، به حرکت بین سلولی نیاز است.
محدودیت (١٠) تضمین میکند اگر تقاضای هر قطعه در یک دوره معین تولید شود، هر عملیات به یـ ک سـلول و بـهیک ماشین تخصیص داده میشود. رابطه (١١) نشان میدهـدکه اگر سلول C ایجاد شـود چـه تعـداد ماشـینآلات در هـردوره در سلول موجود اسـت. محـدودیتهـای (١٢) و (١٣) بهترتیب حد بالا و پایین اندازه سلول را نشان میدهد. رابطـه(١۴) بیان میکند در هر سلول و در هر ماشین، حـداقل یـ ک عملیات انجام میشود. محدودیت (١۵) نشاندهنده آن است که در هر دوره حداقل یک سلول باید ایجاد شود. محدودیت (١۶) بیان می کند یک ماشین در هر دوره یک بـار مـیتوانـدجابهجا شود. رابطه (١7) بیانگر ا یـن اسـت کـه زمـانی یـک ماشین در یک سلول میتواند قرار بگیرد که آن سلول ایجـادشده باشد. رابطه (١٨) بیانگر این است که در هـر دوره چـهتعـداد سـلول ایجـاد شـده اسـت. رابطـه (١٩) و (٢٠) نـوع متغیرهای تصمیم را تعیین میکنند.

۴- متدولوژی
این بین الگوریتمهای تکاملی که از تکنیک بهینـه سـازی مبتنـی (٢٢) {n+1, n+2, … , n+m}: مجموعه ماشینآلات M

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

شما می توانید تکه های دیگری از این مطلب را با جستجو در همین سایت بخوانید

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

اینجا کلیک کنید

در این تحقیق برای حل مـدل بایـ د از روش هـای فـرا ابتکـاری استفاده شود تا بتوان جوابهایی قابل قبول و یا بهینه را بهدست آورد. در روشهای فـرا ابتکـاری بـه طـور کامـل نمـیتـوان بـه جواب بهینه رسید اما میتوان تا حدود زیادی بـه جـواب بهینـهنزدیک شد. الگوریتمهای فراابتکاری، جایگـاه و یـژهای در حـلمسائل بهینهسازی بهخصوص مسائل با ابعـاد بـزرگ د ارنـد. درب ر جمعی ت اس تفاده م یکنن د، بخ ش مهم ی از روشه ای فراابتکاری را تشکیل میدهند. ایده اولیه الگوریتمهای تکـاملی، استفاده از جمعیت محدودی از عناصر است که هر یک از آنهـانقطهای از فضای جستجو (یک جواب برای مسأله) را مشخص میکنند.

۴ -١- نحوه کدگذاری جوابها مدل درنظر گرفته شده یک مدل سلولی است. در ا یـن مـدلایجاد سلول و نحوه قرارگیری ماشینآلات در آن مهم اسـت. در این مدل تعداد قطعه، تعداد ماشینآلات، تعـداد عمل یـات، تعداد دورهها و تعداد جایگاههای کف کارگاه معلـوم هسـتند و هدف بهدست آوردن تعداد سـلول هـا در هـر دوره اسـت . برای بهوجود آوردن کروموزوم در این مدل فقط ماشینآلات و کف کارگاه درنظر گرفته شده است، چـرا کـه جابـه جـایی قطعات وابسته به نحوه قرارگیری ماشـینآلات در سـلول هـااست. بهدلیل داشتن هزینه جابـه جـایی ماشـینآلات از یـک مکان به مکان دیگر، کارگاه قسمتبندی شـده اسـت و اگـرماشینی از یک قسمت به قسمت دیگر جابهجا شـود سیسـتممتحمل هزینه میشود. بیشترین تعداد تشکیل سـلول برابـرn است (به تعداد جایگاهها) و کمتـر ین تعـداد سـلول برابـر ١ است (اگر تعداد سلول صفر باشد بهدلیل ایجاد نشدن سـلولو قرار نگرفتن ماشینآلات در سلول، تولیـ د وجـود نخواهـد داشت). در این مدل تعداد ماشینآلات محدود درنظر گرفتـهشده است و در هر دوره تعداد ماشینآلات تغییری نمـیکنـدو ثابت است. از آنجا که این مدل چند دورهای است بههمین دلیل برای هر دوره یک کروموزوم ایجاد میشود. بهطور مثال در صورت ۴ دورهای بودن مدل، ۴ کروموزوم تولید میشود. کروموزوم بهصورت شکل (١) تعریف می شـود کـه در آنn نشاندهنده تعـداد جایگـاه هـا وm ن یـز نشـاندهنـده تعـدادماشینآلات مورد استفاده است.
(٢١) {n-1, n , … ,3 ,2 ,1}: مجموعه جایگاهها N بهطور مثال فرض میشود یکسری اعداد بهصورت تصـادف ی از اعداد ١ تا ٨ +١٠ در این کروموزوم بهصورت شـکل (٢) تولیـ د میشود، تخصیص دادن این اعداد بهصورت زی ر است:

{٨ ,… ,3,2,1}={n ,…,3,2,1} :مجموعه جایگاهها N

{١٨,…,٩}={n+1,…, n+m} :مجموعه ماشینآلاتM براسـاس کرومـوزوم ایجـاد شـده در بـالا مـیتـوان ترت یـ ب سلولهای ایجاد شده و ماشینآلات قرار گرفته در هر سـلولرا مشخص کرد. اعداد کوچکتر از ٩ مشخص کننده سلولهـا هستند. ماشینآلاتی که در داخل کروموزوم بعد از یک مکان یک سلول در کروموزوم تا مکان سلول بعدی آورده شدهانـدمشخص کننده ماشـ ینآلات تخصـ یص داده شـده بـه سـلولاست. در این شـکل سـلول هـای تشـکیل شـده عبا رتنـد از:سلولهای ١، ٢، ٣، ۴، ۵، 6 و ٧. بهطـور مثـال ماشـین ٩ بـهسلول شماره ۵ اختصاص یافته و ماشین ١١ به سلول شـمار ه ۴. شکل (٣) نحوه قرارگ یـری ماشـینآلات در هـر سـلول رانشان میدهد. این کروموزوم ایجاد شده تنها برای یـ ک دوره زمانی مثًلاً ١= t است و برای بق یـه دورههـا کرومـوزوم هـای مربوطه نیز باید محاسبه شوند.
براساس کروموزوم ایجاد شده در شکل (۴) سـلول هـای تشکیل شده عبارتند از: سلولهای ٢، ٣، ۵، 6، ٧ و ٨. شـکل(۵) نحـوه قـرارگیـری ماشـینآلات در هـر سـلول را نشـان میدهد. در این کروموزوم شماره ماشین ١٢ در اولـ ین خانـ ه کروموزوم افتاده اسـت ، ایـ ن ماشـ ین بـه سـلولی اختصـاصمییابد که شماره آن بعـد از ماشـین ١٢ قـرار گرفتـه اسـت.
براساس مدل، در هر دوره بای د یک سلول ایجاد شود.

۴ -٢- الگوریتم بهینهسازی برمبنای جغرافیای زیستی مسأله تشکیل سلول جزء مسائل سخت طبقه بنـدی مـیشـود[١۵] که بهدست آوردن جوابی دقیق برای آن در ابعاد بـزرگامکانپذیر نیست لذا از روشهای فراابتکاری برای حـل ایـ ن نوع مسائل استفاده میشود. توکلی مقـدم و همکـاران [۴] در مقاله خود ذکر میکنند که مسأله تشکیل سلولهـا در حالـتاستاتیک (تـک دوره ای) جـز مسـائل سـخت اسـت. مسـأله بررسی شده در این مقالـه تشـکیل سـلول هـا را بـهصـورتدینامیک (چند دورهای) دیـ ده اسـت. بنـابراین بـا توجـه بـهسخت بودن حالت استاتیک مسـأله در حالـت د ینامیـ ک نیـ ز سخت خواهد بود و نیاز به زمـان محاسـباتی بیشـتری دارد. الگوریتم بهینهسازی برپایه جغرافیای زیستی کـه بـهاختصـار BBO نامیده میشود از جمله الگوریتمهای مبتنی بر جمعیت است. این الگوریتم برای اولین بار توسـط دن سـایمون [١6] ارائه شد و در آن از چگونگی تقسیم جمعیت در اقلـیم هـای مختلف الهام گرفته شده است. براساس اطلاعات ارائه شـدهدر این مقاله جانوران تمایل دارند به اقلیم هـایی کـه در آنهـاغذا راحتتر و با رقابت کمتر حاصل خواهد شد، مهـاجرتکنند. بنابراین اقلیمهایی که شاخص راحتی١1 در آنهـا بـالاتراست نـرخ مهـاجرت پـذیری١٢ ( ) در آنهـا بیشـتر و نـرخمهاجرت١٣ () از آنها کمتر است.
این الگوریتم براساس بهینهسازی پیوسته ١۴ طراحی شـدهاست ولی با استفاده از ترفندهایی میتوان آن را برای استفاده در مسائل گسسته١۵ نیز مورد استفاده قـرار داد. بـا توجـه بـه روش حل این مقاله و اینکه از یک فرم جایگشـتی از اعـدادگسسته برای حل مسأله استفاده شده است باید اعداد پیوسته مورد استفاده در این الگوریتم به اعداد گسسـته جایگشـتی١6 تبدیل شوند. با توجه به ماهیت پیوسته الگوریتم BBOاعداد تولیدی بهصورت تصادفی در بازه [١-٠] تولید شـ دهانـد تـااعمال اپراتورهای الگوریتمها برروی آنها بهراحتـی صـورتگیرد. بعد از تولید این اعداد تصادفی باید آنهـا را بـه اعـدادصحیح تبدیل کرد تا بتوان آنها را به یک جـواب قابـل قبـول تبدیل نمود. برای این کار، مانند مثال ارائه شده در شکل (6) به هر یک از اعداد تولیدی یک شماره تخصـیص داده شـده و اعداد از بزرگ به کوچک مرتب میشود. بـا مرتـب کـردن ایـن اعداد غیرصحیح، اعداد صحیح تخصیص داده شده به آنهـا نیـزجابهجا میشوند و جایگشت موردنظر از اعداد حاصل میشود. شاخص راحتی منطقه کـه بـاHSI نشـان داده مـیشـود درمسائل بهینهسازی مشخص کننـده نـرخ هـای  و  اسـت کـه مقدار آن متناسب با تابع هدف مسـأله اسـت . همانگونـه کـه درشکل (٧) نشان داده شده است، با افـزایش شـاخص مطلوب یـت یک منطقه، نرخ  آن کاهش و  آن افزایش مییابد.
هر جواب موجود در فضای جوابها از متغیر هـای تصـمیم مختلفی تشکیل شده است که مشـخص کننـده کیف یـت جـواب(مقدار تابع هدف) هستند و آنها را در ایـ ن الگـوریتم شـاخص
١ ٢ ٣ ۴ ۵ 6 . . . n n+1 n+2 . . . n+m
شکل ١- کروموزم تولید شده در n+m عدد

۵ ٩ ٣ ١٢ ١٠ 6 ١٣ ١۴ ۴ ١١ ١ ١6 ٧ ١٧ ٢ ١۵ ١٨ ٨
شکل ٢- کروموزوم ایجاد شده در ٨+١٠ عدد

ماشین ١١- سلول ۴ ماشین ١٢ و ١٠- سلول ٣ ماشین ١۵و ١٨- سلول ٢ ماشین ١6- سلول ١
ایجاد نشده است. سلول ٨ ماشین ١٧- سلول ٧ ماشین ١٣ و ١۴- سلول 6 ماشین ٩- سلول ۵
شکل ٣- نحوه قرارگیری ماشینآلات در هر سلول

١٢ ٢ ١۴ ١٣ ٨ ١٠ ٧ ١١ ۴ ١ ٣ ١۵ ۵ ١6 ٩ 6 ١٧ ١٨
شکل ۴- کروموزوم ایجاد شده در ٨+١٠ عدد. در زمان t=2

تشکیل نشد- سلول ۴ ماشین ١۵- سلول ٣ ماشین ١٢، ١۴ و ١٣ – سلول٢ تشکیل نشد- سلول ١
ماشین ١٠- سلول ٨ ماشین ١١- سلول ٧ ماشین ١٧ و ١٨- سلول 6 ماشین ١6 و ٩- سلول ۵
شکل ۵- نحوه قرارگیری ماشینآلات در هر سلول در زمان t=2

۷ 6 ۵ ۴ ۳ ۲ ۱ اعداد تخصیص داده شده
۰/۱۲۵ ۰/۹۰۲ ۰/۸۷۸ ۰/۵۲۳ ۰/۰۰۱ ۰/۲۵۸ ۰/۴۸۱ اعداد تصادفی تولیدی
6 ۱ ۲ ۳ ۷ ۵ ۴ رتبه اعداد
۳ ۷ ۲ ۱ ۴ ۵ 6 جایگشت حاصله
شکل 6- تبدیل کروموزوم تولیدی پیوسته به گسسته
مطلوبیت١٧ یا به اختصار SIV مینامند. در این الگوریتم هر یک از جوابها با احتمالی که متناسب با مقدار آن جـواب اسـت SIV ها را مهاجرت میدهد و با احتمالی کـه متناسـب بـا  آن جواب است SIV ها مقصد SIV های جوابهای دیگر خواهنـدبود. مراحل الگوریتم BBO شامل موارد زیر اسـت کـه بـهطـور خلاصه ذکر شده است:
گام ١. تولید مجموعهای از جوابهـا و مرتـب سـازی آنهـابراساس تابع هدف.

گام ٢. تعیین مقادیر بین صفر و یک برای  و  بـر اسـاس رتبه جوابها (فضای بین صفر و یـک را بـه تعـداد جـوابهـاتقسیم و براساس رتبه جوابها این مقادیر را به آنها اختصاص داده میشود. باید توجه داشت که بهترین جواب بـالاترین نـرخ
 و پایینترین نرخ  را خواهد داشت).
گام ٣. بـهازای هـر جـواب ماننـدi مراحـل ۴ تـا ٨ تکـرارمیشود.
گام ۴. بهازای هر متغیر مانند k مرتبط با جواب i مراحـل ۵ تا ٨ انجام میشود.
گام ۵. با احتمالi در xik تغییرات را اعمال میشود. طبق مراحل 6 تا ٨ تغییرات انجام داده میشود.
گـ ام 6. تعی ین مب دأ مه اجرت ب ا اسـتفاده از مق ادیر و بهصورت تصادفی که آن j نامیده میشود.
گام ٧. انجام مهاجرت ازx jk بهxik بـا اسـتفاده از روابطـی که در زیر به آنها اشاره میشود:
xiknew  xikold a (xk jk xikold) که در این رابطهak یک عدد تصادفی تولید شده بین صفر و ی ک است. با اندکی سادهسازی رابطه بـالا ، رابطـه زیـ ر حاصـلمیشود که نشاندهنده نوعی عملگر تقاطع١٨ است:

xiknew  (1 a )xkikold a xkjk
گام ٨ . با احتمال معی ن برروی مؤلفهxik جدید تولید شده،

شکل ٧- رابطه بین شاخص راحتی و نرخهای مهاجرت
عملگر جهش١٩ با تولید عدد تصادفی نرمـال بـا م یـانگینxik و واریانس  ، که عددی متناسب با بازه جوابها اسـت ، اعمـالمیشود.
گام ٩. مجموعه پاسخهای جد یـد بـه دسـت آمـده ارز یـابی میشود.
گــام ١٠. جمعیــت قــدیمی و جمعیــت ناشــی از اعمــال مهاجرتها و جهشها ترکیب میشوند.
گام ١١. در صورت برآورده نشدن شرایط خاتمه، به مرحلـه
بازگشت میشود.

-٣- الگوریتم ژنتیک
الگوریتم ژنتیک برای اولین بار توسط هالند [١٧] ارائه شـد. در این الگوریتم پس از ایجاد جمعیت اولیه، عملگـر جهـش بـرای توسعه جمعیت و یافتن جوابهای پراکنده صـورت مـیگیـ رد؛ سپس، در جهت یافتن جـواب هـای بهتـر و به ینـه تـر از فضـای جستجو، با استفاده از عملگر تقاطع، جوابهـا بـا هـم ترک یـب میشوند. درنهایت، براسـاس م یـ زان بـرازش ٢٠، انتخـاب ٢1 بـین جوابهای موجود در جمعیت بـرا ی راه یـابی بـه نسـل بعـدی انجام میشود. به عبارت دیگر، میتوان ساختار کلـی و عمـوم ی یک الگویتم تکاملی را بهصورت زیر نشان داد:
جمعیت اولیه، بهصورت تصـادف ی از نقـاط فضـای جسـتجو تولید میشوند؛
برازندگی هر عضو جمعیت محاسبه میشود؛
فرزندانی از اعضای جمعیت به وجود میآیند؛
برازندگی فرزندان محاسبه میشوند؛
براساس میزان برازش، جمعیت نسل بعدی انتخاب میشود؛
در صورت برآورده نشدن شرط خاتمه، مراحل ٣ تا 6 تکرار میشوند.
در این فرآیند، میزان برازش یـ ک عـدد حق ی قـی اسـت کـهبراساس تابع هدف برای هر عضو جمعیت محاسبه مـ یشـود ومعیاری برای خوب یا بد بودن آن عضو نسبت بـه حـل مسـأله موردنظر است.
الگوریتمهای ژنتیک به عنوان یک روش جهت انجام یک جستجوی هدایت شده برای مدلهای خوب در فضای حـل
مسأله عمل میکند. این الگوریتمهـا، الگـوریتم هـای ژنت یـک نامیده میشوند چـون بـهطـور بـی قاعـدهای الگـوی تکامـلزیستی، که در آن اعضای یک نسل بر سر انتقال خصوصیات خود به نسل بعد رقابت میکنند تا نهایتًاً بهترین مـدل یافـتشود، را دنبال میکنند. اطلاعاتی که باید انتقال داده شـود درقالب کروموزمها که شامل پارامترهـایی بـرای سـاختن مـدلاست قرار میگیرد.
مراحل مربوط به الگوریتم ارائـه شـده در شـکل (٨) نشـانداده شده است. در ای ن مراحل t برابر با تعداد دورههایی است که در مدل اصلی درنظر گرفته شده است. برای شـروع کـار t وM مساوی یک درنظر گرفته شده است. عدد مکس٢٢ برابـربا تعداد تکرارهای موردنظر برای بهدست آوردن جواب بهی نـه مسأله است که از قبل توسط محقـق مشـخص شـده و قابـلتغییر است. در ابتدا به تعـداد دوره هـای معلـوم شـده سـلولایجاد میشود و پس از ایجاد سلولها، ماشینآلات به سلولها و سپس قطعات به ماشینآلات تخصـ یص مـ ییابنـد. پـس ازبهدست آوردن هزینه کل، هزینه تمامی تکرارها با هم مقایسـهشده و در آخر کمترین هزینه بهعنـوان هزی نـه بهینـه انتخـابمیشود. باید توجه شود که این هزینه لزومًاً بهینه نیست چـراکه امکان دارد با تعـداد تکرارهـای بی شـتری بتـوان بـه بهی نـه بهتری رسید.
در این تحقیق فرض شده است که تمام کـف کارگـاه بـهقسمتهای مشخصی تقسیمبندی شده است و از قبل جایگاه هر سلول مشخص است. قابل ذکر است که در هر دوره ایـ ن جایگاهها ثابت است و در هیچ دورهای تغییر نمیکند. شـکل
(٩) شمای شماتیکی از کارگاه را نشان میدهد.
در ای ن مث ال ف رض ش ده اس ت ک ه ح داکثر تع داد سلولهایی که در هر دوره میتواند ایجاد شـود برابـر بـا ١٠ است و بنابر فر ض مسأله این امکان وجود دارد کـه در یـ ک دوره تنها یک سلول ایجاد شود و بقیه قسـمت هـای کارگـاه خالی بماند.

۵- تحلیل نتایج
در این تحقیق ابتدا مدل برای مثالهایی توسط الگوریتم هـای بهینهسازی برمبنای جغرافیای زی سـتی و همچنـین الگـوریتم ژنتیک با دادههایی با مقادیر کوچک و بزرگ حل شده اسـتو دادههای بهدست آمده در جدول (١) نشان داده شده است. از این جدول میتـوان بـرای مقایسـه عملکـرد دو الگـوریتم استفاده کرد. اعداد موجود در جدول براسـاس ۵ بـار اجـرایهر مثال بهدست آمده است و زمان محاسباتی نیز میانگین ۵ بـاراجـرا اسـت. جـدول (١) بـا جمعیـت اولیـه ۵٠ و ٣٠٠ تکـرار بهدست آمده است. با استفاده از نتایج ارائه شده در جـدول (١) میتوان نتیجه گرفت که از نظر زمانی الگوریتم ژنتیک، برای این مسأله، الگوریتم کاراتری است. همچنین در میـانگین عملکـرد نیز الگوریتم ژنتیک در همه مسـائل بـهغیـر از مسـأله شـماره ۴ عملکرد بهتری از خود نشان داده است. حتـی در همـین مسـألهشماره ۴ بهترین جوابی که الگوریتم ژنتیک بهدست آورده بهتـراز الگـوریتم بهینـهسـازی بـرمبنـای جغرافیـای زیسـتی اسـت. درمجموع میتوان گفت برای این مسأله خاص الگوریتم ژنتیک در مقایسه الگوریتم بهینهسازی برمبنـای جغرافیـای زیسـتی، هم از نظر زمانی و هم از نظـر کیفیـت جـوابهـا ، عملکـرد

هزینه

محاسبه

هزینه

محاسبه

هزینه

محاسبه

هزینه

محاسبه
کل

هزینه

محاسبه

دور

در

سلول

تشکیل

ه


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