國(guó)家集訓(xùn)隊(duì)作業(yè)計(jì)劃安排解題報(bào)告

1、計(jì)劃安排解題摘要問(wèn)題描述Dramatic 的工廠最近生意紅火！有 N 位客戶希望工廠為他們加工產(chǎn)品。每位客戶都提供了需要加工的產(chǎn)品的類型，產(chǎn)品到達(dá)工廠的時(shí)間 r 和最遲完成加工的時(shí)間 d。Dramatic 根據(jù)需要加工的產(chǎn)品類型預(yù)計(jì)了每個(gè)產(chǎn)品加工所需的時(shí)間 t。工廠里的生產(chǎn)車間一共有 M 臺(tái)機(jī)器。每個(gè)產(chǎn)品在每臺(tái)機(jī)器上都可以加工，但是，一臺(tái)機(jī)器在任何時(shí)候最多只能加工一件產(chǎn)品，而一件產(chǎn)品在任何時(shí)候也最多只能被一臺(tái)機(jī)器加工。同時(shí)，可以在某臺(tái)機(jī)器正在加工時(shí)將工作打斷，換另一個(gè)產(chǎn)品加工。Dramatic 希望你幫他計(jì)算一下，能否找到一個(gè)方案，使得所有的產(chǎn)品都在規(guī)定的時(shí)間內(nèi)完成加工？數(shù)據(jù)規(guī)模：1N100，

2、1M10，1Q10分析這是我的一道題目，自我感覺(jué)還不錯(cuò)。顯然，這是一道有關(guān)工程安排的題目。這類題目通常的思路是貪心或者動(dòng)態(tài)規(guī)劃。而在這道題目中，這兩種常用的方法卻很難有用武之地，使有些不知所措。注意到題目中的一個(gè)重要條件：可以在某臺(tái)機(jī)器正在加工時(shí)將工作打斷，換另一個(gè)產(chǎn)品加工。也就是說(shuō)：一個(gè)工作可以分多次完成！這提醒，可以考慮從網(wǎng)絡(luò)流的方向上突破。首先，因?yàn)槊總€(gè)工作都有一個(gè)到達(dá)時(shí)間和一個(gè)最遲完成時(shí)間，所以，N 個(gè)工作共有 2N 個(gè)時(shí)間點(diǎn)。這些時(shí)間但離散化，可以得到一些時(shí)間段。因?yàn)樗泄ぷ鞯牡竭_(dá)時(shí)間和最遲完成時(shí)間都被考慮進(jìn)來(lái)了，因此，在一個(gè)時(shí)間段內(nèi)的任何時(shí)刻，所有可以進(jìn)行的工作的集合是相同的！基于

3、這點(diǎn)，網(wǎng)絡(luò)流模型：構(gòu)造如下的首先設(shè)兩個(gè)點(diǎn) s 和 t，表示源點(diǎn)和匯點(diǎn)；每個(gè)工作對(duì)應(yīng)一個(gè)點(diǎn)wi，每個(gè)時(shí)間段對(duì)應(yīng)一個(gè)點(diǎn) vi。接著，從 s 向每個(gè) vi 連一條邊，容量為第 i 個(gè)時(shí)間段算法網(wǎng)絡(luò)流時(shí)間復(fù)雜度O(n5)空間復(fù)雜度O(n2)的長(zhǎng)度乘以機(jī)器的個(gè)數(shù) M，表示所有 M 臺(tái)機(jī)器在時(shí)間段 vi 內(nèi)一共可以提供的加從每個(gè) wi 向 t 連邊，容量為第 i 個(gè)工作所需的時(shí)間 ti，表示工時(shí)間。然后，一共要向第 i 個(gè)工作提供 ti 加工時(shí)間。接著，如果 wj 以在 vi 內(nèi)被加工，就從 vi 向 wj 連邊，容量為 vi 的長(zhǎng)度，表示 wj 在 vi 內(nèi)最多可以被加工的時(shí)間。對(duì)這個(gè)網(wǎng)絡(luò)求最大流，如果

4、每條 wi 至 t 的弧均滿載，則該問(wèn)題有解，否則無(wú)解。通過(guò)一個(gè)例子來(lái)看一下網(wǎng)絡(luò)到底是怎樣建立的。假設(shè)有一臺(tái)機(jī)器，三個(gè)任務(wù)。第一個(gè)任務(wù)所需的時(shí)間為 2 可以加工的時(shí)間從 2 至 8。第二任務(wù)所需的時(shí)間為 2，從 3 至 4；最后一個(gè)任務(wù)所需的時(shí)間為 3，從 5 至 7。那么，所有的時(shí)間段為2，2，3，4，5，7，8，8，v1建立如下的網(wǎng)絡(luò)：w1w21v2122st2223 v333 w331v41上界這個(gè)算法的正確性比較顯然，這里不做分析了。下面來(lái)看一下這個(gè)算法的時(shí)間復(fù)雜度。因?yàn)樽疃嘤?2N 個(gè)時(shí)間點(diǎn)，所以最多有 2N-1 個(gè)時(shí)間段，因此最多有 3N+1 個(gè)點(diǎn)。而邊數(shù)不會(huì)超過(guò) N2，如果使用 O(NM2)的最大流算法，則這整個(gè)算法的復(fù)雜度不超過(guò) O(N5)。但由于實(shí)際中邊數(shù)遠(yuǎn)遠(yuǎn)達(dá)不到 O(N2)，因此這個(gè)算法還是很快的?？偨Y(jié)在解決這道問(wèn)題時(shí)，沒(méi)有使用解決這類問(wèn)題的，而是獨(dú)辟蹊徑，巧妙地構(gòu)造了網(wǎng)絡(luò)流模型，從而順利解決了這