查詢結果分析
相關文獻
- A Network Flow Approach to Solving Weighted Processor-Optimal Allocation Problems
- 網路需求與流量分析(1)--網路量身訂做符合使用者需求
- 近洋貨櫃調度模式之研究
- 對偶陡升法求解多貨品有界網路流量問題
- 智慧型內容遞送:網頁交換技術
- 電腦教室軟硬體設施之管理以國立臺北護理學院為例
- A Computational Comparison of Some Bicriterion Shortest Path Algorithms
- 臺灣地區菸葉產業最適網路流量之研究
- 閘道器採購須知--解析高速內容檢查方案
- 在編碼中看見安全--L7負載平衡器新裝上陣
頁籤選單縮合
| 題 名 | A Network Flow Approach to Solving Weighted Processor-Optimal Allocation Problems=利用網路流量方法解加權最佳處理器指派問題 |
|---|---|
| 作 者 | 蔡中川; 何業勤; | 書刊名 | Proceedings of the National Science Council : Part A, Physical Science and Engineering |
| 卷 期 | 23:3 1999.05[民88.05] |
| 頁 次 | 頁396-401 |
| 分類號 | 448.6 |
| 關鍵詞 | 網路流量; 最佳處理器; 最小權數值; Data-flow graphs; Interprocessor communication; Minimum-cost network flow; Processor allocation; |
| 語 文 | 英文(English) |
| 中文摘要 | 給定一組具有執行時間區間之工作{[a□,z□]|I=1,…,n},其中a□<z□,最佳處理 器安排問題為,如何以最少之處理器執行這些工作,使得任意兩指派至同一處理器之工作執 行區間[a□ , z□]和[a□ , z□]沒有交集,亦即z□≦a□或z□≦a□;而加權最佳處理器安排 問題為,如何得到最小權數值之最佳處理器安排問題。過去曾有許多研究探討相關之指派, 這些研究結果有的是須要指數函數之計算複雜度,有的是沒有考量權數,有的是無法找到最 小權數之指派。本文中,我們利用最小成本流量技術,設計一個多項式計算複雜度之演算法, 以得到最小權數值之最佳處理器指派。 |
| 英文摘要 | Given a set of operations specified by their execution time intervals {[a□,z□]|I=1,…,n}, where a□<z□, a processor-optimal allocation (POA) problem is to allocate the minimum number of processors to execute these operations, where any two operations [a□, z□] and [a□ , z□] executed by a processor have the property of either z□≦a□ or z□≦a□. A weighted version of the POA problem is to find a processor-optimal allocation with a minimal value of a linearly weighted function. There are many existing algorithms for solving these allocation problems. However, these algorithms are having time complexity of an exponential function, solving non-weighted POA problem, or achieving only locally optimal solutions. On the base of the minimum-cost network flow model, this paper proposes an algorithm to optimally solve the weighted POA problem in polynomial time. |
本系統中英文摘要資訊取自各篇刊載內容。