1-3-2-6-1- تعمیرات و نگهداری مبتنی بر قابلیت اطمینان 13

1-3-2-6-2- سیستم نگهداری و تعمیرات بهره ور فراگیر 14

1-4- نظام تولید بهنگام 15

1-5- استهلاک و زمانبندی 16

1-6- مشخصات مساله ماشین های موازی این مطالعه 18

1-7- روش حل 19

1-8- اهداف تحقیق 20

1-9- جمع بندی 20

فصل 2- ادبیات و پیشینه تحقیق 22

2-1- مقدمه 23

2-2- مروری بر رویکرد و اصول سیستم های تولیدی JIT 26

2-3- توالی ماشین های موازی با معیار دیرکرد 29

2-3-1-حداقل کردن کل دیرکرد 29

2-3-2- حداقل کردن دیرکرد وزنی 31

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

2-5- مسائل با تمرکز بر زمان آماده سازی بین کارها 33

2-6- مسائل با تمرکز بر موعد تحویل یکسان برای کارها 34

2-6-1- موعد تحویل معلوم 35

2-6-2- موعد تحویل نا معلوم 35

2-7- مروری بر مطالعات زمانبندی با اثر استهلاک 36

2-8- روش های حل 37

2-8-1- مروری الگوریتم های ابتکاری 37

2-8-2- مروری الگوریتم های فرا ابتکاری 37

2-9- مروری بر کارهای انجام شده 38

فصل 3- روش تحقیق 39

3-1- مقدمه 40

3-2-مدل ریاضیپیشنهادی 41

3-2-1- اندیس­ها 41

3-2-2- پارامترهای ورودی 42

3-2-3- متغیرهای تصمیم 42

3-2-4- ساختار اصلی مدل 43

3-2-5-اعتبار سنجیمدل 46

3-3- ساختار کلی الگوریتم های تکاملی 46

3-4- الگوریتم ژنتیک 47

3-4-1- تعریف 47

3-4-2- گذری برژنتیک طبیعی 49

3-4-3- واژگان الگوریتم ژنتیک 56

3-4-4- ساختار کلی الگوریتم ژنتیک 57

3-4-5-مفاهیم کلیدی الگوریتم ژنتیک 60

3-4-6- کدینگ 60

3-4-7- ایجاد جمعیت اولیه 63

3-4-8- اعمال ژنتیک 64

3-4-8-1- عملگر جهشی 64

3-4-8-2- عملگر تقاطعی 65

3-4-8-3- عمل تحول 66

3-4-8-3-1- فضای نمونه گیری 67

3-4-8-3-2- مکانیسم نمونه گیری 68

3-4-8-3-3- احتمال انتخاب 70

3-4-9- تابع برازش 70

3-4-10 – روش اجرای الگوریتم ژنتیک 71

3-4-11- استرتتژی برخورد با محدودیت ها 73

3-4-11-1- استرتتژی اصلاح عملگرهای ژنتیک 74

3-4-11-2- استرتتژی ردی 74

3-4-11-3- استرتتژی اصلاحی 74

3-4-11-4- استرتتژی جریمه ای 75

3-4-12- انواع عملگر های تقاطعی 76

3-4-12-1- یک نقطه برش 76

3-4-12-2- دو نقطه برش 77

3-4-12-3- چند نقطه برش 77

3-4-12-4- بخش- نگاشته 78

3-4-12-5- ترتیب 79

3-4-13- عملگر های جهشی 80

3-4-13-1- جابجایی 81

3-4-13-2- وارونگی 82

3-4-13-3- جایگذاری 82

3-4-13-4- تغییر مکان 83

3-4-13-5- ابتکاری 83

3-10- ساختار الگوریتم ژنتیک پیشنهادی 84

3-10-1- ساختار کروموزوم 84

3-10-2- جمعیت اولیه 85

3-10-3- تابع برازش 86

3-10-4- عملگر تقاطع 86

3-10-5- عملگر جهش 88

3-10-6- ارزیابی فرزندان 89

3-10-7- جستجوی محلی 89

3-10-8- معیار توقف 89

3-11- جمع بندی 90

فصل 4- محاسبات و یافته های تحقیق 91

4-1- مقدمه 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- اطلاعات مورد نیاز در زمانبندی

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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