توالی عملیات و زمانبندی

زمانبندی

•منظور از زمانبندی برنامه ریزی کوتاه مدت یا برنامه ریزی کارگاهی است. برای انجام برنامه ریزی کارگاهی دو تصمیم مهم باید اتخاذ شود:

•Assignment problem: تخصیص کارها یا سفارشات به منابع یا ماشین های تولیدی

•Sequencing problem: تعیین توالی انجام کارها روی هر منبع یا ماشین تولیدی 

مثال:

فرض کنید 5 سفارش کاری دارید که قرار است در کارگاهی روی یک ماشین انجام شود. اطلاعات مربوط به زمان انجام ti و موعد تحویل di مطابق جدول زیر است:

اگر برش در کارها ممنوع باشد جمعاً 5!=120 توالی مختلف می توان برای انجام این کارها در نظر گرفت. مطمئنا هر کدام از این توالی ها مقدار تابع هدف متفاوتی دارند.

انجام سفارشات به ترتیب FIFO

زمان ها در حالت FIFO

.1زمان تکمیل کل سفارشات = 55

.2متوسط زمان تکمیل هر سفارش:

3.متوسط تعداد سفارشات در سیستم:

4.متوسط زمانیکه سفارشات دیرتر از موعد تحویل شده اند:

توالی کوتاهترین زمان انجام سفارش  SPT / Shortest Processing Time

زمان ها در حالت SPT

1.زمان تکمیل کل سفارشات = 55

2. متوسط زمان تکمیل هر سفارش:

3.متوسط تعداد سفارشات در سیستم:

4.متوسط زمانیکه سفارشات دیرتر از موعد تحویل شده اند:

توالی عملیات

قرارداد:

•نمایش مسائل توالی عملیات:   n/m/A/B

n= تعداد کارها/سفارشات

m= تعداد ماشین ها

A= ساختار محیط اجرای کار

(چیدمان محیط بصورت های تک ماشین، جریان گروهی، سری)

B= شاخص بهینه سازی

مثال:

100/1/ /Cmax

100/2/F/Cmax

i: اندیس شماره کار (i=1,2,…,n)

j: اندیس شماره ماشین (j=1,2,…,m)

tij= زمان انجام کار i روی ماشین j

ti= زمان انجام کارi

ri= نقطه ایی از زمان که کار i در کارگاه آماده انجام است. Real time

di= موعد تحویل کارiام (due date)

ci= زمان تکمیل کارiام (completion time)

Fi= زمان کار در جریان (مدت گردش کار iام در کارگاه) Flow Time

3.حداکثر زمان تکمیل

•نکته:

معمولا فرض می شود تمام کارها در لحظه صفر در کارگاه موجودند. به همین دلیل ri=0 است در نتیجه Fi=Ci

Li= انحراف زمان تکمیل از موعد تحویل - دیرکردlateness

Ti= (عقب افتادگی) مقدار دیر کرد کار iام                 { Ti= max {0,Li

Wij= زمان انتظار کار iام پشت ماشین jام

Wi= زمان انتظار کار iام

Cmax = زمان تکمیل برنامه Makespan

انواع شاخص ها (معیارهای بهینه سازی) در توالی عملیات

1.میانگین زمان تکمیل کار

2.میانگین مدت گردش کار

4.حداکثر مدت گردش کار

5.میانگین مغایرت زمان تکمیل از موعد تحویل

6.میانگین دیرکرد کارها

7.حداکثر مغایرت زمان تکمیل از موعد تحویل

8.حداکثر دیرکرد مجاز

9.تعداد کارهای با تاخیر 

قضایای توالی و زمانبندی

شاخص های معادل:

دو شاخص بهینه سازی را معادل گویند هرگاه بهینه کردن یکی معادل بهینه کردن دیگری باشد.

• قضیه 1: شاخص‌های زیر معادلند:

• قضیه2:

برای  1<αi<0 شاخص های زیر با هم معادلند:

• قضیه3:

توالی SPT مساله n/1//F را بهینه می کند.

[SPT:   t[1]≤ t[2]≤ t[3]≤….. ≤ t[n

t[ij] : کاری که در نوبت iام توالی قرار دارد.

• نتیجه قضیه 1 و قضیه 3:

توالی SPT مسائل n/1//W و n/1//C و n/1//L را بهینه می کند.

• قضیه4:

مساله n/1//Fw توسط توالی WSPT بهینه می شود.

Wi: وزن (اهمیت) کار iام

مثال

• مساله 1/10 زیر را درنظر بگیرید، برنامه ایی ارائه کنید که:

الف) معیار F را کمینه کند.

ب) معیار W را کمینه کند. (F≡W)

ج)معیار Fw را کمینه کند.(WSPT)

د) مقدار F و W و Fw بهینه را محاسبه کنید.

قضیه5:

توالی SPT مسئله زیر را با شرط 0<α بهینه می کند.

قضیه6:

کمینه سازی تعداد کار در کارگاه (j) با کمینه سازی F معادل است.

(حل مثال قبل و بدست آوردن مقدارj)

بررسی توالی زودترین موعد تحویل Earliest due date / EDD

قضیه7:

توالی EDD مسئله n/1//Lmax را بهینه می کند.

•نتیجه قضیه7:

مسئله n/1//Tmax توسط توالی EDD بهینه می شود.

•تذکر:

عکس نتیجه فوق همیشه درست نیست یعنی ممکن است توالی داشته باشیم که EDD نباشد اما Tmax را بهینه کند.

مثال

در مسئله روبرو توالی ای را پیدا کنید که Lmax را بهینه کند. مقدار Lmax بهینه را بیابید.

الگوریتم هاجسون (Hadgson)

از الگوریتم هاجسون برای کمینه کردن NT(تعداد کارهای با دیرکرد) استفاده می شود.

.1ایجاد برنامه به روش EDD

.2اولین کاری را که در این توالی د یر انجام می شود را در صورت وجود مشخص کنید. j[L]

.3از مابین کارهای مجموعه {j[1],…, j[L]} کاری را که دارای بزرگترین ti است را انتخاب کرده و از توالی خارج می کنیم.

.4برای کارهای باقی مانده محاسبات (Li,Ci) را به روز کنید و به قدم 2 بروید.

.5این عملیات تا جایی ادامه می یابد که در توالی باقی مانده هیچ کاری دیر تمام نشود.

مثال

•در مساله 1/6 روبرو توالی ارائه کنید که تعداد کارکردها با دیرکرد (NT) را کمینه کند.

مساله n کار و m ماشین

مساله nکار و mماشین در محیط فلوشاپ توسط جانسون بررسی شده و برای حالت 2 ماشین و شرایط خاص 3 ماشینی یک الگوریتم ارائه شده است.

الگوریت جانسون مبتنی بر دو قضیه زیر می باشد:

• قضیه8:

برای مسائل n/m/F/B کافی است که مجموعه برنامه هایی که در آنها توالی انجام کار بر روی ماشین اول و دوم یکسان است مورد مطالعه قرار گیرد.

• قضیه9:

برای مسائل n/m/F/B کافی است که مجموعه برنامه هایی که در آنها توالی انجام کار بر روی دو ماشین آخر (یعنی ماشین m و m-1) یکی است مورد مطالعه قرار گیرد.

تذکر:

در توالی عملیات اصطلاحا گفته می شود که قضیه 8 و 9 یک مجموعه غالب تعریف می کنند که بر اساس آن تعداد جواب های موجه قابل بررسی کاهش یافته است.

نتیجه:

با استفاده از دو قضیه فوق می توان نتیجه گرفت که برای مسائل n/2/F/B و n/3/F/B کافی است توالی هایی بررسی شود که توالی انجام کارها روی هر دو یا هر سه ماشین دقیقا یکی باشد.

الگوریتم جانسون برای مساله n/2/F/Fmax

1.دو شمارنده k و L را در نظر بگیرید که در ابتدا L=n و k=1

2.در ابتدا مجموعه کارهای برنامه ریزی نشده را برابر {s={j1,j2,..,jn و مجموعه کارهای برنامه ریزی را برابر j={ } قرار دهید.

3.برای کارهای برنامه ریزی نشده (مجموعهs) قرار دهید:  {ai=min{ti1  و{bi=min{ti2  که ti زمان انجام کار i روی ماشین1 می باشد.

4.اگر کوچکترین مقدار قدم3 مربوط به ai باشد آنگاه: کار ji را در مکان k قرار دهید.  قرار دهید K+1

5.اگر کوچکترین مقدار قدم3 مربوط به bi باشد آنگاه: کار ji را در مکان L قرار دهید. قرار دهید L=L-1

6.مجموعه های s و j را به روز نمائید.                    {j=jU{ji  و  {s=s-{ji

7.اگر s={ } باشد آنگاه متوقف شوید؛ در غیر اینصورت به قدم3 بروید.

مثال

توالی بهینه را برای مساله 7/2/F/Fmax روبرو یافته و سپس مقدار بهینه Fmax  را بدست آورید.

الگوریتم جانسون برای مسئله n/3/F/Fmax

در صورتیکه یکی از دو شرط زیر برقرار باشد آنگاه مسئله 3ماشین به یک مسئله با دو ماشین مجازی تبدیل می شود.

{Min {ti1} ≥ Max {ti2

OR

{Min {ti3} ≥ Max {ti2