Оптимизация расписания для минимизации количества временных интервалов (с ограничениями)

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

У каждой задачи есть расписание, в котором указывается список временных интервалов, когда она может быть выполнена. Расписание каждой задачи может быть разным в зависимости от дня недели.

Вот небольшой пример (уменьшенное количество задач и временных интервалов):

task_availability_map = {
    "T1" : [0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    "T2" : [0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    "T3" : [0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    "T4" : [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    "T5" : [0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    "T6" : [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0],
    "T7" : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0],
    "T8" : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0],
    "T9" : [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
    "T10": [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]
}

Ограничение заключается в том, что только до N задач могут выполняться параллельно в одном временном интервале (если они перекрываются). Группа параллельных задач всегда занимает одинаковое количество времени, независимо от того, выполняется ли 1 или N.

Цель состоит в том, чтобы минимизировать количество временных интервалов.

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

def get_tasks_by_timeslot(timeslot, tasks_to_exclude):
    for task in task_availability_map.keys():
        if task in tasks_to_exclude:
            continue
        if task_availability_map[task][timeslot] == 1:
            yield task

total_timeslot_count = len(task_availability_map.values()[0]) # 17
timeslot_indices = range(total_timeslot_count)

timeslot_index_permutations = list(itertools.permutations(timeslot_indices))

possible_schedules = []

for timeslot_variation in timeslot_index_permutations:
    tasks_already_scheduled = []
    current_schedule = []
    for t in timeslot_variation:
        tasks = list(get_tasks_by_timeslot(t, tasks_already_scheduled))
        if len(tasks) == 0:
            continue
        elif len(tasks) > MAX_PARALLEL_TASKS:
            break
        tasks_already_scheduled += tasks
        current_schedule.append(tasks)

    time_slot_count = np.sum([len(t) for t in current_schedule])
    possible_schedules.append([time_slot_count, timeslot_variation])

...

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

Кто-то предложил LP MIP (например, Google OR Tools), но я не очень хорошо с ним знаком и с трудом формулирую ограничения в коде. Любая помощь с LP или каким-либо другим решением, которое может помочь мне начать работу в правильном направлении, очень приветствуется (не обязательно Python, может быть даже Excel).