واژههای کلیدی: ماشینهای موازی نامرتبط، فرآیندهای دوبارهکاری، زمان نصب وابسته به توالی کارها و وابسته به نوع ماشین، دسترسی محدود به ماشینهافصل اول. 1کلیات تحقیق.. 11-1. مقدمه. 21-2. تعریف مسئله. 31-3. اهداف تحقیق.. 61-4. مفروضات عمومی مسئله. 61-5. ضرورت انجام تحقیق.. 61-6. محتویات تحقیق.. 7فصل دوم. 8مرور ادبیات و پیشینه تحقیق.. 82-1. مقدمه. 92-2. محیطهای کارگاهی.. 112-2-1. تک ماشینه. 112-2-2 . ماشینهای موازی.. 112-2-2-1. ماشینهای موازی یکسان. 112-2-2-2. ماشینهای موازی یکنواخت.. 112-2-2-3. ماشینهای موازی نامرتبط.. 122-2-3 . جریان کارگاهی.. 122-2-4 .جریان کارگاهی منعطف.. 122-2-5 . کار کارگاهی.. 122-2-6 . کار کارگاهی منعطف.. 122-2-7 . سیستم کارگاهی باز. 132-2-8 . سیستم ساخت انعطاف پذیر. 132-2-9. سیستم کارگاهی وابسته. 132-3. جزئیات و محدودیتهای نحوه پردازش کارها132-3-1. زمان دسترسی به کار . 132-3-2. زمان نصب وابسته به توالی. 142-3-3. شکست در کارها. 142-3-4. اولویت در پردازش کارها. 142-3-5. خرابی ماشین.. 142-3-6. دسترسی محدود به ماشینها. 142-3-7. جایگشت.. 142-3-8. بلوکه شدن. 152-3-9. بدون انتظار. 152-3-10. گردش مجدد. 152-3-11. گروههای کاری. 152-3-12. پردازش دستهای. 152-4. توابع هدف.. 162-4-1. بیشینه زمان تکمیل کارها. 162-4-2. بیشینه زمان تاخیر کارها . 162-4-3. مجموع زمان تکمیل کارها . 162-4-4. مجموع وزنی زمان تکمیل کارها . 162-4-5. مجموع زمان دیر کرد کارها . 162-4-6. مجموع وزنی زمان دیرکرد کارها. 162-4-7. مجموع تعداد کارهای با تاخیر . 172-4-8. مجموع وزنی تعداد کارهای با تاخیر . 172-4-9. مجموع زمانهای زودکرد و دیرکرد کارها . 172-4-10. مجموع وزنی زمانهای زودکرد و دیرکرد کارها . 172-5. پیشینه تحقیق.. 172-6. ماشینهای موازی نامرتبط.. 182-7. دوبارهکاری.. 212-8. زمان نصب وابسته به توالی کارها242-9. دسترسی محدود به ماشینها272-10. جمع بندی.. 29فصل سوم. 30مدل ریاضی پیشنهادی.. 303-1. مقدمه. 313-2. تعریف مسئله. 313-2. مفروضات مسئله. 323-3. مدل ریاضی پیشنهادی.. 333-3-1. اندیسها و پارامترهای ورودی به مدل. 343-3-2. متغیرهای تصمیمگیری.. 343-3-3. تابع هدف.. 353-3-4. محدودیتها363-4. اعتبار سنجی مدل. 403-5. پیچیدگی مسئله. 433-6. الگوریتم ژنتیک.. 463-6-1. تاریخچه الگوریتم ژنتیک.. 473-6-2. واژگان ژنتیک.. 483-6-3. ساختار الگوریتم ژنتیک.. 493-6-4. کدگذاری.. 503-6-5. ایجاد جمعیت اولیه. 513-6-6. اعمال ژنتیک.. 523-6-6-1. عملگرهای تقاطعی.. 523-6-6-1-1. يك نقطه برش.. 533-6-6-1-2. دو نقطه برش.. 543-6-6-2. عملگرهای جهشی.. 543-6-6-2-1. جابجايي.. 553-6-6-2-2. وارونگي.. 563-6-6-2-3. الحاق یا جاسازی.. 563-6-7. عمل تحول. 573-6-7-1. فضای نمونه گیری.. 573-6-7-2. فضای نمونه گیری عادی.. 573-6-7-3. مکانیسم نمونه گیری.. 573-6-7-4. احتمال انتخاب.. 583-6-8. تابع برازش.. 593-6-9 . استراتژی برخورد با محدودیت.. 593-6-9-1. استراتژی اصلاح عملگرهای ژنتیک.. 603-6-9-2. استراتژی ردی.. 603-6-9-3. استراتژی اصلاحی.. 603-6-9-4. استراتژی جریمه ای.. 603-6-10. معیار توقف.. 613-7. الگوریتم زنبور عسل. 623-7-1. مراحل اجرای الگوریتم. 633-7-2. پارامتر های الگوریتم. 643-7-3. فلوچارت الگوریتم زنبور عسل. 643-7-4. شرح مراحل اجرای الگوریتم. 653-8. جمعبندی.. 66فصل چهارم. 67نتایج محاسباتی و تحلیل آن. 674-1.مقدمه. 684-2. پیادهسازی الگوریتم ژنتیک.. 684-2-1. ساختار کروموزوم. 694-2-2. جمعیت اولیه. 704-2-3. ارزیابی برازندگی تابع هدف.. 714-2-4. استراتژی انتخاب.. 714-2-5. اپراتورهای ژنتیک.. 734-2-6. همگرایی الگوریتم ژنتیک.. 754 -2-7.معیار توقف.. 754-3. پیادهسازی الگوریتم زنبور عسل( شماره یک). 764-3-1. مراحل اجرای الگوریتم زنبورعسل (شماره یک). 764-3-2. پارامترهای الگوریتم زنبورعسل (شماره یک). 774-3-3. روابط حاکم بر مقادیر پارامترها در الگوریتمزنبورعسل (شماره یک). 774-4. پیادهسازی الگوریتم زنبور عسل(شماره دو). 784-4-1. مراحل اجرای الگوریتم زنبورعسل (شماره دو). 784-4-2. پارامترهای الگوریتم زنبورعسل (شماره دو). 794-5. مجموعه دادهها814-6. تنظیم پارامترهای کنترلی الگوریتمها814-7. طراحی آزمایشات چندعاملی برای مسائل با ابعاد متوسط.. 844-7-1.تحلیل نتایج آماری.. 884-8. طراحی آزمایشات چندعاملی برای مسائل باابعاد بزرگ.. 924-8-1.تحلیل نتایج آماری.. 964-9. نتایج محاسباتی.. 994-10. جمعبندی.. 108فصل پنجم. 109نتیجه گیری و پیشنهادات.. 1095-1. مقدمه. 1105-2. نتیجه گیری.. 1105-3. پیشنهادات آتی.. 1115-3-1. پیشنهادات در زمینه ماهیت مسئله طرح شده در تحقیق.. 1115-3-2. پیشنهادات در زمینه روش حل مسئله. 112فهرست منابع. 113پیوست.. 119 جدول 4-1. مقادیر دادههای ورودی به مسائل آزمایشی.. 81جدول 4-2. پارامترهای کنترلی الگوریتم ژنتیک.. 83جدول 4-3. پارامترهای کنترلی الگوریتم زنبور شماره یک.. 83جدول 4-4. پارامترهای کنترلی الگوریتم زنبور شماره دو. 83جدول 4-5. فاکتورها و سطوح آنها در الگوریتم زنبور شماره یک در ابعاد متوسط.. 84جدول 4-6. فاکتورها و سطوح آنها در الگوریتم زنبور شماره دو در ابعاد متوسط.. 84جدول 4-7. فاکتورها و سطوح آنها در الگوریتم ژنتیک در ابعاد متوسط.. 84جدول 4-8 . ترکیب فاکتورها و سطوح پاسخ مربوط به الگوریتم زنبور1 در مسائل با ابعاد متوسط.. 85جدول4-9 . ضرایب همبستگی تخمینی مدل برای نسبتهای SN، الگوریتم زنبور1، ابعاد متوسط.. 86جدول4-10. آنالیز واریانس برای نسبتهای SN، الگوریتم زنبور1، ابعاد متوسط.. 86جدول 4-11. ضرایب همبستگی تخمینی مدل برای میانگین پاسخها، الگوریتم زنبور1، ابعاد متوسط.. 87جدول 4-12. آنالیز واریانس برای میانگین پاسخها، الگوریتم زنبور1، ابعاد متوسط.. 87جدول 4-13. جدول پاسخ نسبتهای SN، الگوریتم زنبور1، ابعاد متوسط.. 88جدول4-14. جدول پاسخ میانگینها، الگوریتم زنبور1، ابعاد متوسط.. 88جدول 4-15. مقادیر پارامترهای کنترلی الگوریتم زنبور 1، ابعاد متوسط.. 90جدول 4-16.مقادیر پارامترهای کنترلی الگوریتم زنبور 2، ابعاد متوسط.. 91جدول 4-17. مقادیر پارامترهای کنترلی الگوریتم ژنتیک، ابعاد متوسط.. 91جدول 4-18. فاکتورها و سطوح آنها در الگوریتم زنبور شماره یک برای ابعاد بزرگ.. 92جدول 4-19. فاکتورها و سطوح آنها در الگوریتم زنبور شماره دو برای ابعاد بزرگ.. 92جدول 4-20. فاکتورها و سطوح آنها در الگوریتم ژنتیک برای ابعاد بزرگ.. 92جدول 4-21. ترکیب فاکتورها و سطوح پاسخ مربوط به الگوریتم زنبور1 در مسائل با ابعاد بزرگ.. 93جدول 4-22 . ضرایب همبستگی تخمینی مدل برای نسبتهای SN، الگوریتم زنبور1، ابعاد بزرگ.. 94جدول 4-23 . آنالیز واریانس برای نسبتهای SN، الگوریتم زنبور1، ابعاد بزرگ.. 94جدول 4-24. ضرایب همبستگی تخمینی مدل برای میانگین پاسخها، الگوریتم زنبور1، ابعاد بزرگ.. 95جدول 4-25. آنالیز واریانس برای میانگین پاسخها، الگوریتم زنبور1، ابعاد بزرگ.. 95جدول 4-26. جدول پاسخ نسبتهای SN، الگوریتم زنبور1، ابعاد بزرگ.. 96جدول4-27. جدول پاسخ میانگینها، الگوریتم زنبور1، ابعاد بزرگ.. 96جدول4-28. مقادیر پارامترهای کنترلی الگوریتم زنبور1، ابعاد بزرگ.. 98جدول4-29. مقادیر پارامترهای کنترلی الگوریتم زنبور2، ابعاد بزرگ.. 98جدول4-30. مقادیر پارامترهای کنترلی الگوریتم ژنتیک، ابعاد بزرگ.. 98جدول4-31. نتایج محاسباتی حاصل از حل مسائل با ابعاد کوچک.. 100جدول4-32. زمانهای محاسباتی و میانگین جوابهای حاصل از حل مسائل با ابعاد کوچک.. 101جدول4-33. نتایج محاسباتی حاصل از حل مسائل با ابعاد متوسط.. 103جدول4-34. زمانهای محاسباتی و میانگین جوابهای حاصل از حل مسائل با ابعاد متوسط.. 103جدول4-35. نتایج محاسباتی حاصل از حل مسائل با ابعاد بزرگ.. 105جدول4-36. زمانهای محاسباتی و میانگین جوابهای حاصل از حل مسائل با ابعاد بزرگ.. 105جدول4-37. مقادیر RPD برای الگوریتمهای ژنتیک، رنبور1 و زنبور2. 107 شکل3-1. حل گرافیکی مسئله (m=2,n=3,L=3) در شرایط فعال نبودن محدودیت دسترسی به ماشینها40شکل3-2. حل گرافیکی مسئله (m=2,n=3,L=3) در شرایط اعمال محدودیت دسترسی به ماشینها41شکل3-3. حل گرافیکی مسئله (m=2,n=3,L=3) در شرایط افزایش در زمان نصب کار شماره 3. 42شکل3-4. سلسله مراتب پیچیدگی محیطهای کارگاهی در مسائل زمانبندی ]4[44شکل 3-5. سلسله مراتب پیچیدگی جزئیات نحوه پردازش و محدودیتها در مسائل زمانبندی ]4[44شکل 3-6. سلسله مراتب پیچیدگی توابع هدف در مسائل زمانبندی ]4[44شکل 3-7. سلسله مراتب پیچیدگی تعدادی از مسائل زمانبندی با تابع هدف Makespan]4[45شکل 3-8 .مقایسه فضاهای ژنوتیپ و فنوتیپ.. 48شکل 3-9. فضای موجه، ناموجه و غیرقانونی.. 51شکل3-10 . نحوه عملکرد اپراتور تقاطع یک نقطه برش... 53شکل3-11. اپراتور تقاطع تک نقطهای.. 54شکل 4-1. رویه کلی الگوریتم ژنتیک.. 68شکل4-2. روش نمایش جواب.. 70شکل 4-3. عملیات تقاطع. 74شکل 4-4. پاسخ میانگینها، الگوریتم زنبور1، ابعاد متوسط.. 89شکل 4-5. میانگین نسبت SN، الگوریتم زنبور1، ابعاد متوسط.. 90شکل 4-6 . پاسخ میانگینها، الگوریتم زنبور1 ، ابعاد بزرگ.. 97شکل 4-7 . میانگین نسبت SN، الگوریتم زنبور 1، ابعاد بزرگ.. 97شکل 4-8. میانگین زمان محاسباتی الگوریتمها در ابعاد کوچک (2ماشین)102شکل 4-9. میانگین زمان محاسباتی الگوریتمها در ابعاد متوسط.. 104شکل 4-10. میانگین زمان محاسباتی الگوریتمها در ابعاد بزرگ.. 106شکل 4-11. نمودار LSD در سطح اطمینان 95% برای معیار RPD.. 107فصل اول کلیات تحقیق 1-1. مقدمهمسائل زمانبندی[1] یکی از مهمترین مسائل دنیای امروز میباشند که تاثیر شگرفی در افزایش بهرهوری سیستمهای تولیدی و خدماتی دارند. زمانبندی در عملبهمعنای تخصیص منابع محدود به فعالیتهایی است که به آن منبع نیاز دارند و در واقع نوعی فعالیت تصمیمگیری است که با هدف بهینهسازی یک و یا چند معیار انجام میگیرد. باید به این نکته توجه داشت که در دنیای رقابتی کنونی، برای موسسهها، داشتن بهترین توالی انجام عملیات و زمانبندی مناسب فعالیتهایک نیاز اساسی به منظور بقاء تعریف میشودو بهعنوان یک فرآیند تصمیمگیری، مبنای کار بسیاری از صنایع تولیدی و خدماتی محسوب میشود. به بیان بهتر، زمانبندی را میتوان تخصیص منابع محدود در طول زمان بهمنظور اجرای مجموعهای از وظایف تعریف کرد. در دنیای امروز، زمان همواره یک محدودیت اساسی بوده است. بنابراین، زمانبندی صحیح فعالیتها بهمنظور حداقل کردن این منبع با توجه به هزینههای تولیدی و خدماتی در واحد زمان، امری ضروری به نظر میرسد.با پیشرفت علم و بهدنبال آن توسعه و شکوفایی صنایع تولیدی و خدماتی، نقش منابع و نحوه تخصیص آنها از اهمیت دو چندانی برخوردار شده است. امروزه منابع در دسترس مانند نیروی انسانی، ماشینآلات، مواد اولیه و ... به عنوان منابع بحرانی در تولید و فعالیتهای خدماتی در نظر گرفته میشوند و زمانبندی و تخصیص به موقع و مناسب این منابع منجر به ارتقاء کارایی، بهرهوری و در نهایت سودآوری بیشتر میشود. از آنجا که خواستگاه بسیاری از مسائل زمانبندی و توالی عملیات محیط های صنعتی میباشد، در بیان بسیاری از مفاهیم زمانبندی از واژههای بکار رفته در صنعت استفاده میشود. به عنوان مثال، در مباحث زمانبندی و توالی عملیات از منابع با عنوان ماشین[2] و از فعالیتها با عنوان کار[3] یاد میشود به نحوی که کارها اغلب بوسیله ماشینها در ایستگاههای مختلف کاری با توالی مشخص پردازش میشوند.در مسائل زمانبندی، هدف از یافتن توالی انجام کارها میتواند متفاوت باشد. تعدادی از اهداف مورد استفاده در مسائل زمانبندی عبارتند از: کمینهسازی بیشترین زمان تکمیل کارها،کمینهسازی مجموع زمان تکمیل کارها، کمینهسازی بیشترین زمان دیرکرد و کمینهسازی تعداد کارهایی که دیرکرد دارند. همچنین بر حسب شرایط حاکم بر محیط مورد مطالعه، محدودیتهای گوناگونی در مسئله لحاظ میشود. تعدادی از محدودیتهای حاکم بر مسائل زمانبندی عبارتند از : زمانهای نصب وابسته به توالی ، محدودیت دسترسی به ماشینها، زمانهای دسترسی به کار، برش در کارها، خرابی ماشینها و محدودیت در اندازه صف کارها که مورد آخر در سیستمهای جریان کارگاهی می تواند لحاظ شود. در ابتدای فصل دوم، مسائل زمانبندی به تفکیک محیطهای کارگاهی، محدودیتهای پردازش و توابع هدف بصورت مختصر معرفی میشوند. یک مسئله زمانبندی بصورت یک مسئله بهینهسازی بیان میشود که با توجه به محدودیتهای موجود، به دنبال ارضاء کردن هدف (اهداف) مورد نظر میباشد.در مباحث زمانبندی، بررسی مدلهای تک ماشینه به علت سادگی و به دلیل اینکه حالت خاصی از سایر مدلها میباشد از اهمیت بالایی برخوردار است. در مقابل، نظریه زمانبندی سه نوع اساسی از مدلهایچند ماشینی را پوشش میدهد: سیستمهای موازی، سیستمهایجریان کارگاهیو سیستمهایتولید کارگاهی.در سیستمماشینهای موازی همانند مدلهای تک ماشینی، هر یک از کارها با انجام یک عملیات بر روی یکی از ماشینهای موازی موجود پردازش میشوند اما در سیستمهای جریان کارگاهی و ترکیبی ساختار مسائل پیچیدهتر است.در ادامه به تعریف مسئله مورد بحث این تحقیق و مفروضات آن پرداخته میشود. در پایان اهداف و ضرورت تحقیق بیان میشود.1-2. تعریف مسئلهمسئله زمانبندی ماشینهای موازی نامرتبط[4]، بهعنوان دسته مهمی از مسائل زمانبندی که دارای اهمیت فراوان از نقطه نظر تئوری و تجربی است شناخته میشود. مسائل ماشینهای موازی نامرتبط حالت عمومیت یافته مسائل تک ماشینه و مسائل کلاسیک ماشینهای موازی و حالت خاصی از مسائل ماشینهای متوالی منعطف[5] محسوب میشوند. در مسائل کلاسیک ماشینهای موازی، مجموعهای از کارهای مستقل وجود دارد که هر کدام از آنها بر روی یکی از ماشینهای موازی یکسان موجود پردازش میشود و زمان پردازش کار نوع jبر روی تمامی ماشینها یکسان است ولی در حالت نامرتبط بودن ماشینها، زمان پردازش کارها بر روی ماشینها نه تنها به نوع کار بلکه به نوع ماشین نیز وابسته است و رابطه مشخصی بین زمانهای پردازش کارها بر روی ماشینهای مختلف وجود ندارد.در بسیاری از تحقیقات و مقالات ارائه شده در زمینه مسائل زمانبندی فرض بر این است که محصولات تولیدی توسط ماشینها دارای کیفیت قابل قبول هستند. ولی در دنیای واقعی این فرض چندان منطبق بر شرایط تولیدی نمیباشد و تولید اقلام معیوب به دلایل متعدد امری اجتناب ناپذیر است. از جمله این دلایل عبارتند از:در مسئله زمانبندی ماشینهای موازی نامرتبط از آنجایی که ممکن است دلیل نامرتبط بودن ماشینها، تفاوت میان عملیات قابل پردازش توسط آنها باشد و هر ماشین لزوما قادر به پردازش هر یک از کارهای موجود در مجموعه کارها نباشد، بنابراین دور از منطق نیست که محدودیت دسترسی به ماشینها[6] در مسئله مورد بررسی در نظر گرفته شود. این محدودیت تضمین میکند که هر کار تنها توسط زیرمجموعهای از ماشینها قابل پردازش باشد و اصطلاحا پردازش کارها با دسترسی محدود به ماشینها صورت میپذیرد.در بسیاری از مسائل زمانبندی فرض بر این بوده است که تمام کارها در ابتدای افق زمانبندی در دسترس هستند. واضح است که در دنیای واقعی لزوما این موضوع صحیح نیست و ممکن است کارها به تدریج وارد سیستم شوند و از ابتدا در دسترس نباشند. در نتیجه محدودیت زمان دسترسی به کارها[7] در مدل پیشنهادی لحاظ خواهد شد.مسائل زمانبندی غالبا به محیطهای تولیدی و خدماتی میپردازند که در آنها زمان نصب ماشین نادیده گرفته میشود و یا به عنوان بخشی از زمان پردازش کارها تلقی میشود. این نوع محیطهای تولیدی و یا خدماتی با این فرض مدلسازی میشوند که زمانهای نصب در مقایسه با زمانهای پردازش کوچک هستند، بنابراین میتوان آنها را نادیده گرفت و یا اینکه زمانهای نصب مستقل از توالی پردازش کارها بر روی ماشینها هستند، در نتیجه میتوان آنها را به زمان پردازش اضافه نمود. با این وجود در بسیاری از محیطهای صنعتی یک زمان نصب وابسته به توالی[8] هنگام تعویض کارها بر روی ماشینها به وقوع میپیوندد ]3[. در این شرایط زمان نصب بهعنوان بخشی مجزا از زمان پردازش در نظر گرفته میشود که مقدار آن علاوه بر نوع کاری که بر روی ماشین پردازش خواهد شد، به نوع کار قبلی که بر روی آن ماشین پردازش شده است نیز بستگی دارد. بهعنوان مثال، در سوراخکاری صفحات فلزی، اگر دو پردازش متوالی از دو الگوی متفاوت پیروی کنند، آنگاه برای انجام پردازش بعدی باید زمانی صرف شود و تغییرات لازم به منظور آمادهسازی ماشین صورت پذیرد.یکی از پرکاربرد ترین توابع هدف در مسائل بهینهسازی ماشینهای موازی، کمینهکردن بیشترین زمان تکمیل کارها[9] میباشد. چرا که رسیدن به این هدف سبب میشود کارها تا حد ممکن با یکنواختی بیشتری بین ماشینها توزیع شوند و به نحوی از ظرفیت کاری تمام ماشینها تا حد مطلوب استفاده شود و در نتیجه از تجمع کارها بر روی یک یا تعدادی از ماشینها جلوگیری بهعمل میآورد. از این رو معیار بیشترین زمان تکمیل کارها به عنوان معیار بهینهسازی در مدل پیشنهادی مورد استفاده قرار گرفته است.در این تحقیق، مسئله زمانبندی ماشینهای موازی نامرتبط با فرض وجود امکان دوبارهکاری[10] اقلام معیوب به همراه محدودیتهای زمان دسترسی به کارها، زمان نصب وابسته به توالی کارها و وابسته به نوع ماشین و دسترسی محدود به ماشینها با هدف کمینهسازی بیشترین زمان تکمیل کارها معرفی و مورد بررسی قرار میگیرد. در ادامه، برای مسئله یاد شده یک مدل برنامه ریزی عدد صحیح ارئه میشود. همچنین از الگوریتمهای فراابتکاری شامل الگوریتم ژنتیک[11] و الگوریتم زنبور عسل[12] برای حل آن استفاده میشود.از جمله کاربردهای مدل پیشنهادی در تحقیق پیش رو را میتوان در یک سیستم خدماتی همانند بانک مشاهده نمود. در یک بانک، چند اپراتور به صورت موازی وجود دارند که هر کدام مسئول رسیدگی به بخشی از امور بانکی هستند. بر فرض مثال اپراتور اول وظیفه بازگشایی حساب، باز گشایی ال سی، صدور انواع حوالههای بانکی و انجام امور مرتبط با انتقال وجه را بهعهده دارد و اپراتور دوم به سایر امور بانکی نظیر رسیدگی به درخواستهای وام مشتریان ، صدور گواهی سپرده، خرید و فروش اوراق مشارکت، تنظیم صورتحسابها و ... میپردازد. در این سیستم خدماتی بهدنبال آن هستیم که بهترین توالی از انجام امور بانکی مشتریان را بهنحوی بدست آوریم که بیشترین زمان تکمیل امور بانکی کمینه شود.1-3. اهداف تحقیقدر تحقیق پیش رو بهدنبال آن هستیم که با ارائه یک مدل ریاضی جدید برای مسئله ماشینهای موازی نامرتبط با فرض وجود امکان دوبارهکاری اقلام معیوب بههمراه محدودیتهای ذکر شده در بخش تعریف مسئله، به اهداف حاصل از طرح مسئله نظیر استفاده کارآمد از منابع و زمان، کاهش هزینههای تولیدی و خدماتی،جلب رضایت مشتریان و حفظ آنها و در نهایت نزدیکتر کردن مسئله زمانبندی ماشینهای موازی نا مرتبط به مسائل دنیای واقعی نائل شویم.1-4. مفروضات عمومی مسئله1-5. ضرورت انجام تحقیقمسائل زمانبندی ماشینهای موازی نامرتبط، یکی از کاربردی ترین مسائل در سیستمهای تولیدی و خدماتی میباشد که در مقایسه با انواع دیگر مسائل ماشینهای موازی، با توجه کمتری از سوی محققین روبرو بوده است. همچنین، موضوع کاهش هزینههای تولید همواره بهعنوان یکی از اهداف عملیاتی بیشتر واحدهای تولیدی مطرح بوده است و یکی از موثرین روشها در تحقق این هدف، دوبارهکاری اقلام معیوب میباشد. لذا در این تحقیق، مسئله زمانبندی ماشینهای موازی نامرتبط با فرض امکان دوبارهکاری اقلام معیوب مورد بررسی قرار میگیرد. همچنین در مسئله فوق، بدلیل اهمیت زمانهای آمادهسازی وابسته به توالی در بسیاری از صنایع، فرض وابسته بودن زمان آمادهسازی ماشین به توالی کارها و نوع ماشینآلات در مسئله لحاظ شده است. با تحقیقات صورتگرفته در زمینه مسائل زمانبندی ماشینهای موازی، جای خالی تحقیقی که در آن مسئله ماشینهای موازی نامرتبط با فرض امکان دوبارهکاری اقلام فاقد کیفیت و محدودیتهای زمان دسترسی به کارها، زمان نصب وابسته به توالی و وابسته به نوع ماشین و دسترسی محدود به ماشینها مورد بررسی قرار گرفته باشد، احساس میشد. لذا در تحقیق پیش رو، مسئله یاد شده مورد مطالعه قرار گرفته است و یک مدل بهینهسازی برای آن ارائه میشود و از الگوریتمهای فراابتکاری شامل الگوریتم ژنتیک و الگوریتم زنبور عسل بهمنظور حل مدل در اندازههای کاربردی استفاده می شود.
زمان بندی ماشین های موازی نامرتبط به همراه دوباره کاری با در نظر گرفتن محدودیت دسترسی به ماشین ها word
واژههای کلیدی: ماشینهای موازی نامرتبط، فرآیندهای دوبارهکاری، زمان نصب وابسته به توالی کارها و وابسته به نوع ماشین، دسترسی محدود به ماشینهافصل اول. 1کلیات تحقیق.. 11-1. مقدمه. 21-2. تعریف مسئله. 31-3. اهداف تحقیق.. 61-4. مفروضات عمومی مسئله. 61-5. ضرورت انجام تحقیق.. 61-6. محتویات تحقیق.. 7فصل دوم. 8مرور ادبیات و پیشینه تحقیق.. 82-1. مقدمه. 92-2. محیطهای کارگاهی.. 112-2-1. تک ماشینه. 112-2-2 . ماشینهای موازی.. 112-2-2-1. ماشینهای موازی یکسان. 112-2-2-2. ماشینهای موازی یکنواخت.. 112-2-2-3. ماشینهای موازی نامرتبط.. 122-2-3 . جریان کارگاهی.. 122-2-4 .جریان کارگاهی منعطف.. 122-2-5 . کار کارگاهی.. 122-2-6 . کار کارگاهی منعطف.. 122-2-7 . سیستم کارگاهی باز. 132-2-8 . سیستم ساخت انعطاف پذیر. 132-2-9. سیستم کارگاهی وابسته. 132-3. جزئیات و محدودیتهای نحوه پردازش کارها132-3-1. زمان دسترسی به کار . 132-3-2. زمان نصب وابسته به توالی. 142-3-3. شکست در کارها. 142-3-4. اولویت در پردازش کارها. 142-3-5. خرابی ماشین.. 142-3-6. دسترسی محدود به ماشینها. 142-3-7. جایگشت.. 142-3-8. بلوکه شدن. 152-3-9. بدون انتظار. 152-3-10. گردش مجدد. 152-3-11. گروههای کاری. 152-3-12. پردازش دستهای. 152-4. توابع هدف.. 162-4-1. بیشینه زمان تکمیل کارها. 162-4-2. بیشینه زمان تاخیر کارها . 162-4-3. مجموع زمان تکمیل کارها . 162-4-4. مجموع وزنی زمان تکمیل کارها . 162-4-5. مجموع زمان دیر کرد کارها . 162-4-6. مجموع وزنی زمان دیرکرد کارها. 162-4-7. مجموع تعداد کارهای با تاخیر . 172-4-8. مجموع وزنی تعداد کارهای با تاخیر . 172-4-9. مجموع زمانهای زودکرد و دیرکرد کارها . 172-4-10. مجموع وزنی زمانهای زودکرد و دیرکرد کارها . 172-5. پیشینه تحقیق.. 172-6. ماشینهای موازی نامرتبط.. 182-7. دوبارهکاری.. 212-8. زمان نصب وابسته به توالی کارها242-9. دسترسی محدود به ماشینها272-10. جمع بندی.. 29فصل سوم. 30مدل ریاضی پیشنهادی.. 303-1. مقدمه. 313-2. تعریف مسئله. 313-2. مفروضات مسئله. 323-3. مدل ریاضی پیشنهادی.. 333-3-1. اندیسها و پارامترهای ورودی به مدل. 343-3-2. متغیرهای تصمیمگیری.. 343-3-3. تابع هدف.. 353-3-4. محدودیتها363-4. اعتبار سنجی مدل. 403-5. پیچیدگی مسئله. 433-6. الگوریتم ژنتیک.. 463-6-1. تاریخچه الگوریتم ژنتیک.. 473-6-2. واژگان ژنتیک.. 483-6-3. ساختار الگوریتم ژنتیک.. 493-6-4. کدگذاری.. 503-6-5. ایجاد جمعیت اولیه. 513-6-6. اعمال ژنتیک.. 523-6-6-1. عملگرهای تقاطعی.. 523-6-6-1-1. يك نقطه برش.. 533-6-6-1-2. دو نقطه برش.. 543-6-6-2. عملگرهای جهشی.. 543-6-6-2-1. جابجايي.. 553-6-6-2-2. وارونگي.. 563-6-6-2-3. الحاق یا جاسازی.. 563-6-7. عمل تحول. 573-6-7-1. فضای نمونه گیری.. 573-6-7-2. فضای نمونه گیری عادی.. 573-6-7-3. مکانیسم نمونه گیری.. 573-6-7-4. احتمال انتخاب.. 583-6-8. تابع برازش.. 593-6-9 . استراتژی برخورد با محدودیت.. 593-6-9-1. استراتژی اصلاح عملگرهای ژنتیک.. 603-6-9-2. استراتژی ردی.. 603-6-9-3. استراتژی اصلاحی.. 603-6-9-4. استراتژی جریمه ای.. 603-6-10. معیار توقف.. 613-7. الگوریتم زنبور عسل. 623-7-1. مراحل اجرای الگوریتم. 633-7-2. پارامتر های الگوریتم. 643-7-3. فلوچارت الگوریتم زنبور عسل. 643-7-4. شرح مراحل اجرای الگوریتم. 653-8. جمعبندی.. 66فصل چهارم. 67نتایج محاسباتی و تحلیل آن. 674-1.مقدمه. 684-2. پیادهسازی الگوریتم ژنتیک.. 684-2-1. ساختار کروموزوم. 694-2-2. جمعیت اولیه. 704-2-3. ارزیابی برازندگی تابع هدف.. 714-2-4. استراتژی انتخاب.. 714-2-5. اپراتورهای ژنتیک.. 734-2-6. همگرایی الگوریتم ژنتیک.. 754 -2-7.معیار توقف.. 754-3. پیادهسازی الگوریتم زنبور عسل( شماره یک). 764-3-1. مراحل اجرای الگوریتم زنبورعسل (شماره یک). 764-3-2. پارامترهای الگوریتم زنبورعسل (شماره یک). 774-3-3. روابط حاکم بر مقادیر پارامترها در الگوریتمزنبورعسل (شماره یک). 774-4. پیادهسازی الگوریتم زنبور عسل(شماره دو). 784-4-1. مراحل اجرای الگوریتم زنبورعسل (شماره دو). 784-4-2. پارامترهای الگوریتم زنبورعسل (شماره دو). 794-5. مجموعه دادهها814-6. تنظیم پارامترهای کنترلی الگوریتمها814-7. طراحی آزمایشات چندعاملی برای مسائل با ابعاد متوسط.. 844-7-1.تحلیل نتایج آماری.. 884-8. طراحی آزمایشات چندعاملی برای مسائل باابعاد بزرگ.. 924-8-1.تحلیل نتایج آماری.. 964-9. نتایج محاسباتی.. 994-10. جمعبندی.. 108فصل پنجم. 109نتیجه گیری و پیشنهادات.. 1095-1. مقدمه. 1105-2. نتیجه گیری.. 1105-3. پیشنهادات آتی.. 1115-3-1. پیشنهادات در زمینه ماهیت مسئله طرح شده در تحقیق.. 1115-3-2. پیشنهادات در زمینه روش حل مسئله. 112فهرست منابع. 113پیوست.. 119 جدول 4-1. مقادیر دادههای ورودی به مسائل آزمایشی.. 81جدول 4-2. پارامترهای کنترلی الگوریتم ژنتیک.. 83جدول 4-3. پارامترهای کنترلی الگوریتم زنبور شماره یک.. 83جدول 4-4. پارامترهای کنترلی الگوریتم زنبور شماره دو. 83جدول 4-5. فاکتورها و سطوح آنها در الگوریتم زنبور شماره یک در ابعاد متوسط.. 84جدول 4-6. فاکتورها و سطوح آنها در الگوریتم زنبور شماره دو در ابعاد متوسط.. 84جدول 4-7. فاکتورها و سطوح آنها در الگوریتم ژنتیک در ابعاد متوسط.. 84جدول 4-8 . ترکیب فاکتورها و سطوح پاسخ مربوط به الگوریتم زنبور1 در مسائل با ابعاد متوسط.. 85جدول4-9 . ضرایب همبستگی تخمینی مدل برای نسبتهای SN، الگوریتم زنبور1، ابعاد متوسط.. 86جدول4-10. آنالیز واریانس برای نسبتهای SN، الگوریتم زنبور1، ابعاد متوسط.. 86جدول 4-11. ضرایب همبستگی تخمینی مدل برای میانگین پاسخها، الگوریتم زنبور1، ابعاد متوسط.. 87جدول 4-12. آنالیز واریانس برای میانگین پاسخها، الگوریتم زنبور1، ابعاد متوسط.. 87جدول 4-13. جدول پاسخ نسبتهای SN، الگوریتم زنبور1، ابعاد متوسط.. 88جدول4-14. جدول پاسخ میانگینها، الگوریتم زنبور1، ابعاد متوسط.. 88جدول 4-15. مقادیر پارامترهای کنترلی الگوریتم زنبور 1، ابعاد متوسط.. 90جدول 4-16.مقادیر پارامترهای کنترلی الگوریتم زنبور 2، ابعاد متوسط.. 91جدول 4-17. مقادیر پارامترهای کنترلی الگوریتم ژنتیک، ابعاد متوسط.. 91جدول 4-18. فاکتورها و سطوح آنها در الگوریتم زنبور شماره یک برای ابعاد بزرگ.. 92جدول 4-19. فاکتورها و سطوح آنها در الگوریتم زنبور شماره دو برای ابعاد بزرگ.. 92جدول 4-20. فاکتورها و سطوح آنها در الگوریتم ژنتیک برای ابعاد بزرگ.. 92جدول 4-21. ترکیب فاکتورها و سطوح پاسخ مربوط به الگوریتم زنبور1 در مسائل با ابعاد بزرگ.. 93جدول 4-22 . ضرایب همبستگی تخمینی مدل برای نسبتهای SN، الگوریتم زنبور1، ابعاد بزرگ.. 94جدول 4-23 . آنالیز واریانس برای نسبتهای SN، الگوریتم زنبور1، ابعاد بزرگ.. 94جدول 4-24. ضرایب همبستگی تخمینی مدل برای میانگین پاسخها، الگوریتم زنبور1، ابعاد بزرگ.. 95جدول 4-25. آنالیز واریانس برای میانگین پاسخها، الگوریتم زنبور1، ابعاد بزرگ.. 95جدول 4-26. جدول پاسخ نسبتهای SN، الگوریتم زنبور1، ابعاد بزرگ.. 96جدول4-27. جدول پاسخ میانگینها، الگوریتم زنبور1، ابعاد بزرگ.. 96جدول4-28. مقادیر پارامترهای کنترلی الگوریتم زنبور1، ابعاد بزرگ.. 98جدول4-29. مقادیر پارامترهای کنترلی الگوریتم زنبور2، ابعاد بزرگ.. 98جدول4-30. مقادیر پارامترهای کنترلی الگوریتم ژنتیک، ابعاد بزرگ.. 98جدول4-31. نتایج محاسباتی حاصل از حل مسائل با ابعاد کوچک.. 100جدول4-32. زمانهای محاسباتی و میانگین جوابهای حاصل از حل مسائل با ابعاد کوچک.. 101جدول4-33. نتایج محاسباتی حاصل از حل مسائل با ابعاد متوسط.. 103جدول4-34. زمانهای محاسباتی و میانگین جوابهای حاصل از حل مسائل با ابعاد متوسط.. 103جدول4-35. نتایج محاسباتی حاصل از حل مسائل با ابعاد بزرگ.. 105جدول4-36. زمانهای محاسباتی و میانگین جوابهای حاصل از حل مسائل با ابعاد بزرگ.. 105جدول4-37. مقادیر RPD برای الگوریتمهای ژنتیک، رنبور1 و زنبور2. 107 شکل3-1. حل گرافیکی مسئله (m=2,n=3,L=3) در شرایط فعال نبودن محدودیت دسترسی به ماشینها40شکل3-2. حل گرافیکی مسئله (m=2,n=3,L=3) در شرایط اعمال محدودیت دسترسی به ماشینها41شکل3-3. حل گرافیکی مسئله (m=2,n=3,L=3) در شرایط افزایش در زمان نصب کار شماره 3. 42شکل3-4. سلسله مراتب پیچیدگی محیطهای کارگاهی در مسائل زمانبندی ]4[44شکل 3-5. سلسله مراتب پیچیدگی جزئیات نحوه پردازش و محدودیتها در مسائل زمانبندی ]4[44شکل 3-6. سلسله مراتب پیچیدگی توابع هدف در مسائل زمانبندی ]4[44شکل 3-7. سلسله مراتب پیچیدگی تعدادی از مسائل زمانبندی با تابع هدف Makespan]4[45شکل 3-8 .مقایسه فضاهای ژنوتیپ و فنوتیپ.. 48شکل 3-9. فضای موجه، ناموجه و غیرقانونی.. 51شکل3-10 . نحوه عملکرد اپراتور تقاطع یک نقطه برش... 53شکل3-11. اپراتور تقاطع تک نقطهای.. 54شکل 4-1. رویه کلی الگوریتم ژنتیک.. 68شکل4-2. روش نمایش جواب.. 70شکل 4-3. عملیات تقاطع. 74شکل 4-4. پاسخ میانگینها، الگوریتم زنبور1، ابعاد متوسط.. 89شکل 4-5. میانگین نسبت SN، الگوریتم زنبور1، ابعاد متوسط.. 90شکل 4-6 . پاسخ میانگینها، الگوریتم زنبور1 ، ابعاد بزرگ.. 97شکل 4-7 . میانگین نسبت SN، الگوریتم زنبور 1، ابعاد بزرگ.. 97شکل 4-8. میانگین زمان محاسباتی الگوریتمها در ابعاد کوچک (2ماشین)102شکل 4-9. میانگین زمان محاسباتی الگوریتمها در ابعاد متوسط.. 104شکل 4-10. میانگین زمان محاسباتی الگوریتمها در ابعاد بزرگ.. 106شکل 4-11. نمودار LSD در سطح اطمینان 95% برای معیار RPD.. 107فصل اول کلیات تحقیق 1-1. مقدمهمسائل زمانبندی[1] یکی از مهمترین مسائل دنیای امروز میباشند که تاثیر شگرفی در افزایش بهرهوری سیستمهای تولیدی و خدماتی دارند. زمانبندی در عملبهمعنای تخصیص منابع محدود به فعالیتهایی است که به آن منبع نیاز دارند و در واقع نوعی فعالیت تصمیمگیری است که با هدف بهینهسازی یک و یا چند معیار انجام میگیرد. باید به این نکته توجه داشت که در دنیای رقابتی کنونی، برای موسسهها، داشتن بهترین توالی انجام عملیات و زمانبندی مناسب فعالیتهایک نیاز اساسی به منظور بقاء تعریف میشودو بهعنوان یک فرآیند تصمیمگیری، مبنای کار بسیاری از صنایع تولیدی و خدماتی محسوب میشود. به بیان بهتر، زمانبندی را میتوان تخصیص منابع محدود در طول زمان بهمنظور اجرای مجموعهای از وظایف تعریف کرد. در دنیای امروز، زمان همواره یک محدودیت اساسی بوده است. بنابراین، زمانبندی صحیح فعالیتها بهمنظور حداقل کردن این منبع با توجه به هزینههای تولیدی و خدماتی در واحد زمان، امری ضروری به نظر میرسد.با پیشرفت علم و بهدنبال آن توسعه و شکوفایی صنایع تولیدی و خدماتی، نقش منابع و نحوه تخصیص آنها از اهمیت دو چندانی برخوردار شده است. امروزه منابع در دسترس مانند نیروی انسانی، ماشینآلات، مواد اولیه و ... به عنوان منابع بحرانی در تولید و فعالیتهای خدماتی در نظر گرفته میشوند و زمانبندی و تخصیص به موقع و مناسب این منابع منجر به ارتقاء کارایی، بهرهوری و در نهایت سودآوری بیشتر میشود. از آنجا که خواستگاه بسیاری از مسائل زمانبندی و توالی عملیات محیط های صنعتی میباشد، در بیان بسیاری از مفاهیم زمانبندی از واژههای بکار رفته در صنعت استفاده میشود. به عنوان مثال، در مباحث زمانبندی و توالی عملیات از منابع با عنوان ماشین[2] و از فعالیتها با عنوان کار[3] یاد میشود به نحوی که کارها اغلب بوسیله ماشینها در ایستگاههای مختلف کاری با توالی مشخص پردازش میشوند.در مسائل زمانبندی، هدف از یافتن توالی انجام کارها میتواند متفاوت باشد. تعدادی از اهداف مورد استفاده در مسائل زمانبندی عبارتند از: کمینهسازی بیشترین زمان تکمیل کارها،کمینهسازی مجموع زمان تکمیل کارها، کمینهسازی بیشترین زمان دیرکرد و کمینهسازی تعداد کارهایی که دیرکرد دارند. همچنین بر حسب شرایط حاکم بر محیط مورد مطالعه، محدودیتهای گوناگونی در مسئله لحاظ میشود. تعدادی از محدودیتهای حاکم بر مسائل زمانبندی عبارتند از : زمانهای نصب وابسته به توالی ، محدودیت دسترسی به ماشینها، زمانهای دسترسی به کار، برش در کارها، خرابی ماشینها و محدودیت در اندازه صف کارها که مورد آخر در سیستمهای جریان کارگاهی می تواند لحاظ شود. در ابتدای فصل دوم، مسائل زمانبندی به تفکیک محیطهای کارگاهی، محدودیتهای پردازش و توابع هدف بصورت مختصر معرفی میشوند. یک مسئله زمانبندی بصورت یک مسئله بهینهسازی بیان میشود که با توجه به محدودیتهای موجود، به دنبال ارضاء کردن هدف (اهداف) مورد نظر میباشد.در مباحث زمانبندی، بررسی مدلهای تک ماشینه به علت سادگی و به دلیل اینکه حالت خاصی از سایر مدلها میباشد از اهمیت بالایی برخوردار است. در مقابل، نظریه زمانبندی سه نوع اساسی از مدلهایچند ماشینی را پوشش میدهد: سیستمهای موازی، سیستمهایجریان کارگاهیو سیستمهایتولید کارگاهی.در سیستمماشینهای موازی همانند مدلهای تک ماشینی، هر یک از کارها با انجام یک عملیات بر روی یکی از ماشینهای موازی موجود پردازش میشوند اما در سیستمهای جریان کارگاهی و ترکیبی ساختار مسائل پیچیدهتر است.در ادامه به تعریف مسئله مورد بحث این تحقیق و مفروضات آن پرداخته میشود. در پایان اهداف و ضرورت تحقیق بیان میشود.1-2. تعریف مسئلهمسئله زمانبندی ماشینهای موازی نامرتبط[4]، بهعنوان دسته مهمی از مسائل زمانبندی که دارای اهمیت فراوان از نقطه نظر تئوری و تجربی است شناخته میشود. مسائل ماشینهای موازی نامرتبط حالت عمومیت یافته مسائل تک ماشینه و مسائل کلاسیک ماشینهای موازی و حالت خاصی از مسائل ماشینهای متوالی منعطف[5] محسوب میشوند. در مسائل کلاسیک ماشینهای موازی، مجموعهای از کارهای مستقل وجود دارد که هر کدام از آنها بر روی یکی از ماشینهای موازی یکسان موجود پردازش میشود و زمان پردازش کار نوع jبر روی تمامی ماشینها یکسان است ولی در حالت نامرتبط بودن ماشینها، زمان پردازش کارها بر روی ماشینها نه تنها به نوع کار بلکه به نوع ماشین نیز وابسته است و رابطه مشخصی بین زمانهای پردازش کارها بر روی ماشینهای مختلف وجود ندارد.در بسیاری از تحقیقات و مقالات ارائه شده در زمینه مسائل زمانبندی فرض بر این است که محصولات تولیدی توسط ماشینها دارای کیفیت قابل قبول هستند. ولی در دنیای واقعی این فرض چندان منطبق بر شرایط تولیدی نمیباشد و تولید اقلام معیوب به دلایل متعدد امری اجتناب ناپذیر است. از جمله این دلایل عبارتند از:در مسئله زمانبندی ماشینهای موازی نامرتبط از آنجایی که ممکن است دلیل نامرتبط بودن ماشینها، تفاوت میان عملیات قابل پردازش توسط آنها باشد و هر ماشین لزوما قادر به پردازش هر یک از کارهای موجود در مجموعه کارها نباشد، بنابراین دور از منطق نیست که محدودیت دسترسی به ماشینها[6] در مسئله مورد بررسی در نظر گرفته شود. این محدودیت تضمین میکند که هر کار تنها توسط زیرمجموعهای از ماشینها قابل پردازش باشد و اصطلاحا پردازش کارها با دسترسی محدود به ماشینها صورت میپذیرد.در بسیاری از مسائل زمانبندی فرض بر این بوده است که تمام کارها در ابتدای افق زمانبندی در دسترس هستند. واضح است که در دنیای واقعی لزوما این موضوع صحیح نیست و ممکن است کارها به تدریج وارد سیستم شوند و از ابتدا در دسترس نباشند. در نتیجه محدودیت زمان دسترسی به کارها[7] در مدل پیشنهادی لحاظ خواهد شد.مسائل زمانبندی غالبا به محیطهای تولیدی و خدماتی میپردازند که در آنها زمان نصب ماشین نادیده گرفته میشود و یا به عنوان بخشی از زمان پردازش کارها تلقی میشود. این نوع محیطهای تولیدی و یا خدماتی با این فرض مدلسازی میشوند که زمانهای نصب در مقایسه با زمانهای پردازش کوچک هستند، بنابراین میتوان آنها را نادیده گرفت و یا اینکه زمانهای نصب مستقل از توالی پردازش کارها بر روی ماشینها هستند، در نتیجه میتوان آنها را به زمان پردازش اضافه نمود. با این وجود در بسیاری از محیطهای صنعتی یک زمان نصب وابسته به توالی[8] هنگام تعویض کارها بر روی ماشینها به وقوع میپیوندد ]3[. در این شرایط زمان نصب بهعنوان بخشی مجزا از زمان پردازش در نظر گرفته میشود که مقدار آن علاوه بر نوع کاری که بر روی ماشین پردازش خواهد شد، به نوع کار قبلی که بر روی آن ماشین پردازش شده است نیز بستگی دارد. بهعنوان مثال، در سوراخکاری صفحات فلزی، اگر دو پردازش متوالی از دو الگوی متفاوت پیروی کنند، آنگاه برای انجام پردازش بعدی باید زمانی صرف شود و تغییرات لازم به منظور آمادهسازی ماشین صورت پذیرد.یکی از پرکاربرد ترین توابع هدف در مسائل بهینهسازی ماشینهای موازی، کمینهکردن بیشترین زمان تکمیل کارها[9] میباشد. چرا که رسیدن به این هدف سبب میشود کارها تا حد ممکن با یکنواختی بیشتری بین ماشینها توزیع شوند و به نحوی از ظرفیت کاری تمام ماشینها تا حد مطلوب استفاده شود و در نتیجه از تجمع کارها بر روی یک یا تعدادی از ماشینها جلوگیری بهعمل میآورد. از این رو معیار بیشترین زمان تکمیل کارها به عنوان معیار بهینهسازی در مدل پیشنهادی مورد استفاده قرار گرفته است.در این تحقیق، مسئله زمانبندی ماشینهای موازی نامرتبط با فرض وجود امکان دوبارهکاری[10] اقلام معیوب به همراه محدودیتهای زمان دسترسی به کارها، زمان نصب وابسته به توالی کارها و وابسته به نوع ماشین و دسترسی محدود به ماشینها با هدف کمینهسازی بیشترین زمان تکمیل کارها معرفی و مورد بررسی قرار میگیرد. در ادامه، برای مسئله یاد شده یک مدل برنامه ریزی عدد صحیح ارئه میشود. همچنین از الگوریتمهای فراابتکاری شامل الگوریتم ژنتیک[11] و الگوریتم زنبور عسل[12] برای حل آن استفاده میشود.از جمله کاربردهای مدل پیشنهادی در تحقیق پیش رو را میتوان در یک سیستم خدماتی همانند بانک مشاهده نمود. در یک بانک، چند اپراتور به صورت موازی وجود دارند که هر کدام مسئول رسیدگی به بخشی از امور بانکی هستند. بر فرض مثال اپراتور اول وظیفه بازگشایی حساب، باز گشایی ال سی، صدور انواع حوالههای بانکی و انجام امور مرتبط با انتقال وجه را بهعهده دارد و اپراتور دوم به سایر امور بانکی نظیر رسیدگی به درخواستهای وام مشتریان ، صدور گواهی سپرده، خرید و فروش اوراق مشارکت، تنظیم صورتحسابها و ... میپردازد. در این سیستم خدماتی بهدنبال آن هستیم که بهترین توالی از انجام امور بانکی مشتریان را بهنحوی بدست آوریم که بیشترین زمان تکمیل امور بانکی کمینه شود.1-3. اهداف تحقیقدر تحقیق پیش رو بهدنبال آن هستیم که با ارائه یک مدل ریاضی جدید برای مسئله ماشینهای موازی نامرتبط با فرض وجود امکان دوبارهکاری اقلام معیوب بههمراه محدودیتهای ذکر شده در بخش تعریف مسئله، به اهداف حاصل از طرح مسئله نظیر استفاده کارآمد از منابع و زمان، کاهش هزینههای تولیدی و خدماتی،جلب رضایت مشتریان و حفظ آنها و در نهایت نزدیکتر کردن مسئله زمانبندی ماشینهای موازی نا مرتبط به مسائل دنیای واقعی نائل شویم.1-4. مفروضات عمومی مسئله1-5. ضرورت انجام تحقیقمسائل زمانبندی ماشینهای موازی نامرتبط، یکی از کاربردی ترین مسائل در سیستمهای تولیدی و خدماتی میباشد که در مقایسه با انواع دیگر مسائل ماشینهای موازی، با توجه کمتری از سوی محققین روبرو بوده است. همچنین، موضوع کاهش هزینههای تولید همواره بهعنوان یکی از اهداف عملیاتی بیشتر واحدهای تولیدی مطرح بوده است و یکی از موثرین روشها در تحقق این هدف، دوبارهکاری اقلام معیوب میباشد. لذا در این تحقیق، مسئله زمانبندی ماشینهای موازی نامرتبط با فرض امکان دوبارهکاری اقلام معیوب مورد بررسی قرار میگیرد. همچنین در مسئله فوق، بدلیل اهمیت زمانهای آمادهسازی وابسته به توالی در بسیاری از صنایع، فرض وابسته بودن زمان آمادهسازی ماشین به توالی کارها و نوع ماشینآلات در مسئله لحاظ شده است. با تحقیقات صورتگرفته در زمینه مسائل زمانبندی ماشینهای موازی، جای خالی تحقیقی که در آن مسئله ماشینهای موازی نامرتبط با فرض امکان دوبارهکاری اقلام فاقد کیفیت و محدودیتهای زمان دسترسی به کارها، زمان نصب وابسته به توالی و وابسته به نوع ماشین و دسترسی محدود به ماشینها مورد بررسی قرار گرفته باشد، احساس میشد. لذا در تحقیق پیش رو، مسئله یاد شده مورد مطالعه قرار گرفته است و یک مدل بهینهسازی برای آن ارائه میشود و از الگوریتمهای فراابتکاری شامل الگوریتم ژنتیک و الگوریتم زنبور عسل بهمنظور حل مدل در اندازههای کاربردی استفاده می شود.