وزارت علوم، تحقیقات و فناوری
دانشگاه علوم و فنون مازندران
پایان نامه
مقطع کارشناسی ارشد
رشته : مهندسی صنایع- مهندسی سیستمهای اقتصادی اجتماعی
عنوان: طراحی الگوریتم فراابتکاری برای زمانبندی ماشینهای موازی نامرتبط با تابع هدف چندگانه در محیط تولید بهنگام
اساتید راهنما: دکتر جواد رضائیان
دکتر ایرج مهدوی
دانشجو: محسن زارعی
(بهار 1393)
تقدیم به
پدر و مادر عزیزم
و تمام کسانی که ساخته شدنم را مدیون زندگی و دوستی با آنها هستم.
تقدیر و تشکر
نگارنده بر خود لازم می داند تا بدين وسيله از تمامي عزيزاني که همواره در راه کسب علم و دانش ياريگر و مشوقش بودهاند، تشکر نمايد .از زحمات بی دریغ و راهنمایی های روشنگرانه و ارزشمند اساتید عزیز آقایان دکتر جواد رضاییان و دکتر ایرج مهدوی که همکاری با ایشان تجربه ای کم نظیر بود,تشکر و قدردانی می نماید.
چکیده
در طول دهه گذشته، گسترش الگوریتمهای فراابتکاری بهینه سازی چند معیاره توجه بسیاری را به خود جلب کرد. مسائل برنامه ریزی تولید بهنگام به عنوان مهمترین مسئله برنامهریزی بهینه سازی نیز مستثنی نبود. البته بسیاری از الگوریتمهای بهینه سازی که برای مسائل گوناگون به کار برده میشدند رویکردی نامناسب داشتند. به زبان دیگر بسیاری از آنها هدف ها را ترکیب میکردند و مسائل را با رویکرد تک هدفه حل میکردند. البته بعضی از محققان الگوریتمهای پارتویی به کار میبرند. در این تحقیق یک برنامه ریزی ماشینهای موازی نامرتبط با زمان آماده سازی وابسته به توالی، زمان دسترسی پویا به کارها، زمان تحویل متفاوت کارها و محدودیت مجموعه پردازشی نشان داده شده است. توابع هدف مورد نظر، مجموع وزنی زمانهای زودکرد و دیرکرد کارها و همچنین مجموع زمان تکمیل کارها را کمینه میکنند. برای حل مدل و اعتبار سنجی آن از الگوریتم مجموع وزنی و الگوریتم محدودیت اپسیلون استفاده شده است. همچنین نشان داده شده است که الگوریتمهایی که از روش شاخه و کران برای حل استفاده میکنند قادر به حل مسائل بزرگ در زمان معقول نمیباشند. بنابراین برای حل این مسئله برنامه ریزی چند معیاره که از نوع چند جملهای سخت (NP-Hard) میباشد الگوربتم فراابتکاری (CENSGA)معرفی شده است. الگوریتم ارائه شده را با استفاده از شاخصهای آماری با الگوریتم فراابتکاری (NSGA-II) مورد مقایسه و تحلیل قرار داده شده است که نتایج نشان دهنده کارایی بهتر الگوریتم فراابتکاری (CENSGA) میباشد.
کلمات کلیدی: تولید بهنگام; زمان آمادهسازی وابسته به توالی; کنترل نخبهگرایی; بهینه سازی چند هدفه; الگوریتم مرتب سازی نامغلوب.
فهرست
فصل اول مقدمه و کلیات1
1-1.مقدمه2
1-2. تعریف مسأله زمانبندی5
1-3. ضرورت انجام تحقیق7
1-4. اهداف تحقیق8
1-5. مفروضات مسئله9
1-6. جنبه هاي نوآوري تحقيق10
1-7. محتوای تحقیق10
فصل دوم ادبیات و پیشینه تحقیق11
2-1. مقدمه12
2-2. طبقه بندی محیط های زمانبندی15
2-3. مسائل ماشينهاي موازي19
2-3-1. زمان نصب و آماده سازی20
2-3-2. دسترسي محدود به ماشينها26
2-3-3. زمان دسترسی متفاوت به کارها27
2-4. مسائل با تمرکز بر موعد تحويل براي کارها27
2-4-1. زمان تکمیل کارها29
2-4-2. زمانهاي زودکرد و ديرکرد29
2-5. مروری بر رویکرد و اصول سیستم تولیدی بهنگام31
2-6. توالي ماشينﻫاي موازي با معيارهاي زودکرد و ديرکرد33
2-7. جمع بندی34
فصل سوم مدل ریاضی و بهینه سازی چند هدفه36
3-1. مقدمه37
3-2. تعريف مسئله37
3-2-1. مفروضات مسئله39
3-3. مدل پيشنهادي39
3-3-1.نمادها، تعاریف، پارامترها و متغیر های تصمیم40
3-3-2. پارامترهاي ورودي40
3-3-3. توابع هدف41
3-3-4. محدوديتها41
3-4. اعتبارسنجي مدل43
3-5. پيچيدگي مسئله45
3-6 بهینه سازی چند معیاره47
3-6-1. ارتباط غالب47
3-6-2. نقاط بهینه موضعی48
3-6-3. نقاط بهینه سراسری48
3-6-4. مرز بهینه48
3-7. روشهای بهینه سازی49
3-7-1. روشهای اسکالر49
3-7-2. روش مجموع وزنی51
3-7-2-1. طراحی روش مجموع وزنی برای حل مسأله مورد نظر54
3-7-3. روش محدودیت-ε55
3-7-3-1. طراحی روش محدودیت – ε برای حل مسأله57
3-7-4. روشهای عکس العملی57
3-7-5. روش های مبتنی بر منطق فازی58
3-7-6. روش های فرا ابتکاری59
3-7-7. الگوریتم NSGA-II60
3-7-7-1. مرتب سازی سریع61
3-7-7-2. عملگر گزینش تورنمنت تراکمی63
3-7-7-3. فاصله تراکمی63
3-7-8. طراحی روش فراابتکاری NSGA-II برای حل مسأله65
3-7-9. طراحی روش فراابتکاری CENSGA برای حل مسأله70
3-8. مقایسه روش های بهینه سازی چند هدفه71
3-8-1. شاخص متوسط فاصله از نقطه ایدهآل73
3-8-2. شاخص نرخ دستیابی به توابع هدف74
3-8-3. شاخص گستردگی جواب های غیر مغلوب (SNS)74
3-8-4. شاخص یکنواختی فضا74
3-9. جمعﺑندي75
فصل چهارم محاسبات و نتایج تحقیق77
4‐1. مقدمه78
4‐2. تنطیمات پارامترها و شرایط اجرای الگوریتم ها79
4-3. الگوریتمهای NSGA-II,CENSGA80
4-4. روش مجموع وزنی80
4-5. روش محدودیت-ε81
4‐6. ساختار مسائل82
4‐7. معیارهای ارزیابی الگوریتمها83
4‐8. مسائل با ابعاد کوچک و متوسط83
4-8-1. نتایج آزمایشات مسائل کوچک و متوسط83
4‐9. مسائل با ابعاد بزرگ90
4‐10. نتایج محاسباتی90
4‐11. جمعﺑندي96
فصل پنجم نتیجه گیری و پیشنهادات97
5‐1. مقدمه98
5‐2. نتيجهﮔيري99
5‐3. پيشنهادهاي آتي100
فهرست منابع و مراجع102

