任务调度，以尽量减少等待时间算法

我完全停留在任务调度问题上。任务调度，以尽量减少等待时间算法

以下是要求：实现一种调度算法，该算法将作业添加到常规队列并推送它们，以使队列中所有作业的平均等待时间最小化。除非最小化平均等待时间，否则不会推进新工作。假设你的程序在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