كلمات كليدي : زمانبندی بهنگام، ماشینهای موازی مستقل، اثرات استهلاک، نگهداری و تعمیرات چندگانه AbstractMaintenance of machines oftenly prevents their breakdowns to keep their production yield. In this study just in time scheduling problem on the parallel machines with depreciation on the processing time of jobs and multiple maintenance activities in the period of scheduling are considered. After maintenance activity, machines return to their initial condition. The objective is calculating number of optimal times, the optimal time of maintenance activities and optimal sequencing due to minimizing the earliness, tardiness and maintenance costs. The mathematical model is presented for this problem; this problem is Np-Hard therefore genetic algorithm(GA) for solving this problem in the large scale is used to reach good solution. The computational results are analyzed.Key words:JIT-Scheduling , Unrelated parallel machines, Aging effects, Multi-maintenance activity فهرستفصل اول: مقدمه و کلیات تحقیق11-1- زمانبندی21-1-1- اهمیت وضرورت زمانبندی تولید21-1-2- معیارهای کارایی زمانبندی31-1-3- اطلاعات مورد نیاز در زمانبندی 31-2- تعریف برخی از مفاهیم 71-3-نگهداری و تعمیرات91-3-1- اهمیت نگهداری و تعمیرات و نقش آن در سازمان101-3-2- سیستم ها و روش های نت101-3-2-1- سیستم های غیر برنامه ای واکنشی111-3-2-2-سیستم های برنامه ای111-3-2-3- نت پیشگیرانه111-3-2-3-1- تعمیرات منظم دوره ای111-3-2-3-2- تعمیرات پیشگویانه 121-3-2-4- نگهداری و تعمیرات اصلاحی 121-3-2-5-تعمیرات اساسی 121-3-2-6- سیستم های نت فراگیر و جامع131-3-2-6-1- تعمیرات و نگهداری مبتنی بر قابلیت اطمینان131-3-2-6-2- سیستم نگهداری و تعمیرات بهره ور فراگیر141-4- نظام تولید بهنگام151-5- استهلاک و زمانبندی 161-6- مشخصات مساله ماشین های موازی این مطالعه181-7- روش حل191-8- اهداف تحقیق201-9- جمع بندی 20فصل 2- ادبیات و پیشینه تحقیق222-1- مقدمه232-2- مروری بر رویکرد و اصول سیستم های تولیدی JIT262-3- توالی ماشین های موازی با معیار دیرکرد292-3-1-حداقل کردن کل دیرکرد292-3-2- حداقل کردن دیرکرد وزنی312-4- توالی ماشین های موازی با معیار زودکرد و دیرکرد 322-5- مسائل با تمرکز بر زمان آماده سازی بین کارها 332-6- مسائل با تمرکز بر موعد تحویل یکسان برای کارها 342-6-1- موعد تحویل معلوم352-6-2- موعد تحویل نا معلوم 352-7- مروری بر مطالعات زمانبندی با اثر استهلاک 362-8- روش های حل 372-8-1- مروری الگوریتم های ابتکاری372-8-2- مروری الگوریتم های فرا ابتکاری372-9- مروری بر کارهای انجام شده 38فصل 3- روش تحقیق 393-1- مقدمه403-2- مدل ریاضی پیشنهادی413-2-1- اندیسها 413-2-2- پارامترهای ورودی423-2-3- متغیرهای تصمیم 423-2-4- ساختار اصلی مدل433-2-5- اعتبار سنجی مدل463-3- ساختار کلی الگوریتم های تکاملی463-4- الگوریتم ژنتیک473-4-1- تعریف473-4-2- گذری برژنتیک طبیعی493-4-3- واژگان الگوریتم ژنتیک563-4-4- ساختار کلی الگوریتم ژنتیک573-4-5-مفاهیم کلیدی الگوریتم ژنتیک603-4-6- کدینگ603-4-7- ایجاد جمعیت اولیه 633-4-8- اعمال ژنتیک 643-4-8-1- عملگر جهشی643-4-8-2- عملگر تقاطعی653-4-8-3- عمل تحول 663-4-8-3-1- فضای نمونه گیری673-4-8-3-2- مکانیسم نمونه گیری683-4-8-3-3- احتمال انتخاب 703-4-9- تابع برازش703-4-10 - روش اجرای الگوریتم ژنتیک713-4-11- استرتتژی برخورد با محدودیت ها 733-4-11-1- استرتتژی اصلاح عملگرهای ژنتیک 743-4-11-2- استرتتژی ردی 743-4-11-3- استرتتژی اصلاحی743-4-11-4- استرتتژی جریمه ای 753-4-12- انواع عملگر های تقاطعی763-4-12-1- یک نقطه برش 763-4-12-2- دو نقطه برش 773-4-12-3- چند نقطه برش 773-4-12-4- بخش- نگاشته 783-4-12-5- ترتیب 793-4-13- عملگر های جهشی 803-4-13-1- جابجایی 813-4-13-2- وارونگی 823-4-13-3- جایگذاری 823-4-13-4- تغییر مکان 833-4-13-5- ابتکاری 833-10- ساختار الگوریتم ژنتیک پیشنهادی843-10-1- ساختار کروموزوم843-10-2- جمعیت اولیه853-10-3- تابع برازش863-10-4- عملگر تقاطع863-10-5- عملگر جهش883-10-6- ارزیابی فرزندان893-10-7- جستجوی محلی893-10-8- معیار توقف893-11- جمع بندی90فصل 4- محاسبات و یافته های تحقیق914-1- مقدمه924-2- تولید مساله نمونه934-3- تنظیم پارامترهای الگوریتم 944-4- معیار های عملکرد 954-4-1- شاخص زمان محاسباتی 954-4-2- روش های اندازه گیری عملکرد الگوریتم 954-5- جمع بندی101فصل 5- نتیجه گیری و پیشنهادات آتی 1025-1- نتیجه گیری1035-2- پیشنهادات آتی104فهرست منابع و مراجع105 لیست شکل هاشکل 1-1. دسته بندی مسائل زمانبندی بر اساس مسیر تولید6شکل 3-1. فرایند مدل تئوری داروین52شکل 3-2. فضای کدینگ و فضای جواب62شکل 3-2. قانونمندی و موجه بودن63شکل 3-4. ساختار دو بخش و نحوه کدگشایی کروموزوم 85شکل 3-5. نحوه عملکرد عملگر تقاطع 87شکل 3-6. شبه نمایش و نخوه علکرد عملگر جهش88شکل 4-1. نمودار RPD98شکل 4-2. نمودار زمان محاسباتی الگوریتم ژنتیک 99 لیست جداولجدول3-1. داده مقایسه الگوریتم ژنتیک با فرآیند تکامل55جدول4-1. بازه های توزیع یکنواخت مناسب برای پارامترهای ورودی مساله 93جدول4-2. پارامترهای مناسب الگوریتم ژنتیک94جدول4-3. نتایج بدست آمده از روش دقیق و الگوریتم ژنتیک97 فصل اول مقدمه وکلیات تحقیق 1-1- زمانبندي زمان، همواره يك محدوديت مهم و اساسي بوده است. انسان ها سعي مي كنند فعاليت هايشان را به گونه اي زمانبندي كنند كه بتوانند كارهايشان را در زمان دسترس انجام دهند. به طور كلي زمانبندي، عمل تعيين توالي ياترتيب فعاليت ها براي ارضاي نیازمندي ها و نيل به اهداف مشخص با توجه به محدوديت هاي موجود است. به صورت دقيق تر زمانبندي را مي توان تخصيص منابع در طول زمان براي اجراي مجموعه اي از وظايف تعريف كرد. اين تعريف نسبتاً كلي، دو مفهوم مختلف را در پي دارد. اول اين كه زمانبندي نوعي تصميم گيري است كه در جريان آن برنامه زماني را تعيين مي كنند كه پيامدهاي آن را مي توان در تصميم گيري هاي ديگر نيز استفاده كرد. از طرف ديگر، زمانبندي مبحثي نظري است كه مجموعه اي از اصول، مدل ها، روش ها و نتايج منطقي را در بر مي گيرد. 1-1-1- اهميت و ضرورت زمانبندي توليد با ادامه فرايند صنعتي شدن جهان، منابع بيشتري حالت بحراني به خود مي گيرند. امروزه ماشين آلات، نيروي انساني و تسهيلات به عنوان منابع بحراني در توليد و فعاليت هاي خدماتي در نظر گرفته مي شوند. زمانبندي اين منابع منجر به ارتقاء كارايي، بهره وري و در نهايت، سودآوي مي شود. فعاليت هاي زمانبندي مي تواند گستره ي وسيعي از فعاليت ها را در برگيرند. كه از آن جمله كار با كاغذ و مداد، نرم افزارهاي صفحه گسترده، ترسيم نمودارها و دياگرام ها تا كار با الگوريتم ها و نظريه هاي پيچيده را مي توان نام برد.زمانبندي، مشخص مي كند چه موقع زمان پردازش هر كار روي هر يك از ماشين هايي كه آن كار در فرآيند توليد خود به آن نياز دارند، آغاز مي شود. به علاوه، اين برنامه زمان پايان هر كار را روي هر ماشين تعيين مي كند. بنابراين نتيجه فرآيند زمانبندي، يك جدول زماني براي كارها و ماشين هاست. زمان شروع اولين فرايند هر كار بايد بزرگتر يا مساوي زمان ورود آن كار به كارگاه باشد. از طرف ديگر در صورتي كه براي محصولي، موعد تحويل در نظر گرفته شده است، زمان پايان آخرين فرايند آن محصول حتي الامكان نبايد از اين زمان تجاوز كند. زمانبندي توليد را مي توان به صورت تعيين توالي زماني و تخصيص سفارشات مشتريان به منابع موجود توليد (اعم از پرسنل، ماشين آلات، ابزار و غيره) به منظور انجام مجموعه اي از عمليات مربوطه تعريف كرد. 1-1-2- معيارهاي كارايي زمانبندي معمولاً زمانبندي با توجه به اهدافي نظير دستيابي به موعدهاي تعهد شده، كمينه سازي زمان كار در جريان ساخت و موجودي كار در جريان ساخت، بيشينه سازي خروجي و بهره برداري بيشتر از مراكز كاري انجام مي شود. قابل ذكر است كه ممكن است اين اهداف با يكديگر در تناقض باشند. لذا در مسائل زمانبندي ممكن است به لحاظ تكنيكي مشكلاتي رخ دهد.1-1-3- اطلاعات مورد نياز در زمانبندي براي توسعه يك برنامه زمانبندي، بايد پردازش هر كار روي هر ماشين را بدانيم. برا ي محاسبه پردازش يك كار، بايد عوامل مربوط به ماشين از قبيل زمان راه اندازي، زمان پردازش واحد محصول، سرعت ماشين و عوامل كيفي به همراه تعداد يا مقدار محصول توليدي را در نظر بگيرم. براي پياده سازي الگوريتم ها با قواعد زمانبندي در يك كارخانه به اطلاعات مختلفي نياز است. اين اطلاعات، ممكن است شامل برنامه كاري اپراتورها، ماشين آلات و مشخصات آنها، اطلاعات تعميرات و نگهداري، ميزان پيشرفت كارهاي زمانبندي شده اي كه در حال حاضر در حال پردازش هستند و وضعيت فعلي ماشين ها از لحاظ دسترسي (به عنوان مثال : مشغول، بيكار، خراب و نيازمند تعمير) باشد. از طرفي به اطلاعاتي در مورد مشتريان از قبيل نام مشتريان، محصول و مقدار سفاش و تاريخ تحويل مقرر نيز نياز داريم از نظر مديريت، هر يك از سفارشات، اولويتي براي انجام دارد كه اين اولويت را مي توان به صورت كمي يا به صورت كيفي در قالب وزن هر سفارش بيان كرد. اطلاعات مربوط به برنامه ريزي نيازمندي هاي مواد مي تواند در تعيين زودترين زمان شروع پردازش هركار مورد استفاده قرار گيرد.در عمل برنامه هاي زمانبندي با استفاده از الگوريتم ها و يا روش هاي قاعده مند ايجاد مي شوند. الگوريتم هاي زمانبندي برنامه ها را باهدف بهينه سازي يك يا چند معيار مانند حداقل سازي انحراف از موعد تحويل، حداقل سازي هزينه دير كرد و... توليد مي كنند روش هاي قاعده مند سعي در يافتن يك برنامه زماني شدني در محيط عملياتي توليد دارند.اطلاعات برنامه زمانبندي، به اشكال مختلفي نمايش داده مي شوند. نمودار گانت كه اولين بار توسط هنري گانت در اواخر قرن نوزدهم معرفي و برنامه زمانبندي مورد استفاده قرار گرفت، همچنان يكي از رايج ترين ابزارهاي نمايش اطلاعات برنامه زمانبندي است. بر این اساس مسائل زمانبندی را می توان به صورت زیر دسته بندی نمود. شکل 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 مي باشد.