Расписание задач для минимизации алгоритма ожидания

Question

Я полностью застрял в задаче планирования задач.

Это требование: Реализовать алгоритм планирования, который добавляет задания в очередную очередь и проталкивает их таким образом, чтобы среднее время ожидания для всех заданий в очереди минимизировалось. Новое задание не проталкивается, если оно не минимизирует среднее время ожидания. Предположим, что ваша программа заработала 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} // принимать Задача 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]

Моя проблема заключается в том, что мой алгоритм работает в некоторых случаях, но не сложные. 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]

Так кто-нибудь знает, как это сделать? Я боюсь, что мой алгоритм может быть принципиально испорчен.

Answer 1

Я не вижу действительно опрятного решения, такого как сортировка по времени окончания, но если есть такое решение, вы должны получить тот же ответ, сортируя задачи, используя в качестве компаратора функцию, которая работает, задача должна быть запланирована первой, если это единственные две задачи, которые необходимо рассмотреть.