植基於頂點對排序的關聯性資料排列法的探討

NHUIR > College of Science and Technology > Department of Information Management > Disserations and Theses > Item 987654321/19525

Please use this identifier to cite or link to this item: http://nhuir.nhu.edu.tw/handle/987654321/19525

Title:	植基於頂點對排序的關聯性資料排列法的探討
Other Titles:	Solving the Directed Linear Arrangement Problem with successive vertex pair ordering technique
Authors:	藍弘文 Lan, Hung-wen
Contributors:	資訊管理學系碩士班蔡德謙 Te-chien Tsai
Keywords:	有向線性排程;貪婪搜尋 Directed linear arrangement;greedy search
Date:	2010
Issue Date:	2015-03-16 11:42:02 (UTC+8)
Abstract:	有向線性排程在於工作排程及無線資料廣播中應用很廣泛且具研究的問題。這著作提出的演算法有不同等級的複雜度來解決此問題，像混合比率切割貪婪排序演算法，其中有數個演算法是根據連續頂點對排序技術及等同邊叢集演算法。混合比率切割貪婪排序演算法是應用雙向貪婪排序以及遞迴二分法，故混合比率切割貪婪排序演算法在全域最佳化中有高效能的區域搜尋。連續頂點對排序技術應用在兩種環境，一種是在於權重邊下的最大延遲縮減技術，另一種是在於優先邊下的搶占邊技術。最大平均延遲縮減比起傳統以切割為基礎的演算法，更可以達成較佳解，如果在權重邊只有優先順序的情形下，搶占邊演算法可以採用且有效。等同邊叢集演算法應用等同邊來取代邊，且使用有向HAC結合頂點成為片斷(segment)。透過實驗來確定不同啟發演算法的效率。　　Directed linear arrangement is a widely adopted and studied problem in task-scheduling and wireless data broadcasting. This work presents algorithms with various levels of complexity to solve this problem, including a hybrid ratio cut greedy sort algorithm, several algorithms based on the successive vertex pair ordering technique, and a equivalent edge clustering algorithm. The hybrid ratio cut greedy sort algorithm, which adopts the two-way greedy sort and recursive bipartition, is a highly efficient local search algorithm with global optimization. The successive vertex pair ordering technique comprises the maximum latency reduction technique for weighted edges, and the preemptive edge technique for priority edge. The algorithm based on maximum average latency reduction could delivers a better solution outcome than a classic cut-based algorithm, and the algorithm based on the priority edge and be adopted when only the edge priority (or preference) is available. The equivalent edge clustering algorithm adopts the equivalent edge technique to replace edges, and adopts the directed HAC process to merge vertices into a segment. Experiments are conducted to check the effectiveness of different heuristic algorithms.
Appears in Collections:	[Department of Information Management] Disserations and Theses

Files in This Item:

File	Description	Size	Format
098NHU05396007-001.pdf		1328Kb	Adobe PDF	260	View/Open
index.html		0Kb	HTML	160	View/Open

Loading...