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

زمان‌بندی کارها روی دو ماشین

این مسئله در مورد یافتن یک زمان‌بندی بهینه برای $n$ کار روی دو ماشین است. هر کار ابتدا باید روی ماشین اول پردازش شود و سپس روی ماشین دوم. کار $i$-ام، $a_i$ زمان روی ماشین اول و $b_i$ زمان روی ماشین دوم نیاز دارد. هر ماشین در هر لحظه تنها می‌تواند یک کار را پردازش کند.

می‌خواهیم ترتیب بهینه‌ی کارها را طوری پیدا کنیم که زمان نهایی پردازش، کمترین مقدار ممکن باشد.

راه حلی که در اینجا مورد بحث قرار می‌گیرد، قانون جانسون (به نام S. M. Johnson) نام دارد.

شایان ذکر است که اگر بیش از دو ماشین داشته باشیم، این مسئله NP-کامل می‌شود.

ساختار الگوریتم

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

ترتیب کارها را همان ترتیب ورودی، یعنی $1, 2, \dots, n$ در نظر بگیرید.

$x_i$ را به عنوان زمان بیکاری ماشین دوم درست قبل از پردازش کار $i$ تعریف می‌کنیم. هدف ما کمینه کردن مجموع زمان بیکاری است:

$$F(x) = \sum x_i ~ \rightarrow \min$$

برای کار اول داریم $x_1 = a_1$. برای کار دوم، از آنجا که در زمان $a_1 + a_2$ به ماشین دوم فرستاده می‌شود و ماشین دوم در زمان $x_1 + b_1$ آزاد می‌شود، داریم $x_2 = \max\left((a_1 + a_2) - (x_1 + b_1), 0\right)$. به طور کلی به این معادله می‌رسیم:

$$x_k = \max\left(\sum_{i=1}^k a_i - \sum_{i=1}^{k-1} b_i - \sum_{i=1}^{k-1} x_i, 0 \right)$$

اکنون می‌توانیم مجموع زمان بیکاری $F(x)$ را محاسبه کنیم. ادعا می‌شود که این مقدار به شکل زیر است

$$F(x) = \max_{k=1 \dots n} K_i,$$

که در آن

$$K_i = \sum_{i=1}^k a_i - \sum_{i=1}^{k-1} b_i.$$

این موضوع را می‌توان به سادگی با استقرا اثبات کرد.

اکنون از روش جایگشت استفاده می‌کنیم: دو کار مجاور $j$ و $j+1$ را با هم جابجا کرده و می‌بینیم که این کار چگونه مجموع زمان بیکاری را تغییر می‌دهد.

با توجه به شکل عبارت $K_i$، واضح است که تنها $K_j$ و $K_{j+1}$ تغییر می‌کنند. مقادیر جدید آن‌ها را با $K_j'$ و $K_{j+1}'$ نشان می‌دهیم.

اگر این جابجایی کارهای $j$ و $j+1$ مجموع زمان بیکاری را افزایش داده باشد، باید داشته باشیم:

$$\max(K_j, K_{j+1}) \le \max(K_j', K_{j+1}')$$

(جابجا کردن دو کار ممکن است هیچ تأثیری نداشته باشد. شرط بالا تنها یک شرط کافی است، نه یک شرط لازم.)

پس از حذف $\sum_{i=1}^{j-1} a_i - \sum_{i=1}^{j-1} b_i$ از هر دو طرف نامساوی، به دست می‌آوریم:

$$\max(-a_{j+1}, -b_j) \le \max(-b_{j+1}, -a_j)$$

و پس از حذف علامت‌های منفی:

$$\min(a_j, b_{j+1}) \le \min(b_j, a_{j+1})$$

بنابراین، یک مقایسه‌گر به دست آوردیم: با مرتب‌سازی کارها بر اساس آن، ترتیب بهینه‌ی کارها را به دست می‌آوریم، که در آن هیچ دو کار مجاوری را نمی‌توان با جابجایی، زمان نهایی را بهبود بخشید.

با این حال، اگر از زاویه‌ای دیگر به این مقایسه‌گر نگاه کنید، می‌توانید مرتب‌سازی را ساده‌تر کنید. این مقایسه‌گر را می‌توان به این صورت تفسیر کرد: اگر چهار زمان $(a_j, a_{j+1}, b_j, b_{j+1})$ را داشته باشیم، و کمترینِ آن‌ها زمانی مربوط به ماشین اول باشد، آنگاه کار مربوطه باید زودتر انجام شود. اگر کمترین زمان مربوط به ماشین دوم باشد، آنگاه آن کار باید دیرتر انجام شود. بنابراین، می‌توانیم کارها را بر اساس $\min(a_i, b_i)$ مرتب کنیم، و اگر زمان پردازش کار فعلی روی ماشین اول کمتر از زمان پردازش آن روی ماشین دوم باشد، آن کار باید قبل از تمام کارهای باقیمانده انجام شود، و در غیر این صورت، بعد از تمام کارهای باقیمانده.

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

پیاده‌سازی

در اینجا، نوع دوم الگوریتم توصیف‌شده را پیاده‌سازی می‌کنیم.

struct Job {
    int a, b, idx;

    bool operator<(Job o) const {
        return min(a, b) < min(o.a, o.b);
    }
};

vector<Job> johnsons_rule(vector<Job> jobs) {
    sort(jobs.begin(), jobs.end());
    vector<Job> a, b;
    for (Job j : jobs) {
        if (j.a < j.b)
            a.push_back(j);
        else
            b.push_back(j);
    }
    a.insert(a.end(), b.rbegin(), b.rend());
    return a;
}

pair<int, int> finish_times(vector<Job> const& jobs) {
    int t1 = 0, t2 = 0;
    for (Job j : jobs) {
        t1 += j.a;
        t2 = max(t2, t1) + j.b;
    }
    return make_pair(t1, t2);
}

تمام اطلاعات مربوط به هر کار در یک struct ذخیره می‌شود. تابع اول تمام کارها را مرتب کرده و زمان‌بندی بهینه را محاسبه می‌کند. تابع دوم زمان‌های پایان کار هر دو ماشین را با توجه به یک زمان‌بندی مشخص محاسبه می‌کند.