بخشی از مقاله
چکیده
زمان بندي به معنی تخصیص مجموعه اي از کارها به مجموعه اي از ماشین ها با در نظر گرفتن محدودیت هاي عملیاتی به منظور دستیابی به استفاده بهینه از منابع موجود می باشد در واقع زمان بندي نوعی فعالیت تصمیم گیري است که با هدف بهینه سازي یک و یا چند هدف انجام می گیردچفدر این پایان نامه قصد بررسی کامل و دقیق مسئله زمان بندي ماشین هاي موازي نامرتبط با در نظر گرفتن محدودیت براي این منظور یک مدل برنامه ریزي عدد صحیح مختلط جدید براي مسئله یاد شده ارائه می شود همچنین از الگوریتم هاي فراابتکاري شامل الگوریتم ژنتیک و الگوریتم شبیه ساري تبرید به منظور حل در مقیاس هاي کاربردي استفاده می شود.
کلید واژه زمان بندي ماشین موازي –اثرات زوال پذیري و یادگیري –الگوریتم ژنتیک نالگوریتم شبیه سازي تبرید
1. مقدمه
سیستم هاي تولیدي داراي اشکال مختلفی میباشند افزایش پیچیدگی در محیط هاي تولیدي، باعث ایجاد سیستم هاي تولیدي پیچیده تري نسبت به قبل شده است که این امر باعث شده که به عواملی مانند ظرفیت محدود و برنامه فرآیندهاي پیچیده بیش از پیش پرداخته شود زمانبندي و تعیین توالی ابزارهاي بسیار مهمی در افزایش بهره وري، استفاده بهینه از منابع، سودآوري خط تولید و حفظ موقعیت رقابتی در محیط هاي تولید با تغییرات سریع میباشند .
در واقع زمانبندي و تعیین توالی کارها داراي کاربرد گسترده اي میباشند که از طراحی تعیین توالی فرآیندها و جریان تولید بر روي ماشین آلات تولیدي گرفته تا مدلسازي صف در صنایع خدماتی را شامل میشوند از طرفی میتوان زمانبندي را نوعی تابع تصمیمگیري دانست که برنامه زمانی در آن تعیین میگردد، به عبارتی دیگر زمانبندي در اکثر سیستم هاي ساخت و تولید به عنوان یک فرآیند مهم تصمیمگیري عمل میکند.
از نظر دمپسترل و همکارانش ]ل[زمانبندي عبارت است از "هنر تخصیص منابع به فعالیتها جهت اطمینان از انجام کامل فعالیت ها در مدت زمانی معقول" میباشد در واقع مسئله اصلی در زمانبندي یافتن توالی از عملیات است که در آن فعالیت ها پمانند کاره از منابع لازم عبور کنند پمانند ماشین آلاتر ، به صورتی که این توالی شدنی بوده و با توجه به معیار عملکرد هدف تعیین شده ، بهینه باشد ]ه[در این مقاله، مسئله زمانبندي ماشینهاي موازي نامرتبط را با در نظر گرفتن برخی محدودیتهاي مختلف جهت هر چه نزدیکتر شدن مسئله زمانبندي به دنیاي واقعی بررسی شده و با استفاده از مدل سازي ریاضی و الگوریتم هاي فراابتکاري حل شده است.
2. بیان مساله
مسئله زمانبندي ماشینهاي موازي نامرتبط با در نظر گرفتن محدودیت هاي زمان آماده سازي وابسته به توالی کارها، دسترسی محدود به ماشینها واثرات همزمان زوال پذیري و یادگیري با هدف کمینه سازي بیشینه زمان تکمیل کارها به شرح زیر ارائه میگردد یک مجموعه از فکار متمایز، = {1,2, … , } ، بر روي مجموعه اي از ماشین } = {1,2, … , که بصورت موازي کنار هم قرار گرفته اند پردازش میشوند بطوریکه هر کار تنها بر روي یک ماشین پردازش میشود و هر ماشین در هر لحظه قادر به پردازش تنها یک کار میباشد ماشینها نامرتبط بوده و زمان پردازش یک کار روي ماشینهاي مختلف یکسان نمیباشد .
پردازش هر کار تنها بر روي زیر مجموعه اي از ماشینها امکان پذیر میباشد که به این مجموعه ها در اصطلاح مجموعه هاي پردازشی گفته می-شود در نتیجه در مسئله مورد بررسی به تعداد کارها مجموعه ي پردازش داریم که هر مجموعه شامل ماشین هایی میباشند که توانایی پردازش کار مورد نظر را دارند بر روي هر کار در طول یک دوره زمانی معین یک بار پردازش صورت میپذیرد که به این دوره زمانی زمان پردازشم اطلاق میشود.
زمان پردازش کارها بر روي ماشینها نه تنها به نوع کار بلکه به نوع ماشین هم بستگی دارد و بین زمان هاي پردازش کارها بر روي ماشینهاي مختلف رابطه مشخصی وجود ندارد از طرفی دیگر اثرات همزمان زوال پذیري و یادگیري روي زمان پردازش در نظر گرفته شده است براي این منظور یک مدل کلی با زوال پذیري کارها و اثرات یادگیري پیشنهاد میشود که در آن زمان پردازش واقعی یک کار، یک تابع کلی از زمان شروع پردازش کار مورد نظر اثر زوال پذیري و موقعیت زمانبندي آن در توالی پاثر یادگیري است .
قبل از آغاز پردازش هر کار روي هر ماشین، به منظور آماده سازي آن ماشین براي پردازش آن کار عملیاتی انجام میگیرد که از آن به عنوان عملیات نصب روي ماشین یاد میشود و به دوره زمانی که در آن عملیات نصب انجام میشود، زمان نصب ماشین اطلاق می-شود این زمان به نوع کاري که در حال حاضر بر روي ماشین پردازش میشود و به نوع کار قبلی پردازش شده روي ماشین بستگی داردضمناً براي کارهایی که در موقعیت اول روي هر ماشین قرار میگیرند نیز زمان آماده سازي در نظر گرفته شده است.
هر کار با در نظر گرفتن موقعیت آن در توالی پردازش کارها بر روي ماشین مربوطه پس از سپري شدن زمان نصب و زمان پردازش تکمیل می-شود معیار کمینه سازي بیشینه زمان تکمیل کارها بعنوان تابع هدف در نظر گرفته شده اند
٣. مدل ریاضی پیشنهادي
در این بخش مدل ریاضی پیشنهادي با رویکرد برنامه ریزي عدد صحیح مختلط براي مسئله تحت بررسی ارائه میگردد پیش از ارائه مدل در ابتدا اندیسها و پارامترهاي ورودي ، متغیرهاي تصمیم گیري، توابع هدف و محدودیتها بصورت جداگانه تشریح میشوند سپس مدل ریاضی پیشنهادي براي مسئله یاد شده ارائه میگردد
اندیس ها
• تعداد ماشین ها
• تعداد کارها
• اندیس کارها ,
• ,اندیس ماشین ها , = 1,2, …
اندیس موقعیت ها روي,= 1,2, … = 1,2, … ,
• هر ماشین
پارامترهاي ورودي مدل
• زمان نرمال پردازش کار فام روي ماشین
• زمان نصب مورد نیاز براي شروع کار نوع هنگامی که ف بلافاصله پس از کار نوع پردازش میشود
• زمان نصب مورد نیاز براي کار نوع هنگامی که در موقعیت اول روي یک ماشین پردازش شود
• اگر امکان پردازش کار نوع فروي ماشین نوع وجود داشته باشد ل، در غیر این صورت مقدار صفر را اتخاذ می-کند
• نرخ زوال پذیري
• نرخ یادگیري
• یک عدد حقیقی مثبت بزرگ
متغیر هاي تصمیم گیري
• زمان تکمیل کار نوع
• زمان شروع پردازش کار نوع
• زمان پردازش واقعی کار ام که در موقعیت ام روي یک ماشین پردازش میشود
