處理具有相同優先級的作業的算法

我正在解決Papadimitrou和Vazirani的算法書中的練習題。處理具有相同優先級的作業的算法

以下是問題：

服務器有n個客戶等待服務。預先知道每個客戶所需的服務時間：對於客戶i而言是ti分鐘。因此，例如，如果客戶按照增加i的順序服務，則第i個客戶必須等待Sum（j = 1到n）tj分鐘。

我們希望儘量減少總的等待時間。爲此提供一個有效的算法。

我嘗試：

我想到了幾個辦法，但不可能決定哪個是最好的，或者拍我的其他方式。

方法1：

爲他們服務輪循方式與時間片爲5。然而，當我需要決定時間片的時候要多加小心。它不應該太高或太低。所以，我想選擇時間片作爲服務時間的平均值。

方法2：假設作業是根據他們採取並且被存儲在一個陣列A中的時間排序[1 ... n]的

首先服務A [1]然後，將[N]然後A [ 2]然後A [n-1]等等。

我真的不能確定哪一個會是這個問題的最佳解決方案。我錯過了什麼。

感謝，錢德爾

來源

2010-10-22 Chander Shivdasani

想象一下，你只有兩個工作，一個短和另一個長...計算等待時間先執行一個或另一個...只是爲了kickstart你的「算法」 – 2010-10-22 01:31:23

然後添加切片功能，看看你是否得到了一些東西...... – 2010-10-22 01:34:54

假設客戶的「等待時間」是他們的工作完成之前的時間，那麼時間片總是更糟糕（除非你有多個CPU /內核並可以在它們之間遷移任務）。如果工作A是最後完成的工作，那麼儘早完成工作會延遲完成其他工作，而完全沒有完成工作A。所以最好不要在完成所有其他工作之前開始上一份工作。通過歸納，你不應該在中途轉換工作。 – 2010-10-22 01:36:17

您可以通過添加排序部分，即興你的輪循方式解決這個問題，

首先排序基於服務時間

現在，而不是隻給每個客戶一個時間片噸的客戶循環賽的方式，你也可以檢查，如果客戶有小於T/2剩餘時間，如果是這樣完成了自己的任務

所以在排序列表中的每個客戶從第一服務器客戶時間t 如果他的剩餘時間是< t/2然後現在完成他的服務其他移動到下一個客戶

來源

2010-10-22 04:00:03 theReverseFlick

讓我承擔的「總的等待時間」是的服務器之前完成每個客戶等待服務的他/她的時間的總和，並承擔客戶在增加我的順序提供，所以客戶C1等待t1分鐘，客戶C2等待t1+t2分鐘，並且客戶C3等待t1+t2+t3分鐘，並且...客戶Cn等待t1+t2+...+t{n-1}+tn分鐘。

或：

C1 waits: t1 
C2 waits: t1+t2 
C3 waits: t1+t2+t3 
... 
Cn waits: t1+t2+t3+...tn

總等待時間加起來n*t1+(n-1)*t2+...1*tn

再次，這是基於客戶在增加我的訂單服務的前提。

現在，你想先服務哪個客戶？

來源

2010-10-22 01:46:45 YYC

處理具有相同優先級的作業的算法

回答

相關問題