مساله تعیین توالی کارها (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

// Program to find the maximum profit job sequence from a given array 
// of jobs with deadlines and profits 
#include<iostream> 
#include<algorithm> 
using namespace std; 
  
// A structure to represent a job 
struct Job 
{ 
   char id;      // Job Id 
   int dead;    // Deadline of job 
   int profit;  // Profit if job is over before or on deadline 
}; 
  
// This function is used for sorting all jobs according to profit 
bool comparison(Job a, Job b) 
{ 
     return (a.profit > b.profit); 
} 
  
// Returns minimum number of platforms reqquired 
void printJobScheduling(Job arr[], int n) 
{ 
    // Sort all jobs according to decreasing order of prfit 
    sort(arr, arr+n, comparison); 
  
    int result[n]; // To store result (Sequence of jobs) 
    bool slot[n];  // To keep track of free time slots 
  
    // Initialize all slots to be free 
    for (int i=0; i<n; i++) 
        slot[i] = false; 
  
    // Iterate through all given jobs 
    for (int i=0; i<n; i++) 
    { 
       // Find a free slot for this job (Note that we start 
       // from the last possible slot) 
       for (int j=min(n, arr[i].dead)-1; j>=0; j--) 
       { 
          // Free slot found 
          if (slot[j]==false) 
          { 
             result[j] = i;  // Add this job to result 
             slot[j] = true; // Make this slot occupied 
             break; 
          } 
       } 
    } 
  
    // Print the result 
    for (int i=0; i<n; i++) 
       if (slot[i]) 
         cout << arr[result[i]].id << " "; 
} 
  
// Driver program to test methods 
int main() 
{ 
    Job arr[] = { {'a', 2, 100}, {'b', 1, 19}, {'c', 2, 27}, 
                   {'d', 1, 25}, {'e', 3, 15}}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    cout << "Following is maximum profit sequence of jobsn"; 
    printJobScheduling(arr, n); 
    return 0; 
} 

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

# Program to find the maximum profit  
# job sequence from a given array 
# of jobs with deadlines and profits 
  
# function to schedule the jobs take 2  
# arguments array and no of jobs to schedule 
def printJobScheduling(arr, t): 
  
    # length of array 
    n = len(arr) 
  
    # Sort all jobs according to  
    # decreasing order of profit 
    for i in range(n): 
        for j in range(n - 1 - i): 
            if arr[j][2] < arr[j + 1][2]: 
                arr[j], arr[j + 1] = arr[j + 1], arr[j] 
  
    # To keep track of free time slots 
    result = [False] * t 
  
    # To store result (Sequence of jobs) 
    job = ['-1'] * t 
  
    # Iterate through all given jobs 
    for i in range(len(arr)): 
  
        # Find a free slot for this job  
        # (Note that we start from the  
        # last possible slot) 
        for j in range(min(t - 1, arr[i][1] - 1), -1, -1): 
              
            # Free slot found 
            if result[j] is False: 
                result[j] = True
                job[j] = arr[i][0] 
                break
  
    # print the sequence 
    print(job) 
  
# Driver COde 
arr = [['a', 2, 100], # Job Array 
       ['b', 1, 19], 
       ['c', 2, 27], 
       ['d', 1, 25], 
       ['e', 3, 15]] 
  
  
print("Following is maximum profit sequence of jobs") 
printJobScheduling(arr, 3) # Function Call 
  
# This code is contributed  
# by Anubhav Raj Singh

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

Following is maximum profit sequence of jobs
c a e

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

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

^^

اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.

«الهام حصارکی»، فارغ‌التحصیل مقطع کارشناسی ارشد مهندسی فناوری اطلاعات، گرایش سیستم‌های اطلاعات مدیریت است. او در زمینه هوش مصنوعی و داده‌کاوی، به ویژه تحلیل شبکه‌های اجتماعی، فعالیت می‌کند.

بر اساس رای 2 نفر

آیا این مطلب برای شما مفید بود؟

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *