Хоёр машин дээр ажил хуваарилах¶

Энэ бодлого нь хоёр машин дээр $n$ ажлын оновчтой хуваарийг олох тухай юм. Ажил бүрийг эхлээд эхний машин дээр, дараа нь хоёр дахь машин дээр боловсруулах ёстой. $i$ дугаар ажил эхний машин дээр $a_i$ хугацаа, хоёр дахь машин дээр $b_i$ хугацаа авна. Машин бүр нэг зэрэг зөвхөн нэг ажил боловсруулж чадна.

Бид эцсийн боловсруулах хугацаа хамгийн бага байхаар ажлуудын оновчтой дарааллыг олохыг хүсэж байна.

Энд авч үзэж буй энэ шийдлийг Жонсоны дүрэм (С. М. Жонсоны нэрээр) гэж нэрлэдэг.

Хоёроос олон машинтай бол бодлого NP-бүрэн болдгийг тэмдэглэх нь зүйтэй.

Алгоритмыг байгуулах¶

Эхлээд эхний ба хоёр дахь машины ажлуудын дараалал давхцах ёстой гэж үзэж болохыг тэмдэглэе. Үнэн хэрэгтээ хоёр дахь машины ажлууд эхний машин дээр боловсруулагдсаны дараа бэлэн болдог тул хэрэв хоёр дахь машинд хэд хэдэн ажил бэлэн байвал боловсруулах хугацаа нь дарааллаас нь үл хамааран тэдгээрийн $b_i$-ийн нийлбэртэй тэнцүү байна. Тиймээс ажлуудыг эхний машинд илгээсэнтэй ижил дарааллаар хоёр дахь машинд илгээх нь л ашигтай.

Ажлуудын оруулах дараалал $1, 2, \dots, n$-тэй давхцах дарааллыг авч үзье.

$i$-г боловсруулахаас яг өмнөх хоёр дахь машины сул зогсолтын хугацаа-г $x_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)$ time complexity-тэй болно.

Implementation¶

Here we implement the second variation of the described algorithm.

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);
}

All the information about each job is store in struct. The first function sorts all jobs and computes the optimal schedule. The second function computes the finish times of both machines given a schedule.