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 مساوي يک درنظر گرفته شده است. عدد مکس٢٢ برابـربا تعداد تکرارهاي موردنظر براي بهدست آوردن جواب بهي نـة مسأله است که از قبل توسط محقـق مشـخص شـده و قابـلتغيير است. در ابتدا به تعـداد دوره هـاي معلـوم شـده سـلولايجاد ميشود و پس از ايجاد سلولها، ماشينآلات به سلولها و سپس قطعات به ماشينآلات تخصـ يص مـ ييابنـد. پـس ازبهدست آوردن هزينة کل، هزينة تمامي تکرارها با هم مقايسـهشده و در آخر کمترين هزينه بهعنـوان هزي نـة بهينـه انتخـابميشود. بايد توجه شود که اين هزينه لزومًاً بهينه نيست چـراکه امکان دارد با تعـداد تکرارهـاي بي شـتري بتـوان بـه بهي نـة بهتري رسيد.
در اين تحقيق فرض شده است که تمام کـف کارگـاه بـهقسمتهاي مشخصي تقسيمبندي شده است و از قبل جايگاه هر سلول مشخص است. قابل ذکر است که در هر دوره ايـ ن جايگاهها ثابت است و در هيچ دورهاي تغيير نميکند. شـکل
(٩) شماي شماتيکي از کارگاه را نشان ميدهد.
در اي ن مث ال ف رض ش ده اس ت ک ه ح داکثر تع داد سلولهايي که در هر دوره ميتواند ايجاد شـود برابـر بـا ١٠ است و بنابر فر ض مسأله اين امکان وجود دارد کـه در يـ ک دوره تنها يک سلول ايجاد شود و بقيه قسـمت هـاي کارگـاه خالي بماند.

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

هزينة

محاسبة

هزينة

محاسبة

هزينة

محاسبة

هزينة

محاسبة
كل

هزينة

محاسبة

دور

در

سلول

تشكيل

ة


پاسخ دهید