任務調度，以儘量減少等待時間算法

我完全停留在任務調度問題上。任務調度，以儘量減少等待時間算法

以下是要求：實現一種調度算法，該算法將作業添加到常規隊列並推送它們，以使隊列中所有作業的平均等待時間最小化。除非最小化平均等待時間，否則不會推進新工作。假設你的程序在0秒開始工作。第i個工作的請求來自requestTimei，我們假設它需要jobProcessi秒來處理它。

def jobScheduling(requestTime, jobProcess, timeFromStart): 

    requestTimeAndDuration={} 
    for i in range(len(requestTime)): 
     job=[] 
     job.append(requestTime[i]) 
     job.append(jobProcess[i]) 
     requestTimeAndDuration[i]=job 

    taskProcessed=[] 
    previousEndTime=0 
    while (requestTimeAndDuration): 
     endTimes={} 
     for k,v in requestTimeAndDuration.items(): 
      if(len(taskProcessed)==0): 
       previousEndTime=0 
      else: 
       previousEndTime=taskProcessed[-1][1] 
      #print previousEndTime 
      if(v[0]<=previousEndTime): 
       endTimes[k]= previousEndTime+v[1] 
      else: 
       endTimes[k]= v[0]+v[1] 

     endTimesSorted = sorted(endTimes.items(), key=lambda endTimes: endTimes[1]) 
     nextJobId = endTimesSorted[0][0] 
     nextJobEndTime = endTimesSorted[0][1] 
     nextJob=[] 
     nextJob.append(nextJobId) 
     previousEndTime=0 
     if(len(taskProcessed)>0): 
      previousEndTime=taskProcessed[-1][1] 
     nextJobStarTime = nextJobEndTime-jobProcess[nextJobId] 
     nextJob.append(nextJobEndTime) 
     nextJob.append(nextJobStarTime) 
     taskProcessed.append(nextJob) 
     del requestTimeAndDuration[nextJobId] 
print taskProcessed

我的算法試圖通過其結束時刻，這是從previousEndTime + currentJobProcess requestTime =計算[0，5，8，11]，將任務進行排序，jobProcess = [9,4，2，1]

迭代1：

任務= [[0,9]，[5,4]，[8,2] [11,1]] PreviousEndTime = 0，因爲我們開始//沒有以前的任務0 + 9 = 9,5 + 4 = 9,8 + 2 = 10,11 + 1 = 12 endTime = {0：9,1：9,2：11,3：12} //帶ta SK 0和從任務
迭代2中移除：

任務= [[5,4]，[8,2] [11,1]] PreviousEndTime = 9 9 + 4 = 13，9 + 2 = 11，11 + 1 = 12 ENDTIME = {1：13,2：11,3：12} //刪除任務2
迭代3：

任務= [[5,4 ]，[11,1]] previousEndTime = 11 11 + 4 = 15，11 + 1 = 12 endTime = {1：13,3：12} //刪除任務3
迭代4：

任務= [[5,4]，[11,1]] previousEndTime = 12 12 + 4 = 15 ENDTIME = {1:16} //刪除任務1

印刷最終的結果是[0,2,3,1]

我的問題是，我的算法適用於某些情況下，而不是複雜的問題。請求時間：[4,6,8,8,15,16,17,21,22,25] jobProcess：[30,25,14,16,26,10,11,11,14,8]

答案是[9，5，6，7，2，8，3，1，4] 但我的算法產生[5,9,6,7,8,3,1,4,0]

那麼有誰知道如何解決這個問題？恐怕我的算法可能有根本性的缺陷。

來源

2016-10-22 Telenoobies

您的算法的解決方案和最終示例中的正確解決方案不包含相同的整數。爲什麼？ – Eyal