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

زمانبندی

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

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

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

مثال:

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

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

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

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

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

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

زمانبندی

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

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

سفارشات به ترتیب FIFO

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

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

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

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

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

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

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

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

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

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

متوسط تعداد سفارشات

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

متوسط دیرکرد

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


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

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

 

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

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

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

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

متوسط تعداد سفارشات در حالت STP

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

متوسط دیرکرد در حالت STP

توالی عملیات

قرارداد:

•نمایش مسائل توالی عملیات:   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<α بهینه می کند.

توالی SPT

قضیه6:

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

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

SPT

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

توالی زودترین موعد تحویل

قضیه7:

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

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

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

•تذکر:

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

توالی EDD

مثال

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

EDD

الگوریتم هاجسون (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 بروید.

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

مثال

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

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

مثال الگوریتم جانسون

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

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

{Min {ti1} ≥ Max {ti2

OR

{Min {ti3} ≥ Max {ti2

 

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

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

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

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

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

سایر مطالب مرتبط از بلاگ
سیستم مدیریت روابط با تامین کنندگان مدیرسان
مدیریت ارتباط با تامین کنندگان، سازمان های امروزی را در افزایش هماهنگی در زنجیره تامین خود، کاهش هزینه های تامین و افزایش بهره وری و رقابت پذیری کمک می کند.
1396/12/17
انواع سیستم های اطلاعاتی از سیستم های MIS تا سیستم های BI
سیستم های اطلاعاتی با اهداف مختلفی توسعه داده می شوند که ا زمیان آنها سیستم های MIS، CRM، ERP، و BIS از اهمیت بیشتری برخوردار هستند.
1396/12/14
معرفی 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

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

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

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

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