بخشی از مقاله
چکیده
یکی از اهداف مهم مدیران در سازمانها و صنایع، بهرهوری میباشد که با شدت بسیاری در دنیا دنبال میشود. استفاده از سیستمهای چندپردازندهای در سیستمهای چندمرحلهای یکی از عوامل موثر در رسیدن به بهرهوری در صنایع به شمار میرود. پژوهش حاضر مسئله زمانبندی جریان کار چند مرحلهای را در سیستمهای چندپردازندهای مورد اندیشه قرار داده است. این مسئله NP-hard توسط الگوریتم شبیهسازی تبرید با هدف بهینه ساختن Cmax توسعه داده شده است. برای اعتبارسنجی کارایی الگوریتم ارائه شده، آزمایشات محاسباتی بروی فایلهای محک خوشنامی انجام گرفت. فرا اکتشافی پیشنهاد شده توانست از 200 نمونه فایل محک مورد بررسی، 114 تای آنها را بهبود بخشد.
مقدمه
با توجه به اهمیتی که امروزه سیستمهای چندپردازندهای در محیطهای صنعتی یافتهاند، مطالعه و تحقیق برای بهینهسازی آنها ضروری به نظر میرسد. زمانبدی مناسب و اصولی چنین سیستمهایی میتواند باعث بهرهوری و افزایش کارایی کلی سیستم و سازمان شود. مسئله زمانبندی وظایف چندپردازندهای یککلیّت از مسئله زمانبندی کلاسیک است که در آن وظایف - کارها - نیاز به دریافت سرویس از بیش از یک پردازنده برای انجام یک مرحله دارند. یکی از تابع هدفهای مهم در چنین سیستمهایی، زمان اتمام کامل کارها میباشد. لذا برای افزایش کارایی باید به دنبال روشی باشیم که زمان اتمام کارها را تا حد امکان کاهش دهیم تا بتوانیم محصول نهایی را سریعتر تحویل دهیم.
زمانبندی چندمرحلهای به سه زیر نوع قابل تق سیم ا ست که این تق سیمبندی برا ساس توالی انجام عملیات قطعات مختلف میباشد. چگونگی قرارگیری پردازندهها - ماشینها - نسبت به یکدیگر و نیز چگونگی حرکت وظایف در بین پردازندهها در مراحل مختلف موجب شد تا این سه نوع مدل با نامهای جریان کار1 ، کار کارگاهی2 و کارگاه باز3 وجود داشته باشد. پژوهش حاضر، مسئله زمانبندی جریان کار در سیستمهای چندپردازندهای را مورد بررسی قرار داده است. بدین منظور تعاریف زیر مد نظر است: مجموعهای از j 1' 2' …' Q کار را در نظر بگیرید که هر یک باید بر روی i 1' 2 ' …' m} ماشین پردازش شود. دیدن یک کار به عنوان دنباله ای از m وظیفه که یک وظیفه برای هر مرحله منا سب ا ست که در آن پردازش هر کار می تواند تنها پس از اتمام کار قبل آغاز شود.
هر وظیفه در یک کار، نیاز به یک یا چند پردازنده - ما شین - از نوع i به طور همزمان دارد. همه پردازنده ها و کارها در زمان t=0 در دسترس هستند. پردازنده های مورد استفاده در هر مرحله یکسان هستند و نمیتوانند وظایف مربوط به مراحل دیگر را پردازش کنند. mi، تعداد پردازنده های همانند موجود در سی ستم ا ست که قابلیت آنرا دارند که به کار Ji,j سرویس دهند و sizeij تعداد پردازنده های مورد نیاز برای پردازش کار Jj در مرحله i است. pij بیان کننده زمان پردازش کار Jj در مرحله i است.
اگر تعداد sizeij پردازندههای نوع i اجرای یک کار Jj را در مرحله i شروع کنند، این اجرا را در طول pij واحد زمانی ادامه میدهند. بهگونهای دیگر میتوان گفت که کار Jj نیاز به تعداد sizeij پردازنده از نوع i به مدت زمان pij دارد تا اُمینi عملیات خود را تکمیل نماید. هیچ پردازندهای نمیتواند بیش از یک کار را پردازش کند. از آنجاکه پردازندههای نوع i ام با هم یکسان هستند و کارها بهصورت انحصاری پردازندهها را در اختیار میگیرند، برای تعریف زمانبندی کافی ا ست تا زمان کامل شدن تمام وظایف هر کار را محا سبه کنیم.
Cjm - s - زمان کامل شدن mاُمین وظیفه از کار Jj در زمانبند s است. یافتن زمانبند کمینه با معیار Cmax - s - =maxj J Cjm - s - ضروری به نظر میرسد. مسئله کمینهسازی معیار Cmax - s - بهعنوان مسئله کمینهسازی زمان اتمام کار 4 شناخته میشود. این مسئله بهصورت Fm - Pm1'…'3Pk - sizeij Cmax بیان میشود. بخش Fm - Pm1'…'3Pk - بیان میکند که هر کار Jj باید در m مرحله با ki - 1 k mi - پردازنده یکسان از نوع i از mi پردازنده موجود، پردازش شود. - اگوز5 و همکاران، . - 2004
ادبیات پژوهش
نرون1 و همکاران - - 2001 م سئله زمانبندی جریان کار ترکیبی را با هدف کمینه ساختن زمان اتمام آخرین کار برر سی کردند. آنها بیان داشتند که استفاده از تنظیمات آزمون رضایت2 و محدودیت در زمان براساس عملیات عمومی میتواند بهرهوری استفاده از روش 3B&B را برای حل مسئله زمانبندی جریان کار ترکیبی بالا ببرد. اگوز و همکاران - - 2003 الگوریتمهای اکتشافی سازندهای را برای زمانبندی جریان کار دو مرحلهای با وظایف چندپردازندهای به منظور کمینه ساختن زمان اتمام آخرین کار ارائه دادند. آنها برای نتیجه بخش بودن الگوریتمهای B&B ارائه داده توسط خود، از قوانین توالی و وظایف مبتنی بر قوانین اولویت سایر الگوریتم ها استفاده کردند.
نتایج حاصل از تجزیه و تحلیل حاکی از موثر بودن و اثر بودن الگوریتمهای اکتشافی مبتنی بر & بوده است. انجین4 و هم کاران - 2011 - برای ز مانب ندی جر یان کار ترکیبی بوسی له و ظایف چندپردازندهای از الگوریتم ژنتیک استفاده کردند. آنها الگوریتم خود را با هدف کاهش زمان اتمام کار بروی 240 نمونه فایل محک مورد آزمایش قرار دادند. نتایج بدست آمده حاکی از آن است که در 58 مسئله کران پایین و در %48,3 از مسائل راه حل بهتری برای کاهش زمان اجرای کل بد ست آمد. ر ضائیان5 و همکاران - - 2013 مدل جدیدی برای م سئله زمانبندی جریان کار ترکیبی با وظایف چندپردازنده ای که در آن به زمان شروع و انحصار بودن وظایف توجه شده را با هدف کمینه کردن زمان اتمام کار و تاخیر ورود6 ارائه دادند.
آنها از سه روش فراابتکاری مبتنی بر الگوریتم ژنتیک، الگوریتم رقابت استعماری7 و ترکیبی از این روش ها برای حل مسئله بوجود آمده استفاده کردند. عملکرد الگوریتم ها توسط زمان محاسباتی و درصد انحراف مرتبط مورد ارزیابی قرار گرفت. نتایج حاکی از آن است که الگوریتم رقابت استعماری مسائل را سریعتر از 2 الگوریتم دیگر حل میکند. لاهیمر 8 و همکاران - - 2013 مسئله به حداقل رساندن زمان اتمام کار را در زمانبندی جریان کار ترکیبی چندمرحلهای در سیستم چندوظیفهای و چندپردازندهای مورد بررسی قرار دادند.
برای تولید تقریبی از راهحلهای با کیفیت بالا در این مسئلهی NP-hard ، آنها از روش جستجوی ابتکاری ناهمخوان که مبتنی بر مفهوم جدیدی از ناهمخوانیهای مجاور است پیشنهاد کردند. بعلاوه، آنها کران پایین جدیدی را بر اساس توابع دوگانهی امکانپذیر شرح دادند. کرانهای بالا و پایین پی شنهادی از طریق آزمای شهای محاسباتی برروی 300 نمونه از فایل محک مورد ارزیابی قرار گرفته است.
برای این موارد، آنها شواهدی مبنی بر اینکه کرانهای پی شنهادی بهطور مداوم، کران بهتری از کرانهای موجود فراهم میکند را ارائه دادند. بهطور خاص، اکت شاف پی شنهاد شده، موفق شد تا راه حل 75 فایل محک شناخته شده را بهبود ببخ شد. یو - 2014 - 9 بو سیله ادغام روش جستجوی محلی ابتکاری با بهینه سازی ازدحام ذرات، الگوریتم بهینه ساز ازدحام ذرات دوقلو را با زمانهای برپایی واب سته برای زمانبندی جریان کار چندپردازندهای پیشنهاد داد.
