توسعه يك الگوريتم شاخه و كران براي حل مساله زمانبندي در سيستم توليد جريان كارگاهي مونتاژي

Proposed a branch and bound algorithm for Assembly flow shop scheduling problem

سيستم توليد جريان كارگاهي مونتاژي شامل دو مرحله است. در مرحله اول پردازش قطعات صورت مي‌گيرد و معمولا به صورت يك ايستگاه با ماشين‌هاي موازي درنظر گرفته مي‌شود. مرحله دوم نيز يك ايستگاه يا خط مونتاژ مي‌باشد كه قطعات پردازش شده، در آن مونتاژ و محصولات نهايي كامل مي‌شود. در اين تحقيق فرض مي‌شود قرار است تعدادي محصول از انواع مختلف توليد شود و هر محصول جهت كامل شدن، نيازمند قطعاتي مشخص است. بعضي از قطعات محصولات مشترك و مشابه بوده و بعضي قطعات هم مختص يك محصول مي‌باشد لذا باتوجه به توليد قطعات مشابه، موضوع زمان آماده‌سازي (setup time) و توليد دسته اي قطعات مشابه نيز نيازمند بررسي است. هدف عبارتست از زمانبندي پردازش قطعات در ايستگاه اول و مونتاژ محصولات در ايستگاه دوم بطوري كه زمان تكميل كل محصولات حداقل شود. طبق بررسي پيشينه تحقيق، اين مساله جزء مسائل nphard محسوب مي‌گردد. ابتدا پارامترها و ويژگيهاي مساله تعريف و پس از ارائه مدل رياضي مساله، يك الگوريتم شاخه و كران براي حل مساله مورد نظر در ابعاد كوچك و متوسط ارائه مي‌شود. همچنين به منظور افزايش كارايي الگوريتم پيشنهادي، دو حد پايين و دو حد بالا براي جواب مسائل توسعه داده مي‌شود. در نهايت، چندين مساله تست با شرايط متنوع طراحي و عملكرد الگوريتم پيشنهادي در حل اين مسائل ارزيابي شده است.

Assembly flow shop production system includes two stages. In the first stage that is usually assumed one station with some parallel machines, the parts are processed. The second stage is an assembly station (or line) to assemble the parts and complete the products. Suppose that a number of products of different kinds are ordered to be produced and each product needs a set of several parts to complete. Some of the parts are common and some others are unique for each product. Therefore it is important to study the setup times and batch production. The aim is to schedule the parts for process and the products for assembly with the minimum complete time objective. Literature review shows that the considered problem is a NP-Hard problem, so the problem characteristics and its parameters are defined and then a branch and bound algorithm is introduced to solve the small and mediocre problems. Some lower bounds and upper bounds are improved to increase the algorithm efficiency. Finally, a variety of problem is designed and performance of the proposed algorithm is evaluated in solving this problems.