حل مساله تعیین توالی کارها – به زبان ساده

مساله تعیین توالی کارها (Job Sequencing Problem) از جمله «مسائل بهینه‌سازی» (Optimization Problems) است. در این مطلب، روش حل مسأله تعیین توالی کارها مورد بررسی قرار می‌گیرد و سپس، روش ارائه شده، در زبان‌های برنامه‌نویسی «سی‌پلاس‌پلاس» (++C) و «پایتون ۳» (Python 3) پیاده‌سازی می‌شود.

فرض می‌شود که یک آرایه از کارها داده شده و هر کاری دارای یک مهلت نهایی انجام و یک سود انجام در صورت نهایی شدن پیش از مهلت نهایی است. هدف پاسخ‌گویی به این پرسش است که چگونه می‌توان سود را در صورتی بیشینه کرد که در هر زمان تنها یک کار قابل انجام باشد.

مثال:

Input: Four Jobs with following 
deadlines and profits
JobID  Deadline  Profit
  a      4        20   
  b      1        10
  c      1        40  
  d      1        30
Output: Following is maximum 
profit sequence of jobs
        c, a   


Input:  Five Jobs with following
deadlines and profits
JobID   Deadline  Profit
  a       2        100
  b       1        19
  c       2        27
  d       1        25
  e       3        15
Output: Following is maximum 
profit sequence of jobs
        c, a, e

یک راهکار ساده آن است که همه زیرمجموعه‌های مجموعه کارهای داده شده تولید و امکان‌پذیری انجام کارهای داخل هر زیرمجموعه یک به یک بررسی شود. همچنین، مجموعه دارای بیشینه سود در میان کلیه مجموعه‌ها انتخاب شود. پیچیدگی زمانی این روش از درجه نمایی است. مساله بیان شده، از جمله مسائل الگوریتم «حریصانه» (Greedy) استاندارد است. راه حل حریصانه این مساله، در ادامه بیان شده است.

1. همه کارها را به ترتیب نزولی سودها مرتب کن.
2. دنباله حاصل شده را به عنوان اولین کار در کارهای مرتب شده مقداردهی اولیه کن.
3. اقدامات زیر را برای n-1 کار باقیمانده انجام بده
   • اگر بتوان بدون از دست دادن مهلت نهایی انجام، کار کنونی را در توالی نتایج کنونی برازش کرد، کار کنونی را به نتایج اضافه کن. در غیر این صورت، از کار کنونی صرف نظر کن.

فیلم آموزش روش حریصانه در طراحی الگوریتم - مرور تست کنکور ارشد (رایگان) در فرادرس

کلیک کنید

در ادامه، پیاده‌سازی الگوریتم بالا ارائه شده است.

الگوریتم حریصانه حل مساله تعیین توالی کارها در ++C

الگوریتم حریصانه حل مساله تعیین توالی کارها در پایتون ۳

خروجی قطعه کدهای بالا، به صورت زیر است.

Following is maximum profit sequence of jobs
c a e

پیچیدگی زمانی راهکار بالا از درجه (O(n² است. این روش را می‌توان با استفاده از ساختار داده مجموعه‌های مجزا بهبود بخشید.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌ نویسی
• آموزش ساختمان داده‌ها
• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• رنگ‌آمیزی گراف به روش حریصانه — به زبان ساده
• الگوریتم دایجسترا (Dijkstra) — از صفر تا صد
• الگوریتم پریم — به زبان ساده
• الگوریتم کروسکال چیست؟ – توضیح کراسکال به زبان ساده با مثال و کد

^^