Notation	discription
C max	Maximum completion time
F max	Maximum flow time
L max	Maximum lateness
T max	Maximum tardiness
E max	Maximu earliness
	Total completion time
	Total weighted completion time
	Total flow time
	Total weighted flow time
	Total tardiness
	Total weighted tardiness
	Number of tardy job
	Total weighted number of tardy job

 

1-2-3.تعریف برخی از مفاهیم اولیه در زمان‌بندی

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

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

زمان پردازش کار 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): یعنی اگر زمان تکمیل قبل از موعد تحویل کاری باشد زودکرد در واقع قدرمطلق تأخیر است در غیر این صورت مقدار صفر را می‌گیرد.

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

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

 

یک مطلب دیگر :

 

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

مدل چند هدفه:

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

s,t: xϵs

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

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

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

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

 

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

 

1-3-2.روش‌های حل مسایل چندهدفه

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

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

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

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

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

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

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

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

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

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

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

 

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

 

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

 

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

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

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

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

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

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

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

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

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

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

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

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

s.t

fj ≤ e_j      j≠i      j=1,2,…,k

xϵX

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

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

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

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

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

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