سؤال ۱

۱۰۰ کار قرار است توسط ۱۰ نفر اجرا شوند. زمان اجرای هر کار از قبل مشخص است. می‌خواهیم کارهایی که هر مجری باید انجام دهد را مشخص کنیم. فرض کنید افراد مجری دقیقاً مثل هم عمل می‌کنند. مثلاً اگر در زمان صفر دو کار به ترتیب با زمان‌های ۱۰ دقیقه و ۲۰ دقیقه را به یک مجری دهیم، او کار اول را دقیقاً در زمان ۱۰ دقیقه و دومی را در زمان ۳۰ دقیقه تمام می‌کند. الگوریتم زیر را برای تخصیص کارها به مجریان در نظر می‌گیریم. فرض می‌کنیم در ابتدا (زمان صفر ) همه‌ی مجریان بی‌کار و آماده‌ی اجرای کارهای تخصیص داده‌شده‌اند.

1) همه‌ی کارها را به ترتیب زمان‌های اجرایشان به‌صورت صعودی مرتب کن و به همین ترتیب مورد بررسی قرار بده،

2) کار موردبررسی را به مجری‌ای بده که کارهایی که قرار است انجام دهد زودتر از بقیه تمام می‌شود.

فرض کنید که مجموع زمان‌های اجرای همه‌ی کارها ۱۰٫۰۰۰ دقیقه و زمان اجرای طولانی‌ترین کار ۲۰۰ دقیقه است. بیش‌ترین زمانی که همه‌ی کارها تمام می‌شود حداکثر جند دقیقه است؟

  1. ۱٫۱۸۰
  2. ۱٫۵۰۰
  3. ۹۸۰
  4. ۲٫۰۰۰
  5. ۱٫۰۰۰

پاسخ

گزینه (۱) درست است.

مجموع کل کارها به غیر از کار ۲۰۰ دقیقه‌ای برابر ۹۸۰۰ می‌باشد که اگر آن را به ۱۰ یعنی تعداد نفرات تقسیم کنیم ۹۸۰ به‌دست می‌آید به این معنا که حداقل یکی از افراد قبل از رسیدن به لحظه ۹۸۰ و یا در همان لحظه کارش تمام می‌شود و در آن لحظه به غیر از کار ۲۰۰ دقیقه‌ای هیچ کار دیگری باقی نمانده است که اگر کار ۲۰۰ دقیقه‌ای را به او بسپاریم قبل از لحظه ۱۱۸۰ کل کار به اتمام خواهد رسید. اگر زمان هر یک از ۹۹ کار دیگر را چنان تنظیم کنیم که به هر یک از ۱۰ نفر دقیقا۹۸۰ دقیقه کار برسد آن‌گاه با اختصاص کار ۲۰۰ دقیقه‌ای به یکی از آن ده نفر٬ دقیقا در لحظه ۱۱۸۰ کل پروژه به اتمام خواهد رسید.