نشریه تخصصی مهندسی صنایع، دوره 48، شماره 2، مهر ماه 1393، از صفحه 215 تا 228
الگوریتم بهینه سازی گروه ذرات برای تعیی اندازة انباشته و زمان بندی یکپارچه در محیط تولیدی جریان کارگاهی

رضا رمضانیان1* ، مح شفیعی نیک آبادی2 و سحر فلاحصنمی3
استادیار دانشکدة مهندسی صنایع دانشگاه صنعتی خواجه نصیرالدین وسی
استادیار دانشکدة اقتصاد و مدیریت دانشگاه سمنان
دانشجوی کارشناسی ارشد دانشکدة اقتصاد و مدیریت دانشگاه سمنان

)تاریخ دریافت 7/8/91 ـ تاریخ دریافت روایت اصلاح شده 28/11/92 ـ تاریخ تصویب 7/4/93( چکیده
هدا این پژوهش مطالعة سیستم های تولیدی وندمحصولی و ونددوره ای در محیو جریان کارگاهی است؛ ـوری کـه محـدودیت هـایتولید و توالی عملیات به صورت یکناروه لحا شود. مدب برنامه ریزی عدد صحیح مختلو برای مسسله پیشنهاد می شود. تابع هدا شـاملهزینه های تولید، موجودی، کمبود، و راه اندازی است. با توجه به پیچیدگی زیاد محاسباتی، الگوریتم بهینـه سـازی گـروه ارات بـرای حـلپیشنهاد می شود. جهت بررسی کارایی الگوریتم، دو روش بر پایة برنامه ریزی عدد صحیح، که به صورت تکرارشـونده بـا ایجـاد مـدب هـایکووک تر به حل مدب می پردازد، پیشنهاد و نتایج با هم مقایسه می شود. به علاوه، روش تاگووی برای تنظیم پارامترهای روش فراابتکـاریبه کار می رود. الگوریتم های حل موردنظر ترکیبی شدنی و نزدیک به بهینه از برنامه ریزی تولید و زمان بندی می یابند. نتایج، بر مجموعه ای از مسائل با اندازه های مختلف، کارایی روش فراابتکاری را نسبت به حل دقیق و روش های ابتکاری ثابت می کند. متوسو مقـدار هـدا بـرایروش های 1PSO، ابتکاری 1، و ابتکاری 2 به ترتیب 21/98، 20/104، و 29/108)103×( است.

واژه های کلیدی: الگوریتم بهینه سازی گروه ارات، تعیین اندازة انباشته و زمان بندی یکناروه، روش ابتکاری بر پایة برنامه ریزی عدد صحیح مختلو، سیستم تولیدی وندمرحله ای، مدب سازی ریاضی
مقدمه
برنامه ریزی تولید و زمان بندی به دو سطح تصمیم گیری مختلــف تعلــق دارد. برنامــه ریــزی تولیــد در ســطحمیان مدت و زمان بندی در سطح کوتـاه مـدت اسـت . بـاتوجه به ارتبا ات درونی سطوح مختلف زنجیرة تأمین ،تبادلات زیادی بین تصمیمات اتخااشده در گـر وه هـای مختلف زنجیرة تـ أمین وجـود دارد. بـرای دسـتیابی بـهج واب ه ای بهین ة ج امع بای د ب ین وظ ایف مختل ف برنامه ریزی وابستگی درونی در نظر گرفته شود.
یکی از روش های دستیابی به برنامـه ریـزی تولیـد وزمان بندی استفاده از رویکـرد تکرارشـونده اسـت. روشتکرارشــونده تــلاش مــی کنــد ورخــ ة ا لاعــات از زیرمسسله های زمان بندی به سوی مسـسل ة سـطح بـالاترحرکت کند و بازخوردی از زیرمسسلة سطح پایین بـ رای مسسلة سطح بالا به وجود آید. لازار [1]، برای اینکـه بـر

نویسندة مسسوب: تلفن: 84063365، فاکم: 88674858
ضعف برنامه ریزی تولید سلسله مراتبی یلبـه کنـد، یـکمدب برنامه ریزی کارگـاهی و زمـان بنـدی یکناروـه درمحیو کارگاهی در نظر گرفت و رویکرد تجزیه ای را بـهکار برد که بین حل یک مسسلة برنامـه ریـزی بـا تـوالیثابت محصولات روی ماشین ها و یک مسسلة زمان بنـدیکارگاهی برای برنامة تولیـد انتخـاب شـد ة ثابـت تلییـرمی کرد. انور و نقی [2] یک روش دوفازی بـرای تعیـیناندازة دسته و زمان بندی یکناروه برای محیو کارگاهی برای افق برنامه ریزی تک دوره ای پیشنهاد کردند. کیم و همکاران [3] یک مسسلة برنامه ریزی تولید و زمان بندی، برای ترکیب کردن محصولات با ساختار سلسـله مراتبـی ، نظیر آنچه در برنامه ریزی نیازمندی مواد وجود دارد، در نظر گرفتند و به حل این مسسله پرداختند.
یکی دیگر از روش هـایی کـه برنامـه ریـزی تولیـد و Email: [email protected]
زمان بنـدی را بـه صـورت یکناروـه در نظـر مـی گیـردبرنامه ریزی مسائل تعیین اندازة انباشـته و زمـان بنـدیهم زمان است. در پیشینة پژوهش دو شیوة مدب سـازیپایه بـرای مسـائل تعیـین انـدازة انباشـت ة پویـا ، شـاملمدب های با ظرا زمـانی بـزرگ و مـدب هـای بـا ظـرازم انی کوو ک، وج ود دارد. در مس ائل ظ را زم انی کووک ابتدا دورة زمانی بزرگ تر به دوره های کووک تـرتجزیه و سنم مدب سازی انجـام مـی شـود . ایـن شـیوهبه شدت بر پیچیدگی مسسله می افزاید. در مدب هـای بـاظرا زمانی کووک معمولاً فرض می شـو د در هـر دورهیک یا حداکثر دو محصـوب ممکـن اسـت تولیـد شـو د .مدب های این حوزه تعیین اندازة انباشته و زمان بندی را یکناروه می کنند. مدب های بـا ظـرا زمـانی بـزرگ درپیشینة پژوهش اجازة تولید محصـولات گونـاگون را در یک دوره می دهند؛ اما تـوالی تولیـد ایـن محصـولات رامشخص نمی کننـد. مسـسلة تعیـین انـدازة انباشـته بـامحدودیت منابع )CLSP(2 مدلی با ظرا زمانی بـزرگاست. مسائل تعیین اندازة دسته با ظرا زمانی کووـکشامل مسسلة تعیین اندازة انباشته و زمان بندی گسسته )DLSP( 3، مسسلة تعیـین انـدازة انباشـته و راهانـدازی پیوســته )CSLP(4، مســسلة تعیــین انــدازة انباشــته و زمان بندی متناسب )PLSP(5، و مسـسلة تعیـین انـدازة انباشته و زمـان بنـدی جـامع )GLSP(6 اسـت . مسـسل ة تعیین اندازة انباشته و زمان بنـدی جـامع مـدل ی جـامعاست که مدب های ارائه شـد ة پیشـین را بـا حالـت هـایخاد دربرمی گیرد. در این مدب، افق زمانی متناهی بـهT )ظرا زمانی بزرگ( دوره شکسته می شود؛ وری که هر دوره با ظرا زمانی بزرگ )t( نیز بـه یـک مجموعـهدوره های با ظرا زمانی کووک )s( تقسیم می شـود. درهر دوره با ظـرا زمـانی کووـک فقـو یـک محصـوب می تواند تولید شـو د [4]. GLSP بـ ه وسـیل ة در کس ـل وکـــیمم [5] و فلـــیچمن و م یـــر [6] بـــه صـــورت تک مرحله ای، وندمحصولی، تک ماشینی با هزینـه هـایراه اندازی وابسته به توالی با ظـرا زمـانی کووـک، امـابـدون درنظرگـرفتن زمـان هـای راه انـدازی و همچنـینکمبود، پیشنهاد شد. کلارك و کلارك [7] GLSP را در حالت ماشین های موازی در نظر گرفتند و مـدب سـازیجدیدی پیشنهاد کردند که اجازة ونـدین راه انـدازی را در ه ر دوره م ی داد. آن ه ا ب رای م دب س ازی مس سله ،تعدادی مشخص و داده شده برای راه اندازی در هـر دورهفرض کردند.
بوشکوب و همکاران [8] مروری بر تحقیقـات وهـاردهة اخیر دربارة مسـسل ة تعیـین انـدازة انباشـت ة پویـا ی محدودیت دار ارائه کردند. آن ها در مرور خود بر تعیـیناندازة دستة وندسـطحی بـا محـدودیت )MLCLSP(7 متمرکز شدند .MLCLSP مدلی با ظرا زمـانی بـزرگاست. مسائل تعیین اندازة انباشـته در محـیو تولیـدیوندسطحی با ظرا زمانی کووک شامل مسسلة تعیین اندازة انباشته و زمان بندی گسسـته )MLDLSP( [9] و متناسب )MLPLSP( [10] و جامع )MLGLSP( [11] اس ت. م دب ه ای MLDLSP و MLPLSP، ه م زم ان، امکان تعیین اندازة انباشته و زمـان بنـدی را دارنـد. امـاتعداد محصولاتی که امکان تولید در هـر دوره را دارنـدمحــدود اســت. بنــابراین ،MLGLSP کــه فانــدب واستمانه گ ن [11] آن را پیشنهاد کردند تلاش می کند با اســـتفاده از یکناروـــه کـــردن مزایـــایMLPLSP و MLCLSP، بر پایة تجزیة دوره های بزرگ تـر بـه تعـدادثابت دوره های کووک تر، به مدب سازی مسسله بنـردازد.
با توجه به پیچیدگی محاسباتی بالای مدب، فقو مسائل با اندازه های بسیار کووک قابلیت حل بهینه با این مدب را دارند. محمدی و همکاران [12] مسسلة تعیین انـداز ة انباشته و زمـان بنـدی وندسـطحی بـا راه انـدازی هـایوابسته به توالی را در نظر گرفتند و مـدب برنامـه ریـزیعدد صحیح مخـتلو را، کـه بـرای هـر دوره بـه تعـدادمحصولات راه اندازی در نظر می گیرد، برای مـدب سـازیمس سله ارائ ه کردن د. م دب س ازی آن ه ا تعم یم م دب پیشنهادی کلارك و کلارك [7] است. با توجه به اینکه در مدب سازی آن ها تعدادی مشخص و داده شـده بـرایراه انــدازی در هــر دوره فــرض مــی شــود، پیچیــدگی محاس باتی اف زایش مـی یاب د. همچن ین، محم دی وهمکــاران [13] دو رویکــرد الگوریتمیــک بــرای حــلمثاب هایی با اندازة بزرگ بـرای ایـن مسـسله در محـیوجریان کارگـاهی جـای گشـتی بـا محـدودیت ظرفیـتپیشنهاد کردند. محمدی [14] رویکردی مشابه با فاندب و استمانه گ ن [11] برای مسسلة تعیین اندازة انباشـته وزمــان بنــدی یکناروــه در محــیو جریــان کارگــاهیانعطاا پایر به کـار بـرد. اخیـراً، رمضـانیان و همکـاران[15] یک مسسلة تعیـین انـدازة انباشـته و زمـان بنـدییکناروه در سیسـتم تولیـدی جریـان کارگـاهی بـدونجای گشتی با محدودیت ظرفیت و راه اندازی وابسته بـهتوالی را مطالعه کردند. آن ها مدلی ریاضی را بـا کـاراییب الاتر ب رای ای ن مس سله پیش نهاد کردن د و دو روش ابتکاری را بر پایة برنامه ریزی عدد صحیح مختلو بـرایحل مسسلة مورد نظر توسعه دادند.
در ای ن پ ژوهش، مس سلة تعی ین ان دازة انباش ته و زمان بندی یکناروه در سیستم تولیدی وندمحصولی و ونددوره ای در محیو جریان کارگاهی جـای گشـتی بـامحدودیت منابع و راه اندازی وابسته بی توالی عملیات در نظر گرفته می شود و یک مدب برنامه ریزی عدد صـحیحمختلو جدید، بـا رویکـرد ظـرا زمـانی بـزرگ، بـرایفرموله کردن آن پیشنهاد می شود که قابلیت برنامه ریزی تولید و زمان بندی را به صورت هم زمان دارد. با توجه به پیچیدگی محاسباتی بسیار زیاد مسـسل ة مـورد بررسـی،برای حـل آن یـک الگـوریتم بهینـه سـازی گـروه اراتاستوار و دو روش ابتکـاری بـر پایـة برنامـه ریـزی عـدد صحیح با وارووب افق یلطان پیشنهاد مـی شـود . ایـن پژوهش به صورتی که در پی می آید سازماندهی شد. در بخش 2 مسسلة مـورد بررسـی تعریـف و مـدب ریاضـیپیشنهادی با جزئیات کامل تشـریح مـی شـو د. جزئیـاتروش های حل ابتکاری و فراابتکاری در بخـش 3 فـراهممی آید؛ همچنـین در آن پارامترهـای روش فراابتکـاریPSO، با استفاده از رح تاگووی، تنظیم مـی شـود. دربخش 4 رح آزمـایش ، شـامل تولیـد داده هـا و نتـایجمحاسباتی، ارائه می شود. در نهایت، نتیجه گیـری هـا دربخش پایانی بـرای خلاصـه کـر دن نـوآوری هـای مقالـهمی آید.
مدل س ز مسئله
در این زیربخش مدب برنامه ریزی عدد صـحیح مخـتلوپیشنهادی برای مسسله ارائه می شود.
ف ضی ت پ امت ه متغی ه تصمیم  هر محصوب به تعدادی عملیـات نیـاز دارد کـه بـرمراکز کاری مختلف، که به صورت سـری ویـدمانیافته اند، پردازش می شود.
تقاضای محصولات نهایی شناخته شده است.
در سیستم تولیـدی مـورد مطالعـه کمبـود مجـازاست.
راه اندازی وابسته به توالی است.
در یک دوره یک جـزء نمـی توانـد تولیـ د شـود تـازمانی که پردازش جزء پیش نیازی آن خاتمه یابد.
ماشین ها نمی تواننـد در یـک زمـان بـیش از یـکعملیات را انجام دهند .در هر زمـان هـر محصـوبفقو بر یک ماشین پردازش می شود.
اند س ه و پ امت ه
تعــداد محصــولات مختلــف )مجموعــة انــواع
N محصولات(؛
M تعداد ماشین آلات) مجموعة ماشین آلات(؛
T تعداد دوره ها )مجموعة دوره های تولید(؛ ظرفیت مصرفی ماشین m برای تولید یک واحد bjm از آیتم j؛ Cmt ظرفیت موجود ماشین m در دورة t؛ djt تقاضا برای آیتم j در دورة t؛ pjt هزینة پردازش یک واحد محصوب j در دورة t؛ hjt هزینة نگهداری یک واحد محصوب j در دورة t؛ BCjt هزینة کمبود یک واحد محصوب j در دورة t؛ زمان راه اندازی وابسته بـه تـوالی، اگـر عملیـاتSijm راه اندازی از محصوب i به محصوب j روی ماشین m انجام شود؛
wijm هزینة راه اندازی وابسته به توالی؛ موجـ ودی بـ رای محصـ وب j در آیـ از افـ ق Ij0 برنامه ریزی تولید.
متغی ه تصمیم
Xjt میزان تولید محصوب j تولیدشده در دورة t؛
Ijt تعداد موجودی برای محصوب j در دورة t؛
Bjt میزان کمبود برای محصوب j در دورة t؛ زمان شروع پردازش محصوب j بـر ماشـینm SOjmt در دورة t؛
زمان خاتمة پردازش محصوب j بر ماشـینm
COjmt در دورة t؛
کامل ارائه می شود.

Yijt متلیر راه انـدازی وابسـته بـه تـوالی=) 1، اگـرعملیات راه اندازی از محصوب i بـه محصـوبj در دورة t انجام پایرد؛ در ییر این صورت 0(؛
متلیر بـاینری =) 1، اگـر محصـوبj در دورة t
Zjt پردازش شود؛ در ییر این صورت 0(.
مدل ب ن مه ز عدد صحیح خطظ مختلط در این زیربخش، مدب ریاضـی پیشـنهادی بـا جزئیـات
iJ jJ mM tT

jN,tT )2(
jN,tT )3(
 jN, mM, tT )4(
 jN, mM, tT )5(
 jN, tT, m  2,…,M )6(
 i, jN,i  j, mM, tT )7(
t T )8(
jN,tT )9(
jN,tT )10(
 jN, mM, tT )11(
 i, jN, t T )12(
Min  p jt .X jt hjt .I jt BC jt .Bjt wijm.Yijt )1(
تابع هدا 1 برای حداقل کردن هزینـه هـای تولیـد،نگهداری، کمبود، و راه اندازی ارائه می شـو د. محـدودیت2 محدودیت بالانم جریان برای تأمین تقاضا برای هـرمحصوب در هـر دوره اسـت . محـدودیت 3 رابطـ ة بـینتولید برنامه ریـزی شـده و متلیـر بـاینری را، کـه نشـان می دهد محصوب j در دورة t تولید می شود یا نه، تعریف می کنـد. محـدودیت 4 محـدودیت ظرفیـت بـرای هـرماشین در هر دوره است. محدودیت 5 رابطة بین زمـانشروع و زمان تکمیل پردازش برای محصـولات تولیـدیبرنامه ریزی شده اسـت . محـدودیت 6 مجبـور مـی کنـدشروع پردازش jامین محصوب برنامه ریزی شده زمانی رخ دهد که پردازش این محصوب بـر ماشـین قبـل خاتمـهیافته باشد. محدودیت 7 وادار می کنـد شـروع پـردازشیک کار بر یک ماشین مشـخص پـم از تکمیـل شـدن
tT jJtT jJtT jJ
s.t.
I j(t1)  Bj(t1)  X jt  I jt  Bjt d jt  0 X jt  bigM.Z jt COjmt  Cmt
COjmt  SOjmt bjm.X jt SOjmt  COj(m1)t SOjmt  COimt  Sijm.Yijt bigM.(1Yijt )
Yijt Z jt 1
iJ,i j iJ jJ Yijt  Z jt
iJ,i j
Yjit  Z jt
iJ,i j
X jt ,I jt ,Bjt ,COjmt ,SOjmt  0; I j0  0 Yijt ,Z jt {0,1}
محصوب قرارگرفتـه در موقعیـت قبـل از آن بـر همـان ماشین و زمان راه اندازی رخ دهد. محدودیت هـای 8 تـا10 توالی محصولات در محیو تولیدی درنظرگرفته شده را تعیین می کنند. بق محدودیت های 9 و 10، تـوالیعملیات، ونانچه محصوب j در دورة t تولید شود، شامل محصوب مورد نظر است.
وش ه حل
روش حل ابتکاری بر پایة چارچوب افق غلطان اصول رویة افق غلطان
استفاده از رویکرد ابتکـاری افـق یلطـان، بـرای مسـائل
MIP ب زرگ، پیچیـدگی محاس باتی را ب ه ور قاب ل توجهی، با جایگزین کردن متلیرهای باینری بـا پیوسـتهبرای دوره های دورتر، کـاهش مـی دهـد . بنـابراین ، ایـنرویکرد حتی زمانی که همـة پارامترهـا بـه ـور کامـلشناخته شده اند مفید است [7، 12، 16].
مط ابق و ارووبی ک ه م رس و فونت ان [16] ارائ ه کردند، در هر گام رویة تکرارشونده افق برنامه ریـزی بـهسه بخش آیازین و مرکزی و پایـانی تقسـیم مـی شـود.
برای هر تکرار مشخص k:
بخ ش آی ازین ش امل) 1-k( دوره اس ت. در ای ن بخ ش، ب ا توج ه ب ه تکراره ای قب ل الگ وریتم،متلیرهای تصمیم به صورت جزئی یا کامل مطابق استراتژی ثابت کردن متلیرهای تصمیم مقـداردهیمی شوند.
بخش مرکزی فقـو شـامل دورة برنامـه ریـزیk ام است؛ وری که مسسله برای این دوره بـ ه صـورتکامل در نظر گرفته می شود. در ایـن بخـش همـة متلیرهای باینری مرتبو با این دورة برنامـه ریـزیدر مدب به صورت باینری لحا می شوند.
بخش پایانی شـامل دوره هـای بـاقی مانـده از دور ة
1+k تا دورة T است که مطابق سیاست ساده سازی انتخاب و ساده می شوند. با توجه به میزان کـاهشپیچیـــدگی در بخـــش پایـــانی، مطـــابق روش ساده سـازی انتخـاب شـده، مسـائل بـا انـدازه هـایبزرگ تر در زمان محاسباتی معقوب حل می شوند.

310134-1634272

k

و

ه

1

و

ه

k

1

و

ه

k

و

ه

T

و

ه

2
t

و

ه

k
+
1

ر

ير

ا

ي

ر

ا

ه

ا

و

ه

1

و

ه

k

1

و

ه

k

و

ه

T

و

ه

2
t

و

ه

k
+
1

k
+
1



قیمت: تومان


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