دانلود مقاله ترجمه شده زمانبندي كاري و تخصیص منابع به طور همزمان در ماشینهای موازی

چکیده

قطعی­ترین مدل های مربوط به زمانبندي ماشین فرض مي­كنند که زمان پردازش یک کار بر روی یک دستگاه، ثابت بوده و قبل از زمانبندي معين ميباشد. با این حال، در اکثر موارد واقع­بینانه، جدا از ماشينها، نیاز به منابع اضافی بمنظور پردازش كارها مطرح ميگردد، و زمان پردازش یک کار بصورت داخلی توسط مقدار منابع اختصاص داده شده، تعیین شده است. در این شرایط، هر دو مورد هزینه مرتبط با زمانبندي کار و هزینه منابع اختصاص داده شده، باید در نظر گرفته شوند. بنابراین، زمانبندي كاري و تخصیص منابع باید به منظور دستیابی به برنامه زمانبندي كلي مقرون به صرفه، به دقت هماهنگ شده باشد.

در این مقاله، ما یک مدل زمانبندي ماشين موازي مربوط به پردازش کار و تخصیص منابع را بطور همزمان، مورد بررسي قرار داده ­ايم. زمان پردازش یک کار با هزینه منابع اختصاص داده شده، افزايش نمي­يابد. هدف، به حداقل رساندن هزینه کل از جمله هزینه اندازه­ گیری شده توسط یک معیار زمانبندي و هزینه كل منابع اختصاص داده شده است.  ما دو مساله خاص از این مدل را در نظر مي­گيريم، یکی شامل زمان كل اتمام بصورت وزني ميباشد، و ديگري تعداد وزنی كارهاي کند ميباشد. ما يك توليد ستوني را بر اساس روش شاخه و حد برای یافتن راه­ حل بهینه برای این مسائل چندجمله­اي غير قطعي سخت توسعه مي­دهيم. این روش برای اولین بار به تدوین و فرموله مسائل به عنوان مجموعه ­ای از فرمولاسیون­ها از نوع پارتیشن­بندی پرداخت، و سپس فرمولاسیونهاي حاصل را دقیقا توسط شاخه و حد حل كرد. در الگوريتم شاخه و حد، تسهیلات خطی مجموعه فرمولاسیون­هاي پارتیشن­بندی به مسائل برجسته و مسائل فرعي توسط روش تولید ستون، تجزيه شده است. الگوریتمهاي طراحی شده بر اساس این روش قادر به حل این دو مساله با ميزان متوسط ​​ بهینگی در مدت زمان محاسباتی معقول، ميباشند.

1. مقدمه

مدلهای زمانبندي ماشين، به يك موضوعي تبديل شده است كه تعداد قابل توجهی از مقالات را در سه دهه گذشته به خود اختصاص داده است. اکثر نتایج در رابطه با مسائل قطعی در این زمینه فرض ميكنند که زمان پردازش یک کار در ماشين ثابت و بوده و قبل از زمانبندي معين ميباشد. با این حال، در اکثر موارد واقع­بینانه، جدا از ماشينها، نیاز به منابع اضافی (به عنوان مثال، برق، نیروی انسانی و تجهیزات پشتیبانی) جهت پردازش امور مطرح ميگردد، و زمان پردازش یک کار توسط مقدار منابع اختصاص داده شده، تعیین شده است. در این شرایط، هر دو مورد هزینه­های مرتبط با برنامه کار و هزینه اختصاص داده شده به منابع باید در نظر گرفته شود. بنابراین، زمانبندي كاري و تخصیص منابع باید به دقت به منظور دستیابی به برنامه­اي مقرون به صرفه، هماهنگ شده باشد.

کار بر روی مدلهای زمانبندي ماشين با زمانهاي پردازش كارهاي کنترل شده توسط تخصیص منابع توسط VICKSON [25-26] و VAN WASSENHOVE و بیکر آغاز شد  [24]. این مدلها در طول دهه گذشته افزایش بسياري را به خود معطوف داشته­اند. دانشمندان ديگري نيز اين مورد را مورد بررسي قرار داده­اند كه ميتوان بعنوان مثال به NOWICKI و ZDRZALKA ، PANWALKAR و RAJAGOPLAN]  [3]، ALIDAEE، و احمدیان [1] ترفند [22]، دانیلز و MAZZOLA و چنگ و  KOVALYOV و دانیلز، و همکاران [10-11]، چنگ، و همکاران [7-8]، و چن و همکاران، اشاره نمود. [3].

دو نوع زمان پردازش کار در ادبیات وجود دارد در نظر گرفته شده است. در نوع اول، نوع مداوم، زمان پردازش کار توسط مقدار یک منبع قابل تقسیم (به عنوان مثال برق) اختصاص داده شده، تعیین شده است و از این رو میتوان در یک فاصله داده شده، حالتهاي متفاوتي را يافت. در نوع دوم، نوع گسسته، منابع اختصاص داده شده، غير قابل تقسیم ميباشند (به عنوان مثال نیروی انسانی، و تجهیزات پشتیبانی) و از این رو زمان پردازش یک کار فقط میتواند داراي طولهاي ممكن بسياري باشد. به جز مقالات دانیلز و MAZZOLA، و همکاران [10-11]، و چن و همکاران [3] که مطالعه مسائل مربوط به با انواع مختلف زمان پردازش گسسته را مورد بررسي قرار داده­اند، تمام نتایج مذكور در بالا زمان پردازش از نوع مداوم را مورد بررسي قرار داده ­اند...