92

 

4-2- تولید مساله نمونه 93

 

4-3- تنظیم پارامترهای الگوریتم   94

 

4-4- معیار های عملکرد 95

 

4-4-1- شاخص زمان محاسباتی 95

 

4-4-2- روش های اندازه گیری عملکرد الگوریتم 95

 

4-5- جمع بندی 101

 

فصل 5- نتیجه گیری و پیشنهادات آتی 102

 

5-1- نتیجه گیری 103

 

5-2- پیشنهادات آتی 104

 

       فهرست منابع و مراجع 105

 

زمانبندی

 

زمان، همواره یك محدودیت مهم و اساسی بوده است. انسان ها سعی می كنند فعالیت هایشان را به گونه ای زمانبندی كنند كه بتوانند كارهایشان را در زمان دسترس انجام دهند. به طور كلی زمانبندی، عمل تعیین توالی یاترتیب فعالیت ها برای ارضای نیازمندی ها و نیل به اهداف مشخص با توجه به محدودیت های موجود است. به صورت دقیق تر زمانبندی را می توان تخصیص منابع در طول زمان برای اجرای مجموعه ای از وظایف تعریف كرد. این تعریف نسبتاً كلی، دو مفهوم مختلف را در پی دارد. اول این كه زمانبندی نوعی تصمیم گیری است كه در جریان آن برنامه زمانی را تعیین می كنند كه پیامدهای آن را می توان در تصمیم گیری های دیگر نیز استفاده كرد. از طرف دیگر، زمانبندی مبحثی نظری است كه مجموعه ای از اصول، مدل ها، روش ها و نتایج منطقی را در بر می گیرد.

 

1-1-1- اهمیت و ضرورت زمانبندی تولید

 

زمانبندی، مشخص می كند چه موقع زمان پردازش هر كار روی هر یك از ماشین هایی كه آن كار در فرآیند تولید خود به آن نیاز دارند، آغاز می شود. به علاوه، این برنامه زمان پایان هر كار را روی هر ماشین تعیین می كند. بنابراین نتیجه فرآیند زمانبندی، یك جدول زمانی برای كارها و ماشین هاست. زمان شروع اولین فرایند هر كار باید بزرگتر یا مساوی زمان ورود آن كار به كارگاه باشد. از طرف دیگر در صورتی كه برای محصولی، موعد تحویل در نظر گرفته شده است، زمان پایان آخرین فرایند آن محصول حتی الامكان نباید از این زمان تجاوز كند. زمانبندی تولید را می توان به صورت تعیین توالی زمانی و تخصیص سفارشات مشتریان به منابع موجود تولید (اعم از پرسنل، ماشین آلات، ابزار و غیره) به منظور انجام مجموعه ای از عملیات مربوطه تعریف كرد.

 

1-1-2- معیارهای كارایی زمانبندی

 

 معمولاً زمانبندی با توجه به اهدافی نظیر دستیابی به موعدهای تعهد شده، كمینه سازی زمان كار در جریان ساخت و موجودی كار در جریان ساخت، بیشینه سازی خروجی و بهره برداری بیشتر از مراكز كاری انجام می شود. قابل ذكر است كه ممكن است این اهداف با یكدیگر در تناقض باشند. لذا در مسائل زمانبندی ممكن است به لحاظ تكنیكی مشكلاتی رخ دهد.

 

1-1-3- اطلاعات مورد نیاز در زمانبندی

 

در عمل برنامه های زمانبندی با استفاده از الگوریتم ها و یا روش های قاعده مند ایجاد می شوند. الگوریتم های زمانبندی برنامه ها را باهدف بهینه سازی یك یا چند معیار مانند حداقل سازی انحراف از موعد تحویل، حداقل سازی هزینه دیر كرد و… تولید می كنند روش های قاعده مند سعی در یافتن یك برنامه زمانی شدنی در محیط عملیاتی تولید دارند.

 

اطلاعات برنامه زمانبندی، به اشكال مختلفی نمایش داده می شوند. نمودار گانت كه اولین بار توسط هنری گانت در اواخر قرن نوزدهم معرفی و برنامه زمانبندی مورد استفاده قرار گرفت، همچنان یكی از رایج ترین ابزارهای نمایش اطلاعات برنامه زمانبندی است.

 

بر این اساس مسائل زمانبندی را می توان به صورت زیر دسته بندی نمود.

 

 

خرید متن کامل این پایان نامه در سایت nefo.ir

 

• کارگاه تک ماشین[1] : فقط یک ماشین در دسترس بوده و هر کار فقط به یک عملیات نیاز دارد.

 

• کارگاه جریان کاری یا کارگاه جریان کاری مرتب[2] : تعداد g ماشین متوالی وجود دارد و هر کار می بایست روی هر ماشین با همان توالی (یک مسیر تولید) پردازش شود.

 

• کار کارگاهی: هر کار به چند عملیات نیاز دارد. جمعا به تعداد g ماشین متوالی وجود دارد و هر کار مسیر تولید خاص خود را دارد.

 

• کارگاه عمومی[3] : هر کار به چند عملیات نیاز دارد. جمعا به تعداد g ماشین وجود دارد، اما الگوی جریان معین نیست. به عبارت دیگر در انجام یک کار ممکن است از یک ماشین چندبار استفاده شود.

 

• ماشین های موازی[4]: هر کار تک عملیاتی بوده و در هر مرحله چندین ماشین برای انجام فرایند در دسترس است. در این حالت ماشین ها می توانند یکسان (I)، یکنواخت (U)، و یا نا مرتبط ® باشند.

 

• کارگاه جریان کاری مختلط: این حالت تعمیم یافته حالت محیط کارگاه جریان کاری و ماشین های موازی است. در اینجا g کارگاه متوالی وجود دارد که در مرحله t آن به تعداد mt ماشین بطور موازی کار می کنند. در هر کارگاه، یک کار حداکثر روی یک ماشین می تواند انجام شود.

 

• کار کارگاهی با ماشین های دوتایی[5] (کارگاهی منعطف): این حالت تعمیم یافته محیط کار کارگاهی و ماشین های موازی است. در اینجا g کارگاه وجود دارد که mtماشین موازی در کارگاه t کار می کنند. در هر کارگاه، یک کار حداکثر روی یک ماشین می تواند پردازش شود.

 

• کارگاه جریان کاری مونتاژ دو مرحلهای: این محیط، حالت خاصی از کارگاه جریان کاری مختلط میباشد که در آن است و تعداد ماشینها در مرحلۀ اول برابرm و در مرحلۀ دوم (مرحلۀ مونتاژ) برابر یک میباشد.

شکل 1-1. دسته بندی مسائل زمانبندی بر اساس مسیر تولید]1[

 

در شکل(1-1) رابطه بین محیط های مختلف نشان داده شده است. در این نمودار هر کمان ازP1 به P2 ،بدین معنی است که P2 حالت خاصی از P1 است و یا به عبارت دیگر P1 شکل تعمیم یافته P2 است

 

* رویدادهای زمان واقعی مرتبط با منابع

 

این رویدادها در ارتباط با منابع سیستم از جمله خرابی ماشین، تعمیرات و نگهداری، بیماری اپراتور، تاخیر در ورود یا كمبود مواد، خرابی ابزار، محدودیت در بارگذاری ماشین، خرابی مواد و غیره هستند.

 

* رویدادهای زمان واقعی مرتبط با كار

 

این رویدادها در ارتباط با كارهای ورودی به سیستم از جمله تغییر در موعد تحویل، تغییر در زمان پردازش، تغییر در اولویت كار، زمان ورود تصادفی غیر صفر و غیره می باشند.

 

1-2- تعریف برخی از مفاهیم اولیه

 

زمان پردازش هر عملیات[6] (Ptij)

 

زمان انجام عملیات برای كار i روی ماشین j در مرحله t را نشان می دهد در حالتی كه زمان پردازش عملیات مستقل از ماشین های موجود در یك مرحله باشد و یا عملیات فقط به روی یك ماشین انجام شود، نماد j حذف می شود.

 

زمان دسترسی به كار[7] (ri)

 

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

 

موعد تحویل (di)

 

زمانی است كه تولید كننده متعهد به تحویل كار به مشتری نهایی است تحویل كار به مشتری پس از موعد تحویل امكان پذیر است ولی تولید كننده بایستی جریمه ای را بابت دیر كرد بپردازد.

 

زمان تكمیل كار (Ci)

 

زمانی است كه آخرین پردازش مورد نیاز برای تكمیل كار i به اتمام می رسد. پس از این مرحله، محصول نهایی آماده ی تحویل به مشتری است.

 

مدت جریان ساخت (Fi)

 

مدت زمانی است كه كار i در سیستم قرار دارد. مدت جریان ساخت كار i از رابطه   Fi=C- ri i به دست می آید.

 

تاخیر (Li)

 

فاصله زمانی بین تكمیل یك كار و موعد تحویل آن را تاخیر می نامند. در صورتی كه زمان تكمیل كاری قبل از موعد تحویل آن باشد. مقدار تاخیر آن كار، منفی و در صورتی كه كاری بعد از موعد تحویل آن تكمیل شود، تاخیر آن كار، مثبت خواهد بود. تاخیر كار i از رابطه Li = Ci – di محاسبه می شود كه در این رابطه Ci زمان تكمیل كار i و di مدت زمان تحویل كار i می باشد.

 

دیر كرد (Ti)

 

دیر كرد كار i از رابطه Ti = max { 0 , Ci –di } به دست می آید به این ترتیب كه اگر كار i بعد از موعد تحویل آن تحویل شود، دیر كرد، تاخیر كار یا همان Li می باشد و در غیر این صورت دیركرد را صفر در نظر می گیرند.

 

زودكرد (Ei)