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

Question

[Сергей Соколов]

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

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

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

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

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

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

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

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

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

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

Answer 1

[Mrrl]

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

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

Answer 2

[386DX]

сделайте визуализацию и посмотрите.

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

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

Comments

[Сергей Соколов]

так может получиться несколько идеальных пачек (ровно среднее арифм.) и несколько остаточных, где большое отклонение от "середины". Может, можно было бы иначе их разложить, чтобы в итоге среднее отклонение от ср.арифм. оказалось меньше?

[386DX]

Сергей Соколов:

Если быть совсем точным то делите количество всех задач на число потоков, получаете N групп задач. берете самую большую задачу и докидываете ее самым Большим из каждой N группы до среднего арифметического, если оно туда лезет, а если не лезет, то самым Большим из следующей более мелкой группы и.т.п.

И проще сделать визуализацию, а не гадать.

[Сергей Соколов]

386DX: как поможет визуализация? Я и так представляю себе как это выглядит: как длинная ёмкость, в которую насыпают крупицы разных размеров. И надо их «растрясти» равномерно )

Answer 3

[Евгений Куманин]

Посчитать средний вес на вагон (+- погрешность)
Отсортировать по убыванию грузы
Берем по порядку самый большой, если входит в пределы погрешности, загружаем в вагон и удаляем из очереди, если нет, пропускаем груз берем следующий чуть меньше и так далее.
Если первый груз для вагона больше среднего, то добавить его одного и на следующий вагон.
И так пока не закончатся грузы.

Comments

[Сергей Соколов]

вот какую принять погрешность и как её минимизировать?

[Евгений Куманин]

Это наверное зависит от конкретной задачи, какие разбеги будут у весов, если в основном маленькие веса, то небольшая погрешность распределит задачи равномерно. Если разбег большой, то маленькая погрешность приведет к нехватки места или загрузки последнего потока.

Answer 4

[mamkaololosha]

1) Сортируете по возрастанию
2) Разбиваете грузы на число вагонов
3) Грузите в один вагон 1 товар с начала, 1 с конца и т.д.

Comments

[Сергей Соколов]

два вагона, грузы 1, 4, 5. Вашим методом получится вагон 1+5 и 4, а могло бы быть идеальное 1+4, 5

Answer 5

[DancingOnWater]

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

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

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

Comments

[Сергей Соколов]

тут известен весь комплект, поэтому вместо мат. ожидания среднее арифм. (масса всех)/N
C такой рекурсией «несовершенство» упаковки будет случайным ведь?

[DancingOnWater]

То, что он известен, не означает, что в его формировании есть какая-то зависимость.

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

[Сергей Соколов]

Re: UPD: задача наполнить N вагонов максимально близко, но не превышая их предел L. Последовательность больше, чем может вместить состав.

Из последовательности можно часть значений пропустить (отложить на следующий «поезд»), но лишь до определённого предела. Грузы имеют приоритет, время, когда их уже можно отправлять, и время, не позже которого они должны уехать.

[DancingOnWater]

Эм, это еще одна задача. Надо подумать. обновите стартовый пост, дабы других не сбивать.

[Сергей Соколов]

DancingOnWater: обновил вопрос. В общем, мне нужно смоделировать утряску стакана с крупицами разной величины )

[DancingOnWater]

Сергей Соколов: Аргх, первый раз просмотрел что задача про потоки. Это накладывает еще доп ограничение по быстродействию алгоритма. Насколько я знаю, типичных решений здесь нет.