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

زمانبندی

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

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

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

این خدمات را از مشاوان مدیرسان بخواهید:

انجام مطالعات امکانسنجی و تهیه طرح های توجیهی اولین و مهمترین مرحله هر کسب و کاری است که ضامن انتخاب بهینه توجیه پذیری فنی و اقتصادی یک پروژه است. مدیرسان شما را در تهیه یک طرح توجیهی مناسب یاری می رساند تا از خطر شروع یک کسب و کار غیر اقتصادی دوری کنید.

اطلاعات بیشتر

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

اطلاعات بیشتر

مثال:

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

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

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

 

نمونه ای از پروژه های تیم مشاوران مدیرسان

طراحی، پیاده سازی و استقرار سیستم یکپارچه مدیریت ارتباط با تامین کنندگان شرکت افق کوروش

اطلاعات بیشتر

استقرار و راهبری سیستم مدیریت هزینه بر اساس تکنیک ارزش کسب شده (EVM) در شرکت پیمانکاری آسفالت طوس

اطلاعات بیشتر

 

انجام سفارشات به ترتیب 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

سیستم های اطلاعاتی

تجزیه و تحلیل سیستم ها

برنامه ریزی و کنترل تولید

مدیریت کیفیت و بهره وری

مدیریت عمومی و منابع انسانی

سایر مطالب مرتبط از بلاگ
معرفی SAP ERP و امکانات آن
SAP به عنوان بهترین سیستم مدیریت منابع سازمانی یکپارچه شناخته شده و بر اساس رتبه بندی برترین شرکت های دنیا، این شرکت به عنوان سومین شرکت تولید کننده نرم افزار در جهان می باشد.
1396/11/23
توصیف کلی مدیریت منابع انسانی
معرفی فرایند کلی جذب و توسعه و سرمایه های انسانی سازمان
1396/11/15
خلاصه کتاب مدیریت نگرش
خلاصه کتاب مدیریت نگرش
1394/5/10
خلاصه کتاب کلیدهای طلایی مدیریت منابع انسانی
خلاصه کتاب کلیدهای طلایی مدیریت منابع انسانی
1394/5/10
خلاصه کتاب رقص تغییر
خلاصه کتاب رقص تغییر
1394/5/10
خلاصه کتاب "چگونه چون یک مدیر عالی بیندیشیم"
خلاصه کتاب "چگونه چون یک مدیر عالی بیندیشیم"
1394/5/10
خلاصه کتاب تحول
خلاصه کتاب تحول
1394/5/10
خلاصه کتاب پنجمین فرمان
خلاصه کتاب پنجمین فرمان
1394/5/10
نگهداری و تعمیرات
نگهداری و تعمیرات
1394/5/3

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

توسط محمد رضا علیخواصی

توسعه ی علم و آگاهی بهترین راه برای پرهیز از عقب ماندگی. و شما پیشگام در این مسیر.

نظر خودتان را بنویسید