فهرست جداول
جدول 2-1. محيطهاي کارگاهي (نماد α) 013
جدول 2-2. توابع هدف رایج در ادبیات 015
جدول 3-1. زمانهای پردازش،موعدهاي تحويل و زمان دسترسی044
جدول 3-2. زمان نصب ماشین یک و دو برای کارهای مختلف 044
جدول 4-1. حدهای بالا برای مسائل مختلف 082
جدول 4-2. جوابهای نامغلوب مربوط به مسأله 5j2m به تفکیک روش ها084
جدول 4-3. ارزیابی روشهای حل مسئله با شاخصهای کمی برای 5j2m 085
جدول 4-4. جوابهای نامغلوب مربوط به مسأله 5j3m به تفکیک روش ها085
جدول 4-5. ارزیابی روشهای حل مسئله با شاخصهای کمی برای 5j3m 086
جدول 4-6. جوابهای نامغلوب مربوط به مسأله 8j2m به تفکیک روش ها087
جدول 4-7. ارزیابی روشهای حل مسئله با شاخصهای کمی برای 8j2m088
جدول 4-8 . جوابهای نامغلوب مربوط به مسأله 8j3m به تفکیک روش ها 089
جدول 4-9. ارزیابی روشهای حل مسئله با شاخصهای کمی برای 8j3m 090
جدول 4-10 نتایج شاخصهای متریک برای الگوریتم CENSGAوNSGA-II 091
جدول 4- 11. ارزیابی آماری الگوریتمهای فراابتکاری بکار گرفته شده 094
فهرست شکلها و نمودارها
شکل 2-1. دسته بندی مسائل زمانبندی بر اساس مسیر تولید 019
شکل 3-1. سلسلهمراتب پيچيدگي محيطهاي کارگاهي در مسائل زمانبندي046
شکل 3-2. سلسلهمراتب پيچيدگي توابع هدف در مسائل زمانبندي046
شکل 3-3. نقاط بهینه موضعی 048
شکل 3-4. رابطه فضای جواب و ارتباط غالب 048
شکل 3-5. نمایش روش مجموع وزنی با مرز بهینه پارتو محدب 052
شکل 3-6. نمایش روش مجموع وزنی با مرز بهینه پارتو غیر محدب 054
شکل 3-7. روش محدودیت- ε 056
شکل 3-8. نمایش الگوریتم NSGAII061
شکل 3-9. محاسبه فاصله تراکمی 064
شکل 3-10. ساختار کروموزوم066
شکل 3-11. نحوه ایجاد جمعیت اولیه 067
شکل 3-12. نحوه عملکرد عملگر تقاطع 069
شکل 3-13. عملگر تقاطع تک نقطه ای با نقطه برش 3069
شکل 3-14. نحوه عملکرد عملگر جهش 070
شکل 3-15. استراتژی انتخاب در الگوریتم CENSGA و NSGA-II 071
شکل 3-16. دو هدف در بهینه سازی چند هدفه072
شکل 3-17. یک مجموعه ایده آل از جواب های نامغلوب072
شکل 3-18. همگرائی خوب، اما تنوع ضعیف (الگوریتم 1)073
شکل 3-19. همگرائی ضعیف، اما تنوع خوب (الگوریتم 2)073
شکل 4-1. نمایش جوابهای نامغلوب ε-محدودیت مسأله 5j2m 084
شکل 4-2. نمایش جوابهای نامغلوب روش وزنی مسأله 5j2m 084
شکل 4-3. نمایش جوابهای نامغلوب روش وزنی مسأله 5j3m086
شکل 4-4. نمایش جوابهای نامغلوب روش محدودیت-ε مسأله 5j3m086
شکل 4-5 . نمایش جوابهای نامغلوب روش وزنی مسأله 8j2m088
شکل 4-6 . نمایش جوابهای نامغلوب روش محدودیت-ε مسأله 8j2m 088
شکل 4-7 . نمایش جوابهای نامغلوب روش وزنی مسأله 8j3m 089
شکل 4-8 . نمایش جوابهای نامغلوب روش محدودیت-ε مسأله 8j3m089
شکل 4- 9 نمودار نتایج محاسباتی شاخص های متریک در مسائل مختل092
شکل 4-10. نمودارجعبه ای (BoxPlot) نتایج ارزیابی الگوریتمهای CENSGA,NSGA-II 093
شکل 4-11. نمودار میانگین و فواصل اطمینان (سطح اطمینان 95%)نتایج ارزیابی الگوریتم ها 095
فصل اول مقدمه و کلیات
مقدمه
زمانبندي1، فرايند تخصيص منابع به فعاليتها با درنظر گرفتن دورههاي زماني مربوط به آنها به منظور بهينهسازي يک يا چند هدف ميباشد. اين فرايند به عنوان يک فرايند تصميمگيري مبناي کار بسياري از صنايع توليدي و خدماتي محسوب ميشود. زمانبندي کاراي فعاليتها زمينهساز بهبود عملکرد سيستمهاي توليدي ميباشد و ضرورتي براي بقا در فضاي رقابتي بازار به شمار ميآيد.
تئوري زمانبندي در ارتباط با مدلهاي رياضي است که فرايند زمانبندي را تشريح ميکنند. چشمانداز تئوريک يک نگرش کمي براي بدست آوردن ساختار مسائل در چهارچوب مدلهاي رياضي بهدست ميدهد که اين امر با تشريح منابع و فعاليتها و تبديل اهداف تصميمگيري به يک تابع هدف، صورت ميپذيرد. عمل زمانبندی در یک سازمان از مدل ها و روش های ریاضی و یا روش های ابتکاری برای تخصیص منابع محدود به کارهای در حال جریان استفاده می کند. اهمیت توالی ماشین های موازی، با هدف متمرکز بر دیرکرد از آن جهت مورد توجه است که در محیط کسب و کار حاضر، رقابت شرکت های تولیدی از طریق قابلیت آنها برای پاسخگویی سریع به تغییرات سریع در زمینه تجارتی و تولید محصولات با کیفیت بالاتر و هزینه های کمتر تعیین می شود. در نتيجه، منابع، فعاليتها و توابع هدف عناصر کليدي مدلهاي زمانبندي محسوب ميشوند.
منابع بر حسب قابليتهاي کمي و کيفي خود مشخص ميشوند، بطوريکه هر مدل نشان دهنده نوع و ميزان منابع بکار رفته در آن ميباشد. از سوي ديگر، فعاليتها بر حسب اطلاعاتي از قبيل منابع مورد نياز، مدت زمان انجام، زمان آغاز و زمان پايان آنها توصيف ميشوند. توابع هدف نيز دربرگيرنده هزينههاي سيستم براي اجراي تصميمات مربوط به تخصيص منابع به فعاليتها ميباشند. تصميمات عمده در فرايند زمانبندي شامل بهرهبرداري کارا از منابع، پاسخگويي سريع به تقاضا و انطباق دقيق زمانهاي تحويل با موعدهاي تحويل تعيينشده ميشوند. شرکت های تولیدی در تلاش هستند تا این قابلیت ها را از طریق اتوماسیون و مفاهیم خلاق مانند تولید به موقع2 (JIT) ، پاسخگوی سریع3 (QR) ، تکنولوژی گروهی4 (GT) و مدیریت کیفیت جامع5 (TQM) بدست آورند[58].
این مفاهیم ( برای مثال JIT و GT ) به بسیاری از شرکت ها در بدست آوردن سود اقتصادی کمک کرده است. در سیسستم های JIT کار نباید نه زودتر و نه دیرتر تکمیل شود، که به مسائل زمانبندی با هزینه های زودکرد و دیرکرد و تخصیص موعدهای تحویل منجر می شود. در یک بازار رقابتی دیرکرد کارها با توجه به موعد تحویل آنها یک مقیاس عملکرد بسیار مهم برای محیط های تولید متنوع است.
مسائل با تعیین موعد تحویل در 25 سال گذشته بعلت روشهای جدید مدیریت مانند مفاهیم JIT مورد توجه بسیار قرار گرفته است. چنگ که کمک زیادی به مسائل زمانبندی و تخصیص موعد تحویل کرد بیان می کند که تکمیل یک کار زودتر از موعد تحویل به معنی تحمیل هزینه های نگهداری موجودی غیر ضروری است ، در حالیکه تکمیل یک کار دیرتر از موعد تحویل منجر به جریمه های قراردادی و از دست دادن اعتبار مشتری می شود[33].
بطور جالب توجه هدف مسئله حداقل دیرکرد و زودکرد6 (ET) کاملا با سیاست کنترل تولید JIT مطابقت دارد.مسئله ماشین های موازی از دو دیدگاه تئوری و عملی دارای اهمیت می باشند. از دیدگاه تئوری به این خاطر که تعمیمی از حالت تک ماشینه می باشد و از دیدگاه عملی به این جهت که در دنیای واقعی بسیارمعمول است مورد توجه قرار گرفته شده است.
مسئله به کارگیری ماشین های موازی از آنجا مورد توجه است که اگر زمانبندی روی یک ماشین منجر به هزینه زیادی شود ممکن است در نظر گرفتن ماشین های بیشتر سبب کاهش هزینه شود. ضمن این که مقدار دیرکرد یا زودکرد نیز می تواند با افزایش تعداد ماشین ها کاهش یابد. در این شرایط هزینه به کارگیری ماشین یا نگهداری ماشین اضافه می شود که با حل مسئله بهینه سازی می توان تعیین کرد چه ماشین هایی به کار گرفته شوند و کدام کارها با چه توالی روی این ماشین ها انجام شود.
در عمل، زمانبندی ها با استفاده از الگوریتم های زمانبندی یا قوانین بر پایه دانش ایجاد می شوند. الگوریتم های زمانبندی ، زمانبندی را توسعه می دهد که یک معیار اندازه گیری مانند حداقل کردن انحراف موعد تحویل، حداقل جریمه دیرکرد یا حداقل حداکثر دیرکرد را بهینه می کند. انگيزه بسياري از توسعهها و پيشرفتهاي علمي در حوزه زمانبندي برخاسته از محيطهاي صنعتي است و بهطور طبيعي در بيان مفاهيم زمانبندي از واژههاي بکار رفته در صنعت استفاده ميشود. به همين خاطر منابع با عنوان ماشين بهکار ميروند و به هر کدام از فعاليتها، کار اطلاق ميشود بطوريکه کارها اغلب به وسيله مجموعهاي از ماشينها در ايستگاههاي مختلف کاري با توالي مشخص پردازش ميشوند.
بطور کلي، مسائل زمانبندي به صورت مسائل بهينهسازي محدوديتدار بيان ميشوند که در آنها به بررسي تصميمات مربوط به تخصيص ماشينها وتوالي پردازش کارها پرداخته ميشود. درحالتي که تنها يک ماشين موجود است، تعيين توالي پردازش کارها يک برنامه زماني کامل را تشکيل ميدهد. مسائل تکماشينه با وجود سادگي ذاتي، سنگبناي درک فراگير مفاهيم زمانبندي را تشکيل ميدهند. درمقابل، زمانبندي مسائل چندماشينه شامل سيستمهاي موازي، سيستمهاي متوالي و سيستمهاي ترکيبي ميباشد. در سيستمهاي موازي، هر يک از کارها با انجام يک عمليات همانند مسائل تکماشينه بر روي يکي از ماشينهاي موازي موجود پردازش ميشوند و به دنبال آن تخصيص ماشينها به کارها موضوعيت پيدا ميکند. اين درحالي است که در سيستم هاي متوالي و ترکيبي، کارها با انجام چند عمليات بر روي ماشينها پردازش ميشوند و مسائل مربوطه ساختار نسبتا پيچيدهتري را تجربه ميکنند.
در اين تحقيق، به بررسي مسئله زمانبندي ماشينهاي موازي نامرتبط7 به عنوان دسته مهمي از مسائل زمانبندي که داراي اهميت فراوان از نقطهنظر تئوري و تجربي است، پرداخته ميشود. مسائل ماشينهاي موازي نامرتبط حالت عموميتيافته مسائل تکماشينه و حالت خاصي از مسائل ماشينهاي متوالي منعطف محسوب ميشوند. تکنيکهاي بهکار رفته در بهينهسازي اين نوع مسائل با اعمال رويههاي ترکيبي در مسائل زمانبندي پيچيدهتر استفاده ميشوند. در بخشهاي آتي اين فصل، شرح تفصيلي مسئله مورد بررسي اين تحقيق ارائه ميشود.
1-2. تعریف مسأله زمانبندی
زمانبندي ماشينهاي موازي نامرتبط حالت عمومي مسائل کلاسيک ماشينهاي موازي بهشمار ميآيد. در يک مسئله کلاسيک زمانبندي ماشينهاي موازي، مجموعهاي از کارهاي مستقل وجود دارد که هر کدام از آنها بر روي يکي از ماشينهاي موازي يکسان موجود پردازش ميشوند. در حالت کلي، ماشينهاي موازي به صورت نامرتبط درنظر گرفته ميشوند بطوريکه زمان پردازش کارها بر روي ماشينها نهتنها به نوع کار بلکه به نوع ماشين نيز وابسته است. در اين حالت پيکربندي ماشينها يکسان نيست و رابطه مشخصي بين زمانهاي پردازش کارها بر روي ماشينهاي مختلف وجود ندارد. محيطهاي کارگاهي شامل ماشينهاي موازي نامرتبط در صنايع توليدي گوناگون نظير صنايع نساجي، الکترونيک، شيميايي و همچنين صنايع خدماتي به وفور بهچشم ميخورد [59].
در برخي از کاربردهاي زمانبندي ماشينهاي موازي نامرتبط، ماشينها داراي سطوح تکنولوژيکي متفاوتي هستند و لزوما قادر به پردازش هر يک از کارهاي موجود در مجموعه کارها نميباشند. در نتيجه، هرکدام از کارها تنها بر روي زيرمجموعهاي از مجموعه ماشينها ميتوانند پردازش شوند و اصطلاحا پردازش کارها با دسترسي محدود به ماشينها8 صورت ميپذيرد.
مسائل زمانبندي غالبا به محيطهاي کارگاهي ميپردازند که در آنها زمان نصب9 ماشين ناديده گرفته ميشود و يا به عنوان بخشي از زمان پردازش کارها تلقي ميشود. اينگونه محيطهاي کارگاهي با اين فرض مدلسازي ميشوند که زمانهاي نصب در مقايسه با زمانهاي پردازش کوچک هستند بنابراين ميتوان آنها را ناديده گرفت و يا اين که زمانهاي نصب مستقل از توالي پردازش کارها بر روي ماشينها هستند، در نتيجه ميتوان آنها را به زمانهاي پردازش اضافه نمود. با اين وجود، در بسياري از محيطهاي صنعتي يک زمان نصب وابسته به توالي10 هنگام تعويض کارها بر روي ماشينها به وقوع ميپيوندد [55]. در اين شرايط، زمان نصب به عنوان بخشي مجزا از زمان پردازش درنظر گرفته ميشود که مقدار آن علاوه بر نوع کاري که بر روي ماشين پردازش خواهد شد، به نوع کار قبلي که بر روي آن ماشين پردازش شده نيز بستگي دارد. تلقي زمان نصب به صورت مجزا از زمان پردازش در بيشتر تکنيکهاي مديريت توليد نوظهور نظير توليد به موقع11و تکنولوژي گروهي12 مورد استقاده قرار ميگيرد.
امروزه با بکارگيري موفقيتآميز مفهوم توليد به موقع در مفاهيمي چون مديريت توليد و انبارداري، نياز به تکميل پردازش کارها در موعد تحويل آنها يک امر کليدي در محيطهاي صنعتي محسوب ميشود. به بيان ديگر، تکميل کارها پيش از موعد تحويل به همان اندازه که ديرکرد در تکميل آنها اهميت دارد، در کانون توجه قرار ميگيرد. هزينههاي مرتبط با زمانهاي زودکرد و ديرکرد کارها، محققان را بر ميانگيزاند که اين هزينهها را در قالب معيارهاي بهينهسازي گوناگون در مسائل زمانبندي بکار گيرند.
در این پایان نامه به مسأله زمانبندی دو معیاره ماشین های موازی با سرعت متفاوت با هدف کمینه کردن مجموع وزنی دیرکردها و زودکردها و نیز کمینه کردن مجموع زمان تکمیل کارها به طور همزمان در حالتی که کارها دارای زمان آماده سازی وابسته به توالی و زمان دسترسی متفاوت و دسترسی محدود به ماشین آلات می باشد می پردازیم.
نظام تولید بهنگام تفکر و نگرشی نوین در اداره سازمانهای صنعتی است که با اصل تکنیکها و روشهای برخاسته از آن، حذف کامل و جامع اتلاف و افزایش بهره وری در تمامی فعالیتها اعم از داخل و خارج سازمان تعقیب می گردد.
تعاریف بسیاری توسط کارشناسان برای تولید بهنگام ارائه شده است، در زیر به تعدادی از این تعاریف اشاره شده است.
JIT یعنی :
پافشاری بر کیفیت برتر انجام امور خرید و تولید و … دقیقا در زمان مقرر
بهنگام بودن نظام، مستلزم بهنگام بودن همه اجزای آن است
در کل JIT یعنی فقط به هنگام ” نه دیرتر نه زودتر”
در JIT هدف تولید بهنگام است، یعنی اگر مشتری و تولید کننده زمان تحویل کالا را در یک زمان معین توافق کنند، تولید کننده باید تولیدات خود را طوری برنامه ریزی کند که کالا را در حد امکان در زمان مناسب تولید و در زمان مقرر تعیین شده به دست مشتری برساند. اگر این دیرتر از زمان تحویل آماده شود، تولید کننده متحمل جریمه ای به عنوان تأخیر تولید خواهد شد که این جریمه امکان دارد به صورتهای مختلف نمود پیدا کند. همچنین اگر تولید کننده، کالا را زودتر از زمان تحویل، تولید کند، این کالا را باید تا زمان تحویل در انبار نگهداری کند لذا در این صورت نیز متحمل هزینه خواهد شد.
در ادبیات زمان بندی تولید بهنگام هدف کمینه کردن معیارهای زودکرد و دیرکرد به صورت توأم می باشد، که در این پایان نامه علاوه بر این هدف معیار مجموع زمان تکمیل کارها را نیز کمینه می شود و از آنجا که زمان آماده سازی وابسته به توالی و زمان در دسترس بودن کارها در مسئله زمانبندی ماشین های موازی حائز اهمیت می باشد از این نظر در این تحقیق روی مسئله ماشین های موازی با زمان آماده سازی وابسته به توالی و زمان دسترسی متفاوت به کار متمرکز شده است.
1-3. ضرورت انجام تحقیق
با توجه به اهمیت روزافزون مسائل ماشین های موازی در نظر گرفتن معیارهای مختلف مورد توجه محققان این علم می باشد.امروزه در اغلب کارخانجات تولیدی و شرکت های خدماتی تأمین به موقع سفارش مشتری یا خدمت رسانی به موقع حائز اهمیت است. هزینه های زودکرد و دیرکرد در این امور نه تنها مشتری را متضرر می گرداند بلکه به شرکت نیز هزینه وارد شده و علاوه بر آن اعتبار خود را نیز از نظر مشتری از دست می دهد. مسائل تخصیص موعد تحویل زمانی جنبه عملی دارد که یک شرکت یک موعد تحویل به مشتریان در طول مذاکرات فروش پیشنهاد می کند و یک قیمت تقلیل یافته (جریمه) برای زمانیکه موعد تحویل دور از موعد انتظار باشد پیشنهاد می کند. هر چه موعدهای تحویل ثابت شده تر باشد احتمال اینکه محصول به موقع تحویل داده شود بیشتر است. به منظور نگهداشتن یک وجهه خوب در میان مشتریان بسیاری از شرکت ها برای حفظ موعدهای تحویل ایجاد شده، هزینه های نگهداری معقولی را متحمل می شوند .
در بحث زمانبندی ماشین های موازی ، هزینه برای هر ماشین وجود دارد که در واقع هزینه به کارگیری ماشین است که با زمان تکمیل کارها رابطه مستقیم دارد و لذا با توجه به این که زمان بکارگیری ماشین چه مقدار است توالی های مختلفی روی ماشین با مقدار زودکرد و دیرکرد می کند. در این پایان نامه مسأله حداقل کردن مجموع زمان تکمیل کارها و هم چنین مجموع هزینه های دیرکرد و زودکرد به طور همزمان در نظر گرفته شده است.
تقریبا همه مقالاتی که هدف های زودکرد و دیرکرد را در نظر می گیرند فرض می کنند که زمان آماده سازی ناچیز و یا مستقل از توالی است و همه کارها در زمان صفر در دسترس هستند لیکن زمان در دسترس بودن کار و زمان آماده سازی وابسته به توالی برای برخی صنایع از قبیل سازندگان اتومبیل و صنعت شیمی بسیار مهم است. با توجه به اهمیت زمان دسترسی و زمان آماده سازی وابسته به توالی در این پایان نامه زمان در دسترس بودن کار و زمان آماده سازی وابسته به توالی در نظر گرفته شده است.
یک مدل ترکیبی بهینه سازی برای این منظور ایجاد شده که از نوع مسائل NP Hard است. که برای مسائل با اندازه کوچک از روشهایی مستقیم که حل بهینه را می دهند استفاده شده و برای مسائل با اندازه متوسط و بزرگ از روش فراابتکاری که جواب بهینه یا نزدیک به بهینه را در یک زمان کوتاه می دهد استفاده شده است .
1-4. اهداف تحقیق
تحقيق حاضر با هدف کاهش فاصله ميان پيشرفتهاي تئوريک و کاربردهاي صنعتي در حوزه علم زمانبندي صورت گرفته است. در اين راستا، يک مدل جديد براي مسئله زمانبندي ماشينهاي موازي نامرتبط با محدوديتهاي زمان نصب وابسته به توالي پردازش کارها و دسترسي محدود به ماشينها وزمان دسترسی به کارها با معيارهای بهينهسازي زمانهاي زودکرد و ديرکرد وزني کل و نیز مجموع زمان تکمیل کارها ارائه ميشود. از اهداف این تحقیق علاوه بر مروری بر مطالعات صورت گرفته در حوزه زمانبندی و مسائل ماشینهای موازی تک هدفه، چند هدفه و چند معیاره ارائه مدل ریاضی دو هدفه و استفاده از روش فرا ابتکاری برای حل مسئله مطرح شده مد نظر میباشد. به همین منظور از الگوريتمهای فراابتکاري چند هدفه بر پايه الگوريتم ژنتيک به منظور حل اين مدل در مقياس کاربردي استفاده ميگردد. در این مطالعه برای حل و اعتبار سنجی مدل و نشان دادن کارایی الگوریتمهای مطرح شده با دو تابع هدف برای مسائل کوچک از روش های حل دقیق، الگوریتم مجموع وزنی13 و الگوریتم محدودیت-ε 14 استفاده شده است و برای مسائل متوسط و بزرگ الگوریتم NSGA-II15 و CENSGA16 توسعه داده شده است.
1-5. مفروضات مسئله
مفروضات زير در ارائه مدل مسئله درنظر گرفته ميشود:
ماشینها به صورت موازی و نامرتبط با یکدیگر قرار گرفتهاند و زمان پردازش کارها بر روی ماشینها متفاوت میباشد.
شکست یا وقفه در کارها مجاز نمی باشد(هر عملی بر روی ماشین نمی تواند بیش از یک بار شروع شود).
کارها دارای زمان نصب و آماده سازی وابسته به توالی هنگام تعویض کارها بر روی ماشینها می باشند.
تمامي کارها در لحظه زماني صفر در دسترس نمیباشند به عبارتی پردازش کار نمیتواند قبل از زمان دسترسی آغاز شود.
زمانهاي پردازش، نصب ماشين، موعد تحويل و ضرايب هزينه زودکرد و ديرکرد زماني معين ميباشند.
کار مجازي نوع صفر مفروض است. اين کار همواره در اولين موقعيت بر روي تمامي ماشينها پردازش ميشود. زمان پردازش اين کار صفر منظور ميشود و شروع پردازش آن نيازي به انجام عمليات نصب ماشين ندارد.
تمامي ماشين ها به طور مستمر دسترس هستند و امکان خرابي ماشين وجود ندارد.
هرکار در طول زمان پردازش خود فقط بر روی یک ماشین پردازش میشود.
هر کاری تنها بر روی زیر مجموعه ای از ماشینها قابل پردازش است.
هر ماشين در هر لحظه قادر به پردازش تنها يک کار ميباشد.
تمام پارامترها قطعی هستند و هیچ پارامتر تصادفی نداریم.
1-6. جنبه هاي نوآوري تحقيق
تحقيق موجود از دو جنبه صورت مسئله و روش حل نسبت به تحقيقات پيشين داراي نوآوري ميباشد. در اين تحقيق يک مدل رياضي جديد براي مسئله زمانبندي ماشينهاي نامرتبط با توابع هدف زمانهاي زودکرد و ديرکرد وزني کل و نیز مجموع زمان تکمیل کارها و محدوديتهاي زمان نصب وابسته به توالي پردازش کارها و دسترسي محدود به ماشينها و زمان دسترسی متفاوت به کارها ارائه داده شده است. همچنين، يک رويکرد فراابتکاري با استفاده از الگوريتمهاي چند هدفه ژنتیک براي حل مسئله ارائه شده است.
1-7. محتوای تحقیق
این پایان نامه دارای ساختار زیر است. در فصل دوم به منظور آشنایی خواننده مروری تقریبا جامع بر ادبیات موضوع در بخش های مختلف اعم از ادبیات موضوع مسئله زمانبندی ماشینهای موازی با معیارهای مختلف و زمانبندی این سیستم ها با زمان های آماده سازی وابسته به توالی صورت گرفته است. فصل سوم به توسعه مدل ریاضی و کلیات، اعتبار سنجی مدل و همچنین مکانیزم روش های دقیق و فرا ابتکاری توضیح داده شده و جزیئات الگوریتم تکاملی چند هدفه توسعه داده شده. به انضمام معیارهای اندازه گیری عملکرد روش های فرا ابتکاری نشان داده میشود. در فصل چهارم پس از بیان نحوه تولید مسائل نمونه، مسائلی کوچک که الگوریتمهای دقیق قادر به حل آن در زمان معقول میباشند را تولید نمودهایم و با استفاده از روشهای دقیق حل نمودهایم و و در ادامه برای مسائل بزرگ پارامترهای الگوریتم های فرا ابتکاری توسعه داده شده را تنظیم کرده و برای هر حالت با استفاده از معیارهای کارایی معرفی شده است. کارایی الگوریتم ها جداگانه در مقایسه با روش های موجود اندازه گیری شده است و نمایش گرافیکی آن با استفاده از نمودار و شکل نشان داده شده است. در پایان در فصل پنجم بعد از نتیجه گیری کلی، چند زمینه تحقیق برای مطالعات آتی به خوانندگان پیشنهاد شده است.
فصل دوم ادبیات و پیشینه تحقیق
2-1. مقدمه
مقاله های مربوط به مسائل زمانبندی برای اولین بار در اواسط دهه 1950 به چاپ رسیدند و پس از آن مقالات زیادی با در نظر گرفتن جنبه های مختلف آن به چاپ رسیدند. البته در اوايل قرن گذشته با مطالعات صورت گرفته توسط هنري گانت17 و ساير پيشگامان در کانون توجه قرار گرفته بود که این مطالعات منجر به ارائه الگوريتمهاي مهمي چون قاعده جانسون18 براي مسئله سيستم کارگاه جرياني19، قاعده زودترين موعد تحويل20 براي کمينهسازي زمان تاخير بيشينه و قاعده کوتاهترين زمان پردازش21 با هدف کمينهسازي زمان جريان ميانگين شد. برای حل مسائل پیچیدهتر تحقیقات به سمت حل با روشهاي دقيق چون برنامهريزي خطي22 و برنامهريزي پويا23 معطوف شد. پس از انتشار مقاله مشهور ريچارد کارپ [29] در زمينه نظريه پيچيدگي، محققان به این نتیجه رسیدند که روشهای دقیق قادر به حل مسائل بزرگ و با دادههای بزرگ نیستند و نمیتوانند درمدت زمان معقول به جواب بهینه برسند .همچنین تا دهه 1980 محققان مسائل زمانبندی بر روی بهینه سازی تک معیاره تمرکز داشتند.اما همانطور که میدانیم در مسائل دنیای واقعی، همواره چند معیار به طور همزمان بر روی بهینه سازی تاثیر دارد.به گونهای که ممکن است علاوه بر معیارهایی که برای بهینه سازی مهم هستند معیارهای متفاوتی از طرف صاحبان صنایع و یا جامعه و ناظرین کیفی نیز افزوده شود.در دهههاي هشتاد و نود ميلادي توجه محققین به حل مسائل زمانبندی در زمان محاسباتي معقول با الگوريتمهاي غير دقيق نظير تبريد شبيهسازي شده24، جستجوي ممنوع25، الگوريتم ژنتيک26 و ساير تکنيکهاي محاسبات تکاملي27 معطوف شد. اما پس از آن در دهه نود و در ابتدای قرن بیستویکم میلادی نسل جدیدی از الگوریتمهای چند هدفه معرفی شدند.این الگوریتمها هدفها را به یک هدف تبدیل نمیکردند.]27[ و بسیار موثرتر از دیگر الگوریتمها در بهینه سازی برای مدلهای چند هدفه هستند. برخی از معیارهایی که مورد بررسی قرار می گیرند عبارتند از :
حداکثر زمان تکمیل، کل زمان گردش کار، حداکثر دیرکرد، کل دیرکرد، حداکثر زودکرد، کل زودکرد، مجموع دیرکرد و زودکرد و تعداد کارهای با تأخیر. بهینه سازی چند هدفه با کشاکشی بین توابع هدف، معمولا به جای یک جواب بهینه، یک مجموعه جواب بهینه ارائه می دهند که بهینه پارتویی نامیده میشوند. این مجموعه جواب پارتویی شامل جوابهایی است نزدیکترین جواب به جواب بهینه که هیچ جواب دیگر بهتر از آنها نمی توان یافت که همزمان تمام توابع هدف را بهبود دهد.
گراهام و همکارانش [21] با استفاده از سیستم سه نمادی γ|β|α مسائل زمانبندي را بر اساس پيکربندي ماشينها و محدوديتهاي پردازش کارها طبقهبندي کردند. این مسائل بر اساس پیکربندی و شکل کارگاه (α)، محدودیت ها و فرضیات (β) و تابع هدف (γ) دسته بندی می شوند. پس هر مسئله میتواند بر اساس سه گانه α|β|γ بیان می شود. پارامتر α ساختار کارگاه را تعریف می کند که شامل تعداد مراحل و تعداد و ویژگی ماشین های داخل هر مرحله می شود. جدول زیر ليست نمادهاي متداول بکار رفته در اين سيستم را نمايش ميدهند:
جدول 2-1 محيطهاي کارگاهي (نماد α)سادهترين شکل و حالت خاص تمامي محيطهاي کارگاهي ممکن.تکماشينه1m ماشين کاملا يکسان به موازات هم قرار ميگيرند؛ هرکدام از کارها نياز به يک عمليات دارد و بر روي يکي از ماشينهاي موجود پردازش ميشود.ماشينهاي موازي يکسانP_mحالت کليتر ماشينهاي موازي يکسان؛ ماشينها داراي سرعت پردازش متفاوت هستند.ماشينهاي موازي يکنواختQ_mحالت کليتر ماشينهاي موازي يکنواخت؛ سرعت پردازش ماشينها هم به نوع ماشين و هم به نوع کار بستگي دارد.ماشينهاي موازي نامرتبطR_mm ماشين به صورت متوالي وجود دارد؛ هر کدام از کارها بر روي تمامي ماشينها پردازش ميشوند، تمامي کارها مسير پردازش يکساني دارند.کارگاه جريانيF_mحالت کليتر کارگاه جرياني؛ m ايستگاه پردازش به صورت متوالي وجود دارد؛ در هر ايستگاه يکي از حالات سهگانه ماشينهاي موازي براي پردازش يک کار رخ ميدهد.کارگاه جرياني منعطف〖FF〗_mهر کدام از کارها داراي مسير پردازش متمايز بر روي m ماشين موجود ميباشند.توليد کارگاهيJ_mحالت کليتر توليد کارگاهي؛ m مرکز پردازش وجود دارد؛ در هر ايستگاه يکي از حالات سهگانه ماشينهاي موازي براي پردازش يک کار رخ ميدهد.توليد کارگاهي منعطف〖FJ〗_mm ماشين وجود دارد؛ هر کدام از کارها بر روي هر کدام از ماشينها يک يا چند بار پردازش ميشود؛ محدوديتي براي مسير پردازش کارها وجود ندارد.کارگاه بازO_mپارامتر دوم، β، محدودیت و فرضیاتی مازاد بر مسئله استاندارد را بیان می کند که معمول ترین آنها در اینجا لیست شده اند:
r_j بیانگر این مطلب است که کار j نمی تواند قبل از روز ترخیصش r_j شروع به پردازش کند.
prmu نشان دهنده ترتیب یکسان پردازش کارها در هر مرحله است.
prec بیانگر این مطلب است که محدودیت های تقدم بین عملیات های کارهای مختلف وجود دارد.
M_j نشان دهنده این مطلب است که پردازش کار j محدود به مجموعه ای از ماشین ها M_j در مرحله k شده است.
S_sd بیانگر این مطلب است که زمان های پردازش وابسته به توالی عملیات ها هستند.
prmp بیانگر آنست که کارها بطور پیوسته و بدون هیچ اختلالی انجام می شوند.
block نشاندهنده ظرفیت محدود بافر(محل ذخیره) بین مراحل است. در واقع کار بایستی در مرحله قبل منتظر بماند تا فضای کافی آزاد شود.
recrc نشان میدهد که کارها می توانند بیش از یک بار نیز روی مراحل پردازش شوند.
unavail نشان میدهد که ماشین در همه زمان ها در دسترس نیست.
no-wait بیانگر این مطلب است که کارها نمی توانند بین دو مرحله متوالی منتظر بمانند و کارگاه تحت سیاست اولین ورودی اولین خروجی (FIFO28) عمل می کند.
p_j=p نشان دهنده برابر بودن تمام زمان های پردازش با p است.
〖size〗_jk بیانگر این مطلب است که o_jk بایستی روی ماشین های 〖size〗_jk بطور همزمان پردازش شوند.
در مسائل زمان بندی C_jk بیانگر زمان تکمیل کار j در مرحله k است و C_j زمان تکمیل کار j را در آخرین مرحله نمایش می دهد. زمان در جریان بودن کار j را با F_j نمایش می دهیم که زمانی است که کار j در سیستم صرف می کند، F_j=C_j-r_j. دیرشدگی 29کار j با L_j ، C_j-d_j نمایش داده می شود که ممکن است مقدار منفی نیز بگیرد.
دیرکرد30، T_j=max{C_j-d_j,0} و زودکرد31، E_j=max{d_j-C_j,0} غیر منفی هستند. U_j∈{0,1} معیاری برای جریمه کردن هر کار با تاخیر است. همچنین معمول است که وزنی مانند w_j به کار j اختصاص می هند تا به کمک آن اهمیت آن را مدل کنند. نماد گذاری های بیشتر به همراه توضیحات در جدول زیر آمده است.
جدول 2-2. توابع هدف رایج در ادبیات
NotationDescriptionMeaningCmaxMaxjCjMaximum Complletion timeFmaxMaxj(Cj-rj)Maximum flow timeLmaxMaxj(Lj)Maximum latenessTmaxMaxj(Tj)Maximum tardinessEmaxMaxj(Ej)Maximum earlinessC ̅∑▒C_j Total/average completion timeC ̅^w∑▒〖w_j C_j 〗Total/average weighted completion timeF ̅∑▒F_j Total/average flow timeF ̅^w∑▒〖W_j F_j 〗Total/avarage weighted flow timeT ̅∑▒T_j Total/average tardinessT ̅^w∑▒〖W_j T〗_j Total/average weighted tardinessU ̅∑▒U_j Number of late jobsU ̅^w∑▒〖W_j U_j 〗Total weighted number of late jobsE ̅∑▒E_j Total/average earlinessE ̅^w∑▒W_j E_jTotal/average weighted earliness2-2. طبقه بندی محیط های زمانبندی
توالی عملیات و زمانبندی32 در واقع نوعی فرایند تصمیم گیری است که نقشی اساسی در ارتقای بهره وری درصنایع تولیدی و خدماتی دارد. در واقع تعیین توالی زمانی و تخصیص سفارشات مشتریان به منابع موجود تولید (اعم از پرسنل، ماشین آلات، ابزار و …) به منظور انجام مجموعه ای از عملیات های مربوط به آن را زمانبندی تولید تعریف میکنند. معمولا زمانبندی با توجه به اهدافی نظیر: دستیابی به موعدهای تعهد شده، کمینه سازی زمان کار33، موجودی کار در جریان ساخت، بیشینه سازی خروجی و بهره برداری بیشتر از مراکز کاری اهدافی هستند که معمولا زمانبندی با توجه به آنها انجام میشود. قابل ذکر است که این اهداف با یکدیگر در تناقض هستند، لذا در مسائل زمانبندی ممکن است به لحاظ تکنیکی مشکلاتی رخ دهد.
مسائل واقعی زمانبندی تولید عموما تعدادی زیاد فعالیت و منابع داشته که مجموعه گوناگونی از اهداف و محدودیت بهره برداری از منابع در مورد آنها مطرح می شود. طبیعی است که روش های حل برنامه ریزی ریاضی و یا حتی فرموله نمودن آنها نسبتا سنگین و پر زحمت باشد. در بعضی موارد از طریق قواعد یا روش های ابتکاری ساده مبتنی بر قواعد تجربی یا آزمایشات شهودی می توان این مشکلات را برطرف نمود، اما در برخی دیگر از موارد تکنیک های مدلسازی منطقی یا بهینه سازی پیچیده تری لازم است.
مسائل زمانبندی را می توان به شیوه های مختلفی طبقه بندی نمود. بعنوان مثال میتوان مسائل زمانبندی را بصورت پویا یا ایستا، قطعی یا احتمالی، تک محصولی یا چند محصولی، تک پردازنده یا چند پردازنده و … دسته بندی نمود. نوع دیگری از طبقه بندی، بر اساس محیط منابع است. بسته به تعداد عملیات های مورد نیاز برای پردازش یک کار و نیز تعداد ماشین های موجود برای پردازش هر عملیات، الگوهای جریان گوناگونی را می توان برشمرد. مواقعی که تکمیل یک کار فقط به یک عملیات نیاز دارد به آن کار تک عملیاتی34 و در غیر اینصورت به آن کار چند عملیاتی35 گفته می شود که در آن مفاهیم مسیر تولید36 ممکن است مطرح شود. بر این اساس مسائل زمانبندی را می توان به صورت زیر دسته بندی نمود.
کارگاه تک ماشین37 : فقط یک ماشین در دسترس بوده و هر کار فقط به یک عملیات نیاز دارد.
کارگاه جریان کاری یا کارگاه جریان کاری مرتب38 : تعداد g ماشین متوالی وجود دارد و هر کار می بایست روی هر ماشین با همان توالی (یک مسیر تولید) پردازش شود.
کار کارگاهی: هر کار به چند عملیات نیاز دارد. جمعا به تعداد g ماشین متوالی وجود دارد و هر کار مسیر تولید خاص خود را دارد.
کارگاه عمومی39 : هر کار به چند عملیات نیاز دارد. جمعا به تعداد g ماشین وجود دارد، اما الگوی جریان معین نیست. به عبارت دیگر در انجام یک کار ممکن است از یک ماشین چندبار استفاده شود.
ماشین های موازی: هر کار تک عملیاتی بوده و در هر مرحله چندین ماشین برای انجام فرایند در دسترس است. در این حالت ماشین ها می توانند یکسان (I)، یکنواخت (U)، و یا نا مرتبط (R) باشند.
ماشین های یکسان در حالت موازی:چندین ماشین یکسان بصورت موازی می توانند کار کنند. فرض می شود که کار j بایستی توسط یکی از این ماشین ها انجام شود. این حالت با عنوان ماشین های یکسان در حالت موازی نامیده می شود. (مثال بانک های خصوصی مانند سامان و پارسیان). اگر یک کار تنها باید به روی یکی از ماشین ها پردازش شود، آنگاه نماد Mj در قسمت β نمایش داده می شود. مثال هایی دیگر در این زمینه صفوف بازرسی بدنی و یا سیستم های بانک و یا سیستم کنترل گذرنامه در فرودگاه ها می باشند.
ماشین های موازی با سرعت های متفاوت: سرعت پردازش ماشین iام بصورت vi نمایش داده می شود. زمان پردازش کار j ام به روی ماشین i ام بصورت P_ij=P_j⁄v_i محاسبه می شود. چنین مسایلی متعلق به ماشین های مشابه می باشند. این مسایل با عنوان ماشین های موازی با سرعت های متفاوت تعریف می شوند. مثالی در این زمینه: تعمیرکاران مختلف ماشین که سرعت آنها بستگی به مهارت آنها دارد (مشتریان ثابت و منابع متحرک). در این حالت سرعت پردازش هر ماشین مستقل از نوع کار است.
ماشین های غیر مرتبط در حالت موازی:در این حالت ماشین هایی متفاوت بصورت موازی وجود دارند. ماشین i می تواند کار j را با سرعتی معادل vij پردازش نماید. زمان پردازش بصورت P_ij=P_j⁄v_ij محاسبه می شود. اگرسرعت پردازش کارهامستقل کارها باشد، مساله به حالت قبلی تبدیل می شود. این حالت با نام ماشین های غیر مرتبط در حالت موازی معروف هستند. در این حالت هر کار ممکن است توسط یکی از ماشین ها با سرعت بالاتری پردازش شود.
کارگاه جریان کاری مختلط: این حالت تعمیم یافته حالت محیط کارگاه جریان کاری و ماشین های موازی است. در اینجا g کارگاه متوالی وجود دارد که در مرحله t آن به تعداد mt ماشین بطور موازی کار می کنند. در هر کارگاه، یک کار حداکثر روی یک ماشین می تواند انجام شود.
کار کارگاهی با ماشین های دوتایی40 (کارگاهی منعطف): این حالت تعمیم یافته محیط کار کارگاهی و ماشین های موازی است. در اینجا g کارگاه وجود دارد که mtماشین موازی در کارگاه t کار می کنند. در هر کارگاه، یک کار حداکثر روی یک ماشین می تواند پردازش شود.
پردازش انباشته ای41 :در این فرایند، کارها در قالب انباشته هایی به صورت همزمان پردازش می شوند. پردازش هر انباشته، نیازمند زمان مشخصی است و ممکن است یک محدودیت ظرفیتی در مورد تعداد کارهایی که می توانند به صورت همزمان پردازش شوند وجود داشته باشد.
سیستم ساخت انعطاف پذیر42 :در این سیستم هر ماشین ممکن است قادر به انجام بیش از یک عملیات باشد. بنابراین هر دو ماشین در انجام یک سری از عملیات ممکن است حکم دو ماشین موازی را داشته باشند و در مورد یکسری از عملیات با یکدیگر اشتراکی نداشته باشند.
سیستم کارگاهی وابسته43 :یک محیط کار کارگاهی است که در آن، زمان شروع و پایان یکسری از کارها، به هم وابسته است. مثال بارز این سیستم، خطوط مونتاژ است. در مورد هر یک از سیستم های تولیدی فوق، وابستگی زمان و هزینه راه اندازی وابسته به توالی، می تواند دو سیستم مختلف را پدید آورد. از طرفی، سیستم های تولیدی در دنیای واقعی با پدیده های تصادفی بسیاری روبرو هستند که موجب قطع یا شکست سیستم می گردد. این رویدادها به عنوان رویدادهای زمان واقعی44 شناخته می شوند.
شکل 2-1. دسته بندی مسائل زمانبندی بر اساس مسیر تولید ]1[
2-3. مسائل ماشينهاي موازي
در یک مدل کلاسیک ماشینهای موازی اینگونه بیان میشود که یک سری کارهای مستقل باید بر روی چند ماشین یکسان که به صورت موازی قرار گرفتهاند پردازش شوند. هرماشین فقط میتواند یک کار را در یک زمان مشخص پردازش کند، و هر کار فقط میتواند توسط یک ماشین پردازش شود. تمامی کارها در ابتدای افق زمانی در دسترس میباشند و هرکدام از کارها زمان پردازش و موعد تحویل متفاوتی دارند ]10[. فرض میشود که ماشینها یکسان هستند و زمان دسترسی به کارها متفاوت نمیباشد و همه آنها با زمان تحویل متعارف در ابتدای زمانبندی در دسترس هستند. در مواردی نیز به خاطر تفاوت بین تکنولوژی ماشینهای به کارگرفته شده،ماشینها دارای سرعت متفاوتی هستند،به همین دلیل زمان کارهایی که باید بر روی این ماشینها زمانبندی شوند یکسان نیست. همچنین ممکن است همه کارها در ابتدای افق زمانی در دسترس نباشند و در زمانهای متفاوتی برسند و دارای زمانهای دسترسی پویا باشند به همین دلیل ممکن است که کارها با زمانهای تحویل متفاوت در نظر گرفته شود. در تمامی محیطهای صنعتی محدودیتهای پیشنیازی برای زمانبندی و توالی کارها بسیار مهم میباشند.در یک محیط واقعی ممکن است ما به زمان شروع یک کار برای تکمیل کار بعدی نیاز داشته باشیم و تا وقتی که کار قبلی تکمیل نشود نمیتوانیم کار بعدی را شروع کنیم.زمانبندی کارها بر روی ماشینهای موازی با محدودیت هایی چون محدودیتهای گفته شده، فضای حل را کوچک میکند، البته این به این معنا نیست که دستیابی به جواب بهینه آسان میشود و برعکس افزایش محدودیتها باعث سختتر شدن دستیابی به جواب بهینه میشود ]41[.
2-3-1. زمان نصب و آماده سازی
زمان نصب و آماده سازی ماشين نمايانگر کليه عملياتي ميباشد که به منظور آمادهسازي يک ماشين براي پردازش کارها بر روي آن صورت ميپذيرد. عملياتي نظير تنظيم و اصلاح ابزارها45، نصب جيگها46 و فيکسچرها47، تميزکاري48 و … از اين قبيل محسوب ميشوند. در بسیاری از تحقیقات فرض شده است که زمان آماده سازی ماشینها ناچیز است و یا آنرا جزئی از زمان پردازش در نظر گرفتهاند. با اینکه این فرض مدل و تحلیل آن را ساده میکند ولی بازتاب مشخصی در کاربرد دارد، تاثیر سوء بر روی کیفیت کارهای کاربردی که نیازمند عملیات مشخص برای آماده سازی هستند، دارد و باعث میشود که مدل در دنیای واقعی کاربردی نباشد. اين وضعيت شايد در برخي از موارد قابل توجيه باشد اما بسياري از مسائل زمانبندي نيازمند در نظر گرفتن زمان نصب به صورت مجزا از زمان پردازش ميباشند. به طور معمول، مسائل تولیدی مرتبط با زمان آماده سازی به دو دسته تقسیم میشوند:1) زمان آماده سازی مستقل از توالي49 2) زمان آماده سازی وابسته به توالی50 در دسته اول زمان نصب تنها به نوع کاري که بر روي ماشين پردازش ميشود بستگي دارد که اصطلاحا زمان نصب مستقل از توالي ناميده ميشود و در دسته دوم زمان نصب علاوه بر نوع کاري که بر روي ماشين پردازش خواهد شد، به کار قبلي که بر روي آن ماشين پردازش شده و ماشینی که کار بر روی آن پردازش میشود نيز بستگي دارد و به آن زمان نصب وابسته به توالي اطلاق ميشود.]41[به عنوان مثال در یک کارخانه تولیدی رنگ هر جا تغيير رنگ نياز باشد يک زمان آمادهﺳازي براي تميز کردن دستگاه لازم است این زمان آماده سازی هم به رنگی که از ماشین پاک شود بستگی دارد هم به رنگی که قرار است پس از آن تولید شود بستگی دارد. در صنعت پلاستيک محصولات با رنگﻫاي متفاوت به ماشينﻫاي اکستروژن متفاوتي تخصيص داده ميﺷوند. وقتی که تغییر رنگ لازم است، زمان مشخصی لازم است که پلاستیک خروجی رنگ مورد نظر را بگیرد. همچنین این مسئله در کارخانه تولید شیشه، شیشه مذاب قبل از پردازش در داخل خمره های بسیار بزرگ قرار دارند.وقتی که رنگ شیشه مذاب و یا مشخصات آن باید تغییر کند به یک زمان آماده سازی زیادی نیاز دارد.همچنین در کارخانه های تولیدی نوشیدنی، هنگامی که در خطوط تولیدی حین پر کردن شیشه های نوشیدنی بخواهیم قوطی را جایگزین شیشه کنیم به زمان آماده سازی نیاز داریم. در يک شرکت توليد کاغذ هر کجا ماشين بين دو نوع کاغذ تعويض انجام دهد، از آنجا که زمان آمادهﺳازي وابسته به درجه تشابه کاغذهاي توليدي متوالي است، اين زمان وابسته به توالي ميﺑاشد. در صنعت توليد بطري،زمان آمادهﺳازي وابسته به اندازه و شکل بطريﻫا ميﺑاشد.]41[
اهميت در نظر گرفتن زمان نصب به صورت مجزا از زمانهاي پردازش کارها در تحقيقات مختلفي بررسي شده است. فلين [16] در تحقیق خود تاثير زمانهای نصب وابسته به توالي را در افزايش ظرفيت توليد بررسي نموده است.یو و جایجین[60] مجموع وزنی دیرکرد را بر روی تک ماشین را با در نظر گرفتن زمان نصب و آماده سازی را حداقل کردند.آنها به این مسئله اشاره کردهاند که زمان نصب به دو دسته زمان نصب متوالی و زمان نصب تفکیک پذیر تقسیم میشوند.و از هر دو حالت زمان نصب برای مدل خود استفاده کرده اند.
در ادامه، مهمترين مطالعات



قیمت: تومان

دسته بندی : پایان نامه ارشد

پاسخ دهید