Алгоритм поиска слота без ресурсов

Question

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

1. зависимость задачи - не запускать раньше,
2. доступность машины и
3. сменные рабочие часы

Я отслеживаю включение машины в таблицу machine_allocations:

machine_allocations
+------------+--------------+-----------------+---------------+
| machine_id | operation_id | start_timestamp | end_timestamp |
+------------+--------------+-----------------+---------------+

Часы смены следуют шаблону.

Теперь, чтобы найти самую раннюю дату и время для операции, я думаю о функции:

function earliest_slot($machine_id, $for_duration, $no_sooner_than) {
   // pseudo code
   1. get records for the machine in question for after $no_sooner_than 
   2. put start and end timestamps into $unavailable array
   3. add non-working times as new elements to the array
   4. in a loop find timeslots which are not in the array
   5. if a timeslot is found which is equal to or bigger than $for_duration, return that
}

Мой вопрос: это хороший подход? Есть ли более простые способы сделать это?

Answer 1

Поиск самой ранней даты и времени для одной операции за раз может не дать вам наилучшего результата.Рассмотрим пример, где операция A использует машину 1 в течение длительного времени, операция B использует машину 1 в течение короткого времени, а операция C использует машину 2 в течение короткого времени, но операция C должна быть выполнена после B.

InВ этом случае лучше запланировать B до A на машине 1, но ваш подход не достиг бы этого.Конечно, написание и использование программного обеспечения для управления этим будет сложнее, чем вы предлагали, поэтому вам нужно решить, стоит ли эта выгода дополнительных усилий.

Посмотрите на Планирование , Планирование работы магазина и Алгоритм планирования .

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

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

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

Answer 2

Это зависит от того, когда вы хотите планировать работу. Если до начала работы машин, то может быть алгоритм Branch & Bound или что-то в этом роде (возможно, динамическое программирование). Если работа должна быть запланирована, когда машины работают, и Вы не можете сказать, какие работы будут выполняться, то для оптимального решения Вы не можете рассчитывать (ну, я не могу думать об этом). Мэйби может поставить следующую работу на машине с минимальным максимальным временем? Mayby - динамическая версия Ford-Bellmas alg (если у вас есть несколько уровней производства). Тяжело сказать. Я бы сделал пару подходов и определил, что ведьма лучшая. Вы можете написать статью об этом :)