1-2.تعریف زمان‌بندی

 

 

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

 

 

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

 

 

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

 

 

1-2-1. ضرورت زمان‌بندی تولید

 

 

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

 

 

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

 

 

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

 

 

1-2-2. اهداف زمان‌بندی

 

 

معمولاً اهدافی که مراکز صنعتی در زمینه‌ی زمان‌بندی فعالیت‌هایشان دنبال می‌کنند شامل دست‌یابی به موعد تحویل سفارشات (تولید بهنگام)[1] یا حداقل سازی زمان فعالیت خط تولید و یا حداکثرسازی تعداد خروجی و بهره‌وری بیشتر از خط تولید و … می‌باشند که در جدول ۱-۱ تعدادی از این اهداف و معیارها معرفی می‌شوند که گاهی اوقات تعدادی از این اهداف در تناقض با هم‌دیگر می‌باشند.

 

 

جدول ۱-۱.اهداف رایج در زمان بندی

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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ام پردازش می‌شود=

 

 

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

 

 

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

 

 

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

 

 

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

 

 

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

 

 

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

 

 

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

 

 

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

 

 

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

 

 

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

 

 

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

 

 

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 ≤ ej      j≠i      j=1,2,…,k

 

 

xϵX

 

 

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

 

 

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

 

 

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

 

 

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

 

 

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

 

 

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

 

 

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

 

 

[1] Just in tim

 

 

[2] Non dominated

 

 

[3]