چکیده:
در این مقاله، مساله زمانبندی ماشینهای موازی پردازشگر دستهای با هدف حداقل کردن حداکثر زمان تکمیل کارها بررسی میشود. نوآوری این پژوهش، به کارگیری زمان های پردازش و در دسترس بودن کارها به صورت احتمالی است. در تحقیقات پیشین اثبات شده است که مساله مورد بررسی دارای پیچیدگی سخت است. بنابراین، از روشهای ابتکاری برای حل مساله استفاده میشود. مساله مورد مطالعه، دو مرحله تصمیمگیری دارد. در مرحله اول ابتدا کارها به دستههایی طبقهبندی میشوند و در مرحله بعد، دستههای به دست آمده به ماشینهای موازی تخصیص مییابند. در این مقاله، از دو روش ابتکاری برای ایجاد دستهها و از سه روش ابتکاری برای ترتیب دهی توالی دستهها استفاده خواهد شد. به علت احتمالی بودن زمانهای پردازش و در دسترس بودن کارها، با استفاده از رویکرد شبیهسازی، 10000 نمونه مساله به صورت تصادفی تولید میشود. 6 حالت ترکیبی روشهای ابتکاری با حل نمونه مسائل به دست آمده از شبیهسازی مقایسه میشوند. نتایج به دست آمده نشان میدهد که ترکیب روشهای ابتکاری MBF در فاز اول و روش ERT-LPT در فاز دوم از کارایی بهتری در رسیدن به جوابهای مناسب برخوردار است.
خلاصه ماشینی:
"(Chandru, Lee, & Uzsoy, 1993) یک روش ابتکاری نسبت حریصانه (GR 206 ) و یک روش ابتکاری کوتاهترین زمان پردازش دسته پر (FBSPT 207 ) برای مسأله ماشینهای پردازشگر دستهای تک ماشین و موازی یکسان ارائه دادند به طوری که زمان تکمیل کل را حداقل کند.
(Chang, Damodaran*, & Melouk, 2004) یک الگوریتم فراابتکاری شبیه سازی تبرید (SA) را برای مسأله زمانبندی ماشینهای موازی پردازشگر دستهای ارائه نمودند و نتایج آن را با نتایج حاصل از حل کننده CPLEX مقایسه نمودند که نتیجه این شد که الگوریتم فراابتکاری کارآیی بهتری در شاخصهای زمانهای محاسبات و کیفیت حل برای مسائل با ابعاد بزرگ در تعداد ماشینهای موازی و کارهای تشکیل دهنده خواهد داشت.
Wang & Chou, 2010) یک مدل برنامه ریزی عدد صحیح ترکیبی برای کمینه کردن حداکثر زمان تکمیل کارها روی ماشینهای پردازشگر دستهای موازی ارائه کردند که زمان آماده بودن برای کارها در نظر گرفته شده است.
در ادامه، (Damodaran & Velez-Gallego, 2010) روش ابتکاری دیگری برای کمینه کردن حداکثر زمان تکمیل کارها روی ماشینهای پردازشگر دستهای موازی ارائه کردند.
در مرحله دوم، دستههای ساخته شده ابتدا به ماشینهای موازی موجود تخصیص مییابد سپس روی هر ماشین دستهها به ترتیب و قاعدهای مرتب میشود تا تابع هدف مورد نظر که در این مقاله حداکثر زمان تکمیل است، بهینه گردد.
7-1-2- 4-1-1- روش ابتکاری نخستین تناسب طراحی 212 شده MFF)) (Velez Gallego, 2009) این روش را برای مسأله زمانبندی ماشینهای پردازشگر دستهای موازی در شرایطی که زمان دردسترس (rj) غیرصفر است ارائه کرد."