algorithm - 任务调度最小等待时间算法

Question

我完全陷入了任务调度问题。

要求如下: 实现一种调度算法，将作业添加到常规队列并以最小化队列中所有作业的平均等待时间的方式推送它们。除非最小化平均等待时间，否则不会推进新工作。 假设您的程序在 0 秒开始工作。在 requestTimei 收到第 i 个作业的请求，我们假设处理它需要 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}//获取任务0并将其从任务中移除

• 迭代 2:

  任务 = [[5,4],[8,2][11,1]] 上一个结束时间=9 9+4=13, 9+2=11, 11+1=12 endTime = {1:13,2:11,3:12}//移除任务2

• 迭代 3:

  任务 = [[5,4],[11,1]] 上一个结束时间=11 11+4=15, 11+1=12 endTime = {1:13,3:12}//移除任务3

• 迭代 4:

  任务 = [[5,4],[11,1]] 上一个结束时间=12 12+4=15 endTime = {1:16}//移除任务1

打印的最终结果是 [0,2,3,1]

我的问题是，我的算法适用于某些情况，但不适用于复杂的情况。 请求时间:[4、6、8、8、15、16、17、21、22、25] 工作进程:[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]

那么有谁知道这道题怎么做呢？恐怕我的算法可能存在根本性缺陷。

Answer 1

我没有看到像按结束时间排序这样的真正巧妙的解决方案，但如果有这样的解决方案，您应该能够通过使用作为比较器的函数对任务进行排序来获得相同的答案，该函数计算出哪个任务如果只有这些是要考虑的两项任务，则应首先安​​排。