Нужна помощь по алгоритму расстановки/заполнения парка транспорта. Есть идеи?

Question

[AstonMartin]

Добрый день!
Пишем систему для распределения заказов по базе транспортных средств.
Условие: есть N одинаковых транспортных средств. И есть X заказов на них на аренду. Аренда подневная, каждая на свой срок, со своим днем начала и окончания.
Задача: расположить заказы по базе транспорта так, чтобы загрузка парка была максимально эффективная. То есть чтобы пропуски между заказами у каждой единицы транспорта были минимальными.

Сейчас делаем полным перебором (на php) всех вариантов и получается очень долго.
Может быть есть готовые эффективные алгоритмы под эту задачу? Или с какой еще стороны подойти к решению?

Answer 1

[Adamos]

1. Сортируем заказы по времени начала.
2. Берем первый заказ в очереди.
3. Находим машину, которая к этому времени свободна минимальное время.
4. Назначаем заказ ей, выкидываем его из очереди.
5. Возвращаемся к п. 2.

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

Comments

[AstonMartin]

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

[Adamos]

AstonMartin, вы определитесь, что такое "занятость парка".
Нужно вам как можно плотнее использовать каждую машину или как можно равномернее раскидать заказы. Это противоположные требования.
Почему на 101 заказе окажется, что что-то стоило переставить? Мы выбираем заказы по порядку начала, ни один следующий уже не мешает предыдущим.

[bearenok]

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

[AstonMartin]

Adamos, именно "как можно плотнее использовать".

Проиллюстрирую на примере:
На картинке: сверху заказы на определенные дни, внизу - они расставляются по автопарку.
Вот мы расставили заказы 1,2,3. Все ставим на одну машину, что логично.
А на заказе 4 оказыавется, что оптимальнее было бы поставить его на место третьего. Тогда пропуск дней между заказами будет минимальный.

[Adamos]

bearenok, а вы можете себе представить алгоритм, который, с одной стороны, с минимальными зазорами загружает технику, а с другой - готов к тому, чтобы вдруг впихнуть новый заказ в график? Естественно, при изменении расписания заказов все нужно менять. Но имеющийся набор заказов выстраивается в наборы для каждой машины с минимальными зазорами именно так, как я написал. Полный перебор здесь просто не имеет смысла, поскольку нам безразлично, какая из свободных машин получит следующий заказ - мы уже распределили те заказы, которые начинаются раньше него.
Собственно, можно взять листок бумаги и наглядно представить, как по такому алгоритму построится диаграмма Ганта по набору заказов - совершенно примитивно, но сложнее и не требуется.

[Adamos]

AstonMartin, см. п. 1 алгоритма.

[AstonMartin]

Adamos, похоже действительно работает. Большая вам благодарность!