У нас следующая ситуация. Есть перерабатывающий завод, который принимает заказы от клиентов. Эти заказы могут обрабатываться в разное время, и им всегда будет предоставляться максимальное количество дней, которое потребуется для доставки заказа клиенту. Для обработки каждого заказа на заводе имеется конечное количество рабочих / переработчиков (оно не может измениться). Нас попросили разработать систему планирования, которая оптимизирует использование процессоров , чтобы они могли обслуживать максимальное количество клиентов, не пропуская сроки доставки. Заказы поступают в любой момент времени, поэтому они ожидают перепланирования очереди в случае необходимости. Они также ожидают, что система сможет уведомить их, когда завод не сможет больше принимать заказы, не начав срывать сроки.
Лучшая абстракция, которую мы получили, это:
- Необходимо выполнить J заданий, каждое из которых требует разного времени для обработки.
- Есть M машин, все они имеют одинаковую вычислительную мощность.
- У каждой работы есть крайний срок, по которому они должны быть обработаны.
Основным ограничением будет не соблюдение сроков, а целью оптимизации будет минимизация времени простоя процессоров.
После рассмотрения этого вопроса мы обнаружили сходство с проблемой рюкзака и проблемой упаковки бункера , но в основном с расписанием работы магазина . Основное отличие от последнего состоит в том, что мы не знаем, как смоделировать сроки.
Первое решение, которое мы можем увидеть, - это назначить приоритет каждому заданию на основе его крайнего срока, а затем проверить, пропускает ли решение какое-либо из них.
Вопросы будут:
- Есть ли более известный алгоритм для решения этой проблемы?
- Есть ли лучший способ решить эту проблему планирования?