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

Question

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

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

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

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).

Answer 1

Мое предложение для модели MIP:

Введите двоичные переменные:

x(i,t) = 1 if task i is assigned to slot t
         0 otherwise

y(t) = 1 if slot t has at least one task assigned to it
       0 otherwise

Кроме того, пусть:

N = max number of tasks per slot
ok(i,t) = 1 if we are allowed to assign task i to slot t
          0 otherwise

Тогда модель может выглядеть следующим образом:

minimize sum(t,y(t))                    (minimize used slots)    
sum(t, ok(i,t)*x(i,t)) = 1   for all i  (each task is assigned to exactly one slot)      
sum(i, ok(i,t)*x(i,t)) <= N  for all t  (capacity constraint for each slot)
y(t) >= x(i,t)  for all (i,t) such that ok(i,t)=1
x(i,t),y(t) in {0,1}                    (binary variables)

Используя N=3, я получаю решение типа:

----     45 VARIABLE x.L  assignment

                s5          s6          s7         s13

task1                    1.000
task2                                1.000
task3                    1.000
task4                    1.000
task5        1.000
task6                                            1.000
task7                                            1.000
task8                                            1.000
task9                                1.000
task10                               1.000

Модель довольно проста, и ее не должно быть очень сложно кодировать и решать с помощью вашего любимого MIP-решателя.Единственное, что вы хотите убедиться, это то, что при ok(i,t)=1 существуют только переменные x(i,t).Другими словами, убедитесь, что переменные не появляются в модели при ok(i,t)=0.Это может помочь интерпретировать ограничения присваивания как:

sum(t | ok(i,t)=1, x(i,t)) = 1   for all i  (each task is assigned to exactly one slot)      
sum(i | ok(i,t)=1, x(i,t)) <= N  for all t  (capacity constraint for each slot)

, где |означает «такой, что» или «где».Если вы все сделаете правильно, ваша модель должна иметь 50 переменных x(i,t) вместо 10 x 17 = 170. Более того, мы можем ослабить y(t), чтобы быть непрерывными между 0 и 1. Это будет либо 0, либо 1 автоматически.В зависимости от решателя, который может повлиять на производительность.

У меня нет оснований полагать, что это проще моделировать как модель программирования с ограничениями или что ее легче решить таким способом.Мое эмпирическое правило таково, если легко смоделировать MIP-флешку для MIP.Если нам нужно пройти через множество обручей, чтобы сделать его правильным MIP, а составление CP облегчает жизнь, тогда используйте CP.Во многих случаях это простое правило работает довольно хорошо.