[Task Scheduling of Feasible Assignments with the Adaptive Branch and Bound Algorithm]

題目：
針對異構處理器上將所有任務做排程，要來獲得最小的 makespan(完成時間)。 任務在不同的處理器上有不同的執行時間。若相依的任務放在不同的處理器上，則需要加上額外的溝通時間。

想法：
我們原先設計是希望將不可能的路徑都剔除掉，然後每一條可行路線都走過一遍，進而找到唯一的最佳解。但是當任務的數量一多，時間上則無法管控。因此我們考慮層與層之間溝通時間的變異數，使用一個α來控制變因，縮短整體執行時間。

步驟：

1. 設計出一條預估公式來預估當前尚未執行過任務的node。
2. 在 dfs 架構下，使用遞迴和 branch and bound，從最小預估值往下延伸，或是將路線設棄掉。

> [example：six tasks on two different processors]

結論：
當任務數量少，我們可以找出最佳解。
當任務數量多，可行解可能呈現指數的成長，我們雖然不一定能夠找出最佳解，但我們所找到的makespan其中的兩成，能比heuristic求出的makesapn縮短10-20%左右。