بخشی از مقاله
ارايه مدلي براي زمان بندي جريان کارگاهي ترکيبي با ماشين هاي پردازش دسته اي
چکيده
اين پژوهش مساله زمان بندي دسته اي کارها در محيط جريان کارگاهي ترکيبي با هدف کمينه کردن زمان تکميل کل کارها را مورد بررسي قرار داده است . ماشين ها، توانايي پردازش چند کار را هم زمان با هم در يک دسته دارند. ظرفيت ماشين ها و زمان پردازش کارها در هر مرحله مشخص است . زمان پردازش دسته ها برابر بزرگترين زمان پردازش کارهاي در دسته است . اندازه کارها مشخص است . زماني که دسته ها تشکيل شدند تا آخرين مرحله ثابت ميمانند. مجموع اندازه کارهاي هر دسته ، از کوچکترين ظرفيت ماشين ها نبايد بيشتر شود. يک مدل برنامه ريزي خطي عدد صحيح مختلط براي مساله ارايه شده است . جهت ارزيابي مدل ، مسايلي با اندازه کوچک به صورت تصادفي توليد شده و با نرم افزار تجاري حل شده است . نتايج حل مدل نشان دهنده پيچيدگي اين مساله است .
کليد واژگان : زمان بندي، جريان کارگاهي ترکيبي، توالي عمليات ، ماشين هاي پردازش دسته اي، برنامه ريزي خطي عدد صحيح مختلط .
١- مقدمه
ماشين هاي پردازش دسته اي ١، توانايي پردازش چند کار را هم زمان با هم در يک دسته دارند. در صنايع مختلفي از جمله صنايع الکترونيک براي توليد برد مدار چاپي ٢، صنايع فلزکاري ٣ و همچنين کوره هاي پخت ٤ کاربرد دارند. هر ماشين ميتواند دسته اي از کارها را به طوري که ظرفيت دسته از ظرفيت ماشين بيشتر نشود، پردازش کند. با توجه به کاربرد ماشين ها، زمان پردازش دسته - ها ثابت يا متغير است . از جمله مزاياي استفاده از اين ماشين ها کاهش زمان توليد، کاهش زمان آماده سازي، کاهش هزينه حمل و نقل و کاهش نيروي انساني است . لذا زمان بندي ماشين هاي پردازش دسته اي ميتواند سهم عمده اي در بهبود و پيشرفت عملکرد شرکت ها داشته باشد.
زمان بندي، تعيين توالي کارها جهت تخصيص به منابع توليد است . جهت دست يابي به اهدافي مانند بهره برداري بهتر از منابع دردسترس ، پاسخ گويي سريع به تقاضاي مشتريان و کمينه کردن زمان تکميل کل کارها است . با توجه به تعداد عملياتي که براي پردازش يک کار مورد نياز است و تعداد ماشين هاي موجود براي انجام هر عمليات ، مسايل زمان بندي را ميتوان تفکيک کرد.
محيط جريان کارگاهي ٥ شامل چند مرحله ي متوالي است که در هر مرحله عمليات خاصي بر روي کارها انجام ميشود. کارها جهت پردازش از تمامي مراحل به ترتيب بايد عبور کنند.
در زمينه ي زمان بندي دسته اي، احمدي ٦ و همکاران (١٩٩٢) مساله زمان بندي جريان کارگاهي دو مرحله اي که در مرحله ي اول کارها به صورت تکي و مرحله ي دوم به صورت دسته اي پردازش شده است ، را مورد بررسي قرار داده اند. زمان پردازش دسته را بدون توجه به کارهايي که در دسته قرار دارند، ثابت در نظر گرفته و يک الگوريتم ابتکاري ٧ براي حل مساله با هدف کمينه کردن زمان تکميل کل کارها ارايه داده اند.
سونگ ٨ و يوون ٩ (١٩٩٧) مساله زمان بندي جريان کارگاهي دو مرحله اي با ماشين هاي پردازش دسته اي در صورتي که کارها در لحظه ي صفر دردسترس نباشند، را مورد بررسي قرار داده اند. زمان ورود کارها حالت پويا داشته و مشخص است . الگوريتمي بر اساس برنامه ريزي پويا براي حل مساله با هدف کمينه کردن ، بيشترين زمان تکميل کل کارها ارايه داده اند.
داموداران ١٠ و سريهاري١١ (٢٠٠٤) مدل برنامه ريزي خطي عدد صحيح مختلط براي مساله زمان بندي جريان کارگاهي دو مرحله اي با ماشين هاي پردازش دسته اي ارايه داده اند. آن ها در پژوهش خود ابتدا با فرض اين که ظرفيت انبارمياني ١٢ صفر است ، مساله را مدل سازي کرده و مدل ديگري که ظرفيت انبارمياني نامحدود باشد، ارايه داده اند. زمان پردازش دسته ها را برابر طولانيترين زمان پردازش کارهاي در دسته فرض کرده اند. آن ها در پژوهش خود ابتدا کارها را دسته بندي کرده و سپس توالي دسته ها را تعيين مي - کنند. براي حل مساله با سايز کوچک نرم افزار سيپلکس پيشنهاد شده است .
لياعو١٣ و لياعو (٢٠٠٨) مساله زمان بندي جريان کارگاهي دو مرحله اي با ماشين هاي پردازش دسته اي را مورد بررسي قرار داده اند.
مدل برنامه ريزي خطي عددصحيح مختلط که توسط داموداران و سريهاري در سال (٢٠٠٤) با هدف کمينه کردن زمان تکميل کل کارها ارايه شده بود، را بهبود دادند. آن ها در پژوهش خود بيان کردند که دسته بندي کارها و تعيين توالي دسته ها، دو تصميم وابسته به هم است که نبايد جداگانه در نظر گرفته شوند. يک کران پايين و يک الگوريتم ابتکاري بر اساس برنامه ريزي خطي عدد صحيح مختلط براي حل مساله ارايه داده اند. امين ناصري١ و بهشتينيا٢ (٢٠٠٩) مساله زمان بندي دسته هاي موازي در محيط جريان کارگاهي ترکيبي با هدف کمينه کردن زمان تکميل کل کارها را مورد بررسي قرار داده اند. در اين پژوهش فرض شده است که در بعضي از مراحل ، ماشين ها توانايي پردازش هم زمان دو يا تعداد بيشتري از کارها را دارند (اگر ظرفيت ماشين برابر يک باشد، ماشين فقط يک کار را پردازش ميکند). ماشين هايي که در يک مرحله به صورت موازي قرار ميگيرند، يکنواخت و سرعت آن ها متفاوت است . سه الگوريتم ابتکاري براي حل مساله ارايه شده است . يک کران پايين براي ارزيابي الگوريتم هاي پيشنهادي درنظرگرفته شده است . در نهايت الگوريتم ژنتيک سه بعدي، براي بالا بردن کيفيت جواب ها پيشنهاد شده است . با توجه به مطالعات انجام شده توجه کمتري به مسايل زمان بندي دسته اي کارها در محيط جريان کارگاهي ترکيبي شده است
لياعو و هونگ ٣ (٢٠١١) مساله زمان بندي جريان کارگاهي دو مرحله اي با ماشين هاي پردازش دسته اي را مورد بررسي قرار داده اند.
براساس الگوريتم جستجوع ممنوعه ، يک الگوريتم ابتکاري براي حل مساله با هدف کمينه کردن زمان تکميل کل ارايه داده اند.
جهت ارزيابي الگوريتم پيشنهادي، آن را با يک الگوريتم ابتکاري بر اساس برنامه ريزي خطي عدد صحيح مختلط مقايسه کرده اند.
موتوسوامي ٤ و همکاران (٢٠١٢) مساله زمان بندي جريان کارگاهي دو مرحله اي با ماشين هاي پردازش دسته اي به طوري که دسته ها نميتوانند بين دو مرحله منتظر بمانند، را مورد بررسي قرار داده اند. زمان پردازش کارها در هر مرحله ، زمان در دسترس بودن کارها و اندازه کارها مشخص است . زمان پردازش دسته براي ماشين اول برابر طولانيترين زمان پردازش کارهاي در دسته است و براي ماشين دوم برابر جمع زمان هاي پردازش همه کارهاي در دسته است . يک مدل برنامه ريزي خطي عدد صحيح مختلط براي مساله مورد نظر ارايه شده است . الگوريتم فراابتکاري بهينه سازي ازدحام ذرات براي حل مساله پيشنهاد شده است .
داموداران ، راعو٥ و مستري٦ (٢٠١٢) مساله زمان بندي جريان کارگاهي چند مرحله اي با ماشين هاي پردازش دسته اي را مورد بررسي قرار داده اند. آن ها در پژوهش خود زمان پردازش دسته ها را برابر طولانيترين زمان پردازش کارهاي در دسته فرض کرده اند.
کارها را طوري دسته بندي ميکنند که ظرفيت دسته ها از ظرفيت ماشين ها بيشتر نشوند. الگوريتم فراابتکاري بهينه سازي ازدحام ذرات را براي حل مساله با هدف کمينه کردن زمان تکميل کل کارها ارايه داده اند. همان طور که پردازش هاي صنعتي پيچيده تر ميشوند، محيط هاي صنعتي ظرفيت خود را بر اساس تعداد فعاليت هاي قابل پردازش افزايش مي دهند (کورز٧ و آسکين ٨ ٢٠٠٣).
با توجه به شرايط رقابتي صنايع ، بسياري از سيستم هاي توليدي کلاسيک به سمت محيط هاي جديدتري مانند جريان کارگاهي ترکيبي ٩ تغيير جهت ميدهند. که اين سيستم توليدي، ترکيبي از جريان کارگاهي و ماشين هاي موازي است . سيستم جريان کارگاهي، به منظور افزايش ظرفيت خود در مراحلي که گلوگاه است از ماشين هاي موازي استفاده ميکند. ماشين هاي موازي مي - توانند يکسان ١٠، يکنواخت ١١ يا نامرتبط ١٢باشند. در سيستم جريان کارگاهي ترکيبي حداقل در يک مرحله بيش از يک ماشين وجود دارد.
پژوهش هاي زيادي مساله ي زمان بندي دسته اي کارها را در محيط جريان کارگاهي مورد بررسي قرار داده اند. از آن جايي که محيط هاي صنعتي، به سمت جريان کارگاهي ترکيبي در حال تغييراند و پردازش دسته اي کارها جهت استفاده ي بهينه از ظرفيت ماشين ها مورد توجه است . هدف اين پژوهش ، ارايه مدلي براي پردازش کارها به صورت دسته اي در محيط جريان کارگاهي ترکيبي با هدف کمينه کردن زمان تکميل کل کارها است .
٢- متن
٢-١- تعريف مساله
مساله زمان بندي که در اين پژوهش مورد بررسي قرار گرفته است ، شامل ويژگيهاي زير است . n کار که در لحظه صفر دردسترس هستند و روي m مرحله بايد پردازش شوند. در هر مرحله i تعداد mi ماشين به صورت موازي وجود دارد. تمامي کارها از تمامي مراحل بايد عبور کنند و فقط روي يک ماشين در هر مرحله پردازش شوند. مسير پردازش براي همه کارها يکسان است . دسته ها فقط يک بار پردازش مي شوند به عبارت ديگر هنگامي که پردازش يک دسته شروع شد امکان قطع شدن عمليات وجود ندارد.
زمان پردازش هر دسته برابر بزرگترين زمان پردازش کارهاي در دسته است . ماشين هاي موازي در هر مرحله يکسان و ظرفيت آن - ها مشخص است . مجموع ظرفيت کارهايي که در دسته قرار مي گيرند نبايد از ظرفيت ماشين بيشتر شود. هنگامي که دسته ها تشکيل شدند تا آخرين مرحله ثابت ميمانند بنابراين ظرفيت دسته ها با کمترين ظرفيت ماشين ها درنظرگرفته ميشود.
٢-٢- مدل رياضي پيشنهادي
در اين بخش مدل برنامه ريزي خطي عدد صحيح مختلط براي مساله مورد بررسي، ارايه شده است . ابتدا پارامترها و نمادهاي استفاده شده در مدل توضيح داده مي شود.
n تعداد کارها
m تعداد مراحل پردازش
g تعداد دسته ها
mi تعداد ماشين هاي موازي در مرحله i
sj اندازه کار j
pji زمان پردازش کار j در مرحله i
j انديس کار
i انديس مرحله
b , kانديس دسته
Sm ظرفيت ماشين مرحله m
M عدد بزرگ مثبت
همچنين متغيرهاي تصميم مدل به شرح زير است :
Xb,i,k ١، اگر دسته b بعد از دسته k در مرحله i پردازش شود.
٠، در غير اين صورت
Yb,i,l ١، اگر دسته b در مرحله i روي ماشين l پردازش شود.
٠، در غير اين صورت
Zj,b ١، اگر کار j در دسته b قرار گيرد.
٠، در غير اين صورت
Cb,i يک متغير پيوسته است که زمان تکميل دسته b در مرحله i را نشان مي دهد.
مدل رياضي مساله زمان بندي جريان کارگاهي ترکيبي با ماشين هاي پردازش دسته اي به صورت زير است :
تابع هدف ، کمينه کردن زمان تکميل کل کارها است در معادله (١) نشان داده شده است . دسته محدوديت (٢) نشان دهنده اين است که هر دسته در هر مرحله فقط روي يک ماشين پردازش شود. دسته محدوديت (٣) نشان دهنده اين است که هر کار فقط به يک دسته تخصيص داده شود. دسته محدوديت (٤) زمان تکميل دسته ها در مرحله اول را مشخص ميکند. دسته محدوديت (٥) اين اطمينان را ميدهد که ظرفيت دسته ها از ظرفيت ماشين ها بيشتر نشود. دسته محدوديت (٦) زمان تکميل دسته ها را از مرحله دو تا آخرين مرحله مشخص ميکند. دسته محدوديت (٧) و (٨) محدوديت مربوط به هر جفت از دسته ها است . تضمين ميکند هر ماشين در هر مرحله و در هر زمان حداکثر در حال پردازش يک دسته است . براي هر جفت از دسته ها فقط يکي از اين دو دسته محدوديت ها فعال ميشود. دسته محدوديت (٩) مقدار تابع هدف را محاسبه ميکند.
