Блог

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

Вот требование: Реализуйте алгоритм планирования, который добавляет задания в обычную очередь и проталкивает их таким образом, чтобы среднее время ожидания для всех заданий в очереди было сведено к минимуму. Новое задание не выполняется, если оно не минимизирует среднее время ожидания. Предположим, что ваша программа начинает работать через 0 секунд. Запрос на i-е задание поступил в requestTimei, и давайте предположим, что для его обработки Jobprocess требуется несколько секунд.

 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
  

Мой алгоритм пытается отсортировать задачи по времени их окончания, которое вычисляется из previiousendtime currentJobProcess
Время запроса = [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 Время окончания = {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 Время окончания = {1:13,2:11,3:12} // удалить задачу 2

• итерация 3:

  задача = [[5,4],[11,1]] Предыдущее время окончания=11 11 4=15, 11 1=12 Время окончания = {1:13,3:12} // удалить задачу 3

• итерация 4:

  задача = [[5,4],[11,1]] Предыдущее время окончания = 12 12 4 = 15 Время окончания = {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]

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

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