بخشی از مقاله
ارائه یک مدل ریاضی براي ماشینآلات و زمانبندي در یک سیستم تولید سلولی (CMS) به کمک الگوریتم متاهیورستیک
خلاصه
سه مسئله مهم در ﻃﺮاﺣﯽ یک سیستم تولید سلولی(CMS) 1 ، پیکر بندي سلولی(CF) 2 ، چیدمان گروهی(GL) 3 و زمانبندي گروهی(GS) 4 است که براي پیاده سازي موفق تولید سلولی میبایست ایـن سـه مسـئله مـرتبط را بـا یکـدیگر و همزمان ﺑﺮاي رسیدن به یک حل بهینه در نظر گرفت . از این رو یک مدل ریاضی عدد صحیح غیر خطی مخـتلط(MINLP) 5 براي یکپارچه سازي این سه مسئله در یک سیستم تولید سلولی ارائه میشود. از ویژگیهاي منحصر بفرد بکار رفته در این مدل ، یکی کردن چندین شاخص مهم طراحی شامل ترتیب عملیات، زمان عملیات ، زمان جابهجایی ، چیدمان درون سـلولی بـرون سلولی و زمانبندي گروهی میباشد . تابع هدف این مدل از جنس هزینه و از سه قسمت شامل کمینه کردن زمان اتمـام کـل ، جریمه دیرکرد براي هر قطعه و جابهجاییهاي درون و برون سلولی تشکیل یافته است.همچنین بـه دلیـل NP-hard مسـئله ، الگوریتم ژنتیک(GA) 6 کارایی براي حل مدل ارائه شده پیشنهاد میگردد . سپس به منظـور بررسـی ﺻـﺤﺖ عملکـرد مـدل ، مثالی عددي توسط مدل خطی کد شده در نرم افزار LINGO SYSTEM حل شده و نتایج محاسباتی ارائه گردیده است.
واژه هاي کلیدي : سیستم تولید سلولی، پیکر بندي سلول، چیدمان گروهی ، زمانبندي گروهی ، الگوریتم ژنتیک
1
مقدمه
امروزه در رقابتهاي تولیدي مدرن، هر شرکتی نیازمند رسیدن به توانایی نشـان دادن عکـسالعمـل سـریع در مقابـل تغییرات ناگهانی تقاضاي بازار براي محصولاتش میباشد. از این رو افزایش انعطافپذیري و راندمان ، جزوي از اهداف اصـلی هـر شرکت تولیدي گردیده است. یکی از روشهاي اصلی و مهم براي رسیدن به این هدف، تولید سلولی(CM ) یکی از روشهـاي مهم تکنولوژي گروهی(GT) میباشد. که در سیستم هاي تولیدي مدرنی از جمله سیستم هاي تولید انعطاف پذیر(FMS) و سیستم تولید بهنگام
2
ومرلو و واخاریا [17] اجراي هشت تولید را مقایسه کردند و نتیجه گرفتند با در نظـر گـرفتن کمتـرین زمـان جریـان و تـأخیر، زمانبندي دسته اي مقدم تر است . وو و همکاران [18] یک رویکرد جدید را پیشنهاد کرد تا پیکربندي سلول و چیدمان گروهی و زمانبندي گروهی را به طور همزمان مشخص کند و یک مدل ریاضی مجتمع با این تصمیمات را توسعه داد. الگـوریتم ژنتیـک سلسله مراتبی پیاده سازي شده است تا مسائل طراحی سلول مجتمع را حل نماید . توکلی مقـدم و همکـاران [16] یـک مـدل جدید براي زمانبندي گروهی در سلولهاي تولیدي ارائه کردند که با زمانبندي درون سلولی توالی قطعات در سلولها تعیـین و بـا زمانبندي بین سلولی توالی سلولها بدست می آید. سپس براي حل مدل از یک روش فرا ابتکـاري مبتنـی بـر Scatter Search استفاده کردند.
. تشریح مسأله
ایـــن تحقیـــق یـــک مـــدل یکپارچـــه CMS ، مرکـــب از مســـأله پیکربنـــدي ســـلولی ، چیـــدمان درون ســـلولی و برون سلولی و زمانبندي تولید است . مسئله پیکربندي سلولی به تخصیص گروهی از ماشین ها به سـلول هـا ، دسـته بنـدي قطعات به خانواده قطعات و تخصیص خانواده قطعات به سلول ها براي شکل دهی سلول هاي مستقل می پردازد. همزمان با این گروهبندي ، ماشینها با تعریف متغیرهاي پیوسته ، درون سلولها در جایگاههاي مربوطه استقرار می یابند. همچنین زمانبنـدي تولید نیز همزمان با مراحل فوق انجام می گردد . در مسئلهي پیکربندي سلولها در طراحی یک سیستم سلولی m ماشین را در c سلول طوري دستهبندي میشود که p قطعه براي تولید در حد امکان در یک سلول ساخته شوند و اگر قـرار باشـد جابجـایی بینسلولی داشته باشیم این جابجاییها کمینه شـوند. در مسـئله چیـدمان درون سـلولی ماشـینهـا در سـلولها طـوري چیـده میشوند که قطعات براي تولید کمترین جابجایی درون سلولی را داشته باشند، چـرا کـه هـم هزینـه جابجـایی درونسـلولی و هم،زمان با آن در کل کم شود. در مسئله چیدمان بینسلولی سلولها را در محیط تولید طوري چیده میشوند که قطعـات بـراي تولید کمترین جابجایی بین سلولی را داشته باشند ، چرا که هم هزینه جابجایی بینسلولی و هم ، زمـان آن در کـل کـم شـود. در مسئله زمانبندي در سیستم تولید سلولی ، فرض میشود m ماشین در c سلول مستقرند که باید p قطعـه را تولیـد نماینـد. هنگامی که قطعهاي در حال پردازش روي یک ماشین است قطعهي دیگري نمیتواند روي آن ماشـین پـردازش شـود، یـا بایـد قطعهي در حال پردازش از ماشین برداشته شود و یا باید قطعهي جدید منتظر بماند تا کار پردازش قطعه قبلـی تمـام شـود . در مسئله مورد بررسی قطع جریان پردازش نیز مجاز نمیباشد. از این رو مسئله تقدم در پردازش بر روي قطعات پیش میآید کـه تصمیم براي اینکه چه قطعهاي زودتر از دیگري پردازش شود اهمیت پیدا میکند که همان زمانبندي تولید است. در زمانبندي ، ترتیب انجام کار پردازش قطعات روي ماشینها تعیین میشود ، همچنین در صورت وجـود داشـتن ماشـین هـاي مـوازي بـراي پردازش عملیات ها ، انتخاب ماشین ها براي پردازش صورت میگیرد به طوري که اهداف مورد نظر برآورده گردد . اهداف مـورد نظر در زمانبندي این مسئله کمینه شدن مدت زمان کل ساخت و همچنین کمینه شدن دیرکرد تحویـل تـک تـک قطعـات بـا توجه به موعد تحویل آنها می باشد . اما چگونگی پیکربندي سلولها و چیدمان درونسلولی و بینسلولی و انتخاب هاي پـردازش از میان ماشین هاي موازي در مدت زمان کل ساخت و نیز ساخت تک تک قطعات تأثیر میگذارد. بنابراین هر چهار مرحله فوق بــا توجــه بــه همــه ي اهــداف مــذکور بطــور همزمــان انجــام مــی گــردد پــس مســئله بــدین صــورت تعریــف مــیشــود: پیکربندي ، چیدمان ماشینها (درون سلولی و بینسلولی) و سلولها در یک سیستم تولید سلولی به صورت پیوسته و زمانبندي گروهی به منظور کمینه کردن مجموع هزینههـاي جابجـایی بـینسـلولی و درونسـلولی ، مـدت زمـان کـل سـاخت و جریمـه دیرکردها.
3
. ارائه مدل ریاضی
در این قسمت به مدل ریاضی غیرخطی ارائه شده بیان خواهیم کرد.و سپس آن را خطی سازي میکنیم :
. تعریف مجموعهها و اندیسها:
اندیس توالی عملیات قطعه .
اندیس تعداد قطعات .
k',k" اندیس توالی پردازشهاي ماشین .
j,j' اندیس تعداد ماشینها .
c,c" اندیس تعداد سلولها .
.3.2 تعریف پارامترهاي مدل:
تعداد عملیات قطعه نوع .
P تعداد قطعات.
حداکثر تعداد پردازشهاي ماشین نوع .
M تعداد ماشینها.
هزینههاي وابسته به واحد زمان در سیستم تولیدي.
جریمه براي هرواحدزمان تأخیردرتحویل قطعه .
موعدتحویل قطعه نوع .
زمان انجام عملیات ام قطعه توسط ماشین .
هزینه جابهجایی درون سلولی در واحد مسافت براي قطعه .
هزینه جابهجایی بین سلولی در واحد مسافت براي قطعه .
حداقل تعداد ماشینهایی که درون هر سلول قرار میگیرند.
حداکثر تعداد ماشینهایی که میتوانند درون هر سلول قرار گیرند.
زمان جابجایی در واحد مسافت براي قطعه .
طول ماشین .
عرض ماشین .
فاصله بین ماشین و ام.
4
مختصه طولی سمت چپ سلول .
مختصه طولی سمت راست سلول .
مختصه عرضی بالاي سلول .
مختصه عرضی پائین سلول .
یک عدد بزرگ مثبت.
.3.3 تعریف متغیرهاي تصمیم:
1= اگر k امین عملیات قطعه i در k' ام عملیات پردازش ماشین jانجام شود،0 در غیر اینصورت
1= اگر ماشین j به جایگاه c اختصاص یابد،0 در غیر اینصورت.
زمان اتمام k'ام عملیات پردازش ماشین jام.
زمان اتمام عملیات قطعه iام.
زمان اتمام کل.
مختصه طولی مرکز ثقل ماشین .j
مختصه عرضی مرکز ثقل ماشین.j
مختصه طولی سمت چپ ماشین .j
مختصه طولی سمت راست ماشین .j
مختصه عرضی بالاي ماشین.j
مختصه عرضی پائین ماشین.j
1= اگر ماشینکاملاًj سمت راست ماشینj 'باشد ،0 در غیر اینصورت.
1= اگر ماشینکاملاًj بالاي ماشینj 'باشد ،0 در غیر اینصورت.
5
.5 تابع هدف
تابع هدف شامل هزینه نگهداري سیستم و هزینه هاي وابسته به زمـان، جریمـه دیرکردهـا و دو نـوع هزینـه جابجـایی قطعات می باشد. معادله((1 مربوط به هزینه نگهداري سیستم و هزینههاي وابسته به زمان است که از ضرب زمان اتمام کل کار در ضــریب هزینــه نگهــداري سیســتم در واحــد زمــان بدســت مــی آیــد. ایــن هزینــه شــامل هزینــهي اســتهلاك و نگهــداري ماشینها میگردد. این معادله زمان اتمام کل کار را کم میکند. معادله (2) مجموع جریمه هاي دیرکـرد قطعـات اسـت . معادلـه (3) مربوط به جابجایی درون سلولی و بین سلولی قطعات میباشد. هزینه درون سلولی هنگامی ایجاد میشـود کـه دو عملیـات متوالی یک قطعه درون یک سلول انجام گیرد و هزینه برون سلولی هنگامی ایجاد میشود کـه دو عملیـات متـوالی یـک قطعـه درون دو سلول انجام گیرد . حاصل ضرب نشان میدهد که آیا دو عملیات متوالی قطعهيi که روي دو ماشـین انجــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــام
میشود ( با توجه به حاصلضرب در سلول c واقع هستند یا نه ( در یک سلول هستند یـا نه ) . بدین ترتیب که اگر این حاصلضرب برابر صفر شود بدین معنی است کـه عملیـات k ام قطعـهي i روي ماشـینی کـه در سلول c واقع است انجام میشود(به عنوان یکی از توالیهایش) و عملیات k-1 ام آن روي ماشینی که درسلول دیگر واقـع اسـت انجــام مــیشــود. از آنجــایی کــه هزینــه جابجــایی بــین ســلولی بالاســت لــذا ماشــینهــا طــوري در ســلولهــا قــرار میگیرند که حتیالامکان جابجایی بین سلولی وجود نداشته باشد و اگر قرار باشد قطعات بین دو سلول جابجا شوند، مدل سعی میکند ماشینهایی را که جابجایی قطعه دارند در سلولهاي با فاصلهي کمتري نسبت به هم قرار دهد. ممکن اسـت یـک قطعـه نسبت به قطعهاي دیگر داراي وزن زیادتر یا اندازه بزرگتر یا شکنندگی بیشتر باشد که جابجایی آن را مشکل میسـازد. بنـابراین هزینه یا زمان بیشتري براي جابجایی نیاز خواهد داشت. یکی از ویژگیهاي این مدل این است کـه بـراي هـر قطعـه یـک زمـان جابجایی و یک هزینه جابجایی خاص آن قطعه بر حسب مسافت در نظر گرفته است، بدین ترتیب با توجه به اینکه میزان هزینه در این قسمت، با فاصله بین دو ماشین رابطه مستقیم دارد، لذا باعث میشود که مدل سـعی کنـد ماشـینهـایی را کـه میـزان جابجایی قطعات بین آنها زیاد میباشد را نزدیکتر به هم قرار دهد.
.6 محدودیتها
محدودیت تضمین میکند که هر ماشین تنها در یک سلول قرار گیرد . محدودیتهاي کران بالا و پایین یک سلول را در نظر میگیرد. محدودیت تضمین میکند هر عملیات قطعه تنها به یک توالی عملیات یک ماشین، تخصیص یابد. محدودیت منطق
بین متغیر و ماتریس زمان را نشان میدهد.
در حقیقت وقتی عملیات kام قطعه i وقتی در توالی عملیات k' ماشین j انجام می شود که مقدار زمان متناظرآن در ماتریس T
بزرگتر از صفر تعریف شده باشد. محدودیت زمان اتمام اولین عملیات هر ماشین را حساب می کند. مثلاً براي ماشین j اگر
اولین قطعه اي که روي آن پردازش می شود i باشد و این قطعه kامین عملیات خود را روي این ماشین انجام بدهد( )
آنگاه زمان اتمام اولین عملیات ماشین j روي قطعه i که همان است برابر خواهد بود با زمان شروع این عملیات بعلاوه
مدت زمان پردازش عملیات. زمان شروع عملیات برابر زمان اتمام عملیات قبلی قطعه (هرکجا که بوده) بعلاوه زمان جابجایی قطعه از جایگاه قبلی به جایگاه فعلی است. محدودیت زمانمامات اولین عملیات هر ماشین را حساب می کند. مثلاً براي ماشین j اگر ام قطعه اي که روي آن پردازش می شود i باشد و این قطعه kامین عملیات خود را روي این ماشین انجام
8
بدهد( ) آنگاه زمان اتمام k'ام عملیات ماشین j روي قطعه i همان است که برابر با زمان شروع این عملیات بعلاوه مدت زمان پردازش عملیات خواهد بود. زمان شروع عملیات، یا برابر با زمان اتمام عملیات قبلی قطعه )iهرکجا که بوده)
بعلاوه زمان جابجایی قطعه از جایگاه قبلی به جایگاه فعلی است یا برابر با زمان اتمام عملیات قبلی ماشینj میباشد، که به صورت max آورده شده است. مدت زمان پردازش نیز که ( ) است. محدودیت زمان اتمام کار هر قطعه را تعیین میکند. محدودیت زمان اتمام کل را حساب می نماید. محدودیتهاي مرکز ثقل ماشینها را محاسبه می کند. محدودیت فواصل مراکز ثقل ماشین ها را به روش مستطیلی محاسبه می کند. محدودیتهاي مختصات طولی و عرضی رئوس هر ماشین را با توجه به اندازه طول و عرض ماشین در نظر میگیرد. محدودیتهاي تضمین میکند هر ماشین کاملاً در سلول متناظر خود قرارگیرد. محدودیت تضمین میکند ماشین ها با یکدیگر تداخل پیدا نکنند. محدودیتهاي نوع متغیرها را بیان می کند. سپس مدل را با توجه به تکنیک هاي خطی سازي ، خطی می کنیم و با استفاده از نرم افزار لینگو نسبت به حل مسئله اقدام می کنیم .
. تجزیه و تحلیل داده ها
در این بخش مثالی عددي که با نرم افزار لینگو حل شده است به تفصیل بیان میشـود و پارامترهـا ، اهـداف مختلـف و نتایج محاسبات مورد بررسی میگیرند تا صحت مدل، مورد بررسی قرار گیرند. سپس الگوریتم ژنتیک پیشـنهادي بـراي مـدل، ارائه می گردد.
.7.1 مثال عددي
با توجه به مدل حل شده در نرمافزار لینگو، جداول 1-7 تا 4-7 مقادیر پارامترهاي مدل را نشان مـیدهـد و شـکلهـاي 1-7و 2 - 7 نحوه چیدمان ماشینهارا نشان میدهد. زمانبندي و ترتیب عملیـات قطعـات روي هـر یـک از ماشـینهـا نیـز در نمودارها1-7 و 2-7 با کلیه جزئیات مشخص شده است.
و ماتریس را خواهیم داشت.
.7.2 نتایج محاسباتی در نرم افزار لینگو
حال با تغییري بر روي مقدار پارامترTT ، تأثیر آن را هم بر روي زمان بندي و هم چیدمان بررسی میکنیم:
همانطور که مشاهده میکنید ، ایجاد حتی تغییراتی جزئی در پارامترهاي مدل، نـه تنهـا بـر روي زمـان بنـدي تـأثیر خـود را میگذارد، بلکه همزمان بر روي نحوه چیدمان ماشینها نیز تأثیر خود را گذاشته است. (نمودار7-7 و شکل ( 8- 7
. الگوریتم ژنتیک پیشنهادي
. ساختار شماتیک الگوریتم ژنتیک
شکل - ساختار یک الگوریتم ژنتیک.
11
یکی از اجزاي مهم در الگوریتم ژنتیک ، ساختار کروموزوم میباشد . از آنجا که جواب مسئله تحقیق میبایست کلیه متغیرهاي تصمیم مدل را پوشش دهد ساختار کروموزوم به صورت زیر میباشد.همانطور که در شکل3-8 مشخص میباشد
ساختار کروموزوم به صورت چند رشتهاي به تعداد ماشینهاي موجود میباشد. طول هر رشته کروموزوم، داراي دو بخش مجزا شامل اطلاعات Layout دراي دو ژن و اطلاعات Scheduling داراي ژن میباشد . در قسمت Layoutنمایش مقادیر یه صورت اعداد حقیقی که نشان دهنده مختصات مرکز ثقل ماشین مورد نظر است ، میباشد. نمایش بخش دوم Scheduling به صورت جایگشتی مبتنی بر ترتیب عملیات ماشین مربوط به آن رشته کروموزوم میباشد. مقادیر هر ژن در این بخش شامل اطلاعات شماره قطعه iو k این عملیات قطعه iم يباشد.که به صورت یک عدد اعشاري k.i نمایش داده میشود. قسمت صحیح این مقادیر بیانگر شماره عملیات قطعهi و قسمت اعشاري این مقادیر معرف شماره قطعه میباشد.
.8.3 ایجاد جمعیت اولیه
اولین مرحله بعد از تعیین تکنیکی که براي تبدیل هر جواب به یک کروموزوم بکار میرود ایجاد یـک جمعیـت اولیـه از کروموزومهاســت. در ایــن الگــوریتم جــواب اولیــه بــراي بخــش اول کرومــوزوم بــه صــورت تصــادفی در بــازه هــاي [LY UY] , [LX UX] بــه ترتیــب بــراي اولــین و دومــین ژن ایجــاد مــیگــردد و بــراي بخــش دوم ، از مجموعــه قطعه- عملیات به صورت جایگشتی مبتنی بر ترتیب ایجاد میگردد.
