國家集訓隊作業(yè)計劃安排解題報告

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

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

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

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