بخشی از مقاله
خلاصه
زمانبندی ماشینهای موازی یکی از مسائل مهم و کاربردی بهینهسازی در حوزه توالی عملیات است که توجه محققان زیادی را به خود معطوف کرده است. در این تحقیق، مسأله زمانبندی ماشینهای موازی غیرمرتبط تک هدفه بررسی میشود که در آن ماشینها در بعضی زمانها در طی افق برنامهریزی در دسترس نبوده و هر ماشین ممکن است توانایی پردازش بعضی از کارها را نداشته باشد . همچنین در این مسأله، زمانهای آمادهسازی به توالی کارها و نوع ماشین وابسته بوده و زمان پردازش کارها تابعی خطی از زمان شروع آنهاست. از طرف دیگر، هر یک از کارها دارای مهلت تحویل بوده و باید پردازش آنها حداکثر تا مهلت تحویلشان پایان پذیرد. تابع هدف مسأله نیز به صورت کمینه کردن مجموع زمان تکمیل کارها میباشد. در این تحقیق، مسأله مورد بررسی به صورت یک مدل برنامهریزی عدد صحیح مختلط فرموله میشود. به دلیل NP-hard بودن مسأله، یافتن جواب بهینه برای مسائل با ابعاد بزرگ در زمانی منطقی مقدور نمیباشد. بنابراین الگوریتم فراابتکاری ژنتیک برای حل مسائل با ابعاد بزرگ توسعه داده میشود. در نهایت به منظور ارزیابی عملکرد الگوریتم پیشنهادی، تعدادی مسأله نمونه در اندازههای مختلف تولید و حل میشوند. نتایج به دست آمده کارائی الگوریتم ارائه شده را نشان میدهند.
کلمات کلیدی: زمانبندی ماشینهای موازی، محدودیت دسترس به ماشین، مهلت تحویل کارها، زمانهای آمادهسازی وابسته به توالی
.1 مقدمه
زمانبندی یک فرایند تصمیمسازی است که در بسیاری از صنایع خدماتی و تولیدی استفاده میشود. زمانبندی با تخصیص منابع به کارها در بازههای زمانی سروکار داشته و هدف آن بهینهسازی یک یا چند معیار است. به طور کلی، روشهای هوشمند زمانبندی برای تخصیص کارها به ماشینها در موقع مواجهه با محدودیت زمان و منابع مورد نیاز است. در مسائل کلاسیک زمانبندی فرض میشود که ماشینها به طور پیوسته در تمام مدت برنامهی تولید در دسترس هستند. این فرض ممکن است در مواردی توجیهپذیر باشد، اما در بسیاری از موقعیتهای عملی در دنیای واقعی توجیهپذیر نیست. عملیات یک ماشین در دورههایی از زمان میتواند به دلایل مختلف از قبیل بازرسی و یا تعمیرات پیشگیرانه قطع شود. بنابراین، بررسی روشهایی برای زمانبندی کارها با توجه به از دسترس خارج شدن ماشینها در بازههایی از زمان، حائز اهمیت است. از سوی دیگر، در نظر گرفتن مهلت تحویل1 برای پردازش کارها و وابسته بودن زمانهای پردازش به زمان شروع کارها در بعضی از صنایع با توجه به ماهیت کارها و سیاست تولید، امری متداول است.
پیشینه تحقیق مسأله زمانبندی ماشینهای موازی بسیار گسترده است و تحقیقات متعددی در این حوزه صورت گرفته که در میان آنها برخی از این مطالعات، محدودیتهای مشابه با محدودیتهای مسأله مورد بررسی در این تحقیق در نظر گرفته شده که در ادامه این بخش به بررسی برخی از آنها پرداخته میشود. مسألهی زمانبندی ماشینهای موازی غیرمرتبط با در نظر گرفتن زمانهای آمادهسازی وابسته به توالی و تابع هدف دامنه عملیات در سالهای اخیر مورد توجه محققان قرار گرفته است. ترن و بک [1] یک رویکرد بر اساس روش تجزیه که ترکیبی از برنامهریزی عدد صحیح آمیخته و مسأله فروشنده دورهگرد است، برای این مسأله ارائه دادند. هلال و همکاران [2] یک الگوریتم جستجوی ممنوع برای این مسأله ارائه دادند. آرناوت و همکاران [3] یک الگوریتم کلونی مورچگان برای این مسأله طراحی کردند. والادا و رویز [4] دو نسخه از الگوریتم ژنتیک برای این مسأله ارائه کرده و عملکرد آنها را ارزیابی کردند. اینگ و همکاران [5] یک الگوریتم جستجوی ممنوع محدود برای این مسأله پیشنهاد کرده و نشان دادند که الگوریتم پیشنهادی آنها نسبت به الگوریتمهای ابتکاری دیگر، عملکرد بهتری از خود نشان می دهد. چانگ و چن [6] با استفاده از روابط غالب و مغلوب یک الگوریتم ابتکاری برای این مسأله توسعه داده و عملکرد بهتر آن را نسبت به الگوریتم-های تبرید شبیهسازی شده و ژنتیک نشان دادند. لین و اینگ [7] یک الگوریتم لانه زنبور عسل ترکیبی برای این مسأله ارائه دادند و عملکرد آن را با الگوریتم ارائه شده توسط چانگ و چن [6] مقایسه کردند.
آوالس رسالس و همکاران [8] یک مدل برنامهریزی عدد صحیح آمیخته برای این مسأله ارائه کردند و نشان دادند که مدل جدید آنها نسبت به مدل ارائه شده قبلی بسیار مؤثرتر است. آنها همچنین برای این مسأله یک الگوریتم فراابتکاری ارائه دادند. ایلماز و همکاران [9] یک الگوریتم ژنتیک همراه با جستجوی محلی برای این مسأله ارائه کرده و نشان دادند که این الگوریتم عملکرد بهتری نسبت به الگوریتمهای پیشین ارائه شده برای این مسأله دارد. برای مسألهی زمانبندی ماشینهای موازی غیرمرتبط با در نظر گرفتن زمانهای آمادهسازی وابسته به توالی و تابع هدف کمینه کردن مجموع تأخیرها در سالهای اخیر مورد توجه محققان قرار گرفته است. چن [10] یک الگوریتم تبرید شبیهسازی شده و دو الگوریتم ابتکاری دیگر برای این مسأله ارائه کرده و با انجام آزمایشات محاسباتی نشان داد که الگوریتم تبرید شبیهسازی شده عملکرد بهتری نسبت به دو الگوریتم ابتکاری دیگر دارد. لین و همکاران [11]
یک الگوریتم حریصانه تکراری برای این مسأله ارائه کردند. لی و همکاران [12] یک الگوریتم جستجوی ممنوع برای این مسأله ارائه کرده و عملکرد مناسب آن را نشان دادند. برای مسألهی زمانبندی ماشینهای موازی غیرمرتبط با در نظر گرفتن زمانهای آمادهسازی وابسته به توالی و محدودیت قابلیت ماشینها و تابع هدف کمینه کردن مجموع تأخیرهای وزندار هم در سالهای اخیر، مطالعات مختلفی صورت گرفته است. لین و هسیه [13] یک مدل برنامهریزی عدد صحیح آمیخته برای این مسأله ارائه کرده و یک الگوریتم فراابتکاری ترکیبی پیشنهاد کردند و آنها نشان دادند که الگوریتم فراابتکاری ارائه شده، نسبت به الگوریتمهای جستجوی ممنوع و کلونی مورچگان که در گذشته برای این مسأله ارائه شدهاند، عملکرد بهتری دارد. پریرا لوپز و کاروالهو [14] هم یک الگوریتم شاخه و قیمت2 برای این مسأله ارائه کردند. آکیول و بایهان [15]
یک مدل برنامهریزی عدد صحیح آمیخته و یک الگوریتم مبتنی بر شبکه عصبی مصنوعی برای مسأله زمانبندی ماشین-های موازی غیرمرتبط با در نظر گرفتن زمانهای آمادهسازی وابسته به توالی و تابع هدف کمینه کردن مجموع زودکردها و دیرکردها ارائه کردند. نوگیرا و همکاران [16] برای همین مسأله، الگوریتمهای ابتکاری مختلفی مبتنی بر الگوریتم جستجوی تصادفی حریصانه ارائه کردند . آنها همچنین نشان دادند که برای این مسأله، زمانبندی بهینه لزوماً بدون تأخیر نیست و بیکار گذاشتن ماشینها ممکن است در راستای بهبود تابع هدف باشد. سان و لی [17] مسأله زمانبندی دو ماشین موازی را با این فرض که هر کدام از ماشینها در بازههایی از زمان برای انجام فعالیتهای نگهداری و تعمیرات در دسترس نبوده و نیز زمان کارکرد متوالی هر ماشین نمیتواند بیشتر از یک مدت از پیش تعیین شده باشد، بررسی کردند. آنها دو مدل متفاوت در نظر گرفتند: در مدل اول، فرض بر این است که فعالیت-های نگهداری و تعمیرات به صورت دورهای انجام شده و هدف کمینه کردن دامنهی عملیات است و در مدل دوم، فرض شده است که زمان انجام این فعالیتها در ابتدای زمانبندی مشخص بوده و هدف کمینه کردن مجموع زمانهای تکمیل است؛ یک الگوریتم چندجملهای برای مدل اول معرفی و برای مدل دوم نیز قاعدهی کلاسیک کوتاهترین زمان پردازش مطرح شده است.
ژائو و همکاران [18] مسأله دو ماشینه را با هدف کمینه کردن مجموع وزنی زمانهای تکمیل و با این فرض که فقط یکی از ماشینها در بازههای مشخصی از زمان در دسترس نیست، بررسی و یک روش تقریبی برای حل آن ارائه کردند تان و همکاران [19] مسأله دو ماشینه را با هدف کمینه کردن مجموع زمانهای تکمیل و با این فرض که هر یک از ماشینها در بازههای مشخصی از زمان در دسترس نیستند، بررسی کردند . آنها نشان دادند که قاعده کوتاهترین زمان پردازش برای حالتی که یکی از ماشینها در بازهای از زمان از دسترس خارج شود و همچنین برای حالتی که هر یک از ماشینها در بازهای از زمان از دسترس خارج شود طوریکه این بازهها همپوشانی نداشته باشند، منجر به جوابی خواهد شد که انحراف آن نسبت به جواب بهینه در بدترین حالت، مشخص است. ژو و یانگ [20] مسأله دو ماشینه را با هدف کمینه کردن دامنهی عملیات و با این فرض که یکی از ماشینها به صورت دورهای از دسترس خارج شده و ماشین دیگر همواره در دسترس است، بررسی کردند. وانگ و چنگ [21] مسأله دو ماشینه را با هدف بیشنه کردن تعداد کارهایی که پردازش آنها بدون تأخیر به پایان میرسد، مورد بررسی قرار داده و با این فرض که یکی از ماشینها در یک بازه زمانی مشخص در دسترس نمیباشد، یک روش ابتکاری برای حل آن پیشنهاد کردند. لی و کیم [22]
مسأله دو ماشینه را با هدف کمینه کردن مجموع دیرکرد3 کارها و با این فرض که هر ماشین پس از پردازش تعداد مشخصی کار باید به منظور انجام فعالیتهای نگهداری و تعمیرات از دسترس خارج شود، بررسی و یک الگوریتم شاخه و کران برای حل آن ارائه کردند . هی و همکاران [23] نیز مسأله دو ماشینه را با هدف کمینه کردن دامنهی عملیات مورد بررسی قرار داده و با این فرض که هر یک از دو ماشین به صورت دورهای در بازههایی از زمان با حداکثر فاصله مشخص از دسترس خارج میشوند، چندین الگوریتم ابتکاری برای حل آن ارائه کردند. لی و همکاران [24] مسأله را با هدف کمینه کردن مجموع دیرکرها و با این فرض که ماشینها نیازمند فعالیتهای نگهداری و تعمیرات هستند، مورد بررسی قرار دادند. آنها یک الگوریتم شاخه و کران و نیز یک الگوریتم ژنتیک برای حل مسأله ارائه کردند. اخیراً نیز یین و همکاران [25] مسأله را با هدف کمینه کردن مجموع زمانهای تکمیل مورد انتظار بررسی کرده و با این فرض که بعضی از ماشینها ممکن است در بازهای از زمان با احتمال مشخصی از دسترس خارج شده و نیز مدت زمان پردازش هر کار با تعویق پردازش افزایش مییابد، روشهای تقریبی حل را توسعه دادند.
برای مسألهی زمانبندی ماشینهای موازی غیرمرتبط با در نظر گرفتن زمانهای آمادهسازی وابسته به توالی و محدودیتهای دسترسی به ماشینها و قابلیت ماشینها در پردازش کارها با تابع هدف کمینه کردن مجموع زودکردها و دیرکردها، مهدوی[26] یک مدل برنامهریزی عدد صحیح آمیخته ارائه کرده و یک الگوریتم رقابت استعماری برای حل مسائل بزرگ پیشنهاد کرده است. در این تحقیق، مسأله زمانبندی ماشینهای موازی غیرمرتبط تک هدفه بررسی میشود که در آن ماشینها ممکن است در ابتدای دوره زمانبندی به دلیل کارهای باقیمانده از دورههای قبل، در زمانهای مختلفی دردسترس قرار گیرند و هر ماشین در بازهای مشخص از زمان در طی افق برنامهریزی به دلیل انجام فعالیتهای نگهداری و تعمیرات از دسترس
