سایر مطالب مرتبط در مقالات پایه
1

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

دسته بندی برنامه‌ریزی کوتاه مدت از حوزه مدیریت عملیات

زمانبندی

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

•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

Fi = ci - ri

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

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)

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

 

 

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

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

•قضیه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

نظرات کاربران

توسط محمد رضا علیخواصی | در 1 سال و 6 ماه قبل
توسعه ی علم و آگاهی بهترین راه برای پرهیز از عقب ماندگی. و شما پیشگام در این مسیر.

نظر شما در مورد این مطلب

جهت ثبت نظرات، ابتدا باید در سایت وارد شوید.

درباره مدیرسان


مدیرسان ارتباطی میان دانشگاه و صنعت


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

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