فصل اول: مقدمه و کلیات تحقیق 1

1-1- زمانبندی 2

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

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

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

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

1-3- نگهداری و تعمیرات 9

1-3-1- اهمیت نگهداری و تعمیرات و نقش آن در سازمان 10

1-3-2- سیستم ها و روش های نت 10

1-3-2-1- سیستم های غیر برنامه ای واکنشی 11

1-3-2-2-سیستم های برنامه ای 11

1-3-2-3- نت پیشگیرانه 11

1-3-2-3-1- تعمیرات منظم دوره ای 11

1-3-2-3-2- تعمیرات پیشگویانه 12

1-3-2-4- نگهداری و تعمیرات اصلاحی   12

1-3-2-5-تعمیرات اساسی 12

1-3-2-6- سیستم های نت فراگیر و جامع 13

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 آن به تعداد 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)

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