---
# System prepended metadata

title: '[Task Scheduling of Feasible Assignments with the Adaptive Branch and Bound Algorithm]'
tags: [爵君的碩士論文]

---

[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]![](https://hackmd.io/_uploads/SkkL96UJT.png)

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