بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
ارائه يک الگوريتم ترکيبي NSGA-II با اهداف فازي براي حل مسئله دوهدفه بالانس خط مونتاژ
چکيده
اين مقاله به زمان بندي مسئله خط مونتاژ ميپردازد. به دليل وجود عدم قطعيت و ابهام در مقدار اهداف ، تعيين مقدار دقيق اهداف براي تصميم رندگان کار دشواري است . بنابراين در اين مقاله از اهداف فازي کمک گرفته شده است . بطورکلي مسئله خط مونتاژ داراي اهداف متناقضي است که بايد به طور همزمان بهينه شوند. هدف از اين مقاله حداقل کردن تعداد ايستگاه هاي کاري و زمان سيکل خط مونتاژ به طور همزمان است . با توجه به متناقض بودن اين دو هدف و همچنين با توجه به NP-Hard بودن مسئله - ي خط مونتاژ، براي حل مسئله ، يک الگوريتم ترکببي ارائه شده است که ترکيبي از اهداف فازي و الگوريتم NSGA-II که يک الگوريتم چندهدفه ي فراابتکاري است . يک مثال روشنگر نيز براي مقايسه عملکرد اين الگوريتم با روش هاي موجود ارائه شده است .
نتايج بدست آمده ، عملکرد بالاي الگوريتم را نشان ميدهند.
کلمات کليدي
بهين سازي چندهدفه ، بالانس خط مونتاژ، اهداف فازي، الگوريتم NSGA-II
١- مقدمه
محيط رقابتي توليدکنندگان را وادار ميسازد که سيستم توليد خود را با کارايي و اثر بخشي بالا و نيز در کمترين زمان ممکن طراحي کنند. لذا، در طراحي واقعي سيستم توليدي، طراحي يک خط مونتاژ کارا بسيار حائز اهميت ميباشد [١]. خط مونتاژ صنعتي نخستين بار توسط هنري فورد در اوايل دهه ١٩٠٠ مطرح شد [٢]. مسئله بالانس خط مونتاژ1(ALBP) شامل تخصيص کارهاي مورد نياز براي توليد يک محصول به صورت سري يا انبوه به مجموعه اي از ايستگاه هاي کاري است [٣].
خط مونتاژ بطورکلي به دو دسته خط مونتاژ ساده (SALBP) و خط مونتاژ تعميم يافته (GALBP) تقسيم مي شود [٤، ٧، ٨، ٩] و اين مسائل در دهه ٧٠ در دسته مسائلي که بطور غير قطعي در زمان چند جمله اي حل مي شوند٢ واقع شدند [١٠] که با توجه به سختي اين قبيل مسائل ، تلاش هايي زيادي براي توسعه و گسترش راه هاي ابتکاري از قبيل تکنيک وزن دهي موقعيتي رتبه اي [١١]، تکنيک
COMSOAL [١٢]، تکنيک MALB [١]، تکنيک MUST [١٤]، و روش LBHA [٤]، و همچنين استفاده از روش هاي فراابتکاري از قبيل الگوريتم ژنتيک [١٥]، شبيه سازي تبريد [١٦]، و جستجوي ممنوعه [١٧] صورت گرفته است .
در دنياي واقعي شرايط عدم قطعيت و ابهام ٣ حکمفرماست .
بعبارت ديگر براي يک تصميم گيرنده يا تصميم گيرندگان تعيين مقدار دقيق هر هدف به دليل نادقيق ، غيرقطعي و مبهم ٤ بودن مقدار آن هدف ، کار بسيار دشواري است و با توجه به اينکه اهداف فازي مي توانند سطح انتظار٥ اهداف غير دقيق را برآورده کنند، برخي از محققان براي مدل کردن مسائل خط مونتاژ از اهداف فازي استفاده کرده اند. به دليل اهميت خط مونتاژ، ادبيات بسيار زيادي در مورد مسائل بالانس خط مونتاژ وجود دارد که از اين ميان تعداد کمي از تحقيقات مربوط به حل اين مسائل در فضاي فازي است ، به عبارت ديگر در مقايسه با مسائل بالانس خط مونتاژ در فضاي قطعي، تاکنون تعداد تحقيقات کمي در رابطه با مسائل بالانس خط مونتاژ فازي صورت گرفته است [٧، ١٨]. علاوه بر اين در ادبيات مروري، تعداد تحقيقاتي که در آن از روش هاي ابتکاري و فراابتکاري براي حل ALBP در محيط فازي استفاده شده ، بسيار کم است که اکثر اين تحقيقات به زمان بندي تک هدفه خط مونتاژ پرداخته اند، از اين رو يک کمبود در حوزه ي بهينه سازي چندهدفه ي خط مونتاژ با اهداف فازي و استفاده از روش هاي فراابتکاري احساس مي شود.
سوجيمورا و همکاران و همچنين جن و همکاران نخستين محققاني بودند که يک الگوريتم ژنتيک فازي براي اين مسئله ارائه دادند، آن ها با يک الگوريتم ژنتيک که زمان پردازش فعاليت ها در آن به صورت اعداد فازي بود، ١-SALBP را حل کردند [١٩، ٢٠]. سلانو و همکاران با الگوريتم ژنتيک و الگوريتم شبيه سازي تبريد يک مدل ترکيبي بالانس خط مونتاژ را حل کردند و نتايج اين دو الگوريتم را با هم مقايسه کردند [٢١]. از طرف ديگر برودارو و والمر يک الگوريتم ژنتيک ترکيبي که با روش شاخه و کران ترکيب شده بود را براي حل ١-SALBP ارائه کردند [٢٢]. فونسکا و همکارانش روش وزن دهي موقعيتي رتبه اي و روش COMSOAL را با اعداد فازي، فازي کردند و از آن براي حل اين قبيل مسائل استفاده کردند [٢]. هاپ يک راه ابتکاري براي حل مدل ترکيبي بالانس خط مونتاژ فازي ارائه کرد
[٢٣]. سو و سايو نيز به کمک الگوريتم ژنتيک براي حل مدل ترکيبي بالانس خط مونتاژ فازي ارائه کردند [٢٤]. ژنگ و همکاران يک راه ابتکاري براي حل با اعداد فازي ارائه کردند [٢٥]. زکريا و نيرچو نيز يک الگوريتم ژنتيک چندهدفه براي ٢-SALBP با اعداد فازي ارائه کردند که در آن از جمع موزون اهداف کمک گرفتند [٢٦].
تکلو و ازکان در سال ٢٠٠٨ مسئله چندهدفه ي SULB را با توابع هدف فازي مدل کردند و به کمک برنامه ريزي آرماني آن را حل کردند و نتايج بدست آمده را با مدل غير فازي آن مقايسه کردند
[٢٧]. جوادي و همکاران نيز مسئله چندهدفه خط مونتاژ ترکيبي را با توابع هدف فازي مدل کردند و به کمک برنامه ريزي آرماني آن را حل کردند [٢٨]. کارا و همکاران در سال ٢٠٠٩ مسئله چندهدفه ي SALB و SULB را با توابع هدف فازي مدل کردند و به کمک برنامه ريزي آرماني آن را براي يک مثال حل کردند [٢٩]. تکلو و ازکان در سال ٢٠٠٩ با الهام از برنامه ريزي آرماني، مدل MIGP٦ را براي اهداف غير فازي و مدل FMIGP٧ را براي اهداف فازي ارائه کردند و يک مسئله تصميم گيري چندمعياره خط مونتاژ دوطرفه را که هم تابع هدف غير فازي و هم تابع هدف فازي داشت را به کمک دو مدل ارائه شده حل کردند [٣٠]. مهدوي و همکاران نيز مدل FMOLP٨ را براي حل مسئله چندهدفه خط مونتاژ ترکيبي با توابع هدف فازي ارائه کردند [٣١].
به طور کلي، در مسائل چندهدفه ، بجاي يک نقطه ي بهينه ، مجموعه اي از جوا هاي نقاط بهينه جستجو ميشود.. برتري اصلي روش هاي فراابتکاري چندهدفه نسبت به روش هاي کلاسيک ، يافتن مجموعه اي از جوا هاي بهينه در يک اجرا بجاي چندين بار اجراست [٣٢]؛ بعبارت ديگر در روش هاي کلاسيک براي يافتن جواب هاي متفاوت بايد اين روش ها را چندين بار تکرار کرد که اين ضعف را روش هاي فراابتکاري برطرف کرده اند.
تا آنجا که نويسندگان اين مقاله اطلاع دارند هيچ تحقيق قبل اي با روش هاي فراابتکاري چندهدفه به حل مسئله SALB با اهداف فازي نپرداخته است . همان طور که قبلا اشاره شد به دليل دشواري در تعيين مقدار دقيق هدف براي تصميم گيرندگان ، استفاده از اهداف فازي باعث واقعيتر شدن مدل ميشود و همچنين به دليل -NP Hard بودن ALBP استفاده از روش هاي فراابتکاري براي حل مسائل بزرگ خط مونتاژ ضروري به نظر مي رسد. به منظور از بين بردن اين شکاف ، اين مقاله به زمان بندي مسئله چندهدفه ي SALB به کمک يک الگوريتم فراابتکاري ترکيبي، مي پردازد. ساختار کلي مقاله به اين شرح است : در بخش ”٢“ چگونگي فرمول بندي بالانس خط مونتاژ مستقيم بيان مي گردد. در بخش ”٣“به بيان چگونگي روش حل و همچنين معرفي الگوريتم ترکيبي 9NSGA-II ارائه شده ، پرداخته مي شود. در بخش ”٤“ الگوريتم ارائه شده مورد محک قرار ميگيرد.
سر آخر نيز برخي نتايج و راهنماييها براي کارهاي آتي در بخش ”٥“ ارائه مي شود.
٢- فرموله کردن مسئله
٢-١- اعلائم
در اين مقاله از نمادهاي زير استفاده شده است :
انديس ها:
j،a،b فعاليت
s،r،q ايستگاه کاري
k تابع هدف
پارامترها:
WSg سطح انتظار تعداد ايستگاه هاي کاري
WS حد بالاي خطاي مجاز١٠ تعداد ايستگاه هاي کاري
wsmim حداقل تعداد ايستگاه هاي کاري از نظر تئوري
wsmax حداکثر تعداد ايستگاه هاي کاري
cg سطح انتظار زمان سيکل خط مونتاژ
c حد بالاي خطاي مجاز براي زمان سيکل
n تعداد فعاليت ها
j مجموعه ي فعاليت ها .
WS مجموعه ي ايستگاه هاي کاري
t مجموعه زمان پردازش فعالیت ها
p مجموعه ي روابط پيش نيازي
متغيرها:
twss زماني که ايستگاه کاري sام براي کامل شدن همه کارهايش نياز دارد.
nws تعداد ايستگاه هاي کاري بهره برداري شده
C زمان سيکل خط مونتاژ
٢-٢- محدوديت هاي مدل
به خط مونتاژ ميتوان به عنوان يک سري از مکان ها که به آن ها ايستگاه کاري گفته ميشود، نگاه کرد، بطوريکه در اين مکان ها، زيرمجموع اي از کارهايي که براي توليد يک واحد لازم است انجام مي يرد [٢٠]. براي اين مسئله هر يک از فعاليت ها بايستي تنها به يکي از اين ايستگاه هاي کاري تخصيص داده شود، علاوه بر اين مجموعه ”J“ را بايد در ايستگاه هاي کاري طوري تقسيم شوند که محدوديت هاي فرمول هاي (١)-(٣) ارضاء شوند [٢، ١٩] :
محدوديت (١) و (٢) تضمين مي کنند که همه فعاليت ها به ايستگاه هاي کاري تخصيص پيدا کنند و هر فعاليت فقط به يک ايستگاه تخصيص پيدا کند.
در خط مونتاژ مستقيم فعاليت jام زماني مي تواند به ايستگاه کاري sام تخصيص يابد که تمام فعاليت هاي پيش نيازي آن به يکي از ايستگاه هاي کاري s،...،١تخصيص داده شده باشند (فرمول (٣)).
و محدوديت (٣) تضمين کننده ي رعايت محدودي هاي پيش نيازي است .
٢-٣- اهداف مدل :
در شرايط واقعي به دليل وجود ابهام و عدم قطعيت ، تعيين مقدار دقيق هدف براي تصيميم رندگان کار سختي است . يکي از ابزارهاي مفيدي براي مواجهه با عدم قطعيت ، نظريه مجموعه فازي است [٣٤]؛ به عبارت ديگر نظريه مجموعه فازي به تصميم گيرندگان کمک مي کند تا بتوانند اهدافي که تعيين مقدار دقيق آن ها دشوار است را به طور طبيعي تعريف کنند.
يک مسئله بهينه سازي در حالت قطعي، در مجموعه جواب x، بصورت فرمول (٤) است و در حالت فازي به فرمول (٥) تبديل مي شود [٣٥].
تابع هدف فرمول (٥) م گويد که مقدار kامين هدف فازي بايد تقريبا کوچک تر يا مساوي (تقريبا بزرگتر يا مساوي) سطح انتظار هدف kام (gk) باشد. gk يا با حل کردن مسئله بصورت تک هدفه براي هدف kام بدست مي آيد و يا توسط تصميم گيرنده مشخص مي شود. در حقيقت [٣٥] براي هر هدف يک حد بالا و يک حد پايين مشخص کرد و به کمک تابع عضويت خطي ١١، اهداف را بصورت فازي مدل کرد. .. تابع عضويت خطي kامين هدف فازي است که بصورت فرمول (٦) و (٧) تعريف مي شود [٣٥].
که در فرمول (٦)، Lk حد پايين خطاي مجاز و در فرمول (٧)، Uk حد بالاي خطاي مجاز kامين تابع هدف هستند که توسط تصميم گيرنده تعيين مي شوند.
در اين مقاله نيز براي تعريف اهداف فازي از تابع عضويت خطي استفاده شده است . هدف هاي فازي موجود در اين مسئله به شرح زير است :
تعداد ايستگاه هاي کاري بهره برداري شده بايد تقريبا کمتر از سطح انتظار تعداد ايستگاه هاي کاري (WSg) باشد (فرمول (٨))
تعريف تابع هدف بصورت فرمول (٨) به تصميم گيرنده کمک مي کند تا بتواند تعداد ايستگاه هاي را به طور غيردقيق تعيين کند.
البته تصميم گيرنده بايد حد بالاي خطاي مجاز تعداد ايستگاه هاي کاري (ws) را نيز تعيين کند.
زمان سيکل کاري هر ايستگاه کاري بايد تقريبا کمتر از سطح انتظار زمان سيکل خط مونتاژ (cg) باشد (فرمول (٩))، بعبارت ديگر، بزرگترين زمان سيکل ايستگاه هاي کاري بايد تقريبا کمتر از cg باشد (فرمول (١٠)).
تعريف توابع هدف بصورت فرمول (٩) يا (١٠) به تصميم رنده کمک ميکند تا بتواند زمان سيکل خط مونتاژ را به طور غيردقيق تعيين کند. البته تصميم رنده بايد حد بالاي خطاي مجاز زمان سيکل (c) را نيز مشخص کند.
توابع عضويت اهداف ذکر شده در فرمول هاي (١١) و (١٢) و همچنین در شکل 1 و شکل 2 مشاهده میشوند .
بنابراین مدل ارائه شده بصورت محودیت های (۱) (۳) و اهداف (۹) و (۱۰) و توابع عضویت (۱۱) و (۱۲) می شود.
۳- روش حل
NSGA-II
الگوریتم های فراابتکاری، روشهای جستجوی تصافی قدرتمندی هستند که با الهام گیری از طبیعت به دنبال جوابهای بهینه می گردند. در این مقاله برای حل مسئله از یک روش فراابتکاری چندهدفه با نام NSGA - II که توسط [۳۲] در سال ۲۰۰۲ ارائه شده است، استفاده شده است. در حقیقیت این الگوریتم یک رویکرد چندهدفه از الگوریتم ژنتیک است. دو عملگر اصلی الگوریتم NSGA - II عبارتند از: مرتب سازی غير مغلوب" و فاصله ی ازدحامی". عملگر مرتب سازی غیرمغلوب، جواب های بدست آمده را در جبهه های پارتوی مختلف طبقه بندی می کند. عملگر فاصله ی ازدحامی، میزان پراکندگی جوابها را هر جبهه محاسبه کرده و تنوع جواب های الگوریتم را حفظ می کند.
٣-٢- الگوريتم ارائه شده
ارائه ي جواب
براي توليد کروموزوم اوليه ، جايگشت اعداد يک تا تعداد فعالي ها، به طور تصادفي توليد ميشود و براي رعايت محدودي هاي پيش نيازي ، کروموزوم توليد شده ، در صورت نياز بايد تعمير گردد. به عنوان مثال فرض کنيد هشت فعاليت وجود دارد که بايد ترتيب توالي آن ها بهينه گردد، به کمک اعداد تصادفي جايگشت يک تا هشت توليد ميشود که [٦ ٢ ٨ ٧ ٤ ٥ ٣ ١] به عنوان يک کروموزوم شناخته ميشود، همچنين فرض کنيد يکي از قيود جدول پيش نيازي ، لزوم انجام فعاليت دوم قبل از انجام فعاليت پنجم
