پرش به محتویات

زمان‌بندی بهینه‌ی کارها با مهلت و مدت زمان معین

فرض کنید مجموعه‌ای از کارها را در اختیار داریم و از مهلت (deadline) و مدت زمان انجام هر کار مطلع هستیم. اجرای یک کار نمی‌تواند قبل از پایانش متوقف شود. هدف، ایجاد یک زمان‌بندی است که بیشترین تعداد کارها را به انجام برساند.

روش حل

الگوریتم حل این مسئله حریصانه است. بیایید تمام کارها را بر اساس مهلتشان مرتب کرده و به ترتیب نزولی بررسی کنیم. همچنین، یک صف $q$ ایجاد می‌کنیم که کارها را به تدریج در آن قرار داده و کاری را که کمترین زمان اجرا را دارد از آن خارج می‌کنیم (برای مثال، می‌توانیم از set یا priority_queue استفاده کنیم). در ابتدا، $q$ خالی است.

فرض کنید در حال بررسی کار $i$-ام هستیم. ابتدا، آن را در $q$ قرار می‌دهیم. بازه زمانی بین مهلت کار $i$-ام و مهلت کار $i-1$-ام را در نظر بگیرید. این یک بازه با طول $T$ است. ما کارها را از $q$ (به ترتیب صعودی مدت زمان باقی‌مانده) خارج کرده و آن‌ها را اجرا می‌کنیم تا زمانی که کل بازه $T$ پر شود. نکته مهم: اگر در هر لحظه، کار خارج‌شده فقط بتواند تا حدی اجرا شود تا بازه $T$ پر شود، آنگاه این کار را تا جای ممکن، یعنی به اندازه زمان $T$، اجرا کرده و بخش باقی‌مانده از کار را دوباره به $q$ برمی‌گردانیم.

پس از اتمام الگوریتم، ما به یک راه‌حل بهینه (یا حداقل یکی از چندین راه‌حل ممکن) دست پیدا می‌کنیم. زمان اجرای الگوریتم $O(n \log n)$ است.

پیاده‌سازی

تابع زیر یک vector از کارها (شامل مهلت، مدت زمان و شماره‌ی کار) را دریافت کرده و یک vector حاوی شماره‌ی تمام کارهای استفاده‌شده در زمان‌بندی بهینه را محاسبه می‌کند. توجه داشته باشید که اگر می‌خواهید برنامه را به صراحت بنویسید، همچنان باید این کارها را بر اساس مهلتشان مرتب کنید.

```cpp file=schedule_deadline_duration struct Job { int deadline, duration, idx;

bool operator<(Job o) const {
    return deadline < o.deadline;
}

};

vector compute_schedule(vector jobs) { sort(jobs.begin(), jobs.end());

set<pair<int,int>> s;
vector<int> schedule;
for (int i = jobs.size()-1; i >= 0; i--) {
    int t = jobs[i].deadline - (i ? jobs[i-1].deadline : 0);
    s.insert(make_pair(jobs[i].duration, jobs[i].idx));
    while (t && !s.empty()) {
        auto it = s.begin();
        if (it->first <= t) {
            t -= it->first;
            schedule.push_back(it->second);
        } else {
            s.insert(make_pair(it->first - t, it->second));
            t = 0;
        }
        s.erase(it);
    }
}
return schedule;

} ```