(در فایل دانلودی نام نویسنده موجود است) (ممکن است هنگام انتقال از فایل اصلی ...

۱-۲-۳.تعریف برخی از مفاهیم اولیه در زمان‌بندی

زمان پردازش عملیات: ( )

با توجه به موضوع تحقیق ما که در مورد زمان‌بندی یک ماشین با قابلیت پردازش دسته‌ای از کارها است و کارها متعلق به خانواده‌های متفاوت می‌باشند، زمان پردازش به‌صورت زیر تعریف می‌شود:

زمان پردازش کار jام متعلق به خانواده‌ی iام که در دسته‌ی نوبت kام پردازش می‌شود=

زمان دسترسی به کار (r_j):

زمان ورود یک کار به کارگاه برای دریافت سرویس از ماشین که این زمان در واقع زودترین زمان ممکن برای ارائه سرویس به کار مدنظر توسط ماشین می‌باشد.

موعد تحویل(d_j):

زمانی که تولیدکننده متعهد است تا به مشتری سرویس منظوره را ارائه کند. ارائه خدمت به مشتری پس از موعد تحویل برای تولید‌کننده جرایمی را به دنبال دارد.

زمان تکمیل کار(c_j):

زمانی که آخرین فرایند پردازش روی کار j انجام می‌شود یعنی بعد از این زمان کار j آماده‌ی تحویل به مشتری است.

مدت جریان ساخت (f_j):مدت زمانی که کار jام در داخل سیستم تولید قرار دارد که از رابطه ی زیر بدست می‌آید.  f_j = c_j – r_j

تأخیر(L_j): فاصله‌ی بین زمان تحویل یک کار و موعد تحویل آن را تأخیر می‌نامند که از رابطه‌ی L_j=c_j-d_j بدست می آید که اگر مقداری مثبت باشد نشان از دیرکرد و اگر منفی باشد نشان از زودکرد تحویل می‌باشد.

دیرکرد (T_j): دیرکرد کار j  از رابطه‌ی روبرو بدست می‌آید:

یعنی اگر زمان تکمیل بعد از موعد تحویل کاری باشد دیرکرد در واقع همان تأخیر است در غیر این صورت مقدار صفر را می‌گیرد.

زودکرد (E_j): یعنی اگر زمان تکمیل قبل از موعد تحویل کاری باشد زودکرد در واقع قدرمطلق تأخیر است در غیر این صورت مقدار صفر را می‌گیرد.

۱-۳.ضرورت بررسی مسائل و روش‌های بهینه‌سازی چند هدفه

بسیاری از مسائل دنیای واقع، به صورت بهینه سازی چند هدف به‌طور همزمان می‌باشند زیرا متغیرها و اهداف متضاد به‌طور واقعی در ذات این مسائل می‌باشند، یعنی بهبود در یکی از اهداف موجب بدتر شدن در هدف دیگر خواهد شد. بهینه‌سازی این‌گونه مسائل کاملاً متفاوت با مسائل تک‌هدفه خواهد بود یعنی الگوریتم‌های بهینه‌سازی تک‌هدفه، یک حل بهینه را با توجه به تک هدف موجود بدست می‌آورند درحالی‌که درمسائل چندهدفه (با وجود چند هدف متضاد) قادر به بدست آوردن یک حل بهینه مجزا نخواهیم بود، بنابراین طبیعی است که باید به دنبال مجموعه‌ای از حل‌های غلبه نشده مؤثر با توجه به فضای حل برای این نوع از مسائل باشیم تا در اختیار تصمیم گیرنده قرار داده تا با توجه به معیارها و استدلال‌های خود بتواند از میان حل‌های نامغلوب متناهی که در اختیار دارد یک حل متناسب با معیارهایش را انتخاب کند.

۱-۳-۱.تعاریف مرتبط با مسائل چند هدفه

مدل چند هدفه:

یک مسئله تصمیم‌گیری چندهدفه در حالت کلی به زبان ریاضیات به‌صورت زیر تعریف می شود:

s,t: xϵs

یعنی در فضایی شدنی x هر حل x دارای n ارزش به ازای n هدف خواهد بود که با مقایسه‌ی این مقادیر بدست آمده از اهداف می‌تواند رابطه‌های مغلوب و نامغلوب رابرا‌ی حل‌های مختلف تعریف کرد.

مجموعه‌ی حل‌های نامغلوب[۲]:

برای یک مسئله Min سازی، حل x، حل y را غلبه می‌کند اگر و فقط اگر:

مطلب دیگر :

پایان نامه کیفیت خدمات درمانی|اندازه گیری کیفیت خدمات

بنابراین مجموعه‌ی حل‌های نامغلوب بهینه به مجموعه‌ای از حل‌ها گفته می‌شوند که خود حل‌های دیگر را غلبه می‌کنند ولی توسط هیچ حلی غلبه نمی‌شوند. در شکل ۱-۱  دایره‌های تیره مجموعه‌ی حل‌های نامغلوب بهینه‌اند.[۳]

شکل ۱-۱.مجموعه حلهای نامغلوب بهینه

۱-۳-۲.روش‌های حل مسایل چندهدفه

برای حل مسائل چندهدفه به حالات مختلفی برمی‌خوریم که در شکل ۱-۲ زیر نشان داده می شود:

بهینه‌سازی     چند هدفه

جستجو بدون تقدم

ابتدا تصمیم‌گیری سپس جستجو

جستجوو تصمیم‌گیری همزمان

ابتدا جستجو سپس تصمیم‌گیری

ارزیابی  مبتنی بر پارتو

برنامه‌ریزی آرمانی

روش سلسله‌مراتبی

روش اپسیلون محدودیت

ترکیب وزنی اهداف

شکل۱-۲.روش های حل مسائل چندهدفه

جستجو بدون تقدم: در این روش از سوی تصمیم‌گیرنده هیچ تقدمی اعمال نمی‌شود مهمترین روش در این زمینه روش مین-ماکس می‌باشد یعنی حداقل کردن مجموع فواصل هر هدف از مقدار بهینه‌ی آن هدف.

نشانه‌ی فاصله‌ی اقلیدسی

نشانه‌ی نرم فاصله‌ی چپیشف

از معایب این روش خروجی آن است که یک حل را در اختیار تصمیم‌گیرنده قرار داده که ملزم به پذیرش آن خواهد بود.

ابتدا تصمیم‌گیری سپس جستجو:

ابتدا تصمیم‌گیرنده یک اولویت برای اهداف تعیین می‌کند سپس به دنبال یک یا چندین حل با ارضای اولویت تعیین‌شده، جستجو انجام می‌شود.

تصمیم‌گیری و جستجوی همزمان: تصمیم‌گیرنده در این روش مجاز به مداخله در حین جستجو می‌باشد یعنی در طی جستجو قادر به تغییر اولویت‌هاست.

ابتدا جستجو سپس تصمیم‌گیری:

در این روش ابتدا حل‌های متنوع بدست می‌آید سپس تصمیم‌گیرنده از میان جواب‌ها هر کدام را که مناسب‌تر ببیند انتخاب می‌کند.

ترکیب وزنی اهداف:

در این روش ابتدا با تعیین اولویت هر هدف و سپس ترکیب خطی اهداف، مسئله‌ را تک هدفه نموده و سپس آن را حل می‌کنیم.

اپسیلون محدودیت: در این روش ابتدا یک هدف را بعنوان هدف اول مسئله انتخاب کرده و اهداف دیگر را در غالب محدودیت قرار می‌دهیم مشکل‌ این روش نحوه‌ی انتخاب یکی از اهداف به‌عنوان هدف اصلی مسئله است تا الگوریتم یک جواب کارا بدهد.

فرمولاسیون این روش به صورت زیر است: