Нэг машин дээр ажил хуваарилах¶

Энэ бодлого нь нэг машин дээр $n$ ажлын оновчтой хуваарийг олох тухай юм; $i$ ажлыг $t_i$ хугацаанд боловсруулж болох боловч ажлыг боловсруулахаас өмнө $t$ секунд хүлээсний төлөө $f_i(t)$ торгууль төлөх ёстой.

Тиймээс бодлого нь нийт торгууль хамгийн бага байхаар ажлуудын сэлгэмэлийг олохыг шаардана. Ажлуудын сэлгэмэлийг $\pi$ гэж тэмдэглэвэл ($\pi_1$ нь эхэлж боловсруулагдах ажил, $\pi_2$ нь хоёр дахь гэх мэт), нийт торгууль нь:

$$F(\pi) = f_{\pi_1}(0) + f_{\pi_2}(t_{\pi_1}) + f_{\pi_3}(t_{\pi_1} + t_{\pi_2}) + \dots + f_{\pi_n}\left(\sum_{i=1}^{n-1} t_{\pi_i}\right)$$

Тусгай тохиолдлуудын шийдэл¶

Шугаман торгуулийн функц¶

Эхлээд бид бүх торгуулийн функц $f_i(t)$ шугаман буюу $f_i(t) = c_i \cdot t$ хэлбэртэй (энд $c_i$ нь сөрөг биш тоо) тохиолдолд бодлогыг бодно. Эдгээр функц тогтмол гишүүнгүй болохыг анхаарна уу. Эс бөгөөс бид бүх тогтмол гишүүнийг нэмж, тэдгээргүйгээр бодлогыг бодож болно.

Ямар нэг $\pi$ сэлгэмэлийг тогтоож, $i = 1 \dots n-1$ индексийг авъя. $\pi'$ сэлгэмэл нь $\pi$ сэлгэмэлд $i$ ба $i+1$ элементүүдийг сольсонтой тэнцүү байг. Торгууль хэр их өөрчлөгдсөнийг харцгаая.

$$F(\pi') - F(\pi) =$$

Өөрчлөлт зөвхөн $i$ дугаар ба $(i+1)$ дугаар нэмэгдэхүүнд гарахыг харахад амархан:

$$\begin{align} &= c_{\pi_i'} \cdot \sum_{k = 1}^{i-1} t_{\pi_k'} + c_{\pi_{i+1}'} \cdot \sum_{k = 1}^i t_{\pi_k'} - c_{\pi_i} \cdot \sum_{k = 1}^{i-1} t_{\pi_k} - c_{\pi_{i+1}} \cdot \sum_{k = 1}^i t_{\pi_k} \\ &= c_{\pi_{i+1}} \cdot \sum_{k = 1}^{i-1} t_{\pi_k'} + c_{\pi_i} \cdot \sum_{k = 1}^i t_{\pi_k'} - c_{\pi_i} \cdot \sum_{k = 1}^{i-1} t_{\pi_k} - c_{\pi_{i+1}} \cdot \sum_{k = 1}^i t_{\pi_k} \\ &= c_{\pi_i} \cdot t_{\pi_{i+1}} - c_{\pi_{i+1}} \cdot t_{\pi_i} \end{align}$$

Хэрэв $\pi$ хуваарь оновчтой бол түүнд гарах аливаа өөрчлөлт торгуулийг нэмэгдүүлэхэд (эсвэл ижил торгуульд) хүргэнэ гэдгийг харахад амархан тул оновчтой хуваарийн хувьд бид дараах нөхцөлийг бичиж болно:

$$c_{\pi_{i}} \cdot t_{\pi_{i+1}} - c_{\pi_{i+1}} \cdot t_{\pi_i} \ge 0 \quad \forall i = 1 \dots n-1$$

Эрэмбэлэн байрлуулсны дараа бид:

$$\frac{c_{\pi_i}}{t_{\pi_i}} \ge \frac{c_{\pi_{i+1}}}{t_{\pi_{i+1}}} \quad \forall i = 1 \dots n-1$$

Ингэснээр бид ажлуудыг $\frac{c_i}{t_i}$ бутархайгаар өсөхгүй дарааллаар зүгээр л эрэмбэлэх замаар оновчтой хуваарь-ийг олно.

Бид энэ алгоритмыг сэлгэмэлийн арга хэмээх аргаар байгуулсныг тэмдэглэх нь зүйтэй: бид зэргэлдээ хоёр элементийг солихыг оролдож, торгууль хэр их өөрчлөгдсөнийг тооцоолоод, дараа нь оновчтой аргыг олох алгоритмыг гаргаж авсан.

Экспоненциал торгуулийн функц¶

Торгуулийн функц дараах байдалтай байг:

$$f_i(t) = c_i \cdot e^{\alpha \cdot t},$$

энд бүх $c_i$ тоо сөрөг биш ба $\alpha$ тогтмол эерэг.

Сэлгэмэлийн аргыг хэрэглэснээр ажлуудыг дараах утгаар өсөхгүй дарааллаар эрэмбэлэх ёстойг тодорхойлоход амархан:

$$v_i = \frac{1 - e^{\alpha \cdot t_i}}{c_i}$$

Ижил монотон торгуулийн функц¶

Энэ тохиолдолд бид бүх $f_i(t)$ тэнцүү бөгөөд энэ функц монотон өсөх тохиолдлыг авч үзнэ.

Энэ тохиолдолд оновчтой сэлгэмэл нь ажлуудыг $t_i$ боловсруулах хугацаагаар буурахгүй дарааллаар байрлуулах явдал гэдэг нь ойлгомжтой.

Лившиц-Кладовын теорем¶

Лившиц-Кладовын теорем нь сэлгэмэлийн арга зөвхөн дээр дурдсан гурван тохиолдолд хэрэглэгдэхийг тогтоодог, тухайлбал:

Шугаман тохиолдол: $f_i(t) = c_i(t) + d_i$, энд $c_i$ нь сөрөг биш тогтмолууд,
Экспоненциал тохиолдол: $f_i(t) = c_i \cdot e_{\alpha \cdot t} + d_i$, энд $c_i$ ба $\alpha$ нь эерэг тогтмолууд,
Ижил тохиолдол: $f_i(t) = \phi(t)$, энд $\phi$ нь монотон өсөх функц.

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

Теоремыг торгуулийн функцүүд хангалттай гөлгөр (гуравдугаар уламжлал оршин байдаг) гэсэн таамаглалын дор баталдаг.

Гурван тохиолдол бүрд бид сэлгэмэлийн аргыг хэрэглэх ба үүгээр дамжуулан хайж буй оновчтой хуваарийг эрэмбэлэх замаар, иймээс $O(n \log n)$ хугацаанд олж болно.