裝箱問(wèn)題和排序問(wèn)題課件

裝箱問(wèn)題和排序問(wèn)題

1裝箱問(wèn)題和排序問(wèn)題本講主要內(nèi)容裝箱問(wèn)題（Bin

Packing）最小完工時(shí)間安排（排序問(wèn)題）（Minimum

Makespan

Scheduling)2本講主要內(nèi)容2BinPacking裝箱問(wèn)題：給定n個(gè)物件，大小為用單位體積的箱子來(lái)裝這些物件，找一個(gè)裝箱方案使得所用的箱子數(shù)目最少？通俗地說(shuō)，把分成最少的組數(shù)，使得每組數(shù)的和不超過(guò)1。在工業(yè)中有許多應(yīng)用，譬如在下料問(wèn)題中，箱子代表標(biāo)準(zhǔn)木料的長(zhǎng)度，而表示實(shí)際問(wèn)題中需要裁截成的木料長(zhǎng)度。當(dāng)然，需要的標(biāo)準(zhǔn)料越少越好。3BinPacking3一個(gè)2倍近似算法4一個(gè)2倍近似算法4證明5證明5一個(gè)不可逼近性結(jié)果6一個(gè)不可逼近性結(jié)果67788NP-難問(wèn)題按照其可逼近性分類沒(méi)有常數(shù)倍近似比：Set-Cover，TSP，MaximumIndependentSet,有常數(shù)倍近似比但不能任意接近1：Vertex-Cover，Bin

Packing,

近似比可以為1+ε（任意逼近1）。Knapsack，Scheduling.9NP-難問(wèn)題按照其可逼近性分類沒(méi)有常數(shù)倍近似比：Set-C多項(xiàng)式時(shí)間近似方案（PolynomialTimeApproximationScheme,PTAS),漸近多項(xiàng)式時(shí)間近似方案10多項(xiàng)式時(shí)間近似方案（PolynomialTimeAppr一個(gè)漸進(jìn)的PTAS11一個(gè)漸進(jìn)的PTAS11限制裝箱問(wèn)題12限制裝箱問(wèn)題12限制裝箱問(wèn)題13限制裝箱問(wèn)題1314141515定理2的證明16定理2的證明161717算法總結(jié)18算法總結(jié)18排序問(wèn)題排序問(wèn)題（MinimumMakespanScheduling）

給定n個(gè)工件的加工時(shí)間以及一個(gè)整數(shù)m，給工件安排一個(gè)在m個(gè)相同機(jī)器上的加工順序，使得最后的完工時(shí)間（makespan）最小。該問(wèn)題是排序問(wèn)題中最簡(jiǎn)單的問(wèn)題。在生產(chǎn)調(diào)度中有廣泛的應(yīng)用。19排序問(wèn)題排序問(wèn)題（MinimumMakespanSchGraham的2-近似算法算法描述（List

Scheduling）

Step

1.將工件任意排序；

Step

2.將工件按照上述順序分配給機(jī)器，將下一個(gè)工件安排給當(dāng)前負(fù)荷最輕（剩余加工時(shí)間最少）的機(jī)器。直到所有工件加工完畢.

20Graham的2-近似算法算法描述（ListSchedu算法分析上述算法的要點(diǎn)是，讓機(jī)器不要閑著，只要有機(jī)器加工完，就把排在最前面尚待加工的工件讓該機(jī)器去做。算法分析的要點(diǎn)是：最小makespan取決于最后一個(gè)工件的完工時(shí)間，在最后一個(gè)活開(kāi)始加工之前，沒(méi)有機(jī)器是空閑的。21算法分析上述算法的要點(diǎn)是，讓機(jī)器不要閑著，只要有機(jī)器加工完2222一個(gè)緊的例子23一個(gè)緊的例子23Lowest

Fit

Decreasing（LFD）算法描述（LFD）

Step

1.將工件按工時(shí)從高到低排列；

Step

2.將工件按照上述順序分配給機(jī)器，將下一個(gè)工件安排給當(dāng)前負(fù)荷最輕（剩余加工時(shí)間最少）的機(jī)器。直到所有工件加工完畢.24LowestFitDecreasing（LFD）算法描述2525262627272828排序問(wèn)題的PTAS排序問(wèn)題與裝箱問(wèn)題有如下緊密聯(lián)系：排序問(wèn)題存在最優(yōu)解t，當(dāng)且僅當(dāng)n個(gè)大小分別為的物件可以裝入m個(gè)容量為t的箱子。因此，可將排序問(wèn)題自轉(zhuǎn)化為裝箱問(wèn)題：令I(lǐng)表示n個(gè)物件大?。涣畋硎灸苎b下n個(gè)物件的容量為t的箱子的最少數(shù)目；則最小排序問(wèn)題轉(zhuǎn)化為：29排序問(wèn)題的PTAS排序問(wèn)題與裝箱問(wèn)題有如下緊密聯(lián)系：29基本思想排序問(wèn)題的最優(yōu)解在[LB，2LB]內(nèi)，利用二分搜索，將問(wèn)題轉(zhuǎn)化為裝箱問(wèn)題這一轉(zhuǎn)化似乎不可行，因?yàn)檠b箱問(wèn)題仍然是NP-難的但是，對(duì)于物件尺寸型號(hào)固定的限制裝箱問(wèn)題，有多項(xiàng)式算法30基本思想排序問(wèn)題的最優(yōu)解在[LB，2LB]內(nèi)，利用二分搜索，不同物件型號(hào)數(shù)目固定的裝箱問(wèn)題31不同物件型號(hào)數(shù)目固定的裝箱問(wèn)題31動(dòng)態(tài)規(guī)劃32動(dòng)態(tài)規(guī)劃32動(dòng)態(tài)規(guī)劃（續(xù)）33動(dòng)態(tài)規(guī)劃（續(xù)）33動(dòng)態(tài)規(guī)劃（續(xù)）34動(dòng)態(tài)規(guī)劃（續(xù)）34把排序問(wèn)題劃歸為限制裝箱問(wèn)題基本思想：如果我們能容忍在計(jì)算最小makespan問(wèn)題的一點(diǎn)小的誤差，則我們可把該問(wèn)題在多項(xiàng)式時(shí)間內(nèi)劃歸為限制裝箱問(wèn)題。主要有兩種類型的誤差：把物件的尺寸做一些調(diào)整，使得不同尺寸的數(shù)目有界。終止二分搜索，保證多項(xiàng)式時(shí)間算法。每種誤差都可以做到任意小，但代價(jià)是計(jì)算時(shí)間的增加。但對(duì)固定的誤差，我們可以得到多項(xiàng)式時(shí)間近似算法。35把排序問(wèn)題劃歸為限制裝箱問(wèn)題基本思想：35箱子容量固定的裝箱算法(核心算法）36箱子容量固定的裝箱算法(核心算法）36核心算法（續(xù)）37核心算法（續(xù)）3