Как правильно планировать задачи?

Question

При заданном количестве задач n, которые упорядочены по приоритету, с timeAvailable (время, когда задача становится доступной - задача не может быть запущена до этого времени), lengthOfTask (количество времени, которое задача должна завершиться) и число mо доступных машинах, как эффективно составить расписание, чтобы число задач в любой момент времени не превышало количество доступных машин, и задачи с более высоким приоритетом будут иметь приоритет в расписании.Все задачи должны быть запланированы, те, которые не могут быть запланированы в timeAvailable, должны быть перенесены на более позднее время.

Чтобы было понятнее: если у нас есть 2 машины и задачи:

let tasks =

[
{name: "task1", priority: 5, timeAvailable : 1 lengthOfTask : 4},
{name: "task2", priority: 4, timeAvailable : 3 lengthOfTask : 4},
{name: "task3", priority: 3, timeAvailable : 3 lengthOfTask : 3},
{name: "task4", priority: 2, timeAvailable : 2 lengthOfTask : 4},
{name: "task5", priority: 1, timeAvailable : 4 lengthOfTask : 4},
]

Я хочумое расписание должно выглядеть следующим образом:

[
{name: "task1", priority: 5, timeAvailable : 1 lengthOfTask : 4},
{name: "task2", priority: 4, timeAvailable : 3 lengthOfTask : 4},
{name: "task3", priority: 3, timeAvailable : 5 lengthOfTask : 3},
{name: "task4", priority: 2, timeAvailable : 7 lengthOfTask : 4},
{name: "task5", priority: 1, timeAvailable : 8 lengthOfTask : 4},
]

Нам пришлось переназначить: task3, который не мог запуститься на 3, потому что две машины уже заняты.Это может начаться 5, когда задачи 5 закончились.Это длится 3, поэтому оно заканчивается 8 ...

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

Проблема заключается в том, что для правильности алгоритма при планировании задачи мы должны проверять (подсчитывать), сколько задач перекрываются.Если число перекрывающихся задач> = количество машин,

, мы должны использовать время окончания самой ранней задачи завершения в качестве нового начального времени.Это делает алгоритм очень сложным.

Мой код написан на узле и использует момент.js для сравнения времени и интервалов

Псевдокод:

let tasks = ... // look at original tasks array above
let schedule = []


for each task in tasks:
    task.startTime = scheduleTask(task.timeAvailable, task.lengthOfTask)
    tasks.endTime = task.startTime + task.lengthOfTask
    schedule.push(task)




function scheduleTask(startTime, lengthOfTask):
    let overlappingTasks = getOverlappingTasks(); //gets all the tasks that overlaps
    if(overlappingTasks.length >= avaliableMachines):
        let earliestEndingOverlappingTask = getEarliestEndingOverlappingTask(overlappingTasks);
        return scheduleTask(earliestEndingOverlappingTask.endTime, lengthOfTask)
    else:
        return startTime

СложностьO (n ^ 2) - я думаю.Я хотел бы алгоритм, который лучше, чем этот.