مسئله‌ی زمانبندی پردازه‌ها

فرض کنید $n$ پردازه و یک پردازنده داریم. هر پردازه یک زمان شروع $(s_i)$ و یک زمان پایان $(f_i)$ دارد. از آنجا که تنها یک پردازنده داریم، باید طوری پردازه ها را به پردازنده بدهیم که بازه‌ی زمانی هیچ دو پردازه ای با هم تداخل نداشته باشد، بیشترین تعداد پردازه های ممکن که می‌توان به پردازنده داد چه قدر است ؟

(در حالت کلی تر مسئله هر پردازه یک مقدار سود تولید می‌کند و می‌خواهیم سود بیشینه شود)

فرض کنید $S_{ij}$ مجموعه پردازه هایی باشد که بین دو پردازه‌ی $a_j$ , $a_i$ هستند و تداخلی با آن دو ندارند و $A_{ij}$ جواب بهینه‌ی این مجموعه‌ی پردازه‌ها باشد. از آنجا که این مسئله دارای زیر ساختار بهینه است، در صورتی که $a_k$ درون یک جواب بهینه باشد، رابطه‌ی $ A_{ij} = A_{ik} + A_{kj} + 1$ برقرار است .

فرض کنید $a_i$ ها به ترتیبی باشند که $f_1 \lt f_2 \lt f_3 ... \lt f_n $ ، در این صورت با اضافه کردن $a_1$ به یک جواب بهینه‌ی دلخواه ، $a_1$ حد اکثر با یک بازه‌ی دیگر تداخل پیدا می‌کند ، زیرا تمام بازه هایی که با $a_1$ تداخل دارند از نقطه‌ی $f_1$ می‌گذرند. با حذف بازه‌ای که با $a_1$ تداخل دارد به یک جواب بهینه‌ی دیگر می‌رسیم، که نشان می‌دهد همواره جواب بهینه‌ای وجود دارد که شامل بازه‌ی اول باشد، پس $a_1$ انتخاب حریصانه‌ی مناسبی است.

درنتیجه الگوریتم حریصانه‌ی زیر جواب بهینه را می‌دهد: در هر مرحله بازه ای با کوچک ترین $f_i$ را که با مجوعه جواب تداخل ندارد را به جواب اضافه می‌کنیم. جواب حاصل تعداد بازه‌های بیشینه را می‌دهد.

در صورت مرتب بودن بازه‌ها به ترتیب انتهای بازه ، پیچیدگی الگوریتم از $O(n)$ است وگر نه به دلیل مرتب سازی پیچیدگی از $O(nlgn)$ می‌شود.

A.c

for(int i = 0 ; i < n ; ++i){
   bool canBeSelected=true;
   for(int j = 0 ; j < i ; ++j)
      if(selected[j] && hasConflict(i,j)){                 // اگر دو بازه تداخل داشته باشند و جی در مجموعه جواب باشد
          canBeSelected=false;
          break;
      }
   if(canBeSelected){
       selected[i]=true;
       ans.push_back(i);
   }
} 

بازه ها دراین کد به صورت $[s_i,f_i)$ فرض شده‌اند.

از آنجا که $f_i$ ها مرتب شده هستند. تنها کافیست تداخل را با آخرین بازه چک کنیم.

‌‌B.c

int lastEnd=-inf;
for(int i = 0 ; i < n ; ++i){
   bool canBeSelected=true;
   if(s[i] < lastEnd)
       canBeSelected=false;   
   if(canBeSelected){
       selected[i]=true;
       lastEnd=f[i];     
       ans.push_back(i);
   }
} 

مثال: صورت مسئله اینجا می‌آید.

• سوال عملی دوره‌ی تابستان ۲۴ [سطح: ساده]

• تابع اویلر - سایت ماکزیمال
• تابع اویلر - ویکی‌پدیا