查詢結果分析
相關文獻
- 計畫網路時程成本問題之切割解法
- 水庫標的線性規劃問題之網路切割法簡介
- The Partition in Linear Space for Predicting the Secondary Structure of Proteins
- A Study on the Software Project Scheduling Under Inflation Conditions Using Simplex Method
- Modified Hamming Neural Network and Its Character Recognition System
- Increasing the Minimum Value of a Linear Program--A Parametric Analysis
- 多層級交換式區域網路
- 用水網路最適化設計
- 線性規劃理論在網路決策計算應用之探討
- 跨越官僚的專業線:網路力量與救災行動
頁籤選單縮合
題 名 | 計畫網路時程成本問題之切割解法 |
---|---|
作 者 | 劉佳明; | 書刊名 | 農業工程學報 |
卷 期 | 41:2 1995.06[民84.06] |
頁 次 | 頁1-10 |
分類號 | 440.8 |
關鍵詞 | 時程; 計畫時程成本低換; 簡形法; 切割演算法; 網路; 線性規劃; Schedule; Network; Project/time cost trade-off; Linear program; Simplex; Cut algorithm; |
語 文 | 中文(Chinese) |
中文摘要 | 本文介紹計畫網路時程/成本抵換問題(Project time/cost trade-off problem) [2]的一個網路切割演算法。這個問題是在關鍵路線法(Critical path method)所考慮的工作順序之外,還容許工作可多付代價以趕工。因此,實際工作時間可長於或短於正常工作時間,但是卻不能短於最趕工作時間。而且各工作除了額外支付趕工的直接成本,還必須分擔整個計畫的辦公費、管理薪資等經常性的間接成本,所以若縮短完成時間,各別工作雖要為趕工付出趕工成本,但是整個計畫卻減少了間接成本。本文所介紹的方法就是要安排各項工作的時程以使總成本為最小。 上述問題能以線性規劃模式表示,所以可用標準方法—簡單形體法(Simplex method)求解,但是由於它的對偶(Dual)問題具有網流(Network flow)型式,因此傳統上是以效率極高的網流方法[2]求解。為了免於藉助非必要而且抽像的對偶問題,本文直接處理原題,根據簡單形體法的原理,專為它發展出效率與網流方法一樣高的網路切割簡形法(Network cut simplex method) [11,12]。 一個計畫的順序關係能以網路圖來表示,對關鍵路線法而言,每一個工作在網路中有一個對應的管線,該工作的正常工作時間是以對應管線的長度表示,這個方法的主要步驟就是在求起點至各節點的最長路線所形成的張成樹(Spanning tree),而樹中連接起點到終點的部份就是所謂的關鍵路線。在上述的網路最長路線張成樹中的管線就稱為枝子,其實際工作時間為正常值或最趕值,其它管線則稱為弦,其實際工作時間不能小於最趕值,可能是在趕工也可能有寬餘時間。枝子的實際工作時間就是各該弦二端節點時間的差值,因此方案的時程與成本便可隨而算得。 因為時程成本問題所考慮的因素不只是時間,另外還有成本,所以網路各管線除了以長度表示工作時間,還能以寬度值表示趕工一單位時間的成本。因此一個工作的趕工時間與成本分別能以切割網路所截下管線的長度與面積來表示。切割法就是對計畫網路反覆進行切割以期降低成本,每次切割還使二條管線的地位對調:一條由枝子變成弦,另一條由弦變成枝子,因而形成新的張成樹。切割反覆進行,直到不再能降低成本時停止,最後的解就是使成本最小的時程方案。 |
英文摘要 | A cut algorithm for a linear program of project time/cost trade-off problem is presented. It is assumed that expediting any job of a project in less than its normal time, but more than its crash time, is possible at a linear additional cost. Apart from these direct costs of shortening duration times of jobs, a linear indirect cost of the project completion time is also assumed. The objective of the problem is to find a schedule so that the total of the direct and the indirect costs is minimized. The algorithm is a specialization of the simplex method. In each iteration, a schedule, identified by a spanning tree with branches just at their normal or crash times, is cut and turns into another schedule, which corresponds to another spanning tree, with improved total cost. This direct approach is visual and thus insightful. The pure primal algorithm avoids the traditional transition to the less tangible dual network flow program and yet the efficiency is the same as the network flow methods. |
本系統中英文摘要資訊取自各篇刊載內容。