مسابقه شماره ۲۴۷
سوال
۱۰۰ کار قرار است توسط ۱۰ نفر اجرا شود.
زمان اجرای هر کار از قبل مشخص است.
می‌خواهیم کارهایی که هر مجری باید انجام دهد
را مشخص کنیم. فرض کنید افراد مجری
دقیقا مثل هم عمل می‌کنند. مثلا اگر در زمان
صفر دو کار به ترتیب با زمان‌های ۱۰ دقیقه و
۲۰ دقیقه را به یک مجری دهیم ٫ او کار اول را دقیقا در زمان ۱۰ دقیقه و دومی را در زمان
۳۰ دقیقه تمام می‌کند. الگوریتم زیر را برای تخصیص کارها به مجریان در نظر
می‌گیریم. فرض می‌کنیم در ابتدا ( زمان صفر ) همه مجریان بی کار و آماده اجرای
کارها تخصیص داده شده‌اند.
الف) همه کارها را به ترتیب زمان‌های اجرایشان به صورت صعودی مرتب کن و به همین
ترتیب مورد بررسی قرار بده.
ب) کا مورد بررسی را به مجری ای بده که کارهایی که قرار است انجام دهد زودتر از بقیه
تمام می‌شود.
فرض کنید که مجموع زمان‌های اجرای همه کارها ۱۰۰۰۰ دقیقه و زمان اجرای طولانی ترین
کار ۲۰۰ دقیقه است. بیشترین زمانی که همه کارها تمام می‌شود حداکثر چند دقیقه
است ؟
پاسخ
مجموع کل کارها به غیز از کار ۲۰۰ دقیقه‌ای برابر ۹۸۰۰ می‌باشد که اگر آن را به ۱۰ یعنی
تعداد نفرات تقسیم کنیم ۹۸۰ به دست می‌آید به این معنا که حداقل یکی از افراد قبل از
رسیدن به لحظه ۹۸۰ و یا در همان لحظه کارش تمام می‌شود و در آن لحظه به غیر از کار
۲۰۰ دقیقه‌ای هیچ کار دیگری باقی نمانده است که اگر کار ۲۰۰ دقیقه‌ای را به او بسپاریم
قیل از لحظه ۱۱۸۰ کل کار به اتمام خواهد رسید. اگر زمان هر یک از ۹۹ کار دیگر را چنان
تنظیم کنید که به هر یک از ۱۰ نفر دقیقا ۹۸۰ دقیقه کار برسد آنگاه با اختصاص کار ۲۰۰
دقیقه‌ای به یکی از آن ده نفر ٫ دقیقا در لحظه ۱۱۸۰ کل پروژه به اتمام خواهد رسید.