واژههای کلیدی : زمانبندی ماشینهای موازی نامرتبط، محدودیتهای پیش نیازی، دسترسی محدود به ماشینها، الگوریتم ژنتیک برمبنای مرتب سازی نامغلوب، الگوریتم کلونی مورچگان چند هدفه فهرست مطالبعنوان صفحهفهرست شکل هاثفهرست جدول هاجفصل اول: کلیات تحقیق11-1. مقدمه21-2. تعریف مسئله81-3. مفروضات عمومی مسئله101-4. ضرورت و اهداف پژوهش11فصل دوم: ادبیات تحقیق122-1. مقدمه132-2. ماشین های موازی نامرتبط132-3. محدودیت پیش نیازی کارها152-4. دسترسی محدود به ماشین ها192-5. زمان آماده سازی وابسته به توالی212-6. بهینه سازی چند هدفه242-6-1. بهینگی پارتو272-6-2. ارزیابی عملکرد282-7. مسائل زمانبندی ماشین های موازی چندهدفه32فصل سوم: مدل ریاضی پیشنهادی353-1. مقدمه363-2. تعریف مسئله363-2-1. مفروضات مسئله373-3. مدل ریاضی پیشنهادی383-3-1. اندیس ها393-3-2. پارامترهای ورودی مدل393-3-3. متغیر های تصمیم گیری403-3-4. توابع هدف403-3-5- محدودیت ها403-4. اعتبارسنجی مدل43فصل چهارم: الگوریتم های پیشنهادی و نتایج محاسباتی474-1. مقدمه484-2. الگوریتم ژنتیک494-2-1. الگوریتم ژنتیک بر مبنای مرتب سازی نامغلوب (NSGA-)524-2-1-1. نمایش کروموزومی مسئله534-2-1-2. تولید جمعیت اولیه544-2-1-3. نحوه ارزیابی یک کروموزوم574-2-1-4. مرتب سازی نامغلوب سریع584-2-1-5. فاصله ازدحامی594-2-1-6. معیار انتخاب والدین604-2-1-7. عملگر تقاطع614-2-1-8. عملگر جهش624-2-1-9. استراتژی تولید دوباره634-3. الگوریتم بهینه سازی کلونی مورچگان664-3-1. نسخه چند هدفه الگوریتم بهینه سازی مورچگان (MOACO)694-3-1-1. ساختن گراف مسئله714-3-1-2. نحوهی ساختن پاسخ برای مسئله724-3-1-3. بروزرسانی فرومون ها744-4. تنظیم پارامترهای کنترل کننده و کالیبراسیون الگوریتم ها754-4-1. طراحی آزمایشات چند عاملی764-5. ارزیابی الگوریتم ها874-5-1. مجموعه داده ها874-5-2. مقایسه عملکرد الگوریتم ها برای مسائل با ابعاد کوچک884-5-3. مقایسه عملکرد الگوریتم ها برای مسائل با ابعاد متوسط904-5-4. مقایسه عملکرد الگوریتم ها برای مسائل با ابعاد بزرگ91فصل پنجم : نتيجه گيريوپيشنهادات965-1. نتیجه گیری975-2. پیشنهادات آتی98فهرست منابع99 فهرست جداولعنوان صفحهجدول 3-1. داده های مربوط به مسئله آزمایشی43جدول 3-2. نتایج بدست آمده از حل مسئله آزمایشی44جدول 3-3. نتایج بدست آمده با اضافه کردن یک محدودیت پیش نیازی جدید45جدول 3-4. نتایج بدست با اضافه کردن یک محدودیت دسترسی محدود به ماشین ها45جدول 4-1. سطوح مربوط به پارامترهای تعداد تکرار و اندازه جمعیت اولیه77جدول 4-2. فاکتورهای الگوریتم ها و سطوح مربوط به آنها77جدول 4-3. ترکیبات فاکتورها و نتایج بدست آمده برای هر آزمایش برای الگوریتم NSGA-79جدول 4-4. سطوح پاسخ مربوط به آزمایشات چند عاملی در الگوریتم NSGA-79جدول 4-5. آنالیز واریانس برای نسبت های SN برای الگوریتم NSGA-80جدول 4-6. آنالیز واریانس برای میانگین پاسخ ها برای الگوریتم NSGA-80جدول 4-7. پاسخ نسبت های SN برای الگوریتم NSGA-80جدول 4-8. پاسخ میانگین ها برای الگوریتم NSGA-80جدول 4-9. سطوح پاسخ مربوط به آزمایشات در الگوریتم MOACO83جدول 4-10. آنالیز واریانس برای نسبت های SN برای الگوریتم MOACO84جدول 4-11. آنالیز واریانس برای میانگین پاسخ ها برای الگوریتم MOACO84جدول 4-12. پاسخ نسبت های SN برای الگوریتم MOACO84جدول 4-13. پاسخ میانگین ها برای الگوریتم MOACO84جدول 4-14. مقادیر داده های ورودی به مسائل آزمایشی88جدول 4-15. نتایج محاسباتی حاصل از حل مسائل با ابعاد کوچک بخش اول89جدول 4-16. نتایج محاسباتی حاصل از حل مسائل با ابعاد کوچک بخش دوم89جدول 4-17. نتایج محاسباتی حاصل از حل مسائل با ابعاد متوسط بخش اول90جدول 4-18. نتایج محاسباتی حاصل از حل مسائل با ابعاد متوسط بخش دوم91جدول 4-19. نتایج محاسباتی حاصل از حل مسائل با ابعاد بزرگ بخش اول 92جدول 4-20. نتایج محاسباتی حاصل از حل مسائل با ابعاد بزرگ بخش دوم 92فهرست شکل هاعنوان صفحهشکل 2-1. محیط سه متغیر تصمیم و دو تابع هدف [64]28شکل 4-1. نحوه نمایش کروموزومی54شکل 4-2. نمونه ای از گراف پیش نیازی56شکل 4-3. نمایش مراحل اجرای الگوریتم اصلاحی56شکل 4-4. نمونه ای از منطقه محاسباتی معیار فاصله ازدحامی60شکل 4-5. مثالی از عملگر تقاطع پیشنهادی64شکل 4-6. مثالی از عملگر جهش پیشنهادی65شکل 4-7. نمونه ای از یک سفر برای یک مورچه73شکل 4-8. میانگین نرخ SN برای الگوریتم NSGA-82شکل 4-9. پاسخ میانگین ها برای الگوریتم NSGA-82شکل 4-10. میانگین نرخ SN برای الگوریتم MOACO86شکل 4-11. پاسخ میانگین ها برای الگوریتم MOACO86شکل 4-12. نمودار LSD با سطح اطمینان 95% برای شاخص NPS93شکل 4-13. نمودار LSD با سطح اطمینان 95% برای شاخص DM94شکل 4-14. نمودار LSD با سطح اطمینان 95% برای شاخص MID94شکل 4-15. نمودار LSD با سطح اطمینان 95% برای شاخص SNS95شکل 4-16. نمودار LSD با سطح اطمینان 95% برای شاخص QM95 فصل اول كليات تحقيق 1-1- مقدمهزمانبندی[1] و توالی عملیات یک فرآیند تصمیم گیری است که در بسیاری از صنایع خدماتی و تولیدی نقش کلیدی دارد. زمانبندی به معنی تخصیص مجموعه ای از منابع به مجموعه ای از فعالیت ها با در نظر گرفتن محدودیت های عملیاتی به منظور دستیابی به استفاده بهینه از منابع موجود با توجه به هدف و یا اهداف مورد نظر سازمان می باشد. به بیان بهتر زمانبندی در محیط های صنعتی به معنی تخصیص منابع (ماشین ها، اپراتورها، قالب ها، ابزارها و غیره) به مجموعه ای از عملیات های صنعتی می باشد. همان طور که می دانید در دنیای امروزی در اکثر امور زمان همواره یک محدودیت اساسی می باشد. بنابراین زمانبندی صحیح فعالیت ها منجر به حداقل کردن این منبع و به دنبال آن موجب کاهش هزینه های تولیدی و خدماتی می گردد.منابع و فعالیت ها در یک سازمان می توانند اشکال مختلفی داشته باشند. منابع ممکن است، ماشین ها در یک کارگاه، خطوط هوایی در یک فرودگاه، کارگران در یک پروژه ی ساخت و ساز، واحد های پردازش در یک محیط محاسباتی و غیره باشند. فعالیت ها ممکن است عملیات در فرآیند تولید، فرودها و پروازها در فرودگاه، مراحل در پروژه ساخت، اجرای برنامه های کامپیوتری و غیره باشند. اهداف نیز می توانند با توجه به خط مشیهای مختلف هر سازمان اشکال مختلفی داشته باشند، بطوریکه یک هدف می تواند حداقل کردن زمان تکمیل آخرین فعالیت و دیگری میتواند به حداقل رساندن تعداد کارهایی که پس از زمان تحویلشان تکمیل شدهاند، باشد[1]. امروزه با افزایش روز افزون نیاز به محصولات و خدمات متنوع و به دنبال آن توسعه و شکوفایی صنایع تولیدی و خدماتی مختلف منابع در دسترس از قبیل نیروی انسانی، ماشین آلات، مواد اولیه و غیره به عنوان منابع بحرانی در تولید و فعالیتهای خدماتی در نظرگرفته میشوند که زمانبندی و تخصیص به موقع و مناسب این منابع منجر به ارتقا کارایی، بهرهوری و در نهایت سود آوری بیشتر میگردد.با توسعه جهان صنعتی و با توجه به افزایش هزینههای مواد اولیه، نیروی انسانی، انرژی و حمل و نقل داشتن یک پروسه زمانبندی و توالی عملیات کارا، یک نقش اساسی را در برنامهریزی و بهره برداری از سیستمهای تولیدی و خدماتی بازی میکند. همچنین تعيين برنامه زمانبندي و توالي عمليات در مسائل برنامهريزي توليد به عنوان يكي از عوامل كليدي موفقيت در هر سازمان توليدي، نقش مهم و موثري دارد، زيرا زمانبندي توليد باعث جلوگيري از انباشت سرمايه، تقليل ضايعات، كاهش و يا حذف بيكاري ماشينآلات و تلاش براي استفاده بهتر از آنها، پاسخگویي بموقع به سفارشهاي مشتريان و تامين مواد اوليه و قطعات مورد نياز در موقع مناسب میشود.از آنجاییکه خواستگاه بسیاری از مسائل زمانبندی و توالی عملیات در محیطهای صنعتی میباشد، در بیان بسیاری از مفاهیم زمانبندی از واژههای بکاررفته در صنعت استفاده شده است. به عنوان مثال در مباحث زمانبندی از منابع بعنوان ماشینها و از فعالیتها بعنوان کار یاد میشود به نحوی که کارها اغلب بوسیله ماشینها در ایستگاههای مختلف کاری با توالی مشخص پردازش میشوند. معمولاً یک مسئله زمانبندی را با نماد های سه گانه توصیف میکنند. نماد ، محیط ماشین را توصیف میکند که فقط شامل یک ورودی میباشد. نماد ، ویژگیها و محدودیتهای عملیاتی فرآیند را نشان میدهد که ممکن است بدون ورودی یا با یک یا چند ورودی همراه باشد. نماد ، هدف یا اهدافی را که باید بهینه شوند را نشان میدهد. محیط های مختلف ماشین که در فیلد می توانند قرار بگیرند عبارتند از:تک ماشین[2]: حالت تک ماشین، ساده ترین محیط ماشین است ولی بررسی آن بدلیل اینکه حالت خاصی از سایر مدل های پیچیده تر میباشد از اهمیت بالایی برخوردار است.ماشینهای موازی[3]: در این محیطm ماشین به صورت موازی قرار دارند که هر کار می تواند توسط همهی این ماشین ها پردازش شود. ماشین ها در محیط موازی بر اساس زمان پردازش کارها به سه دسته عمده طبقه بندی می شوند: ماشین های موازی یکسان[4] (Pm) ، ماشین های موازی یکنواخت[5] (Qm)و ماشین های موازی نامرتبط[6] (Rm). در حالتی که زمان پردازش هر کار بر روی همهی ماشین ها یکسان باشد، ماشین های موازی یکسان نامیده می شوند.اگر ماشین ها دارای سرعت متفاوت باشند یعنی زمان پردازش کارها بر روی ماشین ها متناسب با میزان سرعت در نظر گرفته شده باشد، ماشین های موازی یکنواخت نامیده می شوند. در حالتی که زمان های پردازش یک کار بروی ماشین های مختلف بطور دلخواه متفاوت باشند، ماشین های موازی نامرتبط نامیده می شوند [2].جریان کارگاهی[7]: در این محیط m ماشین به صورت سری قرار دارند که آن را با نماد (Fm) نمایش میدهند. در مدل عمومی این محیط هر کار باید روی هر یک از m ماشین پردازش شود. همهی کارها باید خط ومسیر یکسانی را دنبال کنند به عبارتی، ابتدا روی ماشین 1، سپس روی ماشین 2 و به همین صورت ادامه می یابد. بعد از اتمام کار روی یک ماشین، کار به صف ماشین بعدی ملحق میشود. معمولاً فرض می شود که همهی صفها طبق نظم اولین ورودی اولین خروجی[8] (FIFO) انجام میشوند. حالت تعمیم یافته جریان کارگاهی، جریان کارگاهی انعطاف پذیر[9] (FFc) می باشد با این تفاوت که بجای m ماشین به صورت سری، c ایستگاه به صورت سری وجود دارند که در هر ایستگاه تعدادی ماشین همسان بصورت موازی قرار دارند [1].کار کارگاهی[10]: در یک کار کارگاهی (Jm) با m ماشین، هر کار مسیر از پیش تعیین شده خود را دنبال می کند. بین کار کارگاهی که در آن هر کار نهایتاً یک بار هر ماشین را ملاقات می کند و کار کارگاهی که هر کار می تواند بیش از یک بار یک ماشین را ملاقات کند، تمایز وجود دارد. حالت تعمیم یافته کار کارگاهی، کار کارگاهی انعطاف پذیر[11] (FJc)می باشد با این تفاوت که بجای m ماشین به صورت کارگاهی، c مرکز کاری، هر کدام شامل تعدادی ماشین همسان موازی وجود دارند [1].کارگاه باز[12]: در محیط کارگاه باز (Om)تعداد m ماشین وجود دارد بطوریکه هر کار باید روی هر کدام از m ماشین پردازش شود. هر چند زمان بعضی از این پردازش ها ممکن است صفر باشد. هیچ محدودیتی در خصوص مسیر هر کار از بین ماشین ها وجود ندارد. برنامه ریز مجاز است برای هر کار یک مسیر تعریف کند و کارهای مختلف می توانند مسیرهای متفاوت داشته باشند [1].محدودیت های عملیاتی فرآیند، مشخص شده در فیلد ممکن است شامل چند ورودی باشد. ورودی های ممکن در فیلد عبارتند از:زمان آزادسازی کار[13] : این علامت در فیلد نشان دهنده ی این است که کار j نمی تواند پردازش خود را قبل از زمان آزادسازیش شروع کند.