Как распределить грузы по вагонам равномерно?

Есть много грузов разных весов от 1 до 1E7. Большинство ближе к 1Е3.

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

Думал, надо стремиться к среднему арифметическому (суммарная масса/N) для каждого вагона. Но насколько близко реально приблизиться с имеющимся набором – тут я приехал в тупик.

Похоже на одномерную задачу об упаковке. Грузы/вагоны – просто для иллюстрации. На самом деле задачи и потоки. Помогите с алгоритмом.

Upd. уточнение/усложнение, которое не есть путь к истине. Суть моего вопроса – выше. Но в целом задача немного иная. Эта задача в моей системе встречается дважды:

  1. первый – это разовый запуск многопоточного исполнителя. Тут желательно его загрузить так, чтобы все потоки закончились как можно раньше – для этого нужно раскидать грузы по потокам как можно равномернее, без отдельных «хвостов» в одном потоке и простаивающими остальными.
  2. второй – общее расписание. Эти «вагоны» – регулярные запуски исполнителя из предыдущего пункта на оси времени. Весь поезд – цикл, в течение которого каждый «груз» должен быть отправлен. Тут преследую две цели: соблюдать примерно регулярный интервал в запуске каждого груза, и равномерно распределить нагрузку по всему составу.


По второму пункту подробнее. У груза есть три параметра: уже упомянутая масса; старт – время («номер вагона»), когда его уже можно отправлять; и цель – время («номер вагона»), когда его в идеале нужно отправить.

Отправленный груз обновляет своё расписание: через T часов его нужно отправлять снова.

В ряд грузов иногда «подбрасывают дров»: возникают пики нагрузки, которые со временем должны размазаться по времени, чтобы вагоны опять становились равномерно загруженными. Такая «живая» автобалансирующая система.

Наверняка задача относительно типичная, я просто не знаю, где искать описание такого алгоритма.
  • Вопрос задан
  • 2916 просмотров
Решения вопроса 1
Mrrl
@Mrrl
Заводчик кардиганов
(Про исходную задачу)
После того, как отправили самые тяжелые грузы (которые больше средней загрузки вагона), пересчитываем среднее арифметическое, и начинаем укладывать грузы в вагоны, начиная с самого тяжелого. Возможны три стратегии.
1) Очередной (самый тяжелый из оставшихся) груз кладём в самый пустой вагон
2) Очередной груз кладём в самый загруженный из вагонов, в которые этот груз ещё помещается (т.е. общий вес вагона и груза не превосходит среднего арифметического)
3) Очередной груз кладём в случайный из вагонов, в которые груз помещается.
В стратегиях (2,3) иногда будет возникать ситуация "груз положить некуда". Тогда кладём его в самый пустой вагон, и отправляем.
Дальше надо экспериментировать, чтобы выбрать более подходящую из этих стратегий. Интуиция тут не очень помогает.

Если у вагона есть предел загрузки L, то груз, который не умещается даже в самый пустой вагон, оставляем до следующего поезда. При его загрузке сначала раскидываем очень тяжелые грузы, потом - оставленные от предыдущего поезда, потом - все новые.
Ответ написан
Пригласить эксперта
Ответы на вопрос 4
@386DX
сделайте визуализацию и посмотрите.

А вообще берете самую большую задачу и докидываете ее самым маленькими до среднего арифметического.

Если быть точным то делите количество всех задач на число потоков, получаете N групп задач. берете самую большую задачу и докидываете ее самым маленькими из каждой N группы до среднего арифметического..
Ответ написан
Посчитать средний вес на вагон (+- погрешность)
Отсортировать по убыванию грузы
Берем по порядку самый большой, если входит в пределы погрешности, загружаем в вагон и удаляем из очереди, если нет, пропускаем груз берем следующий чуть меньше и так далее.
Если первый груз для вагона больше среднего, то добавить его одного и на следующий вагон.
И так пока не закончатся грузы.
Ответ написан
@mamkaololosha
1) Сортируете по возрастанию
2) Разбиваете грузы на число вагонов
3) Грузите в один вагон 1 товар с начала, 1 с конца и т.д.
Ответ написан
@DancingOnWater
Если на вход подается довольно длинная случайная последовательность, то задача решается аналогично процедуре голосования:
Случайным образом раскидываем по вагонам грузы. Выбираем который ближе всех лежит к мат ожиданию. И выкинем из исходной последовательности те грузы, что лежат в этом вагоне. Повторить рекурсивно.

UPD: Хотя все зависит от задачи. Я минимизировал СКО. При этом какой-то вагон может быть практически пустым

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы