Многопроцессорное планирование с исключениями заданий и ограничениями приоритетов - PullRequest
Новая
       20

Многопроцессорное планирование с исключениями заданий и ограничениями приоритетов

0 голосов
/ 11 июня 2019

Я пытаюсь найти / разработать алгоритм, который может минимизировать общее время для планирования заданий (со временем выполнения) на машины. I.E стандартный алгоритм многопроцессорного планирования.

Однако у меня есть два дополнительных ограничения: некоторые задания должны быть выполнены раньше других (приоритет). Только определенные машины могут выполнять определенные задания (исключая задания) . Хотя задания не являются уникальными для обработчиков.

Например, у меня может быть 4 рабочих места, таких что - 

(cost): j1 (4) , j2 (2) , j3 (10), j4 (12)

3 machines: m1, m2, m3

Such that: 

m1 can run j1, j2, j3

m2 can run j1, j2 and 

m3 can run j3, j4

j1 must be run before j2 and j4

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

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

Использование DAG должно хорошо работать для ограничения приоритета, но я не могу понять, как включить исключения.

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

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

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

Ответы [ 3 ]

1 голос
/ 11 июня 2019

Один из способов справиться с этим заключается в следующем.

Введите двоичную переменную assign(j,m), чтобы указать, назначаем ли мы задание j машине m. Затем просто исправьте все переменные assign(j,m)=0 для всех недопустимых комбинаций. Хороший MIP-решатель удалит соответствующие переменные из модели в фазе предварительного растворения.

Когда я делаю это, заполняю формулировку MIP и решаю ее, я вижу: 

----     63 --------------- data ---

----     63 SET ok  allowed job/machine combinations

        machine1    machine2    machine3

job1         YES         YES
job2         YES         YES
job3         YES                     YES
job4                                 YES


----     63 PARAMETER proctime  processing time

job1  4.000,    job2  2.000,    job3 10.000,    job4 12.000


----     63 SET prec  precedence

            job2        job4

job1         YES         YES


----     63 --------------- solution -----

----     63 VARIABLE assign.L  assign job to machine

        machine1    machine2    machine3

job1                   1.000
job2                   1.000
job3       1.000
job4                               1.000


----     63 VARIABLE start.L  job start time

job2 4.000,    job4 4.000


----     63 VARIABLE finish.L  job finish time

job1  4.000,    job2  6.000,    job3 10.000,    job4 16.000


----     63 VARIABLE makespan.L            =       16.000  time last job is finished

(обратите внимание, что нулевое время начала не печатается)

Полная модель здесь .

0 голосов
/ 12 июня 2019

Для этого вы можете использовать OR-Tools CP-SAT Solver.

См.

https://developers.google.com/optimization/scheduling/job_shop

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

https://github.com/google/or-tools/blob/master/examples/python/flexible_job_shop_sat.py

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

0 голосов
/ 11 июня 2019

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

Не.

За пределами гипотетических сценариев из учебников;планировщик, как правило, не знает, когда будет запущено больше заданий, сколько времени может занять любое задание, когда какой-либо компьютер (или ЦП) изменит скорость, когда / если произойдут сбои оборудования, если / когда задание будет отменено (иликрах), ...

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

В основномочень частые «события», влияющие на планирование (запуск, остановка, ожидание ввода-вывода, продолжение из-за того, что произошел ввод-вывод, изменения в управлении питанием и т. д.);и планировщик должен реагировать на эти события, когда они происходят, быстрым / эффективным способом.

Если некоторые задания должны быть выполнены раньше других, то это не проблема планировщика - это проблема того, кто бы ни написал коддля этих задач приходится иметь дело (добавляя «ждать завершения другого задания, прежде чем я продолжу», где это уместно - например, возможно waitpid()).

Если только определенные машины могут выполнять определенные задания, тоэто должно быть тривиально (вам нужна только какая-то «маска сходства», чтобы контролировать, где может выполняться задание).

...