— -فایل مقاله رایگان ریسرچ - تحقیق - مقاله -277)

4-2-1-8. عملگر جهش 62
4-2-1-9. استراتژی تولید دوباره 63
4-3. الگوریتم بهینه سازی کلونی مورچگان 66
4-3-1. نسخه چند هدفه الگوریتم بهینه سازی مورچگان (MOACO) 69
4-3-1-1. ساختن گراف مسئله 71
4-3-1-2. نحوهی ساختن پاسخ برای مسئله 72
4-3-1-3. بروزرسانی فرومون ها 74
4-4. تنظیم پارامترهای کنترل کننده و کالیبراسیون الگوریتم ها 75
4-4-1. طراحی آزمایشات چند عاملی 76
4-5. ارزیابی الگوریتم ها 87
4-5-1. مجموعه داده ها 87
4-5-2. مقایسه عملکرد الگوریتم ها برای مسائل با ابعاد کوچک 88
4-5-3. مقایسه عملکرد الگوریتم ها برای مسائل با ابعاد متوسط 90
4-5-4. مقایسه عملکرد الگوریتم ها برای مسائل با ابعاد بزرگ 91
فصل پنجم : نتیجه گیری و پیشنهادات 96
5-1. نتیجه گیری 97
5-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. سطوح پاسخ مربوط به آزمایشات در الگوریتم MOACO 83
جدول 4-10. آنالیز واریانس برای نسبت های SN برای الگوریتم MOACO 84
جدول 4-11. آنالیز واریانس برای میانگین پاسخ ها برای الگوریتم MOACO 84
جدول 4-12. پاسخ نسبت های SN برای الگوریتم MOACO 84
جدول 4-13. پاسخ میانگین ها برای الگوریتم MOACO 84
جدول 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

 برای دانلود فایل کامل به سایت منبع مراجعه کنید  : omidfile.com

یا برای دیدن قسمت های دیگر این موضوع در سایت ما کلمه کلیدی را وارد کنید :

 

شکل 4-6. مثالی از عملگر جهش پیشنهادی 65
شکل 4-7. نمونه ای از یک سفر برای یک مورچه 73
شکل 4-8. میانگین نرخ SN برای الگوریتم NSGA-Π 82
شکل 4-9. پاسخ میانگین ها برای الگوریتم NSGA-Π 82
شکل 4-10. میانگین نرخ SN برای الگوریتم MOACO 86
شکل 4-11. پاسخ میانگین ها برای الگوریتم MOACO 86
شکل 4-12. نمودار LSD با سطح اطمینان 95% برای شاخص NPS 93
شکل 4-13. نمودار LSD با سطح اطمینان 95% برای شاخص DM 94
شکل 4-14. نمودار LSD با سطح اطمینان 95% برای شاخص MID 94
شکل 4-15. نمودار LSD با سطح اطمینان 95% برای شاخص SNS 95
شکل 4-16. نمودار LSD با سطح اطمینان 95% برای شاخص QM 95
فصل اول
کلیات تحقیق
1-1- مقدمه
زمانبندی و توالی عملیات یک فرآیند تصمیم گیری است که در بسیاری از صنایع خدماتی و تولیدی نقش کلیدی دارد. زمانبندی به معنی تخصیص مجموعه ای از منابع به مجموعه ای از فعالیت ها با در نظر گرفتن محدودیت های عملیاتی به منظور دستیابی به استفاده بهینه از منابع موجود با توجه به هدف و یا اهداف مورد نظر سازمان می باشد. به بیان بهتر زمانبندی در محیط های صنعتی به معنی تخصیص منابع (ماشین ها، اپراتورها، قالب ها، ابزارها و غیره) به مجموعه ای از عملیات های صنعتی می باشد. همان طور که می دانید در دنیای امروزی در اکثر امور زمان همواره یک محدودیت اساسی می باشد. بنابراین زمانبندی صحیح فعالیت ها منجر به حداقل کردن این منبع و به دنبال آن موجب کاهش هزینه های تولیدی و خدماتی می گردد.
منابع و فعالیت ها در یک سازمان می توانند اشکال مختلفی داشته باشند. منابع ممکن است، ماشین ها در یک کارگاه، خطوط هوایی در یک فرودگاه، کارگران در یک پروژه ی ساخت و ساز، واحد های پردازش در یک محیط محاسباتی و غیره باشند. فعالیت ها ممکن است عملیات در فرآیند تولید، فرودها و پروازها در فرودگاه، مراحل در پروژه ساخت، اجرای برنامه های کامپیوتری و غیره باشند. اهداف نیز می توانند با توجه به خط مشیهای مختلف هر سازمان اشکال مختلفی داشته باشند، بطوریکه یک هدف می تواند حداقل کردن زمان تکمیل آخرین فعالیت و دیگری میتواند به حداقل رساندن تعداد کارهایی که پس از زمان تحویلشان تکمیل شدهاند، باشد [1]. امروزه با افزایش روز افزون نیاز به محصولات و خدمات متنوع و به دنبال آن توسعه و شکوفایی صنایع تولیدی و خدماتی مختلف منابع در دسترس از قبیل نیروی انسانی، ماشین آلات، مواد اولیه و غیره به عنوان منابع بحرانی در تولید و فعالیتهای خدماتی در نظرگرفته میشوند که زمانبندی و تخصیص به موقع و مناسب این منابع منجر به ارتقا کارایی، بهرهوری و در نهایت سود آوری بیشتر میگردد.
با توسعه جهان صنعتی و با توجه به افزایش هزینههای مواد اولیه، نیروی انسانی، انرژی و حمل و نقل داشتن یک پروسه زمانبندی و توالی عملیات کارا، یک نقش اساسی را در برنامهریزی و بهره برداری از سیستمهای تولیدی و خدماتی بازی میکند. همچنین تعیین برنامه زمانبندی و توالی عملیات در مسائل برنامه‏ریزی تولید به عنوان یکی از عوامل کلیدی موفقیت در هر سازمان تولیدی، نقش مهم و موثری دارد، زیرا زمانبندی تولید باعث جلوگیری از انباشت سرمایه، تقلیل ضایعات، کاهش و یا حذف بیکاری ماشین‏آلات و تلاش برای استفاده بهتر از آنها، پاسخگویی بموقع به سفارش‏های مشتریان و تامین مواد اولیه و قطعات مورد نیاز در موقع مناسب می‏شود.
از آنجاییکه خواستگاه بسیاری از مسائل زمانبندی و توالی عملیات در محیطهای صنعتی میباشد، در بیان بسیاری از مفاهیم زمانبندی از واژههای بکاررفته در صنعت استفاده شده است. به عنوان مثال در مباحث زمانبندی از منابع بعنوان ماشینها و از فعالیتها بعنوان کار یاد میشود به نحوی که کارها اغلب بوسیله ماشینها در ایستگاههای مختلف کاری با توالی مشخص پردازش میشوند. معمولاً یک مسئله زمانبندی را با نماد های سه گانه α β γتوصیف میکنند. نماد α ، محیط ماشین را توصیف میکند که فقط شامل یک ورودی میباشد. نماد β ، ویژگیها و محدودیتهای عملیاتی فرآیند را نشان میدهد که ممکن است بدون ورودی یا با یک یا چند ورودی همراه باشد. نماد γ ، هدف یا اهدافی را که باید بهینه شوند را نشان میدهد. محیط های مختلف ماشین که در فیلد α می توانند قرار بگیرند عبارتند از:
تک ماشین: حالت تک ماشین، ساده ترین محیط ماشین است ولی بررسی آن بدلیل اینکه حالت خاصی از سایر مدل های پیچیده تر میباشد از اهمیت بالایی برخوردار است.
ماشینهای موازی: در این محیطm ماشین به صورت موازی قرار دارند که هر کار می تواند توسط همهی این ماشین ها پردازش شود. ماشین ها در محیط موازی بر اساس زمان پردازش کارها به سه دسته عمده طبقه بندی می شوند: ماشین های موازی یکسان (Pm) ، ماشین های موازی یکنواخت (Qm)و ماشین های موازی نامرتبط (Rm). در حالتی که زمان پردازش هر کار بر روی همهی ماشین ها یکسان باشد، ماشین های موازی یکسان نامیده می شوند. اگر ماشین ها دارای سرعت متفاوت باشند یعنی زمان پردازش کارها بر روی ماشین ها متناسب با میزان سرعت در نظر گرفته شده باشد، ماشین های موازی یکنواخت نامیده می شوند. در حالتی که زمان های پردازش یک کار بروی ماشین های مختلف بطور دلخواه متفاوت باشند، ماشین های موازی نامرتبط نامیده می شوند [2].
جریان کارگاهی: در این محیط m ماشین به صورت سری قرار دارند که آن را با نماد (Fm) نمایش میدهند. در مدل عمومی این محیط هر کار باید روی هر یک از m ماشین پردازش شود. همهی کارها باید خط و مسیر یکسانی را دنبال کنند به عبارتی، ابتدا روی ماشین 1، سپس روی ماشین 2 و به همین صورت ادامه می یابد. بعد از اتمام کار روی یک ماشین، کار به صف ماشین بعدی ملحق میشود. معمولاً فرض می شود که همهی صفها طبق نظم اولین ورودی اولین خروجی (FIFO) انجام میشوند. حالت تعمیم یافته جریان کارگاهی، جریان کارگاهی انعطاف پذیر (FFc) می باشد با این تفاوت که بجای m ماشین به صورت سری، c ایستگاه به صورت سری وجود دارند که در هر ایستگاه تعدادی ماشین همسان بصورت موازی قرار دارند [1].
کار کارگاهی: در یک کار کارگاهی (Jm) با m ماشین، هر کار مسیر از پیش تعیین شده خود را دنبال می کند. بین کار کارگاهی که در آن هر کار نهایتاً یک بار هر ماشین را ملاقات می کند و کار کارگاهی که هر کار می تواند بیش از یک بار یک ماشین را ملاقات کند، تمایز وجود دارد. حالت تعمیم یافته کار کارگاهی، کار کارگاهی انعطاف پذیر (FJc) می باشد با این تفاوت که بجای m ماشین به صورت کارگاهی، c مرکز کاری، هر کدام شامل تعدادی ماشین همسان موازی وجود دارند [1].
کارگاه باز: در محیط کارگاه باز (Om) تعداد m ماشین وجود دارد بطوریکه هر کار باید روی هر کدام از m ماشین پردازش شود. هر چند زمان بعضی از این پردازش ها ممکن است صفر باشد. هیچ محدودیتی در خصوص مسیر هر کار از بین ماشین ها وجود ندارد. برنامه ریز مجاز است برای هر کار یک مسیر تعریف کند و کارهای مختلف می توانند مسیرهای متفاوت داشته باشند [1].
محدودیت های عملیاتی فرآیند، مشخص شده در فیلد β ممکن است شامل چند ورودی باشد. ورودی های ممکن در فیلد β عبارتند از:
زمان آزادسازی کار (rj) : این علامت در فیلد β نشان دهنده ی این است که کار j نمی تواند پردازش خود را قبل از زمان آزادسازیش شروع کند.
قطع کار (prmp) : قطع کار به این معناست که لازم نیست کاری را روی یک ماشین از زمان شروع تا زمان تکمیل، نگاه داشت. برنامه ریز مجاز است که پردازش کار را در هر نقطه زمانی قطع کند و کار متفاوتی را روی ماشین قرار دهد. مقدار پردازشی که روی کار قطع شده انجام گرفته از بین نمی رود. وقتی کار قطع شده مجدداً روی ماشین برگردانده می شود تنها به باقیمانده زمان پردازش رزی آن ماشین نیاز دارد [1].
محدودیت های پیش نیازی کارها (prec) : این محدودیت که در بسیاری از صنایع تولیدی و خدماتی به چشم می خورد بیان کننده این است که برخی از کارها قبل از اینکه کار دیگر اجازه شروع پیدا کند، باید کامل شوند.
زمان آماده سازی وابسته به توالی(Sjk): زمان آماده سازی وابسته به توالی در واقع بیان کننده زمان مورد نیاز برای برداشتن کار قبلی یعنی کار j از روی ماشین و زمان مورد نیاز برای نصب کار بعدی یعنی کار k روی ماشین می باشد. در صورتی که زمان آماده سازی وابسته به توالی و نوع ماشین ها باشد نماد آن بصورت (Sijk) می باشد.
پردازش دسته ای (batch(b)) : یک ماشین ممکن است بتواند تعدادی از کارها را به هم پردازش کند، مثلاً به تعداد b. این بدین معنی است که می تواند دسته ای نهایتاً شامل b کار را در یک زمان پردازش کند. زمان پردازش کارها در یک دسته ممکن است یکسان نباشد و کل دسته هنگامی کامل می شود که آخرین کار در دسته کامل شود، که مبین این حقیقت است که زمان تکمیل کل دسته، با کار با طولانی ترین زمان پردازش تعیین می شود. اگر b=1، آنگاه مسئله به یک محیط زمانبندی عادی تبدیل می شود.
خرابی ها (brkdwn) : این محدودیت بیان می کند که ممکن است ماشین ها به دلیل خرابی یا انجام عملیات های نگهداری و تعمیرات در تمام لحظات در دسترس نباشد.
دسترسی محدود به ماشین ها (Mj) : این محدودیت بیانگر آن است که هر ماشین توانایی پردازش هر کاری را ندارد، بطوریکه مجموعه Mj بیانگر مجموعه ای از ماشین ها است که می توانند کار j را پردازش کنند.
انسداد (block) : انسداد پدیده ای است که ممکن است در محیط جریان کارگاهی رخ دهد. اگر در یک جریانی کارگاهی بین دو ماشین متوالی، انبار موجودی محدود وجود داشته باشد، آنگاه ممکن است هنگامی که ظرفیت این انبار پر باشد، ماشین بالادستی اجازه نداشته باشد که کار تکمیل شده را به این مرحله بفرستد. انسداد بیانگر این است که کامل شده باید روی ماشین بالادستی باقی بماند و از کار کردن آن ماشین بر روی کار بعدی جلوگیری می کند [1].
در مسائل زمانبندی، هدف از یافتن توالی کارها روی ماشین ها می تواند متفاوت باشد. معمولا توابع هدف مورد استفاده در مقالات و کتب مختلف تابعی از زمان های تکمیل و زمان های تحویل کارها می باشند. تعدادی از اهداف مورد استفاده در مسائل زمانبندی عبارتند از :
طولانی ترین زمان تکمیل (Cmax) : اگر زمان تکمیل کار j را با Cjنمایش دهیم آنگاه Cmax برابر است با زمان تکمیل آخرین کاری که سیستم را تر ک می کند یا بعبارتی Cmax=max⁡(C1,…,Cn). کمترین طولانی ترین زمان تکمیل معمولاً بیانگر استفاده بهتر از ماشین ها است.
مجموع وزنی زمان های تکمیل ( WjCj ) : مجموع وزنی زمان های تکمیل کارها، بیانگر مجموع هزینه های نگهداری یا موجودی تحمیل شده توسط زمانبندی می باشد. مجموع زمان های تکمیل در ادبیات اغلب به زمان در جریان ارجاع شده است. به همین دلیل زمان تکمیل وزنی کل به زمان در جریان وزنی معروف است [1].
حداکثر تاخیر(Lmax) : این تابع هدف بدترین مغایرت با زمان های تحویل را در بین کارها اندازه گیری می کند. اگر زمان تحویل کار j را با djنمایش دهیم در نتیجه میزان تاخیر هر کار بصورت Lj=Cj-dj بدست می آید، آنگاه حداکثر تاخیر به صورت Lmax=max⁡(L1,…,Ln) بدست می آید.
دیرکرد وزنی کل ( WjTj ) : این تابع هدف مجموع هزینه های تحمیل شده به سیستم را به دلیل عدم پاسخگویی بموقع به سفارش‏های مشتریان محاسبه می کند. میزان دیرکرد کار j به صورت Tj=max⁡(Cj-dj , 0) بدست می آید.
تعداد کارهای دارای دیر کرد ( Uj ) : این تابع تعداد کارهایی که دارای دیرکرد هستند را کمینه می کند که بصورت زیر محاسبه می شود:
Uj=10 if Cj> dj otherwiseمجموع تاخیر کارها ( Yj ) : این تابع هدف کیفیت یک زمانبندی را برمبنای مجموع بخشی از کارها که خارج از زمان تحویلشان انجام می شوند، اندازه گیری می کند که به صورت زیر محاسبه می شود. Pj نشان دهنده ی زمان پردازش کار j می باشد.
Yj=0 Cj-djPj Cj≤djdj < Cj < dj+ Pjdj+ Pj≤Cj 1-2- تعریف مسئله
محیط مورد بررسی در این پایاننامه، مسئله زمانبندی ماشینهای موازی نامرتبط میباشد. زمانبندی ماشینهای موازی در ارتباط با چگونگی زمانبندی گروهی از کارها بر روی تعدادی از ماشینها به منظور اطمینان از پردازش کارها در مدت زمان منطقی میباشد. ماشینهای موازی از دو دیدگاه تئوری و عملی دارای اهمیت هستند. از دیدگاه تئوری تعمیمی از مساله تک ماشین و حالت خاصی از محیط جریان کارگاهی و کار کارگاهی انعطاف پذیر میباشد. از دیدگاه عملی به این جهت که در دنیای واقعی بسیار معمول هستند دارای اهمیت بالایی میباشند [1]. بطور کلی صنایع مختلف از کاربرد مدل ماشینهای موازی سود بردهاند بطور مثال در صنایع تولید دستگاه نیمه هادی [3،4]، در صنایع نساجی [5]، در فرآیند فولادسازی [6]، در صنایع تولید چرخ دندهها [7]، در صنایع کشتی سازی [8]، و در صنایع تولید بورد های الکتریکی [9،10] وغیره.
در بسیاری از صنایع تولیدی و خدماتی، فعالیت هایی که وجود دارند کاملاً از هم مستقل نیستند و بین برخی از آنها یک رابطهی پیشنیازی و پسنیازی وجود دارد. این مسئله در حالیست که تعداد پژوهشهای کمی در مورد زمانبندی ماشینهای موازی صورت گرفته است که محدودیتهای پیش نیازی را در نظر گرفته باشند. از اینرو برای پوشش این خلا در ادبیات موضوع، در این تحقیق سعی شده است که بطور کامل به این محدودیت پرداخته شود.
در مسئله زمانبندی ماشینهای موازی نامرتبط از آنجاییکه ممکن است دلیل نامرتبط بودن ماشینها، تفاوت میان عملیات قابل پردازش توسط آنها باشد و هر ماشین لزوماً قادر به پردازش هر یک از کارهای موجود در مجموعه کارها نباشد. بنابراین دور از منطق نیست که محدودیتهای دسترسی به ماشینها در مسئله مورد بررسی در نظر گرفته شود. این محدودیت تضمین میکند که هر کار تنها توسط زیر مجموعهای از ماشینها قابل پردازش میباشد و اصطلاحاً پردازش کارها با دسترسی محدود به ماشینها صورت میپذیرد.
اما یکی از محدودیتهای دیگری که در این پژوهش به بررسی آن میپردازیم، زمان آماده سازی وابسته به توالی کارها و نوع ماشینها میباشد. در یک محیط تولیدی، زمان آماده سازی شامل تمام فعالیتهایی میباشد که بر روی مواد به منظور آماده کردن آنها برای انجام فرآیند اصلی صورت میگیرد. بطور کلی زمانهای آمادهسازی که صنایع تولیدی با آنها در ارتباط هستند به دو دسته تقسیم میشوند، اولی زمان آماده سازی مستقل از توالی و دومی زمان آماده سازی وابسته به توالی. در نوع اول معمولاً زمان آماده سازی را بخشی از زمان پردازش کارها در نظر میگیرند که این فرض بیشتر برای ساده سازی مسئله میباشد. ولی این سادهسازی روی کیفیت جوابهای بدست آمده اثر منفی دارد بطوریکه شاید این حلها در محیط صنعتی واقعی کاربردی نداشته باشند. اما نوع دوم که اخیراً در بسیاری از کارهای تحقیقاتی این نوع زمان آماده سازی را در نظر میگیرند، کاربردهای فراوانی در صنایع تولیدی دارد. برای مثال، در یک کارخانه تولیدی که با رنگ سروکار دارند، همواره یک زمان آماده سازی قابل توجهی برای تمیز کردن ماشین برای تغییر رنگ ایجاد میشود. این عملیات، یعنی تمیز کردن ماشینها هم به رنگ قبلی و هم به رنگ بعدی که در حال حاضر به آن نیاز است بستگی دارد. همچنین در صنایع تولیدی که به ابزار، قید و بند و قالب های متفاوتی برای انجام عملیاتهای مختلف نیاز دارند، این نوع زمان آماده سازی بطور ملموسی در فرآیندهای آنها دیده میشود.
امروزه با توجه به محیط رقابتی موجود در بازار ، اکثریت صنایع تولیدی و خدماتی همواره با بیش از یک هدف روبرو هستند که تلاش میکنند آنها را بطور همزمان کمینه کنند. یکی از مهمترین اهدافی که سازمانها همواره در تلاش برای کمینهسازی آن هستند، کاهش هزینههای ناشی از نگهداری موجودی های کارهای در حال پردازش و اختلالات ناشی از کارهای نیمه تمام در کارگاه میباشد. از طرفی دیگر کمینه سازی هزینههای ناشی از عدم پاسخگویی به موقع به نیازهای مشتریان دیگر هدفی است که همواره مورد توجه سازمان ها بوده و هست. از این رو برای دستیابی به هر دو هدف مذکور، در این پژوهش کمینه سازی همزمان دو تابع هدف میانگین وزنی زمان در جریان و میانگین وزنی دیرکرد کارها در نظر گرفته شده است.
1-3- مفروضات عمومی مسئله
1. تمامی ماشینها در لحظه زمانی صفر آماده به کار میباشند.
2. تمامی ماشینها بطور مستمر در دسترس میباشند و امکان خرابی ماشینها وجود ندارد.
3. هر ماشین در هر لحظه قادر به پردازش تنها یک کار میباشد.
4. بیکاری ماشینها مجاز است.
5. زمان پردازش کارها روی ماشینهای مختلف یکسان نمیباشد.
6. کارها دارای زمان های آماده سازی وابسته به توالی پردازش کارها و نوع ماشین ها می باشند، بعلاوه کارها دارای زمان آماده سازی اولیه میباشند که بستگی به نوع ماشینها دارد.
7. هر کار در طول زمان پردازش خود تنها بر روی یک ماشین پردازش میشود و امکان شکست کارها وجو ندارد.
8. تمامی کارها در لحظه زمانی صفر آماده پردازش نمی باشند و زمان های آزاد سازی متفاوتی دارند.
9. کارها از هم مستقل نمیباشند و بین آنها روابط پیش نیازی و پس نیازی وجود دارد.
10. هر کار نمیتواند روی هر ماشینی پردازش شود و مجموعهای از ماشینها میتوانند یک کار بخصوص را پردازش کنند.
11. زمان آماده سازی مربوط به یک کار نمیتواند قبل از زمان آزادسازی مربوط به آن کار انجام شود.
12. زمان آماده سازی مربوط به پس نیاز یک کار میتواند قبل از پایان یافتن پیش نیاز آن کار انجام شود.
1-4- ضرورت و اهداف پژوهش:
مسئله زمانبندی ماشینهای موازی نامرتبط یکی از کاربردیترین مسائلی است که امروزه تعداد زیادی از سازمانهای تولیدی و خدماتی با آن روبرو هستند. این موضوع در حالیست که تا به امروز تعداد پژوهشهای کمی در زمینه زمانبندی ماشینهای موازی نامرتبط وجود دارند که چندین محدودیت عملیاتی را همزمان در پژوهش خود در نظر گرفته باشند که این حقیقت کاربرد آنها را در محیطهای تولیدی واقعی محدود میسازد. به همین دلیل ما در این تحقیق سعی کردهایم تا با در نظر گرفتن محدودیت های عملیاتی مختلف این شکاف موجود در بین تئوری و عملیاتی بودن این گونه تحقیق ها را کاهش دهیم. از طرفی دیگر اکثریت پژوهشهای انجام شده تنها به دنبال بهینه سازی زمانبندی بر مبنای یک هدف هستند، ولی همانطور که میدانید امروزه اکثر سازمانها با بیش از یک هدف روبرو هستند. از اینرو در این تحقیق به منظور پوشش این خلا با در نظر گرفتن همزمان دو تابع هدف میانگین وزنی زمان در جریان کارها و میانگین وزنی دیرکرد کارها، سعی شده تا هزینههای ناشی از دیرکرد و نگهداری موجودی حین تولید را کاهش دهیم. در این تحقیق با در نظر گرفتن محدودیت های عملیاتی کاربردی و توابع هدف متداول در صنعت، اولا به دنبال هر چه نزیک کردن مسئله زمانبندی ماشینهای موازی نامرتبط به مسائل دنیای واقعی و در پی آن استفاده کارآمد از منابع و زمان، کاهش هزینه های ناشی از تولید و خدمات، جلب رضایت مشتریان و حفظ آنها و بالا بردن بهرهوری و کارایی سیستم هستیم.

فصل دوم
ادبیات تحقیق
2-1- مقدمه
در این تحقیق، مسئله زمان بندی ماشین های موازی نامرتبط با فرض وجود محدودیت های پیش نیازی کارها، زمان آماده سازی وابسته به توالی کارها و نوع ماشین ها، زمان های آماده به کار متفاوت و دسترسی محدود به ماشین ها با اهداف میانگین وزنی زمان در جریان کارها و میانگین وزنی دیرکرد کارها مورد مطالعه قرار می گیرد. با توجه به مسئله در نظر گرفته شده، در ادامه این فصل برآنیم تا مروری بر ادبیات موضوع مطرح در زمینه هایی که در این مقاله رایگان ریسرچ - تحقیق - مقاله به آنها پرداخته شده است، بپردازیم. ابتدا به بررسی تحقیقات صورت گرفته در زمینه ماشین های موازی نامرتبط و در ادامه به بررسی محدودیت ها می پردازیم. و سپس، به بررسی مسائل چندهدفه با تمرکز بر روی الگوریتم های تکاملی NSGA-Π و MOACO می پردازیم. بدلیل گستردگی مطالب در ادبیات موضوع، در این تحقیق سعی بر آن است که در بخش بررسی به محدودیت ها، تحقیقاتی مورد بررسی قرار می گیرند که در حیطه ی مسئله زمان بندی ماشین های موازی به ویژه ماشین های موازی نامرتبط و یکسان می باشند.
2-2- ماشین های موازی نامرتبط
در سال های اخیر تحقیقات زیادی در زمینه ماشین های موازی با محدودیت های گوناگون صورت گرفته است اما یکی از اولین تحقیقات صورت گرفته در زمینه ماشین های موازی یکسان توسط مک ناتن [11] در اواخر دهه پنجاه میلادی صورت گرفته است. همچنین محققان دیگری همچون موکوتف [12] ، لام و ژینگ [13] و چنگ و سینگ [14] بررسی و مطالعاتی در زمینه ماشین های موازی یکسان انجام داده اند. حال به بررسی تعدادی از تحقیقاتی که در زمینه ماشین های موازی نامرتبط صورت گرفته است می پردازیم.
مسئله زمانیندی ماشین های موازی نامرتبط با هدف کمینه سازی بیشینه زمان تکمیل کارها حجم گسترده ای از تحقیقات در زمینه مسائل ماشین های موازی نامرتبط را به خود اختصاص داده است. هاروویتز و ساهنی [15] از رویکرد برنامه ریزی پویا برای مسئله زمانبندی دو ماشین موازی نامرتبط به هدف کمینه سازی بیشینه زمان تکمیل کارها استفاده کردند. گلس و همکاران [16] مسئله زمانبندی ماشین های موازی نامرتبط با هدف کمینه سازی بیشینه زمان تکمیل را مورد مطالعه قرار دادند و از سه الگوریتم فراابتکاری ژنتیک، شبیه سازی تبرید و جستجوی ممنوع برای این مسئله ارائه دادند. مارتلو و همکاران [17] برای مسئله مشابه حد پایینی با استفاده از تکنیک آزادسازی لاگرانژ بدست آوردند و برای بهبود این حد پایین یک الگوریتم برش ارائه دادند که قسمت های نشدنی را از فضای جواب بدست آمده حذف می کرد. آن ها همچنین یک الگوریتم تقریبی برای حل این مسئله ارائه دادند و نتایج بدست آمده از این الگوریتم را با حد پایین بدست آمده مورد مقایسه قرار دادند. آدام پولوس و پاپیس [18] مسئله زمانبندی ماشین های موازی نامرتبط با هدف تعیین یک زمان تحویل مشخص برای تمامی کارها بطوریکه مجموع هزینه های ناشی از زود کرد و دیر کرد کارها و همین طور هزینه ناشی از تعیین زمان تحویل معین کمینه شوند. هزینه ای که به زمان تحویل تخصیص داده شده مربوط به تمایل شرکت به تحویل هر چه زودتر محصول به مشتریان با در نظر گرفتن تمام فاکتورهای رضایت مندی مشتری می باشد. آن ها برای این مسئله یک الگوریتم ابتکاری که در یک زمان چند جمله ای اجرا می شود، پیشنهاد دادند. سریواستاوا [19] مسئله مشابهی را مورد بررسی قرار داد و برای حل آن از الگوریتم جستجوی ممنوع استفاده نمود و ادعا کرد که الگوریتم ارائه شده قادر است برای مسائلی در مقیاس های کاربردی، جواب هایی با کیفیت خوب در مدت زمانی قابل قبول محاسبه نماید. لانسیا [20] یک الگوریتم دقیق شاخه و حد برای مسئله زمانبندی دو ماشین موازی نامرتبط با این فرض که کارها در ابتدای افق زمانبندی در دسترس نیستند و با هدف کمینه سازی بیشینه زمان تکمیل کارها پیشنهاد کردند. بانک و ورنر [21] مسئله زمانبندی ماشین های موازی نامرتبط را با هدف حداقل کردن مجموع وزنی دیرکرد و زودکرد مورد بررسی قرار گرفته است. در مسئله مورد بررسی کارها دارای زمان تحویل مشترک می باشند و همچنین تمامی کارها در زمان صفر در دسترس نیستند، به عبارت دیگر مسئله در محیط پویا مورد بررسی قرار گرفته است. در این پژوهش ابتدا چندین خصوصیت ساختاری توسعه پیدا کرده اند و سپس با توجه به ویژگی های حاصل شده الگوریتم های فرا ابتکاری برای حل مسئله پیشنهاد شده اند. لی آ او و همکاران [22] مسئله زمانبندی ماشین های موازی نامرتبط با هدف کمینه سازی مجموع وزنی دیرکرد کارها را در نظر گرفتند. آن ها یک حد پایین و یک حد بالا و همچنین یک الگوریتم شاخه و کران برای غلبه کردن بر این مسئله ارائه دادند. قیرادی و پاتز [23] برای مسئله مشابه یک الگوریتم ابتکاری ارائه نمودند که توانایی بدست آوردن پاسخ هایی با کیفیت خوب برای مسائلی با ابعاد بزرگ را دارد. لاگندران و سوبور [24] مسئله زمانبندی ماشین های موازی نامرتبط را مورد توجه قرار دادند. در مسئله در نظر گرفته شده، کارها و ماشین ها دارای زمان های آماده به کار متفاوت می باشند. در مسئله مذکور، تمهیداتی برای مجموعه ای از کارها در نظر گرفته شده است، بر این اساس کارها به دلیل داشتن اولویت بالا، موعد تحویل تنگ یا میزان بار کاری بالا می توانند شکسته شوند و بر روی چندین ماشین بصورت موازی پردازش شوند. در مطالعه انجام شده، زمان های آماده سازی به صورت مستقل از توالی در نظر گرفته شده بودند که در آن زمان آماده سازی کار بر روی ماشین با زمان پردازش کار بر روی همان ماشین مورد نظر گرفته شده است. کوا و همکاران [25] به طور همزمان مسئله انتخاب و زمانبندی ماشین های موازی نامرتبط را به منظور حداقل کردن هزینه های نگهداری ماشین ها و هزینه دیرکرد کارها مورد بررسی قرار دادند. آن ها برای غلبه بر این مسئله یک مدل ریاضی ترکیبی ارائه دادند. از آنجا که حل این مسئله با ابعاد بزرگ توسط این مدل امکان پذیر نمی باشد، آن ها یک الگوریتم جستجوی ابتکاری مبتنی بر الگوریتم جستجوی ممنوع برای یافتن پاسخ های بهینه و یا نزدیک به بهینه پیشنهاد کردند.
2-3- محدودیت پیش نیازی کارها
از جمله اولین تحقیقاتی که در زمینه ماشینهای موازی یکسان با محدودیت های پیشنیازی کارها انجام شده میتوان به هو [26] اشاره نمود. این محقق با ساده سازی مسئله بدین صورت که کارها دارای زمان پردازش واحد میباشند و گراف پیشنیازی کارها بصورت یک درخت می باشد، الگوریتمی بهنام مسیر بحرانیCP پیشنهاد دادند که توانایی بدست آوردن جواب بهینه را برای مسائل Pm|Pj=1,outtreeCmax و Pm|Pj=1,intreeCmax دارند. این قانون بالاترین اولویت را به کاری میدهد که در راس طولانیترین رشته کارها در گراف پیش نیازی باشد. یولمن [27] اثبات کرد که مسئله زمان بندی کارها روی ماشین های موازی یکسان با روابط پیش نیازی دلخواه و زمان های پردازشی واحد بطور کامل غیر چند جملهای میباشد. بعد ها گراهام [28] الگوریتم تقریبی خوبی با نسبت عملکردی 2-1/m برای حل مسئله Pm|precCmax پیشنهاد کرد. دو و همکاران [29] اثبات کردند که که مسئله زمانبندی کارها روی دو ماشین موازی یکسان با روابط پیش نیازی بصورت درخت و زمان های پردازشی کاملاً دلخواه بطور قویاً غیر چندجملهای میباشد. بروکر و همکارانش با توسعه الگوریتم مسیر بحرانی توانستند الگوریتمی برای حل بهینه مساله Pm|Pj=1,intreeLmax پیشنهاد کنند و همین طور اثبات کردند که مساله Pm|Pj=1,outtreeLmax قویاً NP-hard است. هویت مونت و همکاران [30] یک تکنیک آزادسازی لاگرانژ برای حل مساله زمانبندی ماشین های موازی یکسان با محدودیت های پیش نیازی ساده با هدف کمینه سازی مجموع دیکرد به توان دو کارها پیشنهاد کردند. با توجه به مرور ادبیات انجام تا سال 1997 میلادی هیچ گونه تحقیقی روی زمان بندی ماشین های موازی نامرتبط که محدودیت های پیش نیازی را در نظر گرفته باشند صورت نگرفته است. هرمن و همکارانشان [31] اولین کسانی بودند که به بررسی مساله Rm|chainCmax پرداختند. آنها سه الگوریتم ابتکاری و یک الگوریتم بر مبنای شبیه سازی تبرید برای بهبود حل ها، ارائه کردند. آنها برای ارزیابی عملکرد الگوریتم های پیشنهادی خودشان، سه حد پایین برای این مساله ارائه کردند که نتایج بدست آمده حاکی از کارا بودن الگوریتم های پیشنهادی آنها بوده است.
هرنیک و کنسوت [32] از اولین محققینی بودهاند که به بررسی مسئله زمان بندی ماشین های موازی با در نظر گرفتن محدودیتهای پیش نیازی به همراه سایر محدودیت ها پرداخته اند. آنها مسئله Pm|Sij,PrecCmax را در نظر گرفتند و به دنبال پاسخ به این سوال بوده اند که آیا می توان یک الگوریتم زمانبندی بر مبنای اولویت بندی کارها برای حل این مسئله طراحی نمود؟ آنها در این تحقیق به این نتیجه رسیدند که پاسخ مثبت به این سوال بسیار بعید است و این مسئله به شدت پیچیده است. راماچادرا و المغربی [33] یک مدل برنامه ریزی عدد صحیح باینری و یک مدل برنامه ریزی پویا برای حل مسئله زمانبندی دو ماشین موازی با محدودیت های پیش نیازی کارها به منظور کمینه سازی مجموع زمان تکمیل وزنی پیشنهاد کرده اند. همین طور آنها یک الگوریتم ژنتیک برای حل این مسئله با ابعاد بزرگ پیشنهاد کردند. کیم و همکاران [34] مسئله زمانبندی ماشین های موازی یکسان را با محدودیت پیشنیازی کارها به صورت آغاز به آغاز با هدف کمینه سازی مجموع تکمیل کارها را در نظر گرفته اند. آنها یک الگوریتم ابتکاری برای حل این مسئله ارائه نموده اند. آقای توکلی مقدم و همکاران [35] یک مدل برنامه ریزی عدد صحیح مختلط دو سطحی برای مسئله زمان بندی ماشین های موازی نامرتبط با محدودیت های پیش نیازی کارها و زمان آماده سازی وابسته به توالی کارها با هدف کمینه سازی تعداد کارهای دارای دیرکرد در سطح اول و کمینه سازی مجموع زمان های تکمیل کارها در سطح دوم ارائه داده اند و با استناد به اینکه بدست آوردن جواب های بهینه در سایز های کاربردی برای این مسئله توسط الگوریتم دقیق به علت ماهیت پیچیده آن کاری دشوار است، آنها یک الگوریتم فرا ابتکاری، الگوریتم ژنتیک برای حل این مسئله ارائه دادند اما نتایج بدست آمده نشان دهنده آن است که الگوریتم پیشنهادی آنها خیلی کارا نمی باشد، بطوریکه توانایی یافتن جواب بهینه حتی برای مثال های کوچک را هم ندارد. گاسیاس و همکاران [36] یک الگوریتم دقیق، شاخه و کران برای حل مسئله زمانبندی ماشین های موازی یکسان با ابعاد کوچک که دارای محدودیت های پیش نیازی کارها و زمان آماده سازی وابسته به توالی کارها به منظور کمینه سازی مجموع زمان های تکمیل کارها و کمینه سازی حداکثر تاخیر ارائه نموده اند. آنها برای حل مسئله مورد بررسی با ابعاد بزرگ یک الگوریتم جستجوی محلی ارائه داده اند. هو و همکاران [8] یک الگوریتم ابتکاری برای حل مسئله زمان بندی حمل بلوک ها توسط جرثقیل ها در یک شرکت کشتی سازی ارائه کرده اند. آنها نشان داده اند که این مسئله را می توان بصورت Pm|Mj,PrecCmax مدل نمود. نتایج محاسباتی آنها روی مسائل واقعی جمع آوری شده از شرکت کشتی سازی شانگ های و مقایسه آنها با آنچه که در این شرکت اتفاق می افتد نشان دهنده ی این است که الگوریتم پیشنهادی آنها از کارایی خوبی برخوردار است. دریزل و مونچ [37] مسئله زمانبندی ماشین های موازی یکسان را با محدودیت های پیش نیازی کارها، زمان آماده سازی وابسته به توالی و زمان های آماده به کار متفاوت را در نظر گرفته اند. آنها برای حل این مسئله چندین الگوریتم جستجوی همسایگی متغیر را پیشنهاد نمودند و عملکرد آن ها را از لحاظ کیفیت جواب تولیدی با یک روش ابتکاری که مبتنی بر رویه ATCSRمی باشد، مقایسه نمودند. آن ها گزارش دادند که روش جستجوی همسایگی متغیر در بیشتر موارد کیفیت جواب بهتری نسبت به روش ابتکاری مبتنی بر رویه ATCSR برای مسائل آزمایشی مورد استفاده دارد. کاکر و همکاران [38] مسئله زمانبندی ربات های موازی با محدودیت های پیش نیازی کارها و زمان های آماده به کار متفاوت به منظور حداقل سازی میانگین دیرکرد کارها در نظر گرفته اند و یک الگوریتم فرا ابتکاری که ترکیبی از الگوریتم ژنتیک و الگوریتم شبیه سازی تبرید است برای حل مسئله مورد نظر پیشنهاد نموده اند. لیو [39] یک الگوریتم ترکیبی که شامل الکوریتم ژنتیک و یک الگوریتم ابتکاری بر مبنای قوانین اولویتی می باشد را برای حل مسئله Rm|Prec Tj پیشنهاد کرده اند. پارک و سو [40] مسئله زمانبندی و مسیریابی حمل کننده ها در شرکت کشتی سازی را در نظر گرفتند. این موضوع قابل مدل کردن به مسئله زمانبندی ماشین های موازی یکسان با محدودیت های پیش نیازی کارها و زمان آماده سازی وابسته به توالی می باشد. هدف در نظر گرفته شده در این تحقیق، دستیابی به حداکثر تعادل حجم کاری بین حمل کننده ها تحت یک محدودیت زمانی که می بایستی تمامی بلوک های مونتاژی توسط حمل کننده ها به محل مورد نظر حمل شوند، می باشد. آنها یک الگوریتم GRASP که ترکیبی از الگوریتم های ابتکاری، تصادفی سازی و جستجوی محلی می باشد، برای حل این مسئله پیشنهاد نموده اند.
2-4- دسترسی محدود به ماشین ها
در بسیاری از تحقیقات صورت گرفته در حیطه مسائل زمانبندی، محیط هایی مورد مطالعه قرار می گیرند که در آن ها فرض بر این است تمام کارها می توانند بدون هیچ محدودیتی روی تمام ماشین های موجود پردازش شوند. اما در بعضی از مواقع این فرض با شرایط واقعی حاکم بر سیستم های تولیدی و خدماتی در تضاد است و شرایطی وجود دارد که کارها دارای ویژگی هایی هستند که تنها بخشی از ماشین ها قادر به پردازش آنها می باشند. بدین صورت که کار نوع j تنها روی تعدادی از ماشین ها و نه تمام آن ها قبل پردازش است. مجموعه ماشین هایی که قادرند کار نوع j راپردازش کنند، در قالب یک مجموعه بصورت Mj نمایش داده می شوند که زیر مجموعه ای از تمام ماشین های موجود می باشد. کاربرد مسائل زمانبندی با فرض دسترسی محدود به ماشین ها در بسیاری از محیط های تولیدی و خدماتی دیده می شود. به عنوان مثال، در محیط های بیمارستان هزینه های هنگفتی به منظور تجهیز اتاق های عمل صرف می شود و با توجه به محدودیتی که در میزان تجهیزات موجود در هر اتاق وجود دارد، هر اتاق تنها برای تعدادی از بیماران قابل دسترس است.
سنتنو و آرماکست [41] مسئله زمانبندی ماشین های موازی یکسان را با فرض دسترسی محدود به ماشین ها و زمان های آماده به کار متفاوت با هدف کمینه سازی بیشینه زمان تاخیر در نظر گرفتند. آن ها یک الگوریتم ابتکاری که ترکیبی از قانون اولویتی کار با کمترین انعطاف پذیری(LFJ) و قانون اولویتی ماشین با کمترین انعطاف پذیری (LFM) است برای حل این مسئله ارائه دادند. بعد ها سنتنو و آرماکست [42] یک الگوریتم ابتکاری که ترکیبی از (LFJ) ، (LFM) و قانون طولانی ترین زمان پردازش (LPT) برای مسئله مشابه با تابع هدف کمینه سازی بیشینه زمان تکمیل کارها پیشنهاد کردند. چپین و واخانیا [43] یک الگوریتم چند جمله ای با نسبت عملکردی (2-1m) برای مسئله زمانبندی ماشینهای موازی نامرتبط با فرض دسترسی محدود به ماشین ها به منظور کمینه سازی بیشینه زمان تکمیل کارها پیشنهاد دادند. شین و همکاران [44] یک الگوریتم دقیق شاخه و کران برای مسئله زمانبندی ماشین های موازی با فرض دسترسی محدود به ماشین ها و محدودیت در دسترس نبودن ماشین ها در طول زمانبندی با هدف کمینه سازی بیشینه تاخیر پیشنهاد کردند. لیانگ و لی [45] تحقیقی جامع بر روی ماشین های موازی یکسان، یکنواخت و نامرتبط با فرض وجود محدودیت دسترسی به ماشین ها در دو حالت زمانبندی با فرض مجاز بودن شکست کارها و غیر مجاز بودن شکست کارها بررسی نمودند. طبق بررسی آن ها مساله زمانبندی ماشین های موازی با محدودیت مورد نظر با اسمی مختلفی توسط محقیق علوم کامپیوتر و علوم تحقیق در عملیات نامگداری شده است. این محدودیت عموماً با عناوین محدودیت مجموعه پردازشی، زمانبندی سیستم ها بر اساس نوع عملکرد، زمانبندی ماشین چند منظوره، محدودیت دسترسی و محدودیت دسترسی محدود به ماشین ها شناخته می شوند. لی و همکاران [46] الگوریتمی را برای مسئله زمانبندی ماشین های موازی یکسان که دارای محدودیت دسترسی محدود به ماشین ها و زمان های آماده به کار متفاوت با هدف کمینه سازی بیشینه زمان تکمیل کارها پیشنهاد دادند که توانایی بدست آوردن جواب بهینه را دارد. آنها برای ساده سازی این مسئله فرض کردند که تمامی فعالیت ها دارای زمان پردازش یکسانی باشند.
جاوو [47] مسئله زمانبندی ماشین های موازی نامرتبط با فرض وجود محدودیت های دسترسی محدود به ماشین ها با در نظر گرفتن همزمان دو هدف کمینه سازی بیشینه زمان تکمیل کارها و کمینه سازی مجموع زودکرد و دیرکرد کارها مورد بررسی قرار داد. برای حل این مسئله نسخه چند هدفه الگوریتم سیستم ایمنی مصنوعی پیشنهاد شده است. گوخال و ماسی راجان [7] یک مدل برنامه ریزی عدد صحیح مختلط و چند الگوریتم ابتکاری برای مسئله زمانبندی ماشین های موازی یکسان با فرض وجود محدودیت های دسترسی محدود به ماشین ها، زمان آماده سازی وابسته به توالی کارها و زمان های آماده به کار متفاوت به منظور کمینه سازی مجموع وزنی در جریان کارها پیشنهاد دادند. ونگ و همکاران [4] مسئله زمانبندی ماشین های موازی نامرتبط با فرض وجود محدودیت های دسترسی محدود به ماشین ها، زمان آماده سازی وابسته به توالی کارها و زمان های آماده به کار متفاوت به منظور کمینه سازی تعداد کارهای دارای دیرکرد در نظر گرفتند. آن ها برای این مسئله یک مدل برنامه ریزی عدد صحیح مختلط و یک الگوریتم ابتکاری برای ایجاد پاسخ اولیه و بهبود آن با یک رویه جستجوی محلی پیشنهاد دادند.

2-5- زمان آماده سازی وابسته به توالی کارها
به عنوان یک تعریف کلی، زمان نصب برای هر ماشین به مفهوم زمان مورد نیاز برای آماده سازی ماشین به منظور پردازش کارهای تخصیص یافته به آن می باشد. به طور معمول، در مسائل زمانبندی زمان های آماده سازی به دو گروه کلی تقسیم می شوند. در گروه اول زمان نصب تنها به نوع کاری که روی ماشین پردازش می شود بستگی دارد و اصطلاحاً به آن زمان نصب مستقل از توالی گفته می شود. در گروه دوم زمان نصب علاوه بر نوع کاری که بر روی ماشین پردازش می شود، به کار قبلی که بر روی ماشین پردازش شده است نیز بستگی دارد و از آن به عنوان زمان آماده سازی وابسته به توالی یاد می شود. مسائل زمانبندی مربوط به گروه دوم خود به دو دسته تقسیم می شود. دسته اول شامل مسائلی هستند که در آن ها زمان آماده سازی، وابسته به توالی کارها و مستقل از نوع ماشین آلات است و در دسته دوم زمان نصب هم وابسته به توالی کارها و هم وابسته به نوع ماشین آلات می باشد. در رابطه با اهمیت این موضوع می توان به تحقیقات صورت گرفته توسط برخی از محققین اشاره کرد. بر اساس گزارش پانوالکار [48] که در دهه هفتاد میلادی به چاپ رسید، نزدیک به 70% افراد شاغل در زمینه زمانبندی اذعان کردند که در حداقل یک چهارم کارهایی که توسط آنها زمانبندی می شوند، نمی توان نقش زمان های آماده سازی برای ماشین ها را نادیده گرفت. همچنین، فلین [49] تاثیر فرآیند های نصب وابسته به توالی را در افزایش ظرفیت تولید در محیط تولید سلولی و ورتمن [50] اهمیت آنها را در مدیریت ظرفیت تولید بررسی نمودند.
حال که با حالت های مختلف و اهمیت زمان آماده سازی آشنا شدیم به بررسی تحقیق های انجام شده در زمینه ماشین های موازی که این محدودیت را در نظر گرفته اند می پردازیم. همان طور که ملاحظه می کنید در بخش محدودیت پیش نیازی کارها و دسترسی محدود به ماشین ها به بررسی تعدادی از پژوهش های انجام شده که محدودیت زمان آماده سازی وابسته به توالی را در نظر گرفته بودند، پرداختیم. از این رو در این قسمت بیشتر به بررسی تحقیقاتی می پردازیم که تمرکز آن ها بیشتر روی محدودیت زمان آماده سازی می باشد. گوینت و داسوچی [51] مسئله زمانبندی ماشین های موازی یکسان را با در نظر گرفتن زمان های نصب وابسته به توالی با هدف کمینه سازی بیشینه زمان تکمیل کارها با استفاده از یک روش ابتکاری بر مبنای روش مجارستانی بررسی کردند. کیم و شین [52] مسئله مشابهی را با هدف کمینه سازی بیشترین زمان تاخیر کارها بررسی نموده و برای حل آن از الگوریتم جستجوی ممنوع بهره بردند. همچنین فاولر و همکارانش [53] برای حل مسئله مورد نظر با اهداف مختلف شامل بیشینه زمان تکمیل کارها، مجموع وزنی زمان تکمیل کارها و مجموع وزنی زمان دیرکرد کارها، یک الگوریتم ژنتیک ترکیبی را ارائه نمودند. نتایج محاسباتی بدست آمده برای هر سه معیار ذکر شده، عملکرد بهتر آن را نسبت به الگوریتم های موجود قبلی نشان می دهد. بهنامیان و همکارانش [54] یک الگوریتم فرا ابتکاری ترکیبی برای کمینه سازی بیشینه زمان تکمیل کارها برای مسئله زمانبندی ماشین های موازی یکسان با محدودیت زمان آماده سازی وابسته به توالی پیشنهاد کردند. الگوریتم پیشنهادی آن ها ترکیبی از الگوریتم بهینه سازی موچگان، الگوریتم شبیه سازی تبرید و الگوریتم جستجوی همسایگی می باشد. آن ها برای ارزیابی الگوریتم پیشنهادیشان آن را با دو الگوریتم دیگر که یکی ترکیبی از الگوریتم شبیه سازی تبرید و الگوریتم جستجوی همسایگی و دیگری ترکیبی از الگوریتم بهینه سازی موچگان و الگوریتم جستجوی همسایگی است، مقایسه کردند. نتایج محاسباتی بدست آمده کارایی بالای الگوریتم پیشنهادی آن ها را برای حل مسائلی با ابعاد بزرگ نشان می دهد. ینگ و چنگ [55] از روش ابتکاری جستجوی مکرر حریصانه به منظور حل مسئله زمان بندی ماشین های موازی یکسان با فر ض وجود زمان های آماده به کار متفاوت و زمان آماده سازی وابسته به توالی استفاده کردند.
کیم و همکاران [56] مسئله زمان بندی ماشین های موازی نامرتبط با فرض وجود زمان های نصب وابسته به توالی و مستقل از نوع ماشین را با هدف کمینه سازی مجموع زمان دیرکرد کارها بررسی نمودند و برای حل این مسئله، تعدادی روش ابتکاری بر پایه الگوریتم شبیه سازی تبرید ارائه نمودند. ژو و هیدی [57] یک مدل برنامه ریزی عدد صحیح برای مسئله مشابه با تابع هدف کمینه سازی زمان های زودکرد و دیرکرد کارها ارائه نمودند. آن ها گزارش کردند که مدل پیشنهادی برای یک مسئله با اندازه نه کار و سه ماشین در زمان قابل قبول به جواب می رسد. ونگ و همکاران [58] مسئله زمانبندی ماشین های موازی نامرتبط را با فرض وجود زمان های نصب وابسته به توالی و با هدف کمینه سازی مجموع وزنی زمان تکمیل کارها مطالعه نمودند. آن ها هفت روش ابتکاری ساده را از نظر نتایج محاسباتی با یکدیگر مقایسه نمودند و در نهایت یکی از آن ها را به عنوان بهترین روش انتخاب می نمایند. این روش هر یک کارها را بر اساس کوچکترین نرخ زمان پردازش بعلاوه زمان نصب نسبت به وزن کار در تابع هدف به ماشین ها اختصاص می دهد. روچا و همکاران [59] مسئله زمانبندی ماشین های موازی نامرتبط را با فرض وجود زمان های نصب وابسته به توالی و با هدف کمینه سازی بیشینه زمان تکمیل کارها و مجموع وزنی زمان های دیرکرد مورد بررسی قرار دادند. آن ها برای این مسئله یک روش شاخه و کران پیشنهاد نمودند و از روش فرا ابتکاری GRASP به منظور تولید یک جواب به عنوان حد بالای مسئله استفاده نمودند. آن ها همچنین برای این مسئله، دو مدل برنامه ریزی عدد صحیح آمیخته ارائه کردند و نشان دادند که روش شاخه و کران پیشنهادی، عملکرد بهتری نسبت به دو مدل ارائه شده دارد. والادا و رویز [60] برای مسئله زمانبندی ماشین های موازی نامرتبط با فرض وجود زمان های آماده سازی وابسته به توالی با در نظر گرفتن هدف بیشینه تکمیل کارها یک الگوریتم ژنتیک به همراه یک الگوریتم جستجوی محلی ارائه کردند و آن را برای مسائلی با اندازه های متوسط و بزرگ آزمایش کردند. آن ها ادعا کردند که این الگوریتم در مقایسه با سایر روش های موجود در ادبیات تحقیق دارای بهترین عملکرد است. کسکین ترک و همکاران [61] برای مسئله زمانبندی ماشین های موازی نامرتبط با فرض وجود زمان های آماده سازی وابسته به توالی به منظور کمینه سازی میانگین نسبی درصد عدم بالانس دو الگوریتم فرا ابتکاری شامل الگوریتم بهینه سازی مورچگان و الگوریتم ژنتیک و دو الگوریتم ابتکاری ارائه کردند. آن ها گزارش دادند که الگوریتم مورچگان پیشنهادی آنها عملکرد بهتری نسبت به الگوریتم ژنتیک و دو الگوریتم ابتکاری یاد شده دارد. چن [62] مسئله زمانبندی ماشین های موازی نامرتبط با فرض وجود زمان های آماده سازی وابسته به توالی و زمان آماده به کار متفاوت با هدف کمینه سازی تعداد کارها دارای دیرکرد وزنی را در نظر گرفته است. برای حل این مسئله یک الگوریتم فرا ابتکاری ترکیبی که شامل الگوریتم جستجوی ممنوع و الگوریتم جستجوی همسایگی متغیر است، پیشنهاد کردند و برای ایجاد یک جواب اولیه با کیفیت از یک رویه ابتکاری استفاده نمودند.
2-6- بهینه سازی چند هدفه
بسیاری از مسائل بهینه سازی که در عمل با آن روبرو هستیم همواره با بیش از یک معیار بهینه سازی سر و کار دارند. در یک مسئله بهینه سازی چند هدفه که بهینه سازی چند معیاره یا بهینه سازی برداری هم نامیده می شوند، هر حل بر مبنای بیش از یک هدف ارزیابی می شود. در این گونه مسائل همواره می بایستی چندین هدف که معمولاً در تضاد با یکدیگر هستند بطور همزمان بهینه شوند. از این رو همواره یک پاسخ نمی تواند به تنهایی شامل بهترین مقادیر برای توابع هدف مختلف باشد. در این مسائل همواره مجموعه ای از پاسخ ها وجود داردند که نسبت به سایر پاسخ های موجود در فضای جواب برتر هستند. این مجموعه پاسخ های نامغلوب تحت عنوان مجموعه ی بهینه پارتو نامیده می شوند. این مجموعه جواب همواره انتخاب های مختلفی را برای تصمیم گیرنده به همراه خواهد داشت که در نهایت یکی از این نقاط بعنوان نقطه نهایی توسط تصمیم گیرنده انتخاب می شود.
رویکرد روش های کلاسیک برای حل این مسائل، همواره به صورت وزن دهی به اهداف مختلف و تبدیل یک مسئله ی چند هدفه به یک مسئله تک هدفه می باشد. البته این نکته ای که در روش های کلاسیک حائز اهمیت است، اینکه توابع هدف مختلف مسئله با هم متناسب نباشند، بطور مثال یک هدف دارای مقیاس زمان و دیگری بر مقیاس سرعت باشد که این امر ترکیب معیارهای مختلف و تبدیل آن ها به یک معیار را مشکل می سازد. روش های کلاسیک نقاط ضعف مختلفی دارند، اینکه در این روش ها نیاز به اطلاعات اولیه از مسئله داریم تا بتوان وزن های مناسبی را به اهداف مختلف اختصاص داد که این امر همواره امکان پذیر نمی باشد. روش های کلاسیک توانایی پوشش کامل فضای را نداشته و بسیار وقت گیر می باشند و در هر با اجرا فقط یک حل به ما می دهند. اگر چه امروزه مسائل بهینه سازی چند هدفه می توانند بطور موفقیت آمیزی با بکارگیری نسخه ی چند هدفه الگوریتم های فرا ابتکاری از قبیل الگوریتم بهینه سازی مورچگان، الگوریتم بیهنه سازی ازدحام ذرات و الگوریتم ژنتیک و غیره حل شوند. این الگوریتم ها این توانایی را دارند که در هر بار اجرا تقریبی از مجموعه جواب های نامغلوب را بدست آورند.
بدون از دست دادن عمومیت مسئله، یک مسئله چند هدفه با اهداف مینیمم سازی را می توان بصورت زیر نمایش داد:
minimize FX=[f1X , f1X ,…, fkX]
subject to X=x1 , x2 ,…, xn∈Sجاییکه S فضای شدنی مسئله، FX یک بردار هدف می باشد که k(≥2) تابع هدف می بایستی مینیمم شوند و X یک بردار تصمیم می باشد، یک حل شدنی است اگر X∈S باشد. تصویر فضای شدنی، که توسط Z(=FS) مشخص می شود که به عنوان منطقه شدنی تابع هدف معروف است. عناصر Z مقادیر توابع هدف هستند که توسط FX یا Z=(z1 , z2 ,…, zk)T مشخص می گردند، جاییکه zi=fiX به ازای i=1,...,k مقادیر توابع هدف هستند. به فضای S، فضای متغییر های تصمیم و فضایی که مقادیر توابع هدف را در نظر می گیرد، فضای توابع هدف نامیده می شود.

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *