Распределение и планирование задач по комнатам с условиями - алгоритм оптимизации

Question

Мне нужно найти подходящий метод для разработки алгоритма оптимизации, который выполняет следующие действия:

Допустим, у нас есть N задач, которые нужно выполнить, и у нас есть M комнат, каждая из которых содержит конкретное c количество инфраструктуры / условий. Каждая задача требует использования помещения с подходящими условиями для выполнения задачи.

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

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

Надеюсь, я достаточно хорошо объяснил.

Итак, мне нужно разработать алгоритм, который может распределять задачи для каждой комнаты в правильном расписании, чтобы я мог выполнять все задачи за минимальное общее время и без превышения крайнего срока (а если превышение неизбежно, то получить наименее худший ответ).

Что такое существующие методы или алгоритм, на которых я могу основываться и чему учиться? Я думал о «Job Shop», но мне интересно, есть ли другие подходящие алгоритмы, которые могут справиться с такими проблемами.

Answer 1

Это не алгоритм, а модель смешанного целочисленного программирования. Я не уверен, что это то, что вы ищете.

Допущения: только одно задание может выполняться одновременно в комнате. Работы в разных помещениях можно выполнять параллельно. Кроме того, для простоты я предполагаю, что проблема возможна (модель обнаружит недопустимые проблемы, но мы не возвращаем решение, если это так).

Итак, мы вводим ряд переменных решения:

assign(i,j) = 1 if task i is assigned to room j
              0 otherwise

finish(i) = time job i is done processing

makespan = finishing time of the last job

С их помощью мы можем сформулировать модель MIP:

Используются следующие данные:

Length(i) = processing time of job i
M = a large enough constant (say the planning horizon)
DueDate(i) = time job i must be finished
Allowed(i,j) = Yes if job i can be executed in room j 

Важно отметить, что я предполагаю, что задания упорядочены по сроку. Первое ограничение гласит: если задание i выполняется в комнате j, то оно завершается сразу после выполнения предыдущих заданий в этой комнате. Второе ограничение - это привязка: задание должно быть завершено sh до установленного срока. Третье ограничение гласит: каждое задание должно быть назначено ровно одной комнате, где оно может выполняться. Наконец, время изготовления - это последний конец sh время.

Чтобы проверить это, я сгенерировал несколько случайных данных:

----     37 SET use  resource usage

         resource1   resource2   resource3   resource4   resource5

task2                                              YES
task3                                                          YES
task5                                  YES
task7          YES
task9                      YES                     YES
task11                                                         YES
task12         YES                                 YES
task13         YES
task14         YES
task15                                 YES
task16                                 YES                     YES
task17                     YES
task20                     YES                     YES
task21         YES         YES
task23                     YES
task24                                             YES
task25         YES                                             YES
task26                                 YES
task28                                                         YES


----     37 SET avail  resource availability

        resource1   resource2   resource3   resource4   resource5

room1                     YES         YES         YES         YES
room2                                 YES         YES
room3                                             YES         YES
room4         YES         YES         YES                     YES
room5         YES                     YES         YES         YES

Набор Allowed рассчитывается из use(i,r) и avail(j,r) данные:

----     41 SET allowed  task is allowed to be executed in room

             room1       room2       room3       room4       room5

task1          YES         YES         YES         YES         YES
task2          YES         YES         YES                     YES
task3          YES                     YES         YES         YES
task4          YES         YES         YES         YES         YES
task5          YES         YES                     YES         YES
task6          YES         YES         YES         YES         YES
task7                                              YES         YES
task8          YES         YES         YES         YES         YES
task9          YES
task10         YES         YES         YES         YES         YES
task11         YES                     YES         YES         YES
task12                                                         YES
task13                                             YES         YES
task14                                             YES         YES
task15         YES         YES                     YES         YES
task16         YES                                 YES         YES
task17         YES                                 YES
task18         YES         YES         YES         YES         YES
task19         YES         YES         YES         YES         YES
task20         YES
task21                                             YES
task22         YES         YES         YES         YES         YES
task23         YES                                 YES
task24         YES         YES         YES                     YES
task25                                             YES         YES
task26         YES         YES                     YES         YES
task27         YES         YES         YES         YES         YES
task28         YES                     YES         YES         YES
task29         YES         YES         YES         YES         YES
task30         YES         YES         YES         YES         YES

У нас также есть случайные сроки и время обработки:

----     33 PARAMETER length  job length

task1  2.335,    task2  4.935,    task3  4.066,    task4  1.440,    task5  4.979,    task6  3.321,    task7  1.666
task8  3.573,    task9  2.377,    task10 4.649,    task11 4.600,    task12 1.065,    task13 2.475,    task14 3.658
task15 3.374,    task16 1.138,    task17 4.367,    task18 4.728,    task19 3.032,    task20 2.198,    task21 2.986
task22 1.180,    task23 4.095,    task24 3.132,    task25 3.987,    task26 3.880,    task27 3.526,    task28 1.460
task29 4.885,    task30 3.827


----     33 PARAMETER due  job due dates

task1   5.166,    task2   5.333,    task3   5.493,    task4   5.540,    task5   6.226,    task6   8.105
task7   8.271,    task8   8.556,    task9   8.677,    task10  8.922,    task11 10.184,    task12 11.711
task13 11.975,    task14 12.814,    task15 12.867,    task16 14.023,    task17 14.200,    task18 15.820
task19 15.877,    task20 16.156,    task21 16.438,    task22 16.885,    task23 17.033,    task24 17.813
task25 21.109,    task26 21.713,    task27 23.655,    task28 23.977,    task29 24.014,    task30 24.507

Когда я запускаю эту модель, я получаю в качестве результатов:

----    129 PARAMETER results  

                   start      length      finish     duedate

room1.task1                    2.335       2.335       5.166
room1.task9        2.335       2.377       4.712       8.677
room1.task11       4.712       4.600       9.312      10.184
room1.task20       9.312       2.198      11.510      16.156
room1.task23      11.510       4.095      15.605      17.033
room1.task30      15.605       3.827      19.432      24.507
room2.task6                    3.321       3.321       8.105
room2.task10       3.321       4.649       7.971       8.922
room2.task15       7.971       3.374      11.344      12.867
room2.task24      11.344       3.132      14.476      17.813
room2.task29      14.476       4.885      19.361      24.014
room3.task2                    4.935       4.935       5.333
room3.task8        4.935       3.573       8.508       8.556
room3.task18       8.508       4.728      13.237      15.820
room3.task22      13.237       1.180      14.416      16.885
room3.task27      14.416       3.526      17.943      23.655
room3.task28      17.943       1.460      19.403      23.977
room4.task3                    4.066       4.066       5.493
room4.task4        4.066       1.440       5.506       5.540
room4.task13       5.506       2.475       7.981      11.975
room4.task17       7.981       4.367      12.348      14.200
room4.task21      12.348       2.986      15.335      16.438
room4.task25      15.335       3.987      19.322      21.109
room5.task5                    4.979       4.979       6.226
room5.task7        4.979       1.666       6.645       8.271
room5.task12       6.645       1.065       7.710      11.711
room5.task14       7.710       3.658      11.367      12.814
room5.task16      11.367       1.138      12.506      14.023
room5.task19      12.506       3.032      15.538      15.877
room5.task26      15.538       3.880      19.418      21.713

Деталь: исходя из задания пересчитал старт и финиш sh раз. Модель может допускать некоторую слабину здесь и там, если это не мешает цели и срокам выполнения. Чтобы избавиться от возможных провисов, я просто выполняю все работы как можно раньше. Просто последовательное выполнение заданий в одной комнате с использованием упорядочивания заданий (помните, я отсортировал задания по сроку выполнения).

Эта модель с 30 заданиями и 10 комнатами заняла 20 секунд с использованием Cplex. Гуроби был примерно таким же.

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

Answer 2

Я использовал небольшой вариант модели Alex OPL CP Optimizer для данных, и он находит оптимальное решение (продолжительность = 19,432) за пару секунд и доказывает оптимальность примерно за 5 секунд на моем ноутбуке. Я думаю, что большим преимуществом модели CP Optimizer является то, что она может масштабироваться до гораздо более крупных экземпляров и легко создавать качественные решения, даже если для больших экземпляров, конечно, будет сложно доказать оптимальность.

Вот моя версия модели CP Optimizer:

using CP;

int N = 30; // Number of tasks
int M = 5;  // Number of rooms
int Length [1..N] = ...; // Task length
int DueDate[1..N] = ...; // Task due date
{int} Rooms[1..N] = ...; // Possible rooms for task

tuple Alloc { int job; int room; }
{Alloc} Allocs = {<i,r> | i in 1..N, r in Rooms[i]};

dvar interval task[i in 1..N] in 0..DueDate[i] size Length[i];
dvar interval alloc[a in Allocs] optional;

minimize max(i in 1..N) endOf(task[i]);
subject to {
  forall(i in 1..N) { alternative(task[i], all(r in Rooms[i]) alloc[<i,r>]); }
  forall(r in 1..M) { noOverlap(all(a in Allocs: a.room==r) alloc[a]); }
}

Обратите внимание, что модель MIP использует правило доминирования, определяющее c задачу, согласно которому задачи, выделенные для конкретной комнаты, могут быть упорядочены путем увеличения срока выполнения. Хотя это совершенно верно для этой простой версии проблемы, это предположение может больше не выполняться при наличии дополнительных ограничений (например, минимальное время начала для задач). Формулировка оптимизатора CP не делает этого предположения.

Answer 3

В Pyomo Erwin MIP может быть реализован следующим образом:

        ################################################################################
        # Sets
        ################################################################################

        model.I = Set(initialize=self.resource_usage.keys(), doc='jobs to run')
        model.J = Set(initialize=self.resource_availability.keys(), doc='rooms')
        model.ok = Set(initialize=self.ok.keys())

        ################################################################################
        # Params put at model
        ################################################################################

        model.length = Param(model.I, initialize=self.length)
        model.due_date = Param(model.I, initialize=self.due_date)

        ################################################################################
        # Var
        ################################################################################

        model.x = Var(model.I, model.J, domain=Boolean, initialize=0, doc='job i is assigned to room j')
        model.finish = Var(model.I, domain=NonNegativeReals, initialize=0, doc='finish time of job i')
        model.makespan = Var(domain=NonNegativeReals, initialize=0)

        ################################################################################
        # Constraints
        ################################################################################

        M = 100

        def all_jobs_assigned_c(model, i):
            return sum(model.x[ii, jj] for (ii, jj) in model.ok if ii == i) == 1

        model.all_jobs_assigned_c = Constraint(model.I, rule=all_jobs_assigned_c)

        def finish1_c(model, i, j):
            return sum(
                model.length[ii] * model.x[ii, jj] for (ii, jj) in model.ok if jj == j and ii <= i
            ) - M * (1 - model.x[i, j]) <= model.finish[i]

        model.finish1_c = Constraint(model.I, model.J, rule=finish1_c)

        model.finish2_c = Constraint(
            model.I, rule=lambda model, i: model.finish[i] <= model.due_date[i]
        )

        model.makespan_c = Constraint(
            model.I, rule=lambda model, i: model.makespan >= model.finish[i]
        )

        ################################################################################
        # Objective
        ################################################################################
        def obj_profit(model):
            return model.makespan

        model.objective = Objective(rule=obj_profit, sense=minimize)

Решение с CB C заняло с 4 ядрами около 2 минут и привело к:

Answer 4

В CPLEX вы можете положиться на MIP, но вы также можете использовать Планирование CPOptimizer .

В OPL ваша модель будет выглядеть как

using CP;

int N = 30; // nbTasks
int M = 10; // rooms

range Tasks = 1..N;
range Rooms = 1..M; 

int taskDuration[i in Tasks]=rand(20);
int dueDate[i in Tasks]=20+rand(20);
int possible[j in Tasks][m in Rooms] = (rand(10)>=8);

dvar interval itvs[j in Tasks][o in Rooms] optional in 0..100 size taskDuration[j] ;
dvar interval itvs_task[Tasks];
dvar sequence rooms[m in Rooms] in all(j in Tasks) itvs[j][m];


execute {
        cp.param.FailLimit = 10000;
}

minimize max(j in Tasks) endOf(itvs_task[j]);

subject to {
  // alternative
  forall(t in Tasks) alternative(itvs_task[t],all(m in Rooms)itvs[t][m]);  

  // one room is for one task at most at the same time
  forall (m in Rooms)
    noOverlap(rooms[m]);

  // due dates  
  forall(j in Tasks) endOf(itvs_task[j]) <=dueDate[j]; 

}

и дайте