بخشی از مقاله

*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***

مقایسه عملکرد الگوریتم تپه نوردی و شبیه سازی تبرید در طراحی سیستم تولید سلولی

 

چکیده

در جهـــان رقـــابتی امـــروز تعیـــین تـــوالی و زمانبنـــدی بهینـــه عملیـــات تولیـــد بـــرای محصـــولات تولیـــدی یکـــی از ضـــرورتهای موفقیـــت شـــرکتها در بـــازار مـــی باشـــد.زمان بنـــدی ایـــن عملیـــات هـــا منجـــر بـــه افـــزایش کـــارایی و بهـــره بــرداری از ظرفیــت ،کــاهش زمــان ســاخت و در نهایــت کـــاهش هزینــه هــا و افــزایش ســودآوری یــک شــرکت تولیـــدی مــی شــود. یکــی از راههــای رســیدن بــه ایــن امــر اســتفاده از سیســتم تولیــد ســلولی اســت کــه بــا ســازماندهی تجهیــزات تولیـــدی در گـــروه هـــا و ســـلول هـــای مســـتقل جهـــت تکمیـــل و ســـاخت خـــانواده هـــایی از قطعـــات بـــا مشخصـــه هـــای تولیــدی مشــابه اســتفاده مــی شــود.در مجمــوع سیســتم تولیــد ســلولی یــک فلســفه تولیــدی اســت کــه در آن قطعــات بـــه منظـــور بهـــره بـــرداری از تشـــابهات آنهـــا در طراحـــی و ساخت،شناســـایی و طبقـــه بنـــدی مـــی شـــوند.به طـــور کلـــی سیســتم تولیــد ســلولی جـــزء روش هــای نــوین تولیــد میباشـــد کــه در ســال هــای اخیـــر بخــش صــنعت از مزایـــای آن بهــره منــد شــده اســت. در ایــن تحقیــق ســعی شــده تــا بــا اســتفاده از الگــوریتم هــا ی تپــه نــوردی((Hill Climbing و شـــبیه ســـازی تبریـــد((Simulated Annealing یـــک سیســـتم تولیـــد ســـلولی بـــا هـــدف مینـــیمم کـــردن جریـــان مــواد بـــین ســلولها طراحـــی شـــود. همچنــین کـــارایی ایــن الگوریتمهـــا از نظـــر زمــان حـــل و میــزان بهینگـــی جـــواب در اندازه های مختلف مورد بررسی قرار گرفته شده است.

واژه های کلیدی :تولید سلولی ، الگوریتم شبیه سازی تبرید ، الگوریتم تپه نوردی ، توالی عملیات، برنامه ریزی تولید



.1 مقدمه :

در جهــان رقــابتی امــروز تعیــین تــوالی و زمانبنــدی بهینــه عملیــات تولیــد بــرای محصــولات تولیــدی یکــی از ضــرورتهای موفقیــت شرکتها در بازار می باشد.زمان بندی ایـن عملیـات هـا منجـر بـه افـزایش کـارایی و بهـره بـرداری از ظرفیـت ،کـاهش زمـان سـاخت و در نهایت کاهش هزینه هـا و افـزایش سـودآوری یـک شـرکت تولیـدی مـی شـود. یکـی از راههـای رسـیدن بـه ایـن امـر اسـتفاده از سیستم تولید سـلولی اسـت کـه بـا سـازماندهی تجهیـزات تولیـدی در گـروه هـا و سـلول هـای مسـتقل جهـت تکمیـل و سـاخت خــانواده هــایی از قطعــات بــا مشخصــه هــای تولیــدی مشــابه اســتفاده مــی شــود.در مجمــوع سیســتم تولیــد ســلولی یــک فلســفه تولیــدی اســت کــه در آن قطعــات بــه منظــور بهــره بــرداری از تشــابهات آنهــا در طراحــی و ساخت،شناســایی و طبقــه بنــدی مــی شوند.به طور کلی سیسـتم تولیـد سـلولی جـزء روش هـای نـوین تولیـد میباشـد کـه در سـال هـای اخیـر بخـش صـنعت از مزایـای آن بهره مند شده است[1] .همچنـین بـا بـه کـار بسـتن ایـن سیسـتم تولیـدی،انعطاف پـذیری شـرکت در پاسـخ گـویی بـه نیازهـای متنوع مشتریان افزایش یافته و از طرفی می تـوان بـا بـه کـار گیـری مفـاهیم جدیـد مـدیریت تولیـد ماننـد تولیـد بـه هنگـام( Just (In Time و تولیــد نــاب (Lean Manufacturing) هزینــه ســاخت را بــیش از پــیش کــاهش داد و کنتــرل بهتــری بــر عملیات تولید داشت.

مســاله طراحــی سیســتم تولیــد ســلولی یــک مســاله((NP-Hard مــی باشــد،بنابراین بــه کــارگیری روش هــایی کــه جــواب بهینــه تولید می کنند بسیار دشوار و زمانبر می باشد و اغلـب بـرای مسـائل بـا انـدازه کوچـک میسـر اسـت از اینـرو بهتـر اسـت بـرای حـل
آن از روشــهای متاهیوریســتیک اســتفاده شــود بطــور کلــی بــرای طراحــی سیســتم تولیــد ســلولی بــیش از 300 روش مختلــف و
متنوع ارائـه شـده کـه در مقـالات [ ]،[ ]،[ ]،] [ توضـیحات کـاملی داده شـده اسـت . ایـن روشـها در اکثـر مواقـع قـادر بـه پیـدا
کردن جواب بهینه کلی(( Global نیسـتند ولـی بـا توجـه بـه اینکـه در زمـان کوتـاه تـری نسـبت بـه مـدل هـای دقیـق بـه جـواب می رسـند، معمـولا در مسـائل NP-Hard ایـن روشـها ارجحیـت دارند.هـدف ایـن مقالـه ارایـه الگـوریتمی کـارا بـرای حـل مسـاله طراحــی ســلول در سیســتم تولیــد ســلولی براســاس الگــوریتم هــای تپــه نــوردی((Hill Climbing و شــبیه ســازی تبریــد (Simulated Annealing) بـا هـدف کمینـه کـردن جریـان مـواد بـین سـلولها طراحـی و کـارایی ایـن الگوریتمهـا از نظـر زمـان حل و میزان بهینگـی جـواب مـورد بررسـی قـرار گرفتـه شـده اسـت. در بخشـهای 3 ، 4 و5 ایـن مقالـه توضـیحاتی کلـی از مفـاهیم ذکر شده در بخش 6 نحوه نمایش جـواب در ایـن تحقیـق و نحـوه محاسـبه تـابع فیتـنس در آنهـا مـورد بحـث قـرار مـی گیـرد. در بخــش 7 نتــایج کــدهای نوشــته شــده در نــرم افــزار متلــب و محاســبات انجــام شــده نمــایش داده مــی شــود و عملکــرد الگوریتمهــا مورد مقایسه قرار می گیرد و در نهایت در بخش 8 از مطالب ارایه شده نتیجه گیری می شود.
.2 مروری بر ادبیات :

متد ها و روش هـای مختلفـی در مقـالات مختلـف در زمینـه طراحـی سیسـتم تولیـد سـلولی ارائـه شـده ماننـد دسـته بنـدی و کـد گــذاری سیســتم ،آنــالیز آرایــه ای و برنامــه ریــزی خطــی[6]،[3]،[7 ] نظریــه گــراف[8] شــبکه عصــبی[9]،[10] الگــوریتم ژنتیــک[11] ،شــبیه ســازی تبریــد [12]،[13] جســت و جــوی ممنوعــه[14] ،نظریــه فــازی [15]،شــبیه ســازی[16] و روش هــای فراوان دیگری که در ادامه به توضیح مختصر بعضی از آنها می پردازیم.

ومرلــوو و هییــر[17] طراحــی سیســتمهای تولیــد ســلولی را بــه 4 بخــش تقســیم میکننــد: -1 تشــکیل ســلول(تعیــین خــانواده قطعـات و گـروه هـای ماشـین آلات) -2 تعیـین چیـدمان درون سـلولی(موقعیت ماشـین هــای درون سـلولی نسـبت بـه یکــدیگر در

هـر سـلول) و چیـدمان سـلولی (تعیـین موقعیـت سـلولها نسـبت بـه یکـدیگر در محـیط کارگـاه- 3 زمانبنـدی گروهـی (زمانبنـدی قطعات و خـانواده قطعـات بـرای تولیـد) -4 تخصـیص منـابع و ابزارآلات،مـواد اولیـه و نیـروی انسـانی بـه سـلولها و ماشـینها. هـوو و مودی[18] مـدل برنامـه ریـزی خطـی و الگـوریتم جسـتجویی بـرای طراحـی چیـدمان سـلول و مسـیر جریـان مربـوط بـه آن ارایـه کردنــد . ســلوم[19] رویکــردی دو فــازی بــرای طراحــی ارایــش ســلول براســاس CMS ارائــه کــرد کــه زمــان پیشــبرد قطعــات تولیــدی را کــاهش مــی داد .وانــگ و همکــاران [20] بــرای یــک مســئله تولیــد ســلولی مــدل چیــدمانی را ارائــه کردنــد کــه در آن تقاضــا در طــول چرخــه عمــر محصــول متغیــر فــرض شــده بــود و هــدف آن کمینــه کــردن هزینــه جابجــایی درون ســلولی و بــین ســلولی مــواد بــود .ســلیمانپور و همکــاران [21] یــک مســئله چیــدمان ســلولی را مطــرح کردنــد و آنــرا ماننــد مســائل تخصــیص کوادراتیک (QAP) فرموله کردنـد سـپس مسـئله فرمولـه شـده را بـا یـک الگـوریتم حـل کردنـد .کـیم و همکـاران [22] روشـی را مطرح کردند که همزمان جابجایی بـین سـلول هـا و حجـم کـاری را در در نظـر مـی گرفـت و هـدف آن کمینـه کـردن عـدم تـوازن بین آنهـا بـود کـه بـا برنامـه ریـزی صـفر و یـک فرمولـه شـده بـود . چـان و همکـاران [23] یـک روش سـه مرحلـه ای بـرای حـل مسائل تولید سلولی مطرح کردند که در گـام اول سـلول ماشـین هـا و خـانواده قطعـات بـا یـک مـدل ریاضـی تعریـف مـی شـوند در گام دوم یک رویکرد کلـی سـاختار سـلولی مسـئله را بـه گونـه ای بدسـت مـی آورد کـه ترتیـب عملیـاتی آن جابجـایی بـین سـلولی را کمینه کند و در گام آخر مسئله جانمـایی سـلول هـا بـه صـورت جانمـایی خطـی و بـه شـکل مسـائل (QAP) فرمولـه مـی شـود. توکلی مقدم و همکاران[24] مـدل ریاضـی را بـرای حـل مسـائل جایـابی امکانـات در سیسـتم تولیـد سـلولی بـا تقاضـای متغیـر کـه هزینــه جابجــایی درون ســلولی و بـین ســلولی را بطــور همزمــان کمینــه میکنــد ارایـه کردنــد. اهـی و همکــاران [25] یـک تصــمیم گیـری چنــد معیـاره را بکـار بردنــد و یـک روش دو مرحلــه ای را مطـرح کردنــد کــه آرایـش سـلولی ،چیـدمان بـین ســلولی و درون سلولی را به عنوان 3 ویژگی اصلی در طراحی سیستم تولید سلولی بدست می آورد.

.3 سیستم تولید سلولی:

پیشــرفته تــرین کــاربرد تکنولــوژی گروهــی در عرصــه تولید،تولیــد ســلولی اســت .امــروزه صــنایع تولیــدی زیــر فشــار شــدیدی از جانب بازار هـای رقـابتی جهـانی قـرار دارنـد.چرخـه عمـر کوتـاه تـر محصـول ،کوتـاه تـر شـدن سـیکل عرضـه محصـول بـه بـازار و خواســته هــای متعــدد و گونــاگون مشــتریان، تولیــد کننــدگان را وادار کــرده اســت تــا کــارایی و بهــره وری فعالیــت هــا و فراینــد تولیــدی خــود را بهبــود دهنــد در واقــع بایــد سیســتم هــای تولیــدی خــود را بهبــود دهنــد26]،. [3 در واقــع بایــد سیســتم هــای تولیدی خود را به نحوی تغییـر دهنـد کـه قـادر باشـند محصـولات خـود را بـا کمتـرین هزینـه ،بـالاترین کیفیـت و در سـریع تـرین زمان ممکن جهت تحویل به موقع بـه مشـتریان ،تولیـد نمایـد.هـم چنـین ایـن سیسـتم هـا بایـد قـادر باشـند تـا خـود را سـرعاًیبـا تغییرات در تقاضا و طراحی محصولات ،بدون نیاز به سرمایه گذاری مجدد زیاد،سازگار سازند. [27]

.4 الگوریتم تپه نوردی

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

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

بــرای پیــاده ســازی روش تپــه نــوردی نیــاز بــه دو تــابع Objective و Neighbor داریــم.کــد ایــن الگــوریتم در حالــت کلــی بــه صورت زیر است.

Procedure HillClimbing Generate a solution ( s’ ) Best = S’ Loop

S = Best S’ = Neighbors (S) Best = SelectBest (S’)

Until stop criterion satisfied End

شکل(:( 1 کد الگوریتم تپه نوردی

.5 الگوریتم شبیه سازی تبرید

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

در این رابطه ΔE تفـاوت بـین تـابع هـدف جـواب فعلـی و جـواب همسـایهاسـت و T یـک پـارامتر بـه نـام دمـا اسـت. در هـر دمـا، چندین تکرار اجرا میشود و سپس دما بـه آرامـی کـاهش داده مـیشـود. در گـامهـای اولیـه دمـا خیلـی بـالا قـرار داده مـیشـود تـا احتمال بیشتری برای پذیرش جوابهای بـدتر وجـود داشـته باشـد. بـا کـاهش تـدریجی دمـا، در گـامهـای پایـانی احتمـال کمتـری برای پذیرش جـوابهـای بـدتر وجـود خواهـد داشـت و بنـابراین الگـوریتم بـه سـمت یـک جـواب خـوب همگـرا مـیشـود.الگـوریتم SAیک الگوریتم غیرمقید می باشد که برای طراحی های سخت به کار می رود.

در هــر مرحلــه، الگــوریتم تبریــد شــبیهســازی شــده، چنــد حالــت را در همســایگی حالــت کنــونی s در نظــر مــیگیـرد، و بــه طــور احتمــالی تصــمیم مــیگیــرد کــه سیســتم را از حالــت s منتقــل کنــد یــا در همــین حالــت بــاقی بمانــد. ایــن احتمــالات در نهایــت سیستم را به حالت با انرژی کمتر میل میدهـد. همسـایههـای یـک حالـت (جـواب)، حالـتهـای جدیـدی از مسـئله هسـتند کـه بـا تغییر در حالت کنـونی و بـا توجـه بـه روشـی از پـیش تعیـین شـده ایجـاد مـیشـوند. بـرای مثـال در مسـئله فروشـندهی دورهگـرد، هر حالت به طـور کلـی یـک جایگشـت خـاص از شـهرهایی اسـت کـه بایـد ملاقـات شـوند. همسـایهی یـک جـواب، جایگشـتهـایی هستند کـه بـا انتخـاب یـک جفـت از شـهرهای هـم جـوار، از کـل مجموعـه جایگشـتهـا، و جابجـا کـردن آن دو شـهر ایجـاد مـی شــوند. عمــل تغییــر در جــواب فعلــی و رفــتن بــه جــوابهــای همســایه "حرکــت" (move) خوانــده مــیشــود و "حرکــت"هــای متفاوت، همسایههای گوناگون را بدست میدهد.

به طور کلی کد این الگوریتم به صورت زیر است:

.6 تنظیمات مسئله

.1.6 نحوه نمایش جواب

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

اول جایگشــتی از تمــامی ماشــین هــا نمــایش داده مــی شــود و در بخــش دوم تعــداد ماشــین آلات در هــر ســلول نشــان داده مــی شود. به عنوان مثال فرض کنید 12 ماشین و 5 سلول داریم.رشته زیر نحوه نمایش یک سلول را نشان می دهد:


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

Cell 1: Machine2 → Machine11 Cell 2: Machine10 → Machine8 → Machine4 Cell 3: Machine9 → Machine3

Cell 4: Machine6 → Machine5 →Machine1 → Machine12 → Machine7


شکل 3 :ساختار سلولی و چینش ماشین آلات در سلول ها طبق جواب بالا

.2.6 حرکت در همسایگی

به ایجاد یک جواب جدید با اسـتفاده از جـواب فعلـی حرکـت در همسـایگی مـی گوینـد. در ایـن تحقیـق روال کـار بـه صـورت زیـر است:

گام :1در قسمت اول جواب دو مکان به صورت تصادفی با مقادیر متفاوت انتخاب می شود. گام :2مکان اعداد انتخاب شده با یکدیگر تعویض می شود.

گام :3 برای بخش دوم به تعـداد سـلولها عـدد تصـادفی تولیـد مـی کنـیم بـه صـورتی کـه جمـع آنهـا برابـر بـا تعـداد ماشـین آلات شود.

در متن اصلی مقاله به هم ریختگی وجود ندارد. برای مطالعه بیشتر مقاله آن را خریداری کنید