کلمات کلیدی: تولید بهنگام; زمان آمادهسازی وابسته به توالی; کنترل نخبهگرایی; بهینه سازی چند هدفه;الگوریتم مرتب سازی نامغلوب. فهرست1- فصل اول مقدمه و کلیات.. 11-1. مقدمه.. 21-2. تعریف مسأله زمانبندی.. 51-3. ضرورت انجام تحقیق.. 71-4. اهداف تحقیق.. 81-5. مفروضات مسئله.. 91-6. جنبه هاي نوآوري تحقيق.. 101-7. محتوای تحقیق.. 102- فصل دوم ادبیات و پیشینه تحقیق.. 112-1. مقدمه.. 122-2. طبقه بندی محیط هایزمانبندی.. 152-3. مسائل ماشينهاي موازي.. 192-3-1. زمان نصب و آماده سازی.. 202-3-2. دسترسي محدود به ماشينها.. 262-3-3. زمان دسترسی متفاوت به کارها.. 272-4. مسائل با تمرکز بر موعد تحويل براي کارها.. 272-4-1. زمان تکمیل کارها.. 292-4-2. زمانهاي زودکرد و ديرکرد.. 292-5. مروری بر رویکرد و اصول سیستم تولیدی بهنگام.. 312-6.توالي ماشينﻫاي موازي با معيارهاي زودکرد و ديرکرد.. 332-7. جمع بندی.. 343- فصل سوم مدل ریاضی و بهینه سازی چند هدفه.. 363-1. مقدمه.. 373-2. تعريف مسئله.. 373-2-1. مفروضات مسئله.. 393-3. مدل پيشنهادي.. 393-3-1.نمادها، تعاریف، پارامترها و متغیر های تصمیم.. 403-3-2. پارامترهاي ورودي.. 403-3-3. توابع هدف.. 413-3-4. محدوديتها.. 413-4. اعتبارسنجي مدل.. 433-5. پيچيدگي مسئله.. 453-6 بهینه سازی چند معیاره.. 473-6-1. ارتباط غالب.. 473-6-2. نقاط بهینه موضعی.. 483-6-3. نقاط بهینه سراسری.. 483-6-4. مرز بهینه.. 483-7. روشهای بهینه سازی.. 493-7-1. روشهای اسکالر.. 493-7-2. روش مجموع وزنی.. 513-7-2-1. طراحی روش مجموع وزنی برای حل مسأله مورد نظر.. 543-7-3. روش محدودیت-. 553-7-3-1. طراحی روش محدودیت – برای حل مسأله.. 573-7-4. روشهای عکس العملی.. 573-7-5. روش های مبتنی بر منطق فازی.. 583-7-6. روش های فرا ابتکاری.. 593-7-7. الگوریتم NSGA-II. 603-7-7-1. مرتب سازی سریع.. 613-7-7-2. عملگر گزینش تورنمنت تراکمی.. 633-7-7-3. فاصله تراکمی.. 633-7-8. طراحی روش فراابتکاری NSGA-II برای حل مسأله.. 653-7-9. طراحی روش فراابتکاری CENSGA برای حل مسأله.. 703-8. مقایسه روش های بهینه سازی چند هدفه.. 713-8-1. شاخص متوسط فاصله از نقطه ایدهآل.. 733-8-2. شاخص نرخ دستیابی به توابع هدف.. 743-8-3. شاخص گستردگی جواب های غیر مغلوب (SNS).. 743-8-4. شاخص یکنواختی فضا.. 743-9. جمعﺑندي.. 754- فصل چهارم محاسبات و نتایج تحقیق.. 774‐1. مقدمه.. 784‐2. تنطیمات پارامترها و شرایط اجرای الگوریتم ها.. 794-3. الگوریتمهای NSGA-II,CENSGA.. 804-4. روش مجموع وزنی.. 804-5. روش محدودیت-. 814‐6. ساختار مسائل.. 824‐7. معیارهای ارزیابی الگوریتمها.. 834‐8.مسائل با ابعاد کوچک و متوسط.. 834-8-1. نتایج آزمایشات مسائل کوچک و متوسط.. 834‐9. مسائل با ابعاد بزرگ.. 904‐10. نتایج محاسباتی.. 904‐11. جمعﺑندي.. 965- فصل پنجم نتیجه گیری و پیشنهادات.. 975‐1. مقدمه.. 985‐2. نتيجهﮔيري.. 995‐3. پيشنهادهاي آتي.. 100فهرست منابع و مراجع.. 102.. فهرست جداولجدول 2-1. محيطهاي کارگاهي (نماد α) 13جدول 2-2. توابع هدف رایج در ادبیات 15جدول 3-1. زمانهای پردازش،موعدهاي تحويل و زمان دسترسی44جدول 3-2. زمان نصب ماشین یک و دو برای کارهای مختلف 44جدول 4-1. حدهای بالا برای مسائل مختلف 82جدول 4-2. جوابهای نامغلوب مربوط به مسأله 5j2m به تفکیک روش ها84جدول 4-3. ارزیابی روشهای حل مسئله با شاخصهای کمیبرای 5j2m 85جدول 4-4. جوابهای نامغلوب مربوط به مسأله 5j3m به تفکیک روش ها85جدول 4-5. ارزیابی روشهای حل مسئله با شاخصهای کمی برای 5j3m 86جدول 4-6. جوابهای نامغلوب مربوط به مسأله 8j2m به تفکیک روش ها87جدول 4-7. ارزیابی روشهای حل مسئله با شاخصهای کمی برای 8j2m88جدول 4-8 . جوابهای نامغلوب مربوط به مسأله 8j3m به تفکیک روش ها 89جدول 4-9. ارزیابی روشهای حل مسئله با شاخصهای کمی برای 8j3m 90جدول 4-10 نتایج شاخصهای متریک برای الگوریتم CENSGAوNSGA-II 91جدول 4- 11. ارزیابی آماری الگوریتمهای فراابتکاری بکار گرفته شده94فهرست شکلها و نمودارهاشکل 2-1. دسته بندی مسائل زمانبندی بر اساس مسیر تولید 19شکل 3-1. سلسلهمراتب پيچيدگي محيطهاي کارگاهي در مسائل زمانبندي46شکل 3-2. سلسلهمراتب پيچيدگي توابع هدف در مسائل زمانبندي46شکل 3-3. نقاط بهینه موضعی48شکل 3-4. رابطه فضای جواب و ارتباط غالب48شکل 3-5. نمایش روش مجموع وزنی با مرز بهینه پارتو محدب 52شکل 3-6. نمایش روش مجموع وزنی با مرز بهینه پارتو غیر محدب 54شکل 3-7. روش محدودیت-56شکل 3-8. نمایش الگوریتم NSGAII61شکل 3-9. محاسبه فاصله تراکمی 64شکل 3-10. ساختار کروموزوم66شکل 3-11. نحوه ایجاد جمعیت اولیه 67شکل 3-12. نحوه عملکرد عملگر تقاطع 69شکل 3-13. عملگر تقاطع تک نقطه ای با نقطه برش 369شکل 3-14. نحوه عملکرد عملگر جهش70شکل 3-15. استراتژی انتخاب در الگوریتم CENSGA و NSGA-II 71شکل 3-16. دو هدف در بهینه سازی چند هدفه72شکل 3-17. یک مجموعه ایده آل از جواب های نامغلوب72شکل 3-18. همگرائی خوب، اما تنوع ضعیف (الگوریتم 1)73شکل 3-19. همگرائی ضعیف، اما تنوع خوب (الگوریتم 2)73شکل 4-1. نمایش جوابهای نامغلوب ε-محدودیت مسأله 5j2m 84شکل 4-2. نمایش جوابهای نامغلوب روش وزنی مسأله 5j2m 84شکل 4-3. نمایش جوابهای نامغلوب روش وزنی مسأله 5j3m86شکل 4-4. نمایش جوابهای نامغلوب روش محدودیت- مسأله 5j3m86شکل 4-5 . نمایش جوابهای نامغلوب روش وزنی مسأله 8j2m88شکل 4-6 . نمایش جوابهای نامغلوبروش محدودیت- مسأله 8j2m 88شکل 4-7 . نمایش جوابهای نامغلوب روش وزنی مسأله 8j3m 89شکل 4-8 . نمایش جوابهای نامغلوبروش محدودیت- مسأله 8j3m89شکل 4- 9 نمودار نتایج محاسباتی شاخص های متریک در مسائل مختل92شکل 4-10. نمودارجعبه ای (BoxPlot) نتایجارزیابی الگوریتمهای CENSGA,NSGA-II 93شکل 4-11. نمودار میانگین و فواصل اطمینان (سطح اطمینان 95%)نتایج ارزیابی الگوریتم ها95 Article I. فصل اول مقدمه و کلیات 1-1. مقدمهزمانبندي[1]، فرايند تخصيص منابع به فعاليتها با درنظر گرفتن دورههاي زماني مربوط به آنها به منظور بهينهسازي يک يا چند هدف ميباشد. اين فرايند به عنوان يک فرايند تصميمگيري مبناي کار بسياري از صنايع توليدي و خدماتي محسوب ميشود. زمانبندي کاراي فعاليتها زمينهساز بهبود عملکرد سيستمهاي توليدي ميباشد و ضرورتي براي بقا در فضاي رقابتي بازار به شمار ميآيد.تئوري زمانبندي در ارتباط با مدلهاي رياضي است که فرايند زمانبندي را تشريح ميکنند. چشمانداز تئوريک يک نگرش کمي براي بدست آوردن ساختار مسائل در چهارچوب مدلهاي رياضي بهدست ميدهد که اين امر با تشريح منابع و فعاليتها و تبديل اهداف تصميمگيري به يک تابع هدف، صورت ميپذيرد. عمل زمانبندی در یک سازمان از مدل ها و روش های ریاضی و یا روش های ابتکاری برای تخصیص منابع محدود به کارهای در حال جریان استفاده می کند. اهمیت توالی ماشین های موازی، با هدف متمرکز بر دیرکرد از آن جهت مورد توجه است که در محیط کسب و کار حاضر، رقابت شرکت های تولیدی از طریق قابلیت آنها برای پاسخگویی سریع به تغییرات سریع در زمینه تجارتی و تولید محصولات با کیفیت بالاتر و هزینه های کمتر تعیین می شود. در نتيجه، منابع، فعاليتها و توابع هدف عناصر کليدي مدلهاي زمانبندي محسوب ميشوند.منابع بر حسب قابليتهاي کمي و کيفي خود مشخص ميشوند، بطوريکه هر مدل نشان دهنده نوع و ميزان منابع بکار رفته در آن ميباشد. از سوي ديگر، فعاليتها بر حسب اطلاعاتي از قبيل منابع مورد نياز، مدت زمان انجام، زمان آغاز و زمان پايان آنها توصيف ميشوند. توابع هدف نيز دربرگيرنده هزينههاي سيستم براي اجراي تصميمات مربوط به تخصيص منابع به فعاليتها ميباشند. تصميمات عمده در فرايند زمانبندي شامل بهرهبرداري کارا از منابع، پاسخگويي سريع به تقاضا و انطباق دقيق زمانهاي تحويل با موعدهاي تحويل تعيينشده ميشوند. شرکت های تولیدی در تلاش هستند تا این قابلیت ها را از طریق اتوماسیون و مفاهیم خلاق مانند تولید به موقع[2] (JIT)، پاسخگوی سریع[3] (QR)، تکنولوژی گروهی[4] (GT)و مدیریت کیفیت جامع[5] (TQM)بدست آورند[58].این مفاهیم ( برای مثال JIT و GT ) به بسیاری از شرکت ها در بدست آوردن سود اقتصادی کمک کرده است. در سیسستم های JIT کار نباید نه زودتر و نه دیرتر تکمیل شود، که به مسائل زمانبندی با هزینه های زودکرد و دیرکرد و تخصیص موعدهای تحویل منجر می شود. در یک بازار رقابتی دیرکرد کارها با توجه به موعد تحویل آنها یک مقیاس عملکرد بسیار مهم برای محیط های تولید متنوع است.مسائل با تعیین موعد تحویل در 25 سال گذشته بعلت روشهای جدید مدیریت مانند مفاهیمJITمورد توجه بسیار قرار گرفته است.چنگ که کمک زیادی به مسائل زمانبندی و تخصیص موعد تحویل کرد بیان می کند که تکمیل یک کار زودتر از موعد تحویل به معنی تحمیل هزینه های نگهداری موجودی غیر ضروری است ، در حالیکه تکمیل یک کار دیرتر از موعد تحویل منجر به جریمه های قراردادی و از دست دادن اعتبار مشتری می شود[33].بطور جالب توجه هدف مسئله حداقل دیرکرد و زودکرد[6] (ET) کاملا با سیاست کنترل تولید JITمطابقت دارد.مسئله ماشین های موازی از دو دیدگاه تئوری و عملی دارای اهمیت می باشند. از دیدگاه تئوری به این خاطر که تعمیمی از حالت تک ماشینه می باشد و از دیدگاه عملی به این جهت که در دنیای واقعی بسیارمعمول است مورد توجه قرار گرفته شده است.مسئله به کارگیری ماشین های موازی از آنجا مورد توجه است که اگر زمانبندی روی یک ماشین منجر به هزینه زیادی شود ممکن است در نظر گرفتن ماشینهای بیشتر سبب کاهش هزینه شود. ضمن این که مقدار دیرکرد یا زودکرد نیز می تواند با افزایش تعداد ماشین ها کاهش یابد. در این شرایط هزینه به کارگیری ماشین یا نگهداری ماشین اضافه می شود که با حل مسئله بهینه سازی می توان تعیین کرد چه ماشین هایی به کار گرفته شوند و کدام کارها با چه توالی روی این ماشین ها انجام شود.در عمل، زمانبندی ها با استفاده از الگوریتم های زمانبندی یا قوانین بر پایه دانش ایجاد می شوند. الگوریتم های زمانبندی ، زمانبندی را توسعه می دهد که یک معیار اندازه گیری مانند حداقل کردن انحراف موعد تحویل، حداقل جریمه دیرکرد یا حداقل حداکثر دیرکرد را بهینه می کند. انگيزه بسياري از توسعهها و پيشرفتهاي علمي در حوزه زمانبندي برخاسته از محيطهاي صنعتي است و بهطور طبيعي در بيان مفاهيم زمانبندي از واژههاي بکار رفته در صنعت استفاده ميشود. به همين خاطر منابع با عنوان ماشين بهکار ميروند و به هر کدام از فعاليتها، کار اطلاق ميشود بطوريکه کارها اغلب به وسيله مجموعهاي از ماشينها در ايستگاههاي مختلف کاري با توالي مشخص پردازش ميشوند.بطور کلي، مسائل زمانبندي به صورت مسائل بهينهسازي محدوديتدار بيان ميشوند که در آنها به بررسي تصميمات مربوط به تخصيص ماشينها وتوالي پردازش کارها پرداخته ميشود. درحالتي که تنها يک ماشين موجود است، تعيين توالي پردازش کارها يک برنامه زماني کامل را تشکيل ميدهد. مسائل تکماشينه با وجود سادگي ذاتي، سنگبناي درک فراگير مفاهيم زمانبندي را تشکيل ميدهند. درمقابل، زمانبندي مسائل چندماشينه شامل سيستمهاي موازي، سيستمهاي متوالي و سيستمهاي ترکيبي ميباشد. در سيستمهاي موازي، هر يک از کارها با انجام يک عمليات همانند مسائل تکماشينه بر روي يکي از ماشينهاي موازي موجود پردازش ميشوند و به دنبال آن تخصيص ماشينها به کارها موضوعيت پيدا ميکند. اين درحالي است که در سيستم هاي متوالي و ترکيبي، کارها با انجام چند عمليات بر روي ماشينها پردازش ميشوند و مسائل مربوطه ساختار نسبتا پيچيدهتري را تجربه ميکنند.در اين تحقيق، به بررسي مسئله زمانبندي ماشينهاي موازي نامرتبط[7] به عنوان دسته مهمي از مسائل زمانبندي که داراي اهميت فراوان از نقطهنظر تئوري و تجربي است، پرداخته ميشود. مسائل ماشينهاي موازي نامرتبط حالت عموميتيافته مسائل تکماشينه و حالت خاصي از مسائل ماشينهاي متوالي منعطف محسوب ميشوند. تکنيکهاي بهکار رفته در بهينهسازي اين نوع مسائل با اعمال رويههاي ترکيبي در مسائل زمانبندي پيچيدهتر استفاده ميشوند. در بخشهاي آتي اين فصل، شرح تفصيلي مسئله مورد بررسي اين تحقيق ارائه ميشود.زمانبندي ماشينهاي موازي نامرتبط حالت عمومي مسائل کلاسيک ماشينهاي موازي بهشمار ميآيد. در يک مسئله کلاسيک زمانبندي ماشينهاي موازي، مجموعهاي از کارهاي مستقلوجود دارد که هر کدام از آنها بر روي يکي از ماشينهاي موازي يکسان موجود پردازش ميشوند. در حالت کلي، ماشينهاي موازي به صورت نامرتبط درنظر گرفته ميشوند بطوريکه زمان پردازش کارها بر روي ماشينها نهتنها به نوع کار بلکه به نوع ماشين نيز وابسته است. در اين حالت پيکربندي ماشينها يکسان نيست و رابطه مشخصي بين زمانهاي پردازش کارها بر روي ماشينهاي مختلف وجود ندارد. محيطهاي کارگاهي شامل ماشينهاي موازي نامرتبط در صنايع توليدي گوناگون نظير صنايع نساجي، الکترونيک، شيميايي و همچنين صنايع خدماتي به وفور بهچشم ميخورد [59].در برخي از کاربردهاي زمانبندي ماشينهاي موازي نامرتبط، ماشينها داراي سطوح تکنولوژيکي متفاوتي هستند و لزوما قادر به پردازش هر يک از کارهاي موجود در مجموعه کارها نميباشند. در نتيجه، هرکدام از کارها تنها بر روي زيرمجموعهاي از مجموعه ماشينها ميتوانند پردازش شوند و اصطلاحا پردازش کارها با دسترسي محدود به ماشينها[8] صورت ميپذيرد.مسائل زمانبندي غالبا به محيطهاي کارگاهي ميپردازند که در آنها زمان نصب[9] ماشين ناديده گرفته ميشود و يا به عنوان بخشي از زمان پردازش کارها تلقي ميشود. اينگونه محيطهاي کارگاهي با اين فرض مدلسازي ميشوند که زمانهاي نصب در مقايسه با زمانهاي پردازش کوچک هستند بنابراين ميتوان آنها را ناديده گرفت و يا اين که زمانهاي نصب مستقل از توالي پردازش کارها بر روي ماشينها هستند، در نتيجه ميتوان آنها را به زمانهاي پردازش اضافه نمود. با اين وجود، در بسياري از محيطهاي صنعتي يک زمان نصب وابسته به توالي[10] هنگام تعويض کارها بر روي ماشينها به وقوع ميپيوندد [55]. در اين شرايط، زمان نصب به عنوان بخشي مجزا از زمان پردازش درنظر گرفته ميشود که مقدار آن علاوه بر نوع کاري که بر روي ماشين پردازش خواهد شد، به نوع کار قبلي که بر روي آن ماشين پردازش شده نيز بستگي دارد. تلقي زمان نصب به صورت مجزا از زمان پردازش در بيشتر تکنيکهاي مديريت توليد نوظهور نظير توليد به موقع[11]و تکنولوژي گروهي[12] مورد استقاده قرار ميگيرد.