The Design of Approximation Algorithms

2.1 Scheduling jobs with deadlines on a single machine

首先要了解延遲Lj=Cj-dj和最大延遲Lmax.

對(duì)于有到達(dá)時(shí)間rj的排序問(wèn)題，設(shè)計(jì)近似比時(shí)，一般會(huì)放到最大的（接受）工件，從r_max開(kāi)始排序無(wú)間斷加工。

而對(duì)于帶有交貨期（due date）的排序問(wèn)題，設(shè)計(jì)近似比時(shí)，比較常用的就是EDD規(guī)則（最早交貨期規(guī)則，the earliest due date rule）。

本節(jié)2-近似算法的核心是，從最大的到期日期開(kāi)始加工工件，因此之后機(jī)器無(wú)空閑，再減去最小的交貨期。即假設(shè)將第一個(gè)加工工件到期日期放縮到最大，此后機(jī)器一直加工到最后一個(gè)工件，再將最后一個(gè)加工工件交貨期放縮到最小。

該章節(jié)翻譯如下，如有錯(cuò)誤或其他問(wèn)題，麻煩大家指出，??的個(gè)人分享，以后會(huì)持續(xù)更新，歡迎大家積極討論。