待機時間アルゴリズムを最小限に抑えるタスクスケジューリング

私はタスクスケジューリングの問題に完全に固執しています。通常のキューにジョブを追加し、キュー内のすべてのジョブの平均待機時間が最小限になるようにスケジューリングアルゴリズムを実装します。平均待機時間を最小化しない限り、新しいジョブはプッシュスルーされません。プログラムが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

マイアルゴリズムはjobProcess = 9、4、2、1]、previousEndTime + currentJobProcess たrequesttime =から計算され、その終了時刻、[0、5、8、11]によってタスクを分類しようとします

反復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} //タを取るSK 0とタスク
反復2から削除：

タスク= [5,4]、[8,2]、[11,1] PreviousEndTime = 9,9 + 4 = 13、9 = 11 + 2、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]

私の問題は私のアルゴリズムは、いくつかのケースのために働く、ということではなく、複雑なもの。 requestTime：[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