Please enable JavaScript.

Coggle requires JavaScript to display documents.

6-2 工作排程與資源分配 ( 103 班 ) (二. 資源分配取得資源的先後順序 (使用率, 產能, 等待時間, 完成時間)…

- - - - 較有效率地完成事情
        
        課本舉例 有三支手機要充電但只有兩個充電器，充飽一支手機要兩小時，要如何在最短時間內，將三支手機充飽電?
        
        方法一
        
        需四小時
        
        方法二
        
        需三小時
        
        最短時間為三小時，因此選擇方法二
        
        舉例圖書館裡有三位學生要查資訊，但是只有兩台電腦，每一位學生最多只能使用30分鐘，要如何安排才能耗費最少時間來讓三位同學都能使用玩電腦?
        
        方法一
        
        需60分鐘
        
        方法二
        
        需45分鐘
        
        最短時間為45分鐘，因此選擇方法二
  - - - 範例
        小編規劃了某周六的活動，如下表。但因時間重疊，有些活動無法進行。
        他該如何選擇，才能安排最多項活動？
        
        解題演算法
        
        1.選擇最早結束的活動作為第一項活動-彈鋼琴
        
        2.找出上一項活動結束後才開始，且最早結束活動
        
        演算法執行過程
        
        1.彈鋼琴最早結束 (10:00)，所以先安排
        
        2.找出 10:00 以後開始最早結束的活動，所以選擇寫程式
        
        3.寫程式11:00結束，所以找出11:00以後開始最早結束的活動，選擇複習英文
        
        3.反複進行步驟 2，直到找到最後一項活動
      - 例題
        策旅行社劃了一場台北半日遊，並舉辦投票票選出客戶最想去的景點。現在經理要開始安排行程，請問怎樣才能讓客戶參觀最多台北的景點?(活動時間:上午9點~下午5點）
        
        解題演算法
        
        1.圓山大飯店結束時間為10:00，找出10:00以後最先開始的活動，選擇開始時間為11:00的行天宮
        
        圓山大飯店到行天宮到台北101
        
        2.行天宮13:00結束，所以找出13:00以後開始最早結束的活動，選擇台北101
      - 延伸活動-背包問題(knapsack problem)
        
        若有一背包容量為30，有3 個可分割之物品的重要和價值如下表，請問如何在背包內裝入最高價值的物品?
        
        1.C單價最高(140/20=7)，所以先安排放入。所以此時重量剩[30-20=10]
        
        2.找出第二單價高的，為B(60/10=6)，所以安排放入背包此時重量剩[10-10=0]
        
        3.已沒容量放入A，總價值為140+60=200
  - - - 1.流水線
        2指令分成
        (1)擷取
        (2)解碼
        (3)執行
        
        課本舉例:烹飪大餐
        
        烹煮的順序與時間:
        
        1.若用單口爐
        
        至少要10+10+20+30+20=90分鐘
        
        2.用雙口爐
        
        至少需要60分鐘
        
        爐口一:洋蔥10分鐘彩椒10分鐘番茄20分鐘調味及香料20分鐘
        
        爐口二:雞肉30分鐘
        
        3.用三口鍋
        
        至少需要50分鐘
        
        爐口一:洋蔥10分鐘番茄20分鐘調味及香料20分鐘
        
        爐口二:彩椒10分鐘
        
        爐口三:雞肉30分鐘
        
        舉例:烤餅乾
        
        園遊會要到了，千蝶要烤餅乾共需100片，糖霜和原味個需50片，糖霜餅乾需要烤10分鐘，原味需要20分鐘，現在有2個烤箱，一個烤箱一次能放20片，另一個能烤30片。請問她該如何烤才能在最短的時間內烤完這些餅乾呢？
        
        兩個烤箱同時烤
        
        至少需要30分鐘
        
        烤箱一:糖霜餅乾20片10分鐘原味餅乾20片20分鐘
        
        烤箱二:糖霜餅乾30片10分鐘原味餅乾30片20分鐘
- - - - 意思
        
        就像抽號碼一樣，最先到者，最先取得資源
        
        課本舉例
        
        到達順序 P1，P2，P3
        
        等待時間：P1 為 0、P2 為 24、P3 為 30平均等待時間為 (0 + 24 + 30) / 3 = 18
        完成時間：P1 為 0、P2 為 24、P3 為 30平均完成時間為 (24 + 30 + 33) / 3 = 29
      - 總結
        
        優點
        
        簡單、公平，每個工作都會服務到
        
        缺點
        
        會因到達的時間不同而有不同效率，若先執行長時間的服務，那其他工作就會被延遲，平均完成時間也會變長
  - - - 先找到所需時間較短的事，並優先完成它
        
        課本舉例
        
        P1:3分鐘
        P2:9分鐘
        P3:33分鐘
        平均等待時間:(0+3+9)/3=4
        平均完成時間:(3+9+33)/3=15
        最短的工作先做排程效益最佳，平均等待與完成時間最小
        
        例子
        
        我先寫國文語練要20分鐘
        複習公民要20.5分鐘
        背英文單字30個要21分鐘
        最短的工作先做
        於是
        先語練再公民再背單字
      - 優點
        
        簡單，公平
      - 缺點
        
        順序不同，而有不同效率
  - - - 優先度高的先做
        
        優點
        
        重要的工作可優先
        
        舉例
        
        缺點
        
        可能使優先度低的工作無限期延遲
  - - - 平均等待時間：(9 + 10 + 16) / 3 = 10.3
        
        平均完成時間： (33 + 16 + 19) / 3 = 22.67
        
        時間片段越大越接近先到先服務
      - 依序循環是規定一個時間片段，讓資源輪流服務每個工作
        
        依序循環排程演算法的效率和時間片段的長短有關。若長短適當，每個工作都能公平取得服務；太長則和先來先做演算法相同；太短則會造成系統不斷切換工作，使效能降低。
      - 依序循環的例子中，若時間片段是 10 秒，依 P1, P2, P3 的順序服務，平均完成時間為何？片段的長短對平均完成有沒有影響？
        Sol : P1: 24 P2 : 6 P3 : 3
- - - - 避免死結的方法
        
        2.除非一次取得全部需要的資源，才允許持有資源，否則不允許持有任何資源
        
        3.初期可持有部分資源，但要在取得其他資源前，虛線釋放擁有的所有資源
        
        1.允許工作可以搶奪他人正在使用的資源
- - - - 方法一 先來先做FCFS
        
        31.25
        
        53.75
        
        平均完成時間(分)
      - 方法二 最短的工作先做
        
        27.5
        
        平均等待時間(分)
        
        48.75
      - 方法三 優先權排程
        
        28.75
        
        51.25
      - 方法四 依序循環RR
        
        47.5
        
        72.5
    - - 1.有一些人要過橋
      - 2.有
    - - 1.依照每個人過橋的所需時間來決定順序
      - 2.依照