دانلود مقاله ترجمه شده زمان بندی ماشین موازی با منابع منعطف

مسائل زمان­بندی منابع منعطف ماشین­های موازی (PMFRS) منابع منعطف اضافی را مورد بررسی قرار می­دهد (مانند اپراتورها)، که آن­ها می­توانند آزادانه به هر کاری یا هر ماشینی تخصیص داده شوند و می­توانند به نسبت مقدارشان به پردازش سرعت ببخشند. اگر تخصیص کار-ماشین مشخص شده نباشند. این مساله با عنوان (PMFRS)  نامشخص (UPMFRS) اشاره می­شود. در این مقاله، مدل­های ریاضی هر دو مساله PMFRS و UPMFRS در ادبیات موضوع مرور می­شود و فقط تعدادی بسط به مساله پویا PMFRS می­دهیم، اما همچنین مدل­های برنامه ­ریزی عدد صحیح (IP) برای حالت ایستا و پویا با تابع هدف کمینه کردن کل زمان انجام کار ارائه می­کنیم. به منظور حل مسائل سایز بزرگ پویا PMFRS و UPMFRS ، رویکرد برنامه­ریزی محدودیت­دار بر مبنای IP آزاد شده (CP) نیز ارائه شده است. تمام مدل­های و رویکرد IP/CP مطرح شده با مطالعه محاسباتی مبسوطی تست شده­اند. نتایج آزمایش­های محاسباتی برای پارامترهای مهم مساله مورد بحث قرار گرفته­اند و نتایج به تصویر کشیده شده­اند.

مسائل زمان­بندی ماشین­های موازی با منابع اضافی به طور گسترده­ای در ادبیات موضوع مطالعه شده است. مروری اخیرا از این مطالعات در ادیس، اگوز و ازکاراهان (برای انتشار فرستاده شده) می­توان دید. در این مقاله، ما نوع خاصی از این مسائل با نام زمان­بندی منابع منعطف ماشین­های موازی(PMFRS) را مورد بررسی قرار می­دهیم. در PMFRS که برای اولین بار توسط دنیل، هوپس و مازولا (1996) مطرح شد، زمان پردازش کارها ثابت نیستند اما به مقدار منابع اضافی اختصاص داده شده به کارها وابسته­اند. مساله PMFRS به صورت قائده­مند زیر تعریف می­شود: مجموعه­ای از nکار روی مجموعه­ای از m ماشین پردازش می­شوند که تخصیص کارها به ماشین­ها از قبل مشخص شده­است، بعلاوه، پردازش هر کار نیازمند نوعی منبع محدود تجدیدپذیر منفرد است و زمان پردازش هر کار تابع ناصعودی از مقدار مرتبط از منابع اختصاص داده شده است. مقدار منابع تخصیص داده شده به هر کاری اشاره به حالت عملیاتی­اش دارد (دنیلز و همکاران 1996). R را نشان­دهنده مقدار کل منابع اضافی در سیستم در هر لحظه فرض می­کنیم. هر کار i می­تواند در هر شماره­ای از مدها، با Ki که نشان­دهنده مجموعه­ای از مدهای ممکن برای کار i است، پردازش شود. فرض کنید که Pik نشان­دهنده زمان پردازش کار i است وقتی که در مد  پردازش شود. برای دستیابی به زمان پردازش واحدهای منابع به کار i برای زمان آن باید اختصاص داده شود. منابع منعطف می­تواند آزادانه در میان کارها اختصاص داده شود، گرچه، در هر زمانی، کل مقدار منابع تخصیص داده شده به کارها نمی­تواند از کل مقدار R از منابع در دست بیشتر شود. (دنیلز، هوا و وبستر(1999)). مساله PMFRS در فرم اصلی­اش فرض می­شود که تخصیص کارها به ماشین­ها از پیش تعیین شده­اند که زیر مساله تخصیص کار-ماشین را حذف می­کند و Nj مجموعه­ای از کارها را مشخص می­کند که روی ماشین j پردازش شده­اند (دنیلز و همکاران 1996). اگر تخصیص کارها به ماشین­ها مشخص نشده باشد، ما با مساله PMFRS نامشخص (UPMFRS) روبرو هستیم، که نوعی زیر مساله تخصیص کار-ماشین اضافی باید حل شود (دنیلز و همکاران(1999)). برای هر دو مساله PMFRS و UPMFRS، ما می­توانیم هر دو نوع ایستا و پویا را بر اساس آنکه چگونه منابع به ماشین­ها و کارها تخصیص داده شوند، تعریف کنیم. در نوع ایستا منابع می­توانند آزادانه به ماشین­ها اختصاص یابند اما نتیجه این تخصیص منابع باید در افق زمان­بندی ثابت باقی بماند (دنیلز و همکاران 1996). مدل پویا، از طرف دیگرمحیط­های زمان­بندی عمومی­تری دارد که منابع منعطفی آزادانه می­تواند در بین ماشین­ها در میان باقی افق زمانبندی تخصیص داده شود(دنیلز و همکاران 1996).   با توجه به پیچیدگی محاسباتی، در حالی­که مساله PMFRS در زمان چندجمله­ای قابل حل هستند، مسائل دیگر مانند PMFRSپویا، UPMFRS پویا و ایستا NP-سخت هستند..