بخشی از مقاله
چکیده
در این پژوهش یک مسئله زمانبندی در شرایطی که ماشینالات به شکل موازی و نیز به صورت غیر مرتبط با یکدیگر هستند در نظر گرفته میشود. هدف از این مسئله انجام زمانبندی بدون تاخیر در پردازش قطعات است. در حقیقت مدل به گونهای طراحی خواهد شد که سیستم دارای چند نوع قطعه متفاوت باشد که هر کدام به عملیات خاص خود نیازمند هستند.
بنابراین با توجه به متفاوت بودن نوع قطعات و نیز تفاوت در عملیات مورد نیاز هریک از قطعات، زمانهای پردازش نیز متفاوت خواهد بود. از طرفی توانایی ماشینالات در انجام عملیات نیز با یکدیگر یکسان نیست. بدین معنی که هر ماشین، توانایی انجام عملیات خاصی را دارد. تابع هدف مدل نیز کمینهسازی زمان انجام عملیات خواهد بود. همچنین به دلیل اینکه مسئله زمانبندی تولید یک مسئله فوق سخت میباشد از الگوریتم ژنتیک برای حل این مسئله استفاده خواهیم کرد.
.1 مقدمه
زمانبندی یک فرآیند تصمیمسازی است که در بسیاری از صنایع خدماتی و تولیدی استفاده میشود. زمانبندی با تخصیص منابع به فعالیتها در بازههای زمانی داده شده، سروکار داشته و هدف آن بهینهسازی یک یا چند هدف تعیین شده است. منابع وکارها در یک سازمان میتوانند اشکال مختلفی داشته باشند. منابع ممکن است ماشینها در یک کارگاه، خطوط هوایی در یک فرودگاه، کارگران در یک مکان ساخت و ساز، واحدهای پردازشی در یک محیط محاسباتی و غیره باشند. کارها ممکن است عملیات در فرآیند تولید، فرودها و پروازها در فرودگاه، مراحل در یک پروژه ساخت، اجرای برنامههای کامپیوتری و غیره باشند
در جهان رقابتی حاضر، تعیین توالی و زمانبندی موثر محصولات تولیدی ضرورتی برای بقا در فضای بازار است. زمانبندی ابزاری برای استفاده بهینه از منابع در دسترس است. منابع و کارها در زمانبندی ممکن است انواع گوناگونی داشته باشند و با توسعه جهان صنعتی، منابع مربوطه بحرانیتر میشود. زمانبندی این منابع به افزایش کارایی و بهرهبرداری از ظرفیت، کاهش زمان مورد نیاز برای تکمیل کارها و نهایتا افزایش سوددهی یک سازمان منجر میشود. زمانبندی موثرمنابع مانند ماشینها و نیروی انسانی در محیط رقابتی امروز یک باید است.
لاموت1 و همکاران - 2012 - مسئله زمانبندی ماشینهای موازی با زمان آمادهسازی و محدودیت زمانی برای انجام کارها را مورد بررسی قرار دادند. آنها از الگوریتم تبرید شبیهسازی شده به منظور کمینهسازی کل دیرکردها استفاده کردند.
تسای و وانگ - 2012 - 2 سه مدل برنامهریزی عدد مختلط را برای مسئله ماشین های موازی نامرتبط با موعدهای تحویل متفاوت پیشنهاد نمودند. هدف این مدلسازی کمینهسازی مجموع زودکرد و دیرکرد میباشد. در این تحقیق آنها بهترین استفاده از زمان بیکاری ماشین ها جهت افزایش انعطاف پذیری زمانبندی کارها را مدنظر قرار دادند. با وجود اینکه این مدلها در زمانی قابل توجیه جوابگو میباشند، زمانهای بیکاری ایجاد شده در تنظیم برنامه زمانبندی استفاده میگردد، زمانیکه موعدهای تحویل باز بالا باشند کارها بسیار بهتر قابل زمانبندی هستند، زمان بیکاری موجود انعطافپذیری زمانبندی کارها را افزایش میدهد، اما این مدلها محدودیت برنامهریزی را در تعدادکارها و ماشینها دارد و برای تمامی حالات قابل کاربری نیستند.
لی 3 و همکاران - 2013 - به بررسی مسئله زمانبندی ماشین آلات موازی غیرمرتبط با پردازش دستهایی با هدف کمینه سازی ماکزیمم زمان تکمیل کارها پرداختند . در این مسئله کارها با سایز های غیر مشابه بر روی ماشینهای پردازش دستهای که قادر به پردازش چندین کار هستند قرار میگیرند به طوری که ظرفیت ماشینآلات نبایستی نقض گردد.
یانگ و یانگ - 2013 - 4 به بررسی مسئله زمانبندی همراه با فعالیتهای نرخ اصلاحی چندگانه یر روی ماشینهای موازی غیر مرتبط پرداختند. فرض شده است که هر ماشین شامل فعالیت های اصلاحی چندگانه بوده و هدف نیز تعیین همزمان تکرار بهینه فعالیتهای نرخ اصلاح چندگانه، موقعیتهای بهینه فعالیتهای نرخ اصلاحی، زمانبندی بهینه به منظور کمینهسازی زمانهای تکمیل کارها و در نهایت بار کل ماشین میباشد.
ترابی5 و همکاران - - 2013 یک مدل چندهدفه برای مسئله زمانبندی ماشینآلات موازی غیرمرتبط با در نظرگرفتن عدمقطعیت در زمانهای پردازش و موعد تحویل کارها ارائه کردند. به طوری که در این مسئله برای هر کار زمانهای آمادگی غیر صفر، زمانهای آمادهسازی وابسته به توالی و ماشین و همچنین محدودیت منابع ثانویه در نظر گرفته شده است.
جیانگ و تان - 2016 - 6 به معرفی مدلی برای زمانبندی کارها بر روی ماشین آلات موازی غیرمرتبط با امکان رد کارها پرداختند. در این مدل تمام کارها در زمان صفر در دسترس بوده اما برخی از ماشین ها در این زمان در اختیار نمیباشند. هدف نیز کمینهسازی زمانهای تکمیل تمام کارهای مورد پذیرش واقع شده، هزینه کل کارهای رد شده و همچنین زمان پردازش کارها است.
در ادامه در جدول زیر سایر تحقیقات صورت گرفته در زمینه ماشینهای موازی به طور مختصر بیان میگردد.
جدول : - 1 - سایر تحقیقات صورت گرفته در زمینه ماشینهای موازی
مسئله کمینهسازی میانگین وزنی دیر کردها در ماشینهای موازی مرتبط را مورد بررسی قرار دادند.
به ارائه یک سری قوانین چیره در مسئله زمانبندی ماشین های موازی با زمان دسترسی به کارها به هدف کمینهسازی کل دیر کرد وزنی پرداختند.
از متد فراابتکاری بهینه سازی بخشی دسته و کلونی مورچه برای ایجاد نتایج بهینه براساس معیارهای متفاوت زودکرد و دیرکرد استفاده نمودند، و روش فازی برای انتخاب بهترین ترکیب وزنی زودکرد و دیرکرد در مورد ماشین موازی غیرمرتبط بکار بردند.
از الگوریتم ژنتیک برای زمانبندی ماشینهای موازی استفاده نمودند. آنها برنامه بهبود و اپراتور عملکردی مناسب را توسعه دادند و با الگوریتم ژنتیک تلفیق نمودند.
یک حد پایین برای مسئله زمانبندی زودکرد و دیرکرد در سیستم ماشینهای موازی ارائه دادند.
یک ژنتیک از الگوریتم های کلونی مورچگان2، تبرید شبیه سازی شده3 و جستجوی همسایگی متغیر4 برای مسئله ارائه دادند.
برای مسئله یک مدل برنامهریزی عدد صحیح مختلط ارائه داده و برای حل آن یک الگوریتم ژنتیک پیشنهاد کردند سپس با تعریف یک حد پایین برای مسئله، عملکرد الگوریتم ژنتیک خود را مورد ارزیابی قرار دادند.
یک الگوریتم ابتکاری برای مسئله ارائه دادند و عملکرد مطلوب الگوریتم را با مقایسه آن با حد پایین و جواب بهینه نشان دادند.
برای مسئله با محدودیتهای واجد شرایط بودن ماشین ها و اینکه بعضی کارها نیازمند پردازش مجدد باشند ، یک الگوریتم فراابتکاری پیشنهاد کردند.
برای مسئله با در نظر گرفتن محدودیتهای دسترسی تولید، یک مدل برنامهریزی عدد صحیح آمیخته ارائه داده و برای حل مسائل سایز بزرگ یک الگوریتم ژنتیک پیشنهاد کردند. سپس با انجام آزمایشهای محاسباتی، عملکرد الگوریتم را مورد ارزیابی قرار دادند.
برای مسئله یک مدل برنامهریزی عدد صحیح آمیخته ارائه کرده و یک الگوریتم فراابتکاری ترکیبی پیشنهاد کردند و نشان دادند که الگوریتم فراابتکاری آنها، نسبت به الگوریتمهای جستجوی ممنوع و کلونی مورچگان که در گذشته برای این مسئله ارائه شده، عملکرد بهتری دارد.
برای مسئله، یک الگوریتم فراابتکاری جدید تحت عنوان الگوریتمABC و یک الگوریتم ژنتیک ارائه کردند.
