از دیدگاه عملی و صنایع تولیدی

دانلود پایان نامه

پردازش دسته ای : یک ماشین ممکن است بتواند تعدادی از کارها را به هم پردازش کند، مثلاً به تعداد b. این بدین معنی است که می تواند دسته ای نهایتاً شامل کار را در یک زمان پردازش کند. زمان پردازش کارها در یک دسته ممکن است یکسان نباشد و کل دسته هنگامی کامل می شود که آخرین کار در دسته کامل شود، که مبین این حقیقت است که زمان تکمیل کل دسته، با کار با طولانی ترین زمان پردازش تعیین می شود. اگر ، آنگاه مسئله به یک محیط زمانبندی عادی تبدیل می شود.
خرابی ها : این محدودیت بیان می کند که ممکن است ماشین ها به دلیل خرابی یا انجام عملیات های نگهداری و تعمیرات در تمام لحظات در دسترس نباشد.
دسترسی محدود به ماشین ها : این محدودیت بیانگر آن است که هر ماشین توانایی پردازش هر کاری را ندارد، بطوریکه مجموعه بیانگر مجموعه ای از ماشین ها است که می توانند کار j را پردازش کنند.
انسداد : انسداد پدیده ای است که ممکن است در محیط جریان کارگاهی رخ دهد. اگر در یک جریانی کارگاهی بین دو ماشین متوالی، انبار موجودی محدود وجود داشته باشد، آنگاه ممکن است هنگامی که ظرفیت این انبار پر باشد، ماشین بالادستی اجازه نداشته باشد که کار تکمیل شده را به این مرحله بفرستد. انسداد بیانگر این است که کامل شده باید روی ماشین بالادستی باقی بماند و از کار کردن آن ماشین بر روی کار بعدی جلوگیری می کند [1].
در مسائل زمانبندی، هدف از یافتن توالی کارها روی ماشین ها می تواند متفاوت باشد. معمولا توابع هدف مورد استفاده در مقالات و کتب مختلف تابعی از زمان های تکمیل و زمان های تحویل کارها می باشند. تعدادی از اهداف مورد استفاده در مسائل زمانبندی عبارتند از :
طولانی ترین زمان تکمیل : اگر زمان تکمیل کار را با نمایش دهیم آنگاه برابر است با زمان تکمیل آخرین کاری که سیستم را تر ک می کند یا بعبارتی . کمترین طولانی ترین زمان تکمیل معمولاً بیانگر استفاده بهتر از ماشین ها است.
مجموع وزنی زمان های تکمیل : مجموع وزنی زمان های تکمیل کارها، بیانگر مجموع هزینه های نگهداری یا موجودی تحمیل شده توسط زمانبندی می باشد. مجموع زمان های تکمیل در ادبیات اغلب به زمان در جریان ارجاع شده است. به همین دلیل زمان تکمیل وزنی کل به زمان در جریان وزنی معروف است [1].
حداکثر تاخیر : این تابع هدف بدترین مغایرت با زمان های تحویل را در بین کارها اندازه گیری می کند. اگر زمان تحویل کار را با نمایش دهیم در نتیجه میزان تاخیر هر کار بصورت بدست می آید، آنگاه حداکثر تاخیر به صورت بدست می آید.
دیرکرد وزنی کل : این تابع هدف مجموع هزینه های تحمیل شده به سیستم را به دلیل عدم پاسخگویی بموقع به سفارش‏های مشتریان محاسبه می کند. میزان دیرکرد کار به صورت بدست می آید.
تعداد کارهای دارای دیر کرد : این تابع تعداد کارهایی که دارای دیرکرد هستند را کمینه می کند که بصورت زیر محاسبه می شود:
مجموع تاخیر کارها : این تابع هدف کیفیت یک زمانبندی را برمبنای مجموع بخشی از کارها که خارج از زمان تحویلشان انجام می شوند، اندازه گیری می کند که به صورت زیر محاسبه می شود. نشان دهنده ی زمان پردازش کار می باشد.
1-2- تعریف مسئله
محیط مورد بررسی در این پایاننامه، مسئله زمانبندی ماشینهای موازی نامرتبط میباشد. زمانبندی ماشینهای موازی در ارتباط با چگونگی زمانبندی گروهی از کارها بر روی تعدادی از ماشینها به منظور اطمینان از پردازش کارها در مدت زمان منطقی میباشد. ماشینهای موازی از دو دیدگاه تئوری و عملی دارای اهمیت هستند. از دیدگاه تئوری تعمیمی از مساله تک ماشین و حالت خاصی از محیط جریان کارگاهی و کار کارگاهی انعطاف پذیر میباشد. از دیدگاه عملی به این جهت که در دنیای واقعی بسیار معمول هستند دارای اهمیت بالایی میباشند [1]. بطور کلی صنایع مختلف از کاربرد مدل ماشینهای موازی سود بردهاند بطور مثال در صنایع تولید دستگاه نیمه هادی [3،4]، در صنایع نساجی [5]، در فرآیند فولادسازی [6]، در صنایع تولید چرخ دندهها [7]، در صنایع کشتی سازی [8]، و در صنایع تولید بورد های الکتریکی [9،10] وغیره.
در بسیاری از صنایع تولیدی و خدماتی، فعالیت هایی که وجود دارند کاملاً از هم مستقل نیستند و بین برخی از آنها یک رابطهی پیشنیازی و پسنیازی وجود دارد. این مسئله در حالیست که تعداد پژوهشهای کمی در مورد زمانبندی ماشینهای موازی صورت گرفته است که محدودیتهای پیش نیازی را در نظر گرفته باشند. از اینرو برای پوشش این خلا در ادبیات موضوع، در این تحقیق سعی شده است که بطور کامل به این محدودیت پرداخته شود.
در مسئله زمانبندی ماشینهای موازی نامرتبط از آنجاییکه ممکن است دلیل نامرتبط بودن ماشینها، تفاوت میان عملیات قابل پردازش توسط آنها باشد و هر ماشین لزوماً قادر به پردازش هر یک از کارهای موجود در مجموعه کارها نباشد. بنابراین دور از منطق نیست که محدودیتهای دسترسی به ماشینها در مسئله مورد بررسی در نظر گرفته شود. این محدودیت تضمین میکند که هر کار تنها توسط زیر مجموعهای از ماشینها قابل پردازش میباشد و اصطلاحاً پردازش کارها با دسترسی محدود به ماشینها صورت میپذیرد.
اما یکی از محدودیتهای دیگری که در این پژوهش به بررسی آن میپردازیم، زمان آماده سازی وابسته به توالی کارها و نوع ماشینها میباشد. در یک محیط تولیدی، زمان آماده سازی شامل تمام فعالیتهایی میباشد که بر روی مواد به منظور آماده کردن آنها برای انجام فرآیند اصلی صورت میگیرد. بطور کلی زمانهای آمادهسازی که صنایع تولیدی با آنها در ارتباط هستند به دو دسته تقسیم میشوند، اولی زمان آماده سازی مستقل از توالی و دومی زمان آماده سازی وابسته به توالی. در نوع اول معمولاً زمان آماده سازی را بخشی از زمان پردازش کارها در نظر میگیرند که این فرض بیشتر برای ساده سازی مسئله میباشد. ولی این سادهسازی روی کیفیت جوابهای بدست آمده اثر منفی دارد بطوریکه شاید این حلها در محیط صنعتی واقعی کاربردی نداشته باشند. اما نوع دوم که اخیراً در بسیاری از کارهای تحقیقاتی این نوع زمان آماده سازی را در نظر میگیرند، کاربردهای فراوانی در صنایع تولیدی دارد. برای مثال، در یک کارخانه تولیدی که با رنگ سروکار دارند، همواره یک زمان آماده سازی قابل توجهی برای تمیز کردن ماشین برای تغییر رنگ ایجاد میشود. این عملیات، یعنی تمیز کردن ماشینها هم به رنگ قبلی و هم به رنگ بعدی که در حال حاضر به آن نیاز است بستگی دارد. همچنین در صنایع تولیدی که به ابزار، قید و بند و قالب های متفاوتی برای انجام عملیاتهای مختلف نیاز دارند، این نوع زمان آماده سازی بطور ملموسی در فرآیندهای آنها دیده میشود.
امروزه با توجه به محیط رقابتی موجود در بازار ، اکثریت صنایع تولیدی و خدماتی همواره با بیش از یک هدف روبرو هستند که تلاش میکنند آنها را بطور همزمان کمینه کنند. یکی از مهمترین اهدافی که سازمانها همواره در تلاش برای کمینهسازی آن هستند، کاهش هزینههای ناشی از نگهداری موجودی های کارهای در حال پردازش و اختلالات ناشی از کارهای نیمه تمام در کارگاه میباشد. از طرفی دیگر کمینه سازی هزینههای ناشی از عدم پاسخگویی به موقع به نیازهای مشتریان دیگر هدفی است که همواره مورد توجه سازمان ها بوده و هست. از این رو برای دستیابی به هر دو هدف مذکور، در این پژوهش کمینه سازی همزمان دو تابع هدف میانگین وزنی زمان در جریان و میانگین وزنی دیرکرد کارها در نظر گرفته شده است.
1-3- مفروضات عمومی مسئله
1. تمامی ماشینها در لحظه زمانی صفر آماده به کار میباشند.
2. تمامی ماشینها بطور مستمر در دسترس میباشند و امکان خرابی ماشینها وجود ندارد.
3. هر ماشین در هر لحظه قادر به پردازش تنها یک کار میباشد.
4. بیکاری ماشینها مجاز است.