زمان بندی ماشین های موازی نامرتبط به همراه دوباره کاری با در نظر …

زمانی در قالب یک محدودیت مشاهده میشود که ماشینها بطور مستمر در دسترس نباشند.
۲-۳-۶٫ دسترسی محدود به ماشین ها[۵۰]
این حالت زمانی رخ می دهد که m ماشین بطور موازی در دسترس باشند ولی تنها تعدادی از ماشینها قادر به پردازش کار نوع j باشند. مجموعه شامل ماشینهایی است که قابلیت پردازش کار نوع j را دارند.
۲-۳-۷٫ جایگشت[۵۱]
در شرایطی برقرار است که ترتیب پردازش کارها روی تمامی ماشینها یکسان است. غالبا در مسائل جریان کارگاهی برقرار است.
۲-۳-۸٫ بلوکه شدن[۵۲]
در مسائل جریان کارگاهی با ظرفیت محدود برای بافر، هنگامی که ظرفیت صف بین دو ماشین متوالی تکمیل میشود، کار تکمیل شده بر روی ماشین بالادستی باقی میماند و از پردازش کار بعدی بر روی آن جلوگیری میشود.
۲-۳-۹٫ بدون انتظار[۵۳]
در مسائل جریان کارگاهی، یک کار نبایستی در حین پردازش میان دو ماشین متوقف شود.
۲-۳-۱۰٫ گردش مجدد[۵۴]
در شرایطی برقرار است که در مسائل کار کارگاهی و یا کار کارگاهی منعطف، حداقل یکی از کارها بتواند از یکی از ماشینها و یا یکی از مراکز کاری بیش از یک مرتبه عبور کند.
۲-۳-۱۱٫ گروه های کاری[۵۵]
حالتی است که در آن کارهای تخصیص یافته برای پردازش متعلق به خانوادههای مختلف هستند. زمان پردازش اعضای هر گروه میتواند متفاوت باشد اما آنها میتوانند بصورت متوالی بر روی یک ماشین بدون نیاز به زمان نصب پردازش شوند.
۲-۳-۱۲٫ پردازش دسته ای[۵۶]
در این فرآیند، کارها به صورت دستهایی بصورت همزمان پردازش میشوند. پردازش هر دسته، نیازمند زمان مشخصی است و ممکن است برای تعداد کارهایی که میتوانند در یک زمان پردازش شوند یک محدودیت ظرفیتی وجود داشته باشد.
۲-۴٫ توابع هدف
۲-۴-۱٫ بیشینه زمان تکمیل کارها[۵۷]
به مفهوم زمان تکمیل آخرین کاری است که سیستم را ترک میکند. این ضابطه بهرهوری ماشینآلات را به طرز چشمگیری افزایش میدهد.
۲-۴-۲٫ بیشینه زمان تاخیر کارها[۵۸]
بیشترین انحراف زمانی از موعدهای تحویل کارها را نشان میدهد.
۲-۴-۳٫ مجموع زمان تکمیل کارها[۵۹]
مجموع زمانهای تکمیل کارها را اندازهگیری میکند و سعی بر کمینه کردن آن موجب کاهش هزینههای نگهداری میشود. در ادبیات زمانبندی از کمینهسازی مجموع زمانهای تکمیل کارها با عنوان کمینهسازی مجموع زمانهای در جریان ساخت[۶۰] نیز یاد میشود.
۲-۴-۴٫ مجموع وزنی زمان تکمیل کارها[۶۱]
حالت کلیتر تابع هدف مجموع زمان تکمیل کارها میباشد. در این حالت به کارهای با هزینه نگهداری بیشتر، وزن بالاتری داده میشود.
۲-۴-۵٫ مجموع زمان دیرکرد کارها[۶۲]
مجموع انحرافهای زمانی کارها از موعدهای تحویل را محاسبه مینماید.
۲-۴-۶٫ مجموع وزنی زمان دیرکرد کارها[۶۳]
مجموع انحرافهای زمانی وزنی کارها از موعدهای تحویل را محاسبه مینماید.
۲-۴-۷٫ مجموع تعداد کارهای با تاخیر[۶۴]
تعداد کارهایی که موعد تحویل آنها گذشته است را نشان میدهد.
۲-۴-۸٫ مجموع وزنی تعداد کار های با تاخیر[۶۵]
حالت کلیتر تابع هدف مجموع تعداد کارهای با تاخیر میباشد. در این حالت به کارهایی که از لحاظ اهمیت تحویل در موعد مقرر از درجه اهمیت بالاتری برخوردار هستند، ضرایب وزنی بالاتری داده میشود.
۲-۴-۹٫ مجموع زمان های زودکرد و دیرکرد کارها[۶۶]
این تابع هدف از نوع توابع هدف معمولی که در بالا به آنها اشاره شد نمیباشد چرا که در آنها با اتمام کارها مقدار تابع هدف بصورت غیر نزولی افزایش مییابد ولی تابع هدف مجموع زمانهای زودکرد و دیرکرد از این جنس نمیباشد. در این تابع هدف بهدنبال آن هستیم که کارها تا حد امکان در موعد تحویل مربوطه آماده شوند. از کاربردهای آن می توان به صنایع تولید مواد فاسد شدنی اشاره کرد.
۲-۴-۱۰٫ مجموع وزنی زمانهای زودکرد و دیرکرد کارها[۶۷]
حالت کلیتر تابع هدف مجموع زمانهای زودکرد و دیرکرد کارها میباشد که در آن با توجه به اهمیت هر کار و میزان بحرانی بودن زودکرد و دیرکردد آن نسبت به موعد تحویل، به هر کار دو ضریب وزنی اختصاص مییابد.
۲-۵٫ پیشینه تحقیق
از اواسط قرن گذشته مباحث زمانبندی و توالی عملیات بصورت فزایندهای مورد توجه محققین و دانشمندان قرار گرفت و تحقیقات گستردهای در این حیطه صورت پذیرفت. از آنجایی که این مسائل در دنیای واقعی عموما دارای تعداد زیادی فعالیت و منبع میباشند، در نتیجه یک مجموعه گوناگون از اهداف و محدودیت بهرهبرداری از منابع در مورد آنها مطرح میشود. به همین دلیل است که تلاشهای انجام شده بهمنظور حل برنامهریزی ریاضی و یا حتی فرموله نمودن آن ها وقت گیر و پر زحمت میباشد. یکی از انواع مسائل مورد بررسی در این زمینه، مسئله زمانبندی ماشینهای موازی میباشد که از نقطه نظر تئوری و تجربی دارای اهمیت فراوانی میباشد. از دیدگاه آکادمیک، اهمیت مسئله زمانبندی ماشینهای موازی از آنجایی است که این مسئله حالت عمومیت یافته مسئله زمانبندی تک ماشینه و حالت خاصی از مسائل زمانبندی جریان کارگاهی منعطف و کار کارگاهی منعطف میباشد. از نقطه نظر تجربی نیز اهمیت این مسئله در آن است که در بسیاری از محیطهای تولیدی و خدماتی وضعیت قرار گیری ماشینها (اپراتورها) نسبت به یکدیگر بصورت یکی از انواع سه گانه مسائل ماشینهای موازی میباشد.
در این تحقیق، مسئله زمانبندی ماشینهای موازی نامرتبط با

دانلود متن کامل پایان نامه در سایت jemo.ir موجود است

فرض وجود امکان دوبارهکاری اقلام معیوب بههمراه محدودیتهای زمان دسترسی به کارها، زمان نصب وابسته به توالی کارها و وابسته به نوع ماشینآلات و دسترسی محدود به ماشینها با هدف کمینهسازی بیشترین زمان تکمیل کارها مورد مطالعه قرار میگیرد. در ادامه به منظور مروری بر ادبیات و مطالعات صورت پذیرفته، تحقیقات مرتبط با مسئله مورد بررسی در این تحقیق به تفکیک نوع محیط کارگاهی و محدودیتهای قید شده در صورت مسئله در بخشهای جداگانهای آدرسدهی میشوند. بدلیل گستردگی مطالب در ادبیات زمانبندی، در این تحقیق سعی بر آن است که در بخش بررسی محدودیتها، تحقیقاتی مورد بررسی قرار بگیرند که در حیطه مسائل زمانبندی ماشینهای موازی بویژه ماشینهای موازی نامرتبط میباشند.
۲-۶٫ ماشینهای موازی نامرتبط
مسئله زمانبندی ماشینهای موازی، یکی از پرکاربرد ترین مسائل زمانبندی در سیستمهای تولیدی و خدماتی میباشد و در سه گروه ماشینهای موازی یکسان، ماشینهای موازی یکنواخت و ماشینهای موازی نامرتبط دستهبندی میشود. در یک تعریف ساده، مسئله زمانبندی ماشینهای موازی بدین صورت بیان میشود که یک مجموعه از n کار متمایز، ، بر روی مجموعه ای از m ماشین موجود و در دسترس، ، که بصورت موازی نسبت به هم قرار گرفتهاند پردازش میشوند. هر کار تنها بر روی یک ماشین پردازش میشود و هر ماشین در هر لحظه قادر به انجام تنها یک کار میباشد.
در سالهای اخیر، یک مطالعه جامع و کامل بر روی مسائل زمانبندی توسط الله وردی و همکاران ]۶[ صورت پذیرفت. آنها یک مرور کامل بر مسائل تک ماشینه، ماشینهای موازی، جریان کارگاهی، جریان کارگاهی بدون تاخیر[۶۸] ، جریان کارگاهی منعطف، کار کارگاهی و سیستم کارگاهی باز انجام دادند و آنها را در دو قالب پردازش دستهای و غیر دستهای[۶۹] و زمان نصب وابسته به توالی و زمان نصب مستقل از توالی[۷۰] واکاوی کردند. یکی از اولین تحقیقات در زمینه مسائل زمانبندی ماشینهای موازی توسط مک ناتن ]۷[ در اواخر دهه پنجاه میلادی صورت پذیرفت. همچنین محققان دیگری همچون موکوتوف ]۸[ ،لام و ژینگ ]۹[ و چنگ و سین ]۱۰[ بررسیها و مطالعاتی بر روی مسائل ماشینهای موازی انجام دادند ولی بیشتر این تحقیقات در زمینه مسائل ماشینهای موازی یکسان بود و مسائل ماشینهای موازی نامرتبط در حجم بسیار کمتری مورد مطالعه قرار میگرفت. در ادامه این بخش، تعدادی از تحقیقات صورت پذیرفته در زمینه مسائل ماشینهای موازی نامرتبط آدرسدهی میشوند